1
\$\begingroup\$

I imagine I get a minuscule performance improvement by doing the %3 as a branch off the %5 rather than the other way round or as an if '%15'. Am I correct about that? (I know there is no practical difference)

#include <stdio.h>

///Write a program that prints the numbers from 1 to 100.
///But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz".
///For numbers which are multiples of both three and five print "FizzBuzz".
int main()
{
    int a=1;
    while (a<101)
    {
        if (a%5==0)
        {
            if (a%3==0)
            {
                printf("FizzBuzz\n");
            }
            else
            {
                printf("Buzz\n");
            }
        }
        else if(a%3==0)
        {
            printf("Fizz\n");
        }
        else
        {
            printf("%d\n",a);
        }
        a++;
    }
return 0;
}
\$\endgroup\$
5
  • 4
    \$\begingroup\$ 1. It wouldn't matter with compiler optimizations. 2. If you turned off compiler optimizations, your code would be slower thanks to branch prediction. \$\endgroup\$
    – syb0rg
    Jun 21 '16 at 18:18
  • \$\begingroup\$ ah. so the processor improvements would, in this case, reduce the effectiveness, (as I assume a blind 'do as I am told' approach would lead to the code being more efficient) \$\endgroup\$
    – user101969
    Jun 21 '16 at 18:20
  • 2
    \$\begingroup\$ I'm not sure what you mean by "processor improvements". You should always try to reduce the number of branches in your code, as it helps improve readability and performance. \$\endgroup\$
    – syb0rg
    Jun 21 '16 at 18:23
  • \$\begingroup\$ Oh, I meant the branch predictor, which is an enhancement, but in this case would wreck it. I knew about the style, but didn't know about the performance penalty- thanks for that . \$\endgroup\$
    – user101969
    Jun 21 '16 at 18:29
  • \$\begingroup\$ It would be more meaningful to discuss this if you state which target system you have in mind. \$\endgroup\$
    – Lundin
    Jun 28 '16 at 9:50
1
\$\begingroup\$

The performance bottleneck in this specific scenario is the branch prediction tables (e.g. the if..else statements). To eke out any minor improvements in your code, you'll want to cut the branch prediction down as much as possible, which could been done a few ways, here are a couple as an example:

// using a switch and some bit-shifting
#include <stdio.h>

int main(int argc, char** argv)
{
    int i = 0;
    while (++i < 101)
    {
        switch ((((i % 3) << 4) | (i % 5)))
        {
            case 0: // 3 and 5
                printf("FizzBuzz"); break;
            case 1: case 2: case 3: case 4: // i % 3
                printf("Fizz"); break;
            case 16: case 32: // i % 5
                printf("Buzz"); break;
            default:
                printf("%d", i); break;
        }
        printf("\n");
    }
    return 0;
}

Or

// using some 'bool' types
#include <stdio.h>

int main(int argc, char** argv)
{
    int is3 = 0;
    int is5 = 0;
    int i = 0;
    while (++i < 101)
    {
        is3 = (i % 3 == 0);
        is5 = (i % 5 == 0);
        if (is3 || is5) {
            if (is3) { printf("Fizz"); }
            if (is5) { printf("Buzz"); }
        } else {
            printf("%d", i);
        }
        printf("\n");
    }
    return 0;
}

I'm preferential to the first example because of the switch, though it's not as immediately clear as to what it does (say vs. the second).

It should be noted that modulus math and bit shifting is computationally more complex than checking a boolean value (i.e. the assembly generated), so which of the 2 examples above is actually faster would need further testing, but both examples do reduce the branch tables.

I hope that can help.

\$\endgroup\$
5
  • \$\begingroup\$ Thanks, the first is particularly useful, because I was wondering about switches, and I haven't had time to look at bit-shifting yet (I'm taking a course, but it's mainly C# and webdev; C was by way of introduction.) \$\endgroup\$
    – user101969
    Jun 22 '16 at 8:33
  • \$\begingroup\$ @Orangesandlemons, the switch is nice because the compiler can generate a hash for all values that relate, thus they have the same branch time; the bit shifting just makes it so that the values of the modulus operation can sit in 1 int to switch on. The first example works in C# (changing the printf to Console.Write, etc.) too if you wish to explore it there. \$\endgroup\$
    – txtechhelp
    Jun 22 '16 at 8:38
  • 1
    \$\begingroup\$ "The performance bottleneck in this specific scenario is the branch prediction tables" Says who? You can't just run off and optimize code with no particular system in mind. You would need some quite solid arguments before you start obfuscating the code for the sake of performance. On some systems, division might be the big bottleneck, rather than branch prediction, and then all you achieved was to make the code slower and less readable. \$\endgroup\$
    – Lundin
    Jun 28 '16 at 9:46
  • \$\begingroup\$ That being said, you didn't really reduce the number of branches much at all... depending on how well the compiler optimizes that switch, it may end up with plenty of branches. \$\endgroup\$
    – Lundin
    Jun 28 '16 at 9:53
  • \$\begingroup\$ There is nothing preventing the compiler from rewriting a bunch of if-statements into a switch statement and vice versa, don't assume that there is a benefit to using switch. Also, from experience, different compilers, different CPU architectures and different optimization levels give wildly different results. In these cases, I would first optimize for readability and maintainability (so I would prefer your second example), only if this code is a performance bottleneck would I start investigating ways to optimize for speed. \$\endgroup\$
    – G. Sliepen
    Nov 22 '20 at 9:59
2
\$\begingroup\$

I have my doubts that any method is significantly faster than another given the sink-hole of time that printf() is, but here is another approach

#define FB "FizzBuzz\n"
#define F "Fizz\n"
#define B "Buzz\n"
#define N "%d\n"

int main(void) {
  static const char *fmt[15] = {
      FB, N, N, F, N, B, F, N, N, F, B, N, F, N, N };
  for (int a = 1; a <= 100; a++) {
    printf(fmt[a % 15], a);
  }
  return 0;
}
\$\endgroup\$
4
  • \$\begingroup\$ I do like this very much- I'm also wondering about using a cyclical value that resets to 1 when it reaches 16, which allows us to avoid the modulus. \$\endgroup\$
    – user101969
    Jun 22 '16 at 8:29
  • \$\begingroup\$ @Orangesandlemons What is the goal "performance improvement" or "avoid the modulus"? \$\endgroup\$ Jun 22 '16 at 13:04
  • \$\begingroup\$ my original question was regarding whether the branch layout made it faster, which was exactly wrong of me :-) I just was noting in my comment that I could miss out the modulus- more out of interest than performance. \$\endgroup\$
    – user101969
    Jun 22 '16 at 13:09
  • 1
    \$\begingroup\$ Avoiding modulus and improving performance may or may not be the same thing, depending on system. It doesn't make much sense to discuss performance with no specific system in mind. That being said, I think this proposed algorithm will give nice performance on most systems. \$\endgroup\$
    – Lundin
    Jun 28 '16 at 9:49
1
\$\begingroup\$

To benchmark I eliminated the line printing and extended to 10 million. Only a summary is printed.

This seems to be the fastest version:

/* Nested if. No direct test for mod 15. Start with low divisor first */
/* Needs extra printf() for printing (newline after fizz when no buzz follows) */
void buzz1(void) {

    int i, fz=0, bz=0, fzbz=0, none=0;

    for (i = 1; i <= 10000000; i++) {
        
        if (i % 3 == 0) { 
            fz++;  
            if (i % 5 == 0) 
               fzbz++;  
            continue;
        }
        if (i % 5 == 0) {     
            bz++;
            continue;
        }
        none++;
    }
    printf("%d %d %d %d", none, fz, bz, fzbz);     
} 

The "perf" tool gives:

 34939315      cycles                    #    3.237 GHz                    
152120375      instructions              #    4.35  insn per cycle         
 28165712      branches                  # 2609.413 M/sec                  
     7255      branch-misses             #    0.03% of all branches        

   0.011164707 seconds time elapsed

For the OP version:

  53842208      cycles                    #    3.242 GHz                    
 195796482      instructions              #    3.64  insn per cycle         
   2668305      branches                  #  160.653 M/sec                  
      7597      branch-misses             #    0.28% of all branches        

    0.017125379 seconds time elapsed

That is: 25% slower (more cycles/instructions), one tenth of branches, but the same amount of branch misses.

The switch version behaves very similar to OP version.

As does this version, which is a bit slower, but very simple:

void buzz2(void) {

    int i, fz=0, bz=0, fzbz=0, none=0;
    for (i = 1; i <= 10000000; i++) {

        if (i % 15 == 0) {
            fzbz++;
            continue;
        }
        if (i % 3 == 0) {
            fz++;
            continue;
        }
        if (i % 5 == 0) {
            bz++;
            continue;
        } 
        none++;
    }
    printf("%d %d %d %d", none, fz, bz, fzbz);

}

Not the number of branches, but of branch-misses (absolute or relative) seem to be important here.

This Fizzbuzz game is actually just one-halve of a prime searching function.


The buzz2() version (with i % 15) leads to very special code: about 200 lines like this with several xmm registers and only one jump:

12d2:       |   66 44 0f 6f 74 24 b8        movdqa xmm14,XMMWORD PTR [rsp-0x48]
12d9:       |   66 0f 73 f6 20              psllq  xmm6,0x20
12de:       |   66 41 0f d4 f0              paddq  xmm6,xmm8
12e3:       |   66 44 0f f4 f0              pmuludq xmm14,xmm0
12e8:       |   66 44 0f 6f c1              movdqa xmm8,xmm1
12ed:       |   0f c6 ee dd                 shufps xmm5,xmm6,0xdd

buzz1() has only 40 lines - no division, but 2 multiplications:

    117b:       |  |  |     |   81 fa 81 96 98 00       cmp    edx,0x989681
    1181:       |  |  |  /--|-- 74 35                   je     11b8 <buzz1+0x68>
    1183:       |  |  >--|--|-> 89 d0                   mov    eax,edx
    1185:       |  |  |  |  |   48 0f af c6             imul   rax,rsi
    1189:       |  |  |  |  |   48 c1 e8 22             shr    rax,0x22
    118d:       |  |  |  |  |   8d 0c 80                lea    ecx,[rax+rax*4]
    1190:       |  |  |  |  |   89 d0                   mov    eax,edx
    1192:       |  |  |  |  |   29 c8                   sub    eax,ecx
    1194:       |  |  |  |  |   69 ca ab aa aa aa       imul   ecx,edx,0xaaaaaaab
    119a:       |  |  |  |  |   81 f9 55 55 55 55       cmp    ecx,0x55555555
    11a0:       |  |  |  |  \-- 77 ce                   ja     1170 <buzz1+0x20>



"...after fizz when no buzz follows"

So this "boring" Fizzbuzz is full of subtle questions. At 15, 30, 45...: is it "Fizz""Buzz" or "Fizzbuzz"? My first (printing) version (a lie: the first version did not work:-) uses the fact that the "Fizz" in "Fizzbuzz" is the same as in a simple "Fizz". It is more complicated than handling the modulo 15 first.

The putchar() elegantly decides between "Fizz" and "FizzBuzz" (not "-buzz"!), but this additional output command is a performance killer.

So the printing version with the same flow as the fastest counting version is:


    int i, fz=0, bz=0, fzbz=0, none=0;

        for (i = 1; i <= 100; i++) {

                if (i % 3 == 0) {
                        printf("Fizz");
                        if (i % 5 == 0)
                            printf("Buzz");
                        putchar('\n');
                    continue;
                }
                if (i % 5 == 0) {
                        printf("Buzz\n");
                        continue;
                }
                printf("%d\n", i);
        }
}

Just replacing the printf's gives wrong numbers:

none fizz buzz fizzbuzz

5333333 2666667 1333334 666666 5333333 3333333 1333334 666666

One third of fizzes is wrong: some of them are Fizzbuzzes:

3333333-3333333/5
2666667

Or 10000000 * 1/3 * 4/5, but we forgot the even numbers, and the 10 million does not matter. So it is:

1/2 * 2/3 * 4/5
.266666

Which leads to super-famous Euler's Product formula

\$\left({\frac {\ldots \cdot 10\cdot 6\cdot 4\cdot 2\cdot 1}{\ldots \cdot 11\cdot 7\cdot 5\cdot 3\cdot 2}}\right)\zeta (1)=1\$

which is directly connected to the Harmonic series, Eratosthenes' sieve and Riemann's Zeta function. All that from Fizzbuzz "game".


Review: Actually use loop constructs

The idea of these for- and while-loops is to put the standard loop-control expressions in one place. They sometimes get overloaded, but you definitely underemply you while():

while (a < 101) {
...
a++
}

...has the check and the increment one screen apart. Rather:

while (a++ <= 100) { ... }

But why is for-loop boring, complicated, and often used? Because you often also set a variable before the loop:

Nothing wrong with your int a=1; by itself, but when you combine all that, the usual way to do this would be:

int a;
for (a = 1; a <= 100; a++) {
...
}

For uneven numbers:

for (a = 1; a <= 100; a += 2) {

minuscule performance improvement

At second thought it does not matter here with only two divisors involved and you have to go through the full logical tree for each number 00,01,10,11 or 0,A,B,AB ...or [number], fizz, buzz, fizzbuzz.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy