Lazy calculations considered harmful?

Actually, the trap I’m going to write about is a little more subtle and doesn’t apply only to lazy calculations, but it’s one of the most typical scenarios. Consider the following situation:

1float Rectangle::GetArea() const
2{
3    if (m_isAreaDirty)
4        CalcArea(); // Calculates area (width * height), clears isAreaDirty flag
5    return m_area;
6}

That’s rather typical (albeit very simplified, of course) example of performing calculations only when they’re really needed. As long as rectangle dimensions don’t change and no one needs to know its area - it doesn’t have to be recalculated. In theory, in 99% of cases, GetArea() should be blazingly fast, after all, it only tests one flag and then returns a value. Right? Not exactly.

That’s another situation when our good friend load-hit-store rears its ugly head again. Let’s examine code generated for GetArea() function (I’m assuming it’s not inlined!):

 182742138 mflrr12
 28274213C stw r12,-8(r1)
 382742140 stwu  r1,-60h(r1)
 482742144 lbz r11,0Ch(r3)
 582742148 cmplwi  -  cr6,r11,0
 68274214C beq  cr6,Rectangle::GetArea + 001ch (82742154h)
 782742150 bl Rectangle::CalcArea (82741e18h)
 882742154 lfsfr1,8(r3)
 982742158 addi r1,r1,96 ; 60h
108274215C lwz r12,-8(r1)
1182742160 mtlr r12
1282742164 blr

Consider, the most common case, when area doesn’t have to be recalculated (= no call to CalcArea). We enter the function, have to save link register, because it’s possible that we’ll have to call another one. It doesn’t happen, so instead we just load link register and return. Bam! Load-hit-store on ‘8(r1) (LR). Once in a while CalcArea actually is called, in which case we’re safe.

Another, similar scenario is function that tries to do more than one thing (it’s a bad practice, but still popular). Example:

1bool TestCondition(bool extendedTest)
2{
3    return m_simpleCondition && (!extendedTest || TestExtendedCondition());
4}

Same problem again, LR will be saved/reloaded even if it’s not needed in majority of cases (I assume that usually extendedTest == false).

Now, the point of this article isn’t to make you remove all lazy calculations from your code. Think about each situation. How often does the value need to be recalculated? In some cases, it’s still a win, especially if calculating returned value is expensive. If not - consider recalculating area (our first example) every time dimensions change and make GetArea() to return it immediately. In the second case, it’d be probably best to separate functionality into two distinct functions. The general conclusion isn’t very revolutionary – there’s nothing wrong with the idiom itself, just make sure it’s being used in sane way (not like in our Rectangle example).

PS. I think I already linked to it, but Shawn keeps adding new articles, and the resource is just too good to miss. Make sure to visit his blog and read all MotoGP related notes. It’s a great collection of tips/tricks that are actually proven in a commercial title. Many of them, you don’t even notice, but you’d certainly would if they weren’t there (and game would run 15fps for example). The blue-tack one is just hilarious (in a carefully selected nerd-ish definition of the word). Very creative, usually simple, but elegant, game programming at its best. There are no tags, I think, but other articles are definitelly worth reading as well.

Old comments

ed 2009-06-24 19:24:33

Blue-tack “technique” reminds me an old Atari XL/XE era where you had no profilers and all calculations were measured in “per screen line” :) Just wait to screen line no. 10, change the color of the background to white, do some calculations and change background to black again. Count screen lines that are white, do some optimizations and run code again :)

admin 2009-06-24 20:15:28

Yes, I used to do it even on PC, back in the DOS days where you could easily change background (border) color just by writing to the right (0x3C0?) port.