0
\$\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\$
  • 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\$ – Orangesandlemons 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\$ – Orangesandlemons 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\$
  • \$\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\$ – Orangesandlemons 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
  • \$\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
3
\$\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\$
  • \$\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\$ – Orangesandlemons Jun 22 '16 at 8:29
  • \$\begingroup\$ @Orangesandlemons What is the goal "performance improvement" or "avoid the modulus"? \$\endgroup\$ – chux 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\$ – Orangesandlemons 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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.