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)
{
puts("1\n2\nFizz\n4\nBuzz\nFizz\n7\n8\nFizz\nBuzz\n11\nFizz\n13\n14\nFizzBuzz\n16\n17\nFizz\n19\nBuzz\nFizz\n22\n23\nFizz\nBuzz\n26\nFizz\n28\n29\nFizzBuzz\n31\n32\nFizz\n34\nBuzz\nFizz\n37\n38\nFizz\nBuzz\n41\nFizz\n43\n44\nFizzBuzz\n46\n47\nFizz\n49\nBuzz\nFizz\n52\n53\nFizz\nBuzz\n56\nFizz\n58\n59\nFizzBuzz\n61\n62\nFizz\n64\nBuzz\nFizz\n67\n68\nFizz\nBuzz\n71\nFizz\n73\n74\nFizzBuzz\n76\n77\nFizz\n79\nBuzz\nFizz\n82\n83\nFizz\nBuzz\n86\nFizz\n88\n89\nFizzBuzz\n91\n92\nFizz\n94\nBuzz\nFizz\n97\n98\nFizz\nBuzz");
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 responses to “Fastest FizzBuzz”
You should call write(2) directly, you don’t want to pay the cost of stdio’s buffering.
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.
Robby, I wonder if the system call + branch to figure that out would be fast enough to be worth the optimization?
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.
Obviously we’re I/O-bound. The solution is to convince management to buy a faster console.
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.
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.
*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.