-2

I am sorry beforehand if my terminology is lacking. I wrote a code to demonstrate inefficiency of series of if statements vs else/if statements. And the results dont make any sense to me.

It's a simple algorithm that goes through an array (100000000 of elements) and counts occurrences of the elements, being 1,2,3,4,5 or else.

clock_t time1;
time1 = clock();
    for (int i=1; i<=n; i++)
    {
        if (arr[i]==1)
            p1++;
        if (arr[i]==2)
            p2++;
        if (arr[i]==3)
            p3++;
        if (arr[i]==4)
            p4++;
        if (arr[i]==5)
            p5++;
        if (!(arr[i]>=1 && arr[i]<=5))
            j++;
    }
time1 = clock() - time1;

printf("count of 1s:\t %d\n",p1);
printf("count of 2s:\t %d\n",p2);
printf("count of 3s:\t %d\n",p3);
printf("count of 4s:\t %d\n",p4);
printf("count of 5s:\t %d\n",p5);
printf("count of errors:\t %d\n",j);
printf("\n ---  counting took: %.10f ms---\n",((double)(time1)/CLOCKS_PER_SEC)*1000);

and then the same but with else if

clock_t time2;
time2 = clock();
    for (int i=1; i<=n; i++)
    {
        if (arr[i]==1)
            p1++;
        else if (arr[i]==2)
            p2++;
        else if (arr[i]==3)
            p3++;
        else if (arr[i]==4)
            p4++;
        else if (arr[i]==5)
            p5++;
        else j++;
    }
time2 = clock() - time2;

as expected when given an array of random values from 1 to 5 the else if is faster about two times BUT (here comes the confusion) when its given an array of thousand 1s I would expect the if series to take the same amount of time bc it has to check every condition even tho the first one is already true - but it takes HALF the time and when I give it array of only 5s it is also quicker.

Can anyone explain how it can be faster, please? - Thanks :/ (when I give it ran values from 4 to 5 it is actually takes about the same time as with values from 1 to 5)

(here are the results of the whole thing [ignore the Czech please])

Edit

Here are the times from the image:

Code 1 - random input: 2451 ms
Code 2 - random input: 2401 ms

Code 1 - all-one input: 932 ms
Code 2 - all-one input: 573 ms

Code 1 - all-five input: 923 ms
Code 2 - all-five input: 697 ms
leftjoin
  • 36,950
  • 8
  • 57
  • 116
lordQuick
  • 53
  • 5
  • 1
    What have you got against arr[0]? – Martin James Apr 25 '18 at 07:35
  • 1
    With modern compiler optimizations, your inefficient `if` structure could very well be getting rewritten – Stephen Docy Apr 25 '18 at 07:37
  • Simplify the program right down, and check the generated assembly. That might surprise you. Also the statistical rigour of your test is lacking. – Bathsheba Apr 25 '18 at 07:38
  • Low level optimization only make sense for a precise version of a precise compiler with precise flags. Different compilers of optimization level could lead to different results. If you are using gcc or clang, you could try to check the generated assembly. – Serge Ballesta Apr 25 '18 at 07:40
  • 1
    Hard to say without knowing all details of your system. But I would consider whether branch prediction plays a role here. – Support Ukraine Apr 25 '18 at 07:43
  • 1
    Link: https://stackoverflow.com/a/11227902/4386427 – Support Ukraine Apr 25 '18 at 07:45

1 Answers1

0

Modern CPUs are very complicated beasts.

I guess you are more benchmarking CPU branch predictor rather then anything else: If you fill the array with random numbers from the range 1...5, branch predictors will quite often guess wrong when any of the if is executed.

If you fill the array with constants, the predictors will be right in 100%.

I.e. with randomized input, the count of evaluated ifs really matters as substantial number of them cause CPU pipeline stall.

With the constant input, the number of executed ifs is more or less negligible, and there are no pipeline stalls. All what matters is some CPU internals and also how well your compiler is able to optimize your code. Smart compiler might be able to effectively replace one of the two or both of your examples into switch statement, so without looking at the instructions generated we can just speculate.

mity
  • 2,299
  • 17
  • 20