# Performance of adding eight numbers sequentially vs. in a tree

The simplest way to add 8 numbers would be something like this,

sum = one + two + three + four + five + six + seven + eight;


This (in C) would add one and two, and add the result to three and do the same till eight. Instructions for adding three,four and so on till eight will have wait the first instruction to complete.

If we rewrite the same addition as,

sum = (   (  (one+two) + (three+four) )  + (  (five+six) + (seven+eight)  )   );


the variables enclosed inside the brackets should be added before the total addition can take place. This presents an obvious chance for the compiler to optimise the program by pipelining the instructions for one+two,three+four,five+six and seven+eight, since they don't have any data dependence.

Can compilers like GCC identify such a situation, or are there any practical difficulties? If yes, which would be faster?

I think your analysis is basically right. Some notes.

1. Pipelining is the wrong word here; what you're looking at here is data dependency. A CPU pipeline splits an individual instruction into multiple steps, and different steps of consecutive instructions can then be executed concurrently. A data dependency, on the other hand, is a situation where an instruction cannot begin execution until the result of a previous instruction is available. This instruction will still be pipelined, and the individual pipeline stages will be executed right up until the stage for which the unavailable previous result is necessary: this is a pipeline stall due to data dependency.

Your analysis of the data dependency here is right; the tree-version should be the same or faster. However, your question about what the compiler will do is complicated.

2. If the numbers are floating-point numbers, the two versions are not identical, so the compiler would not be permitted to change the sequential version into the tree version (that would be a bug if it did). Typically, you would have to specify some option like -ffast-math to indicate that non-equivalent algebraic floating-point expression transformations are acceptable.

The internal details of the processor matter too. In the first version, even if there is a dependency between successive instructions, if there is only one arithmetic unit, there would still not be a stall.

3. My version of clang (5.1) on my laptop (OSX) does the following to this code:

#include <iostream>
using namespace std;

int main(int argc, char** argv) {
typedef double T; // Also try with long
T M[8] = {1,2,3,4,5,6,7,8};
// Don't let the compiler compute the sum of M's at compile time.
for (int i = 1; i <= 8; ++i)
if (argc > i) M[i-1] = atof(argv[i]);

// T S1 = M[0] + M[1] + M[2] + M[3] + M[4] + M[5] + M[6] + M[7];
// cout << S1 << endl;
T S2 = (((M[0] + M[1]) + (M[2] + M[3])) + ((M[4] + M[5]) + (M[6] + M[7])));
cout << S2 << endl;

return 0;
}


The tree version becomes this:

-> 0x100000de0:  addsd  %xmm6, %xmm7
0x100000de4:  addsd  %xmm5, %xmm1
0x100000de8:  addsd  %xmm7, %xmm1
0x100000dec:  addsd  %xmm4, %xmm3
0x100000df0:  addsd  %xmm2, %xmm0
0x100000df4:  addsd  %xmm3, %xmm0
0x100000df8:  addsd  %xmm1, %xmm0


(the top two level of additions actually got sequentialized) and the sequential version becomes this:

-> 0x100000de8:  addsd  %xmm7, %xmm2
0x100000dec:  addsd  %xmm6, %xmm2
0x100000df0:  addsd  %xmm4, %xmm2
0x100000df4:  addsd  %xmm5, %xmm2
0x100000df8:  addsd  %xmm1, %xmm2
0x100000dfc:  addsd  %xmm3, %xmm2
0x100000e00:  addsd  %xmm0, %xmm2


This is with flags -O3 -ffast-math -std=c++11 -g. To get the assembly output, I ran the program under lldb, set a breakpoint at the line of interest with break and used the command dis.

So clearly my version of clang doesn't rewrite the expression like that.

4. As for performance, obviously the second version should be at least as fast. However, you have to actually try this on a function you actually have. And if you find that the performance improvement is insignificant, it's just not worth thinking about it.

5. As an example of how it can be insignificant, if you store the vector of values to be added in memory, the time required to fetch all the values from memory is much much greater than the time required to actually add them up. In hierarchical memory, accesses to main memory (rather than registers, or the L1 cache) are just so much slower that performance gains from these kinds of micro-optimizations are just rounding errors. Most of the time the CPU will not be executing anything, and will just be sitting there waiting for data to arrive.