Fizz Buzz is a common challenge given during interviews. The challenge goes something like this:
Write a program that prints the numbers from 1 to n. If a number is divisible by 3, write Fizz instead. If a number is divisible by 5, write Buzz instead. However, if the number is divisible by both 3 and 5, write FizzBuzz instead.
The goal of this question is to write a FizzBuzz implementation that goes from 1 to infinity (or some arbitrary very very large number), and that implementation should do it as fast as possible.
Write your fizz buzz program. Run it. Pipe the output through
<your_program> | pv > /dev/null. The higher the throughput, the better you did.
A naive implementation written in C gets you about 170MiB/s on an average machine:
There is a lot of room for improvement here. As you will see further below, the implementation below is able to reach 55,000 MiB/s (55 GiB/s). The implementation we will discuss is over 323 times faster than the above.
- All languages are allowed.
- The program output must be exactly valid fizzbuzz. No playing tricks such as writing null bytes in between the valid output – null bytes that don’t show up in the console but do count towards
Here’s an example of valid output:
Valid output must be simple ASCII, single-byte per character, new lines are a single
\n and not
\r\n. The numbers and strings must be correct as per the FizzBuzz requirements. The output must go on forever (or a very high astronomical number) and not halt / change prematurely.
- Parallel implementations are allowed (and encouraged).
- Architecture specific optimizations / assembly is also allowed. This is not a real contest – I just want to see how people push fizz buzz to its limit – even if it only works in special circumstances/platforms.
This program is most conveniently built using
gcc. Save it as
fizzbuzz.S (that’s a capital
S as the extension), and build using the commands
./fizzbuzz piped into one command, e.g.
./fizzbuzz | pv > /dev/null (as suggested in the question),
./fizzbuzz | cat, or
./fizzbuzz | less. To simplify the I/O, this will not work (producing an error on startup) if you try to output to a file/terminal/device rather than a pipe. Additionally, this program may produce incorrect output if piped into two commands (e.g.
./fizzbuzz | pv | cat > fizzbuzz.txt), but only in the case where the middle command uses the
splice system call; this is either a bug in Linux (very possible with system calls this obscure!) or a mistake in the documentation of the system calls in question (also possible). However, it should work correctly for the use case in the question, which is all that matters on CGCC.
This program is somewhat system-specific; it requires the operating system to be a non-ancient version of Linux, and the processor to be an x86-64 implementation that supports AVX2. (Most moderately recent processors by Intel and AMD have AVX2 support, including the Ryzen 9 mentioned in the question, and almost all use the x86-64 instruction set.) However, it avoids assumptions about the system it’s running on beyond those mentioned in the header, so there’s a decent chance that if you can run Linux, you can run this.
The program outputs a quintillion lines of FizzBuzz and then exits (going further runs into problems related to the sizes of registers). This would take tens of years to accomplish, so hopefully counts as “a very high astronomical number” (although it astonishes me that it’s a small enough timespan that it might be theoretically possible to reach a number as large as a quintillion without the computer breaking).
As a note: this program’s performance is dependent on whether it and the program it outputs to are running on sibling CPUs or not, something which will be determined arbitrarily by the kernel when you start it. If you want to compare the two possible timings, use
taskset to force the programs onto particular CPUs:
taskset 1 ./fizzbuzz | taskset 2 pv > /dev/null versus
taskset 1 ./fizzbuzz | taskset 4 pv > /dev/null. (The former will probably run faster, but might be slower on some CPU configurations.)
I’ve spent months working on this program. I’ve long thought that “how fast can you make a FizzBuzz” would be a really interesting question for learning about high-performance programming, and when I subsequently saw this question posted on CGCC, I pretty much had to try.
This program aims for the maximum possible single-threaded performance. In terms of the FizzBuzz calculation itself, it is intended to sustain a performance of 64 bytes of FizzBuzz per 4 clock cycles (and is future-proofed where possible to be able to run faster if the relevant processor bottleneck – L2 cache write speed – is ever removed). This is faster than a number of standard functions. In particular, it’s faster than
memcpy, which presents interesting challenges when it comes to I/O (if you try to output using
write then the copies in
write will take up almost all the runtime – replacing the I/O routine here with
write causes the performance on my CPU to drop by a factor of 5). As such, I needed to use much more obscure system calls to keep I/O-related copies to a minimum (in particular, the generated FizzBuzz text is only sent to main memory if absolutely necessary; most of the time it’s stored in the processor’s L2 cache and piped into the target program from there, which is why reading it from a sibling CPU can boost performance – the physical connection to the L2 cache is shorter and higher bandwidth than it would be to a more distant CPU).
On my computer (which has a fairly recent, but not particularly powerful, Intel processor), this program generates around 31GiB of FizzBuzz per second. I’ll be interested to see how it does on the OP’s computer.
I did experiment with multithreaded versions of the program, but was unable to gain any speed. Experiments with simpler programs show that it could be possible, but any gains may be small; the cost of communication between CPUs is sufficiently high to negate most of the gains you could get by doing work in parallel, assuming that you only have one program reading the resulting FizzBuzz (and anything that writes to memory will be limited by the write speed of main memory, which is slower than the speed with which the FizzBuzz can be generated).
This isn’t code-golf, so my explanation of the program and its algorithm are given as comments in the program itself. (I still had to lightly golf the program, and especially the explanation, to fit this post within the 65536 byte size limit.)
The program is written in a “literate” assembly style; it will be easiest to understand if you read it in order, from start to end. (I also added a number of otherwise useless line labels to separate the program into logical groups of instructions, in order to make the disassembly easier to read, if you’re one of the people who prefers to read assembly code like that.)