3

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?

Mysticial
  • 464,885
  • 45
  • 335
  • 332
Tae-Sung Shin
  • 20,215
  • 33
  • 138
  • 240
  • 4
    Have you tried profiling your code? – nhahtdh Oct 05 '12 at 03:34
  • 7
    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

1 Answers1

4

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.

Community
  • 1
  • 1
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 4
    `wrong 90% of the time` That's not how predictors work. – scientiaesthete Oct 05 '12 at 03:52
  • 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