Fastest FizzBuzz

The always-entertaining FizzBuzz problem came up again on Hacker News today, and for no other reason than I just got out from under a nasty deadline, I looked around on the net for interesting solutions, for which this Rosetta Code page is a gold mine. The Windows batch file and BSD make versions are hilarious, though I was a bit disappointed that Piet was not represented. Anyhow, here it is: (reference)

Another wonderful FizzBuzz solution uses template metaprogramming to evaluate the solution at compile time. I was disappointed, however, to look at the code emitted by Clang++, G++, and Intel’s C++ compiler, which all generate a large amount of crap instead of boiling the program down to its essence: emitting a single string.

I also noticed that various sites that discuss the efficiency of FizzBuzz implementations, such as this one, failed to provide what I would consider the most efficient code:

#include <stdio.h>

int main (void)
  return 0;

It would perhaps be better style to use printf() instead of puts(), counting on the compiler to optimize the former to the latter, but the version of GCC that I use does not actually do that.

Using my timing code on a random Nehalem 64-bit Linux machine I get:

g++ -O3: 125,000 cycles

Intel C++ -fast: 103,000 cycles

Clang++ -O3: 103,000 cycles

gcc -O3: 29,000 cycles

gcc -O3 -static: 21,000 cycles

Here’s the C code and C++ code. For benchmarking purposes I piped their STDOUT to /dev/null.

8 Replies to “Fastest FizzBuzz”

  1. Someone should add an optimization that detects if stdout is going to /dev/null and then just not do anything. I bet you can finish that in less than 21,000 cycles.

    PS: Benchmarks suck.

  2. Robby, I wonder if the system call + branch to figure that out would be fast enough to be worth the optimization?

  3. It’s not a DOS batch file, though. I went through all of Rosetta code a few years ago changing the name of the language, because all but two examples were using Windows features anyway.

  4. Hi pdw, I considered that but figured portable C was better.

    Robby, given how UNIX redirection works, is it even possible for the process to tell whether its stdout is hooked to /dev/null? I’m not sure it is, at least portably.

  5. Redirection itself doesn’t pose any difficulty: there’s still a file underlying a redirected descriptor, and you can just look to see whether that’s the same file underlying /dev/null:

    struct stat stdout_stat;
    struct stat devnull_stat;

    if (fstat(STDOUT_FILENO, &stdout_stat) < 0)
    err(2, "failed fstat");

    if (stat("/dev/null", &devnull_stat) /dev/null should do the job.

  6. *sigh* Well, that’s what I get for assuming that the comment box uses markdown.

    The code just compares inode numbers. I also point that you can defeat such trickery easily enough by piping through cat – although that comes with a performance hit.

Comments are closed.