# 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 = {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 + M + M + M + M + M + M + M;
// cout << S1 << endl;
T S2 = (((M + M) + (M + M)) + ((M + M) + (M + M)));
cout << S2 << endl;

return 0;
}


The tree version becomes this:

-> 0x100000de0:  addsd  %xmm6, %xmm7


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

-> 0x100000de8:  addsd  %xmm7, %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.