Loops - storing data or recalculating

Question

How much time does saving a value cost me processor-vise? Say i have a calculated value x that i will use 2 times, 5 times, or 20 times.At what point does it get more optimal to save the value calculated instead of recalculating it each time i use it? example:

int a=0,b=-5;
for(int i=0;i<k;++i)
  a+=abs(b);

or

int a=0,b=-5;
int x=abs(b);
for(int i=0;i<k;++i)
  a+=x;

At what k value does the second scenario produce better results? Also, how much is this RAM dependent?

Answer 1

It is almost impossible to provide an answer other than measure in a real scenario. When you cache the data in the code, it may be stored in a register (in the code you provide it will most probably be), or it might be flushed to L1 cache, or L2 cache... depending on what the loop is doing (how much data is it using?). If the value is cached in a register the cost is 0, the farther it is pushed the higher the cost it will take to retrieve the value.

In general, write code that is easy to read and maintain, then measure the performance of the application, and if that is not good, profile. Find the hotspots, find why they are hotspots and then work from there on. I doubt that caching vs. calculating abs(x) for something as above would ever be a hotspot in a real application. So don't sweat it.

Answer 2

Since the value of abs(b) doesn't change inside the for loop, a compiler will most likely optimize both snippets to the same result i.e. evaluating the value of abs(b) just once.

Answer 3

I would suggest (this is without testing mind you) that the example with int x=abs(b) outside the loop will be faster simply because you're avoiding allocating a stack frame each iteration in order to call abs().

That being said, if the compiler is smart enough, it may figure out what you're doing and produce the same (or similar) instructions for both.

Answer 4

As a rule of thumb it doesn't cost you much, if anything, to store that value outside the loop, since the compiler is most likely going to store the result of abs(x) into a register anyways. In fact, when the compiler optimizes this code (assuming you have optimizations turned on), one of the first things it will do is pull that abs(x) out of the loop.

You can further help the compiler generate good code by qualifying your declaration of "x" with the "register" hint. This will ask the compiler to store x into a register value if possible.

If you want to see what the compiler actually does with your code, one thing to do is to tell it to compile but not assemble (in gcc, the option is -S) and look at the resulting assembly code. In many cases, the compiler will generate better code than you can optimize by hand. However, there's also no reason to NOT do these easy optimizations yourself.

Addendum:

Compiling the above code with optimizations turned on in GCC will result in code equivalent to:

a = abs(b) * k;

Try it and see.

Answer 5

For many cases it produces better perf from k=2. The example you gave is . not one. Most compilers try to perform this kind of hoisting when even low levels of optimization are enabled. The value is stored, at worst, on the local stack and so is likely to stay fairly cache warm, negating your memory concerns.

But potentially it will be held in a register.

The original has to perform an adittional branch, repeat the calculations and return the value. Abs is one example of a function the compiler may be able to recognize as a constexpr and hoist.

While developing your own classes, this is one of the reason you should try to mark members and references as construe whenever possible.