addition vs comparison

Question

Let say I have an array of 1,000,000 elements with about 90% of 0s and 10% of 1s.

In order to count of 1s, I can do

sum=0;
for(int i=0;i<size;i++) {
    sum+=x[i]
}

But I thought maybe comparison is cheaper than addition so this would be better.

sum=0;
for(int i=0;i<size;i++) {
    if(x[i]==1)
        sum++;
}

But I am not sure. Which one is faster?

Even without profiling, I can almost guarantee that the first option is faster unless `sum` happens to be `volatile` or something stupid like that. The second case could also suffer from [branch prediction](http://stackoverflow.com/q/11227809/922184). — Mysticial, Oct 05 '12 at 03:37

score 3 · Accepted Answer · edited May 23 '17 at 12:18

3

It is hard to say which one is going to be faster without trying it, but a even a slightly slower instruction without a branch will usually be faster due to pipelining and branch prediction.

In your case, the branch predictor will be wrong 90% of the time, reducing the speed quite a bit.

edited May 23 '17 at 12:18

Community

1
1

answered Oct 05 '12 at 03:35

Sergey Kalinichenko

697,062
78
1,055
1,465

3

`wrong 90% of the time` That's not how predictors work. – scientiaesthete Oct 05 '12 at 03:52
Amazingly good stuff. Thanks. – Tae-Sung Shin Oct 05 '12 at 03:53
1

I agree with @scientiaesthete here; the branch predictor should get it right 90% of the time. Otherwise it's a lousy predictor. However, the more interesting point is that comparing a number to 1 is essentially the same as adding the number to something. So compare and optionally increment is more work than unconditionally add. – rici Oct 05 '12 at 04:19

addition vs comparison

1 Answers1