Optimization Techniques for C++

Question

In his talk a few days ago at Facebook - slides, video, Andrei Alexandrescu talks about common intuitions that might prove us wrong. For me one very interesting point came up on Slide 7 where he states that the assumption "Fewer instructions = faster code" is not true and more instructions will not necessarily mean slower code.

Here comes my problem: The audio quality of his talk (around 6:20min) is not that well and I don't understand the explanation very well, but from what I get is that he is comparing retired instructions with optimality of an algorithm on a performance level.

However, from my understanding this cannot be done because these are two independent structural levels. Instructions (especially actually retired instructions) are one very important measure and basically, gives you an idea about performance to achieve a goal. If we leave out the latency of an instruction, we can generalize that fewer retired instructions = faster code. Now, of course there are cases where an algorithm that performs complex calculations inside a loop will yield better performance even though it is performed inside the loop, because it will break the loop earlier (think graph traversal). But wouldn't it be more useful to compare to algorithms on a complexity level rather than saying this loop has more instructions and is better than the other? From my point of view, the better algorithm will have less retired instructions in the end.

Can someone please help me to understand where he was going with his example, and how can there be a case where (significantly) more retired instructions lead to better performance?

**[Branch prediction](http://stackoverflow.com/q/11227809/572670)**, for example. In the linked example - adding instructions (sorting the array before doing the iteration) actually allows faster code, because the branch prediction is MUCH better for the sorted array. — amit, Dec 20 '12 at 13:22
also cache trashing can reduce performances. See for example this : http://stackoverflow.com/questions/7905760/matrix-multiplication-small-difference-in-matrix-size-large-difference-in-timi — BЈовић, Dec 20 '12 at 13:28
An other nice (imo) example is division by a constant. The shortest way is to actually divide, but the fastest way is a little complex: http://gmplib.org/~tege/divcnst-pldi94.pdf — harold, Dec 20 '12 at 13:34
@harold: fortunately for such optimization the compiler knows its pipeline optimization as the back of its hand. — Matthieu M., Dec 20 '12 at 17:04

score 20 · Accepted Answer · edited May 23 '17 at 12:06

20

The quality is indeed bad, but I think he leads to the fact that CPUs are good for calculations, but suffer from bad performance for memory seek (RAM is much slower then CPU), and branches (because CPU works as a pipeline, and branches might cause the pipeline to break).

Here are some cases where more instructions are faster:

Branch prediction - even if we need to do more instructions, but it causes for a better branch prediction, the pipeline of the CPU will be full more time, and less ops will be "thrown out" of it, which ultimately leads to better performance. This thread for example, shows how doing the same thing, but first sorting - improves performnce.
CPU Cache - If your code is more cache optimized, and follows the principle of locality - it is more likely to be faster then a code who doesn't, even if the code that doesn't do half the amount of instructions. This thread gives an example for a small cache optimization - that the same number of instructions might result in much slower code if it is not cache optimized.
It also matters which instructions are done. Sometimes - some instructions might be slower to perform then others, for example - divide might be slower then integer addition.

Note: All of the above are machine dependent and how/if they actually change the performance might vary from one architecture to the other.

edited May 23 '17 at 12:06

Community

1
1

answered Dec 20 '12 at 13:27

amit

175,853
27
231
333

With regards to branch prediction: I'm not sure this is still valid. Yes, there where times when branch prediction had a serious impact (depending on the arch, I'm on X86 here), but if I run the example from the thread on my Xeon 7560 the unsorted version is a few percent faster. So back to square one? – grundprinzip Dec 21 '12 at 09:15
With regard to your point 2: The example you mention does not change the number of retired instructions, rather the ordering of data structures to exploit the cache structure. Any other example? – grundprinzip Dec 21 '12 at 09:19
@grundprinzip: Branch prediction is constantly changing, as as said - different from one architecture to another. In order to find a killer case for your hardware, you might need an expert on the specific branch predictor. I am afraid I am not one of them. – amit Dec 21 '12 at 09:20
@grundprinzip: Regarding #2: You can add a dummy instruction to each iteration in the cache-optimized loop, you will get more instructions and probably faster code in the optimized version (again, architecture dependent, and of course, compiler optimization dependent). Also, there is also a variation of this optimization with disks. A code that have a lot of disk seeks - but they are sequential might be faster then code with fewer random disk seeks, since the disk is not Random Access, and sequential read is *much* faster then random access read. – amit Dec 21 '12 at 09:28

score 6 · Answer 2 · answered Dec 20 '12 at 13:36

The number of instructions is not a good measure in itself.

Fewer retired instructions (because there is nothing more to do) = faster code.

Fewer retired instructions (because they have to wait for dependencies) = slower code.

It can sometimes be that more instructions in the code also means more retired instructions, because they can use up execution slots that would otherwise be wasted in case 2.

Optimization Techniques for C++

2 Answers2