40
\$\begingroup\$

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.

Checking throughput

Write your fizz buzz program. Run it. Pipe the output through <your_program> | pv > /dev/null. The higher the throughput, the better you did.

Example

A naive implementation written in C gets you about 170MiB/s on an average machine:

#include <stdio.h>

int main() {
    for (int i = 1; i < 1000000000; i++) {
        if ((i % 3 == 0) && (i % 5 == 0)) {
            printf("FizzBuzz\n");
        } else if (i % 3 == 0) {
            printf("Fizz\n");
        } else if (i % 5 == 0) {
            printf("Buzz\n");
        } else {
            printf("%d\n", i);
        }
    }
}

There is a lot of room for improvement here. In fact, I've seen an implementation that can get more than 3GiB/s on the same machine.

I want to see what clever ideas the community can come up with to push the throughput to its limits.

Rules

  • 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 pv throughput.

Here's an example of valid output:

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz

# ... and so on

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.

Scores

Scores are from running on my desktop with an AMD 5950x CPU (16C / 32T). I have 32GB of 3600Mhz RAM.

enter image description here

Also @Aiden4's submission - 3GiB/s. I lost the plotting code, might add it to the image once I find it

Also @Toby Speight's submission - 6.2-6.8GiB/s with OMP_NUM_THREADS=1

\$\endgroup\$
19
  • 1
    \$\begingroup\$ How are we scoring speed? If you change the machine the speed will change drastically. You mentioned architecture specific optimizations as well, so it seems like it is tested on multiple different architectures. How do you ensure that comparison is fair? \$\endgroup\$ – Wheat Wizard Nov 14 '20 at 18:07
  • 2
    \$\begingroup\$ That's definitely a problem. I will try and run the implementations posted here on my desktop and keep score in the main question by editing it when new answers are posted. If it's something architecture specific I can't run, it'll still interesting to see, doesn't have to compete in the same score table. \$\endgroup\$ – Omer Tuchfeld Nov 14 '20 at 18:09
  • 5
    \$\begingroup\$ @agtoever note that the benchmark is done using piping to pv, which means that the Linux default pipe buffer size of 64K is used, as well as pv's default 64K buffer size. My entry exploits these properties by setting the buffer size to 64K, but it still blocks on write due to many factors; one of which is the generation speed being affected by the varying length of the printed numbers. \$\endgroup\$ – Isaac G. Nov 15 '20 at 10:29
  • 1
    \$\begingroup\$ related: My answer on an SO question about x86-64 asm fizz buzz includes a tutorial on tuning some parts of it for performance. (e.g. unroll by 3 and use a down-counter starting at 5 instead of modulo on i). But it still uses a slow div for int->string, and critically uses write for each group of 15 output lines built up in a buffer. Full-on perf tuning would probably just unroll by 15, and of course use much bigger buffers. \$\endgroup\$ – Peter Cordes Nov 16 '20 at 18:25
  • 1
    \$\begingroup\$ Hoe do you measure throughput of a program which runs "for ever"? If I have a program which first does calculations for a year, then outputs a googol lines in a minute, it will lose if you stop measuring if you cut off the measurement within a year, but it'll be a winner if you measure for a year and a minute. This is of course an extreme example, but many programs will get slower when numbers get larger, so how you long you measure matters. \$\endgroup\$ – Abigail Nov 21 '20 at 11:30
38
\$\begingroup\$

After much trial and error, with the goal of not resorting to Assembly while achieving the best single-threaded performance, this is my entry:

#include <unistd.h>

#define unlikely(e)      __builtin_expect((e), 0)
#define mcpy(d, s, n)    __builtin_memcpy((d), (s), (n))

#define CACHELINE 64
#define PGSIZE 4096
#define ALIGNED_BUF 65536
#define FIZZ "Fizz"
#define BUZZ "Buzz"
#define DELIM "\n"

typedef struct {
    unsigned char offset;
    char data[CACHELINE - sizeof(unsigned char)];
} counters_t;

static inline void os_write(int out, void *buf, unsigned int n)
{
    while (n)
    {
        ssize_t written = write(out, buf, n);

        if (written >= 0)
        {
            buf += written;
            n -= written;
        }
    }
}

int main(void)
{
    const int out = 1;

    __attribute__((aligned(CACHELINE))) static counters_t counter = {
        sizeof(counter.data) - 1, "00000000000000000000000000000000000000000000000000000000000000"
    };
    __attribute__((aligned(PGSIZE))) static char buf[ALIGNED_BUF + (sizeof(counter.data) * 15 * 3)] = { 0 };
    char *off = buf;

    for (;;)
    {
        // Write chunks of 30 counters until we reach `ALIGNED_BUF`
        while (off - buf < ALIGNED_BUF)
        {
            #define NN (sizeof(counter.data) - 2)

            // Hand-rolled counter copy, because with non-constant sizes the compiler
            // just calls memcpy, which is too much overhead.
            #define CTRCPY(i) do { \
                const char *src = end; \
                char *dst = off; \
                unsigned _n = n; \
                switch (_n & 3) { \
                case 3: *dst++ = *src++; \
                case 2: \
                    mcpy(dst, src, 2); \
                    dst += 2; src += 2; \
                    break; \
                case 1: *dst++ = *src++; \
                case 0: break; \
                } \
                for (_n &= ~3; _n; _n -= 4, dst += 4, src += 4) { \
                    mcpy(dst, src, 4); \
                } \
                mcpy(off + n, i DELIM, sizeof(i DELIM) - 1); \
                off += n + sizeof(i DELIM) - 1; \
            } while (0)

            // Write the first 10 counters of the group (need to separate the
            // first 10 counters from the rest of the chunk due to possible decimal
            // order increase at the end of this block)
            {
                const char *const end = counter.data + counter.offset;
                const unsigned int n = sizeof(counter.data) - counter.offset - 1;

                CTRCPY("1"); // 1
                CTRCPY("2"); // 2

                mcpy(off, FIZZ DELIM, sizeof(FIZZ DELIM) - 1); // Fizz (3)
                off += sizeof(FIZZ DELIM) - 1;

                CTRCPY("4"); // 4

                mcpy(off, BUZZ DELIM FIZZ DELIM, sizeof(BUZZ DELIM FIZZ DELIM) - 1); // Buzz (5) Fizz (6)
                off += sizeof(BUZZ DELIM FIZZ DELIM) - 1;

                CTRCPY("7"); // 7
                CTRCPY("8"); // 8

                mcpy(off, FIZZ DELIM BUZZ DELIM, sizeof(FIZZ DELIM BUZZ DELIM) - 1); // Fizz (9) Buzz (10)
                off += sizeof(FIZZ DELIM BUZZ DELIM) - 1;

                // Carry handling on MOD 10
                for (unsigned d = NN; ; --d)
                {
                    if (counter.data[d] != '9')
                    {
                        ++counter.data[d];
                        break;
                    }
                    counter.data[d] = '0';
                }

                // Decimal order increases only when `counter MOD 30 == 10`
                if (unlikely(counter.data[counter.offset - 1] != '0'))
                {
                    if (unlikely(counter.offset == 1))
                    {
                        goto end;
                    }

                    --counter.offset;
                }
            }

            // Write the chunk's remaining 20 counters
            {
                const char *const end = counter.data + counter.offset;
                const unsigned int n = sizeof(counter.data) - counter.offset - 1;

                CTRCPY("1"); // 11

                mcpy(off, FIZZ DELIM, sizeof(FIZZ DELIM) - 1); // Fizz (12)
                off += sizeof(FIZZ DELIM) - 1;

                CTRCPY("3"); // 13
                CTRCPY("4"); // 14

                mcpy(off, FIZZ BUZZ DELIM, sizeof(FIZZ BUZZ DELIM) - 1); // FizzBuzz (15)
                off += sizeof(FIZZ BUZZ DELIM) - 1;

                CTRCPY("6"); // 16
                CTRCPY("7"); // 17

                mcpy(off, FIZZ DELIM, sizeof(FIZZ DELIM) - 1); // Fizz (18)
                off += sizeof(FIZZ DELIM) - 1;

                CTRCPY("9"); // 19

                mcpy(off, BUZZ DELIM FIZZ DELIM, sizeof(BUZZ DELIM FIZZ DELIM) - 1); // Buzz (20) Fizz (21)
                off += sizeof(BUZZ DELIM FIZZ DELIM) - 1;

                // Carry handling on MOD 10
                for (unsigned d = NN; ; --d)
                {
                    if (counter.data[d] != '9')
                    {
                        ++counter.data[d];
                        break;
                    }
                    counter.data[d] = '0';
                }

                CTRCPY("2"); // 22
                CTRCPY("3"); // 23

                mcpy(off, FIZZ DELIM BUZZ DELIM, sizeof(FIZZ DELIM BUZZ DELIM) - 1); // Fizz (24) Buzz (25)
                off += sizeof(FIZZ DELIM BUZZ DELIM) - 1;

                CTRCPY("6"); // 26

                mcpy(off, FIZZ DELIM, sizeof(FIZZ DELIM) - 1); // Fizz (27)
                off += sizeof(FIZZ DELIM) - 1;

                CTRCPY("8"); // 28
                CTRCPY("9"); // 29

                mcpy(off, FIZZ BUZZ DELIM, sizeof(FIZZ BUZZ DELIM) - 1); // FizzBuzz (30)
                off += sizeof(FIZZ BUZZ DELIM) - 1;

                // Carry handling on MOD 10
                for (unsigned d = NN; ; --d)
                {
                    if (counter.data[d] != '9')
                    {
                        ++counter.data[d];
                        break;
                    }
                    counter.data[d] = '0';
                }
            }
        }

        os_write(out, buf, ALIGNED_BUF);
        mcpy(buf, buf + ALIGNED_BUF, (off - buf) % ALIGNED_BUF);
        off -= ALIGNED_BUF;
    }

end:
    os_write(out, buf, off - buf);

    return 0;
}

Compiled as clang -o fizz fizz.c -O3 -march=native (with clang 11.0.0 on my Ubuntu 20.10 installation, running kernel version 5.8.0-26.27-generic 5.8.14 on an Intel Core i7-8750H mobile CPU while plugged into the wall), this produces ~3.8GiB/s when run as ./fizz | pv > /dev/null (not very steady due to write blocking every once in a while, but there's nothing I can do about that when single-threaded, I guess).

EDIT: Optimised the carry handling a bit, and now I'm getting ~3.9GiB/s on my machine (same configuration as above).

\$\endgroup\$
5
  • 8
    \$\begingroup\$ Welcome to the site! Nice first post. \$\endgroup\$ – Redwolf Programs Nov 14 '20 at 18:38
  • 1
    \$\begingroup\$ Interesting, GCC sees through your memcpy(dst,src,4) loop and decides to turn into one variable-sized call to libc memcpy. godbolt.org/z/14K5Pd. But clang does turn that nasty-looking memcpy(dst,src,4) repeat-loop into vmovups instructions that load/store 32 bytes at a time, not just 4! godbolt.org/z/jM3f8K. So basically I think it turns (part of?) your manual memcpy back into one big memcpy like gcc does, but then inlines it instead of calling the libc function. \$\endgroup\$ – Peter Cordes Nov 16 '20 at 20:23
  • 2
    \$\begingroup\$ You don't need a macro for __builtin_memcpy, just use memcpy. GCC and clang define memcpy as a builtin (same as __builtin_memcpy) by default, unless you use -fno-builtin-memcpy or -fno-builtin (which you'd use for writing unit-tests or benchmarks for a hand-written libc or kernel implementation for example, to make it actually call the function instead of inlining or optimizing away). \$\endgroup\$ – Peter Cordes Nov 16 '20 at 20:26
  • 1
    \$\begingroup\$ @PeterCordes you're right about __builtin_memcpy in this case, but as an embedded developer (where GCC/clang don't assume that memcpy can be inlined with constant size) it's an instinct for me to reach for __builtin_memcpy in order to ensure inlining. \$\endgroup\$ – Isaac G. Nov 16 '20 at 20:37
  • 1
    \$\begingroup\$ Ok, so you're used to compiling with -fno-builtin for embedded systems. Oh right, that's implied by -ffreestanding, unfortunately even for the functions gcc requires the freestanding environment to provide (memcpy, memmove, memset and memcmp). That's unfortunate; you end up wanting a #define to the __builtin version for every ISO C standard function you do implement. \$\endgroup\$ – Peter Cordes Nov 16 '20 at 20:49
21
\$\begingroup\$

I was struggling to get more than 2.75GB/s on my rig but then I realised I wasn't compiling with -O3 which bumped me up to 6.75GB/s.

#include <stdio.h>
#include <string.h>
#include <unistd.h>
char buf[416];
char out[65536 + 4096] = "1\n2\nFizz\n4\nBuzz\nFizz\n7\n8\nFizz\n";
int main(int argc, char **argv) {
  const int o[16] = { 4, 7, 2, 11, 2, 7, 12, 2, 12, 7, 2, 11, 2, 7, 12, 2 };
  char *t = out + 30;
  unsigned long long i = 1, j = 1;
  for (int l = 1; l < 20; l++) {
    int n = sprintf(buf, "Buzz\n%llu1\nFizz\n%llu3\n%llu4\nFizzBuzz\n%llu6\n%llu7\nFizz\n%llu9\nBuzz\nFizz\n%llu2\n%llu3\nFizz\nBuzz\n%llu6\nFizz\n%llu8\n%llu9\nFizzBuzz\n%llu1\n%llu2\nFizz\n%llu4\nBuzz\nFizz\n%llu7\n%llu8\nFizz\n", i, i, i, i, i, i, i + 1, i + 1, i + 1, i + 1, i + 1, i + 2, i + 2, i + 2, i + 2, i + 2);
    i *= 10;
    while (j < i) {
      memcpy(t, buf, n);
      t += n;
      if (t >= &out[65536]) {
        char *u = out;
        do {
          int w = write(1, u, &out[65536] - u);
          if (w > 0) u += w;
        } while (u < &out[65536]);
        memcpy(out, out + 65536, t - &out[65536]);
        t -= 65536;
      }
      char *q = buf;
      for (int k = 0; k < 16; k++) {
        char *p = q += o[k] + l;
        if (*p < '7') *p += 3;
        else {
          *p-- -= 7;
          while (*p == '9') *p-- = '0';
          ++*p;
        }
      }
      j += 3;
    }
  }
}
\$\endgroup\$
12
  • \$\begingroup\$ Nicely done! The printed buffer reuse is something that intended to do as well, but didn't get around to due to the complexity of my code. Impressive work! \$\endgroup\$ – Isaac G. Nov 15 '20 at 14:46
  • 1
    \$\begingroup\$ Very nice. I tried parallelizing your and @IsaacG.'s solutions, but unfortunately two threads is already enough to cause enough contention on my 3900X to get less overall performance out of it than out of the single-threaded versions! Two threads pinned to the right cores seem to get it up to 8 GB/s for just a second or two, probably just the CPU boosting frequencies for a moment. Afterwards there is no benefit. \$\endgroup\$ – G. Sliepen Nov 15 '20 at 18:56
  • 1
    \$\begingroup\$ What CPU (model number and/or uarch and frequency it actually ran at), compiler version, and OS? Benchmark numbers are most useful when we know the test system. \$\endgroup\$ – Peter Cordes Nov 16 '20 at 18:41
  • 1
    \$\begingroup\$ @PeterCordes My rig? it's an AMD Ryzen 7 3700X 8-core @ 2.2-3.6GHz using GCC 9.3.1 on Fedora 31. \$\endgroup\$ – Neil Nov 16 '20 at 18:50
  • 1
    \$\begingroup\$ Consider using -O3 -march=native to let it take advantage of CPU features like AVX (32-byte vectors) if it ever wants to inline a memcpy or something. (The -mtune=znver2 implied by -march on your machine may help, too.) With memcpy size being runtime variable, it will just call the library function. so -fno-plt should reduce overhead for each call. Also -fno-pie -no-pie may make global arrays slightly more efficient (mov-immediate instead of RIP-relative LEA to put the address in a register, or t-&out[65536] could be a sub-immediate or maybe even LEA.) \$\endgroup\$ – Peter Cordes Nov 16 '20 at 20:10
14
\$\begingroup\$

I tweaked Neil's code a bit (so most credit goes to him) and managed to squeeze some more performance out of it; I also prepared it for unrolling more loops but ultimately I gave up (that's why the code is unreadable gobbledygook).

#include <stdio.h>
#include <string.h>
#include <unistd.h>

#define f(Z) {char*p=q+=Z+l;if(*p<'7')*p+=3;else{*p---=7;while(*p=='9')*p--='0';++*p;}}
#define v(N) {while(j<i){memcpy(t,buf,N);t+=n;if(t>=&out[65536]){char*u=out; \
           do{int w=write(1,u,&out[65536]-u);if(w>0)u+=w;}while(u<&out[65536 \
           ]);memcpy(out,out+65536,t-&out[65536]);t-=65536;}char*q=buf;f(4); \
           f(7);f(2);f(11);f(2);f(7);f(12);f(2);f(12);f(7);f(2);f(11);f(2);f \
           (7);f(12);f(2);j+=3;}}
char buf[256];
char out[65536 + 4096] = "1\n2\nFizz\n4\nBuzz\nFizz\n7\n8\nFizz\n";
int main(void) {
  char *t = out + 30;
  unsigned long long i = 1, j = 1;
  for (int l = 1; l < 20; l++) {
    int n=sprintf(buf, "Buzz\n%llu1\nFizz\n%llu3\n%llu4\nFizzBuzz\n%llu6\n%llu7\nFizz\n%llu9\nBuzz\nFizz\n%llu2\n%llu3\nFizz\nBuzz\n%llu6\nFizz\n%llu8\n%llu9\nFizzBuzz\n%llu1\n%llu2\nFizz\n%llu4\nBuzz\nFizz\n%llu7\n%llu8\nFizz\n", i, i, i, i, i, i, i + 1, i + 1, i + 1, i + 1, i + 1, i + 2, i + 2, i + 2, i + 2, i + 2);
    i*=10;
    v(n);
  }
  return 0;
}

On my PC, Neil's submission is ~5% slower. I also tried it on friend's Intel box and the tweaked version is faster.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Added to the scoreboard. This is the best one so far. You seem to also have made Neil's submission much more "stable" (less variance in the output rate). \$\endgroup\$ – Omer Tuchfeld Nov 15 '20 at 22:59
  • \$\begingroup\$ @IsaacG pointed out that my buf is actually too small and my program would crash if it ever got to the really high numbers. \$\endgroup\$ – Neil Nov 16 '20 at 22:32
  • \$\begingroup\$ @Neil Yeah, I noticed this too, but if I tried to enlargen it the performance gets a solid drop. So we're just hoping it works lol \$\endgroup\$ – Kamila Szewczyk Nov 17 '20 at 6:25
  • \$\begingroup\$ Huh, so it does, but I tried 416 and it seems to be OK, so... \$\endgroup\$ – Neil Nov 17 '20 at 10:09
  • \$\begingroup\$ i feel like the buffer is too big to fit in l1 cache, not that it affects anything... \$\endgroup\$ – ASCII-only Feb 9 at 6:41
4
\$\begingroup\$

Coded in rust- modern languages can be fast too. Build with cargo build --release* and run with ./target/release/fizz_buzz. The count goes up by 15 every iteration of the loop. The itoap crate is used to quickly write integers to the buffer. Adds 15 line chunks to an array unless there isn't enough space left in the buffer for a max-sized chunk, and when that happens it flushes the buffer to stdout.

main.rs:

use std::io::*;
use itoap::Integer;
const FIZZ:*const u8 = "Fizz\n".as_ptr();
const BUZZ:*const u8 = "Buzz\n".as_ptr();
const FIZZBUZZ:*const u8 = "FizzBuzz\n".as_ptr();
const BUF_SIZE:usize = 1024*256;
const BLOCK_SIZE:usize = 15 * i32::MAX_LEN;
/// buf.len() > count
macro_rules! itoap_write{
  ($buf:ident,$count:ident,$num:ident)=>{
    $count += itoap::write_to_ptr(
      $buf.get_unchecked_mut($count..).as_mut_ptr(),
      $num
    );
    $buf.as_mut_ptr().add($count).write(b'\n');
    $count += 1;
  }
}
///ptr must be valid, buf.len() > count, ptr.add(len) must not overflow buffer
macro_rules! str_write{
  ($buf:ident,$count:ident,$ptr:ident,$len:literal)=>{
    let ptr = $buf.get_unchecked_mut($count..).as_mut_ptr();
    ptr.copy_from_nonoverlapping($ptr,$len);
    $count += $len;
  }
}

fn main() -> Result<()>{
  let mut write = stdout();
  let mut count:usize = 0;
  let mut buf = [0u8;BUF_SIZE];
  let mut i:i32 = -1;
  loop{
    if &count + &BLOCK_SIZE > BUF_SIZE{
      unsafe{
        write.write_all(
          buf.get_unchecked(..count)
        )?;
      }
      count = 0;
    } 
    i += 2;
    unsafe{
      itoap_write!(buf,count,i);     
      i += 1;
      itoap_write!(buf,count,i);
      str_write!(buf,count,FIZZ,5);
      i += 2;
      itoap_write!(buf,count,i);
      str_write!(buf,count,BUZZ,5);
      str_write!(buf,count,FIZZ,5);
      i += 3;
      itoap_write!(buf,count,i);
      i += 1;
      itoap_write!(buf,count,i);
      str_write!(buf,count,FIZZ,5);
      str_write!(buf,count,BUZZ,5);
      i += 3;
      itoap_write!(buf,count,i);
      str_write!(buf,count,FIZZ,5);
      i += 2;
      itoap_write!(buf,count,i);
      i += 1;
      itoap_write!(buf,count,i);
      str_write!(buf,count,FIZZBUZZ,9);
    }
  }
}

Cargo.toml:

[package]
name = "fizz_buzz"
version = "0.1.0"
authors = ["aiden4"]
edition = "2018"

[dependencies]
itoap = "0.1"
[[bin]]
name = "fizz_buzz"
path = "main.rs"

[profile.release]
lto = "fat"

*requires cargo to be able to connect to the internet

\$\endgroup\$
3
\$\begingroup\$

My code works on Windows 10. It outputs 8-9 GiB/s when the CPU is cool enough.

I used the following ideas in my code:

  • Filling a buffer 256 KiB and sending it to output; for smaller buffer size the performance suffers; bigger buffer sometimes improves performance, but never by much.
  • For numbers which have the same number of digits, it works in chunks of 15 output lines. These chunks have identical length. While the size of the output buffer is big enough, it copies the previous chunk and adds 15 to the ASCII representation of all the numbers in it.
  • Near the end of the buffer and for first chunk, it calculates the output messages explicitly. Also, if numbers in the chunk have different length (e.g. 9999 and 10000).
  • It uses OpenMP to calculate 4 chunks simultaneously. I set NUM_THREADS to 4 (best on my computer, which has 8 logical cores); a larger setting might be better.

When I want to verify the output, I set check_file = 1 in code; if check_file = 0, it writes to NUL, which is the null output device on Windows.

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <inttypes.h>
#include <assert.h>
#include "windows.h"
#include "fileapi.h"
#include "process.h"

int size_15(int num_digits) // size of 15 messages, where numbers have a given number of digits
{
    return 8 * num_digits + 47;
}

int num_of_digits(int64_t counter) // number of digits
{
    int result = 1;
    if (counter >= 100000000)
    {
        counter /= 100000000;
        result += 8;
    }
    if (counter >= 10000)
    {
        counter /= 10000;
        result += 4;
    }
    if (counter >= 100)
    {
        counter /= 100;
        result += 2;
    }
    if (counter >= 10)
        return result + 1;
    else
        return result;
}

void print_num(char* buf, int64_t counter, int num_digits)
{
    for (int i = 0; i < num_digits; ++i)
    {
        buf[num_digits - 1 - i] = counter % 10 + '0';
        counter /= 10;
    }
}

void add_15_to_decimal_num(char* p, int num_digits)
{
    char digit = p[num_digits - 1] + 5;
    int c = (digit > '9');
    p[num_digits - 1] = (char)(digit - c * 10);
    c += 1;
    for (int i = 1; i < num_digits; ++i)
    {
        if (c == 0)
            break;
        digit = (char)(p[num_digits - 1 - i] + c);
        c = digit > '9';
        p[num_digits - 1 - i] = (char)(digit - c * 10);
    }
}

uint64_t fill_general(char* buf, int size, uint64_t counter, int* excess)
{
    char* p = buf;
    while (p < buf + size)
    {
        int fizz = counter % 3 == 0;
        int buzz = counter % 5 == 0;
        if (fizz && buzz)
        {
            memcpy(p, "FizzBuzz\n", 9);
            p += 9;
        }
        else if (fizz)
        {
            memcpy(p, "Fizz\n", 5);
            p += 5;
        }
        else if (buzz)
        {
            memcpy(p, "Buzz\n", 5);
            p += 5;
        }
        else
        {
            int num_digits = num_of_digits(counter);
            print_num(p, counter, num_digits);
            p[num_digits] = '\n';
            p += num_digits + 1;
        }
        ++counter;
    }
    *excess = (int)(p - (buf + size));
    return counter;
}

void fill15(char* buf, int64_t counter, int num_digits, int num_ofs[8])
{
    char* p = buf;
    int m15 = counter % 15;
    for (int i = m15; i < m15 + 15; ++i)
    {
        if (i % 15 == 0)
        {
            memcpy(p, "FizzBuzz\n", 9);
            p += 9;
        }
        else if (i % 3 == 0)
        {
            memcpy(p, "Fizz\n", 5);
            p += 5;
        }
        else if (i % 5 == 0)
        {
            memcpy(p, "Buzz\n", 5);
            p += 5;
        }
        else
        {
            *num_ofs++ = (int)(p - buf);
            print_num(p, counter + i - m15, num_digits);
            p += num_digits;
            *p++ = '\n';
        }
    }
}

// memcpy replacement; works only for sizes equal to 47 + 8 * n, for small n
void copy_47_8n(char* src, unsigned size)
{
    char* dst = src + size;

    memcpy(dst, src, 47);
    size -= 47;
    dst += 47;
    src += 47;

    if (size >= 128)
        exit(1);
    if (size >= 96)
        memcpy(dst + 64, src + 64, 32);
    if (size >= 64)
        memcpy(dst + 32, src + 32, 32);
    if (size >= 32)
        memcpy(dst + 0, src + 0, 32);
    dst += size / 32 * 32;
    src += size / 32 * 32;
    size %= 32;
    if (size >= 24)
        memcpy(dst + 16, src + 16, 8);
    if (size >= 16)
        memcpy(dst + 8, src + 8, 8);
    if (size >= 8)
        memcpy(dst + 0, src + 0, 8);
}

#define NUM_THREADS 4

uint64_t fill_fast(char* buf, int size, uint64_t counter, int* excess)
{
    const int num_digits = num_of_digits(counter);
    const int chunk_size = 8 * num_digits + 47;
    const int num_iter = size / chunk_size;
    int thread;
#pragma omp parallel for
    for (thread = 0; thread < NUM_THREADS; ++thread)
    {
        const int begin_iter = num_iter * thread / NUM_THREADS;
        const int thread_num_iter = num_iter * (thread + 1) / NUM_THREADS - begin_iter;
        char* output = buf + begin_iter * chunk_size;
        int num_ofs[8];
        fill15(output, counter + begin_iter, num_digits, num_ofs);
        for (int iter = 1; iter < thread_num_iter; ++iter)
        {
            copy_47_8n(output, chunk_size);
            for (int i = 0; i < 8; ++i)
                add_15_to_decimal_num(output + chunk_size + num_ofs[i], num_digits);
            output += chunk_size;
        }
    }

    buf += num_iter * chunk_size;
    size -= num_iter * chunk_size;
    counter += num_iter * 15;

    return fill_general(buf, size, counter, excess);
}

uint64_t fill(char* buf, int size, uint64_t counter, int* excess)
{
    int num_digits = num_of_digits(counter);
    int64_t max_next_counter = counter + size / (8 * num_digits + 47) * 15 + 15;
    int max_next_num_digits = num_of_digits(max_next_counter);
    if (num_digits == max_next_num_digits)
        return fill_fast(buf, size, counter, excess);
    else
        return fill_general(buf, size, counter, excess);
}

void file_io(void)
{
    int check_file = 0;
    HANDLE f = CreateFileA(check_file ? "my.txt" : "NUL", GENERIC_WRITE, FILE_SHARE_READ, 0, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, 0);
    DWORD e = GetLastError();
    LARGE_INTEGER frequency;
    QueryPerformanceFrequency(&frequency);

    DWORD read;
    int bufsize = 1 << 18;
    long long statsize = 1ll << 34;
    char* buf = malloc(bufsize);
    uint64_t counter = 1;
    int excess = 0;
    while (counter < 9999999900000000)
    {
        LARGE_INTEGER start, stop;
        QueryPerformanceCounter(&start);
        for (int i = 0; i < statsize / bufsize; ++i)
        {
            memcpy(buf, buf + bufsize, excess);
            counter = fill(buf + excess, bufsize - excess, counter, &excess);
            e = WriteFile(f, buf, bufsize, &read, 0);
            if (check_file)
                FlushFileBuffers(f);
            if (e == 0 || (int)read != bufsize)
            {
                e = GetLastError();
                exit(1);
            }
        }
        QueryPerformanceCounter(&stop);
        double time = (double)(stop.QuadPart - start.QuadPart) / frequency.QuadPart;
        printf("Throughput (GB/s): %f\n", statsize / (1 << 30) / time);
    }

    CloseHandle(f);
    exit(0);
}

int main()
{
    file_io();
}
\$\endgroup\$
2
\$\begingroup\$

My solution maintains a buffer with a batch of lines (6000 lines worked best on my system), and updates all the numbers in the buffer in a parallelisable loop. We use an auxiliary array nl[] to keep track of where each newline lies, so we have random access to all the numbers.

The addition is all in-place decimal character-by-character arithmetic, with no arithmetic division after the buffer is initialised (I could have created the buffer without division, too, but opted for shorter, readable code!). Every so often, when the number of digits rolls over, we have to stop and re-position all the numbers within the buffer (that's what the shuffle counter is for), and update the corresponding entries in nl[]; this happens more and more infrequently as we proceed.

I compiled using gcc -std=gnu17 -Wall -Wextra -fopenmp -O3 -march=native, and ran with OMP_NUM_THREADS=3 set in the environment (a different number of threads may be optimal on another host).

#include <stdatomic.h>
#include <stdio.h>              /* sprintf */
#include <string.h>             /* memset */
#include <unistd.h>

/* This is the single tunable you need to adjust for your platform */
#define chunk 6000 /* must be multiple of 3*5, with only one nonzero digit */
/* i.e. 3, 6 or 9 times an exact power of ten */

/* Select a number of digits to use.  If we produce one billion numbers
   per second, then we'll finish all the 18-digit numbers in just 30
   years.  24 digits should suffice until next geological epoch, at least. */
#define numlen 25               /* 24 decimal digits plus newline */

#define STR_(x) #x
#define STR(x) STR_(x)
#define chunk_str STR(chunk)

#define unlikely(e) __builtin_expect((e), 0)

char format[chunk * numlen];
char *nl[chunk+1];

int main()
{
    /* Create the format string. */
    /* We do this twice, as the numbers written first time round are
       too short for the addition. */
    for (int j = 0, n = 1;  j < 2;  ++j)
    {
        nl[0] = format;
        char *p = format;
        for (int i = 0;  i <= chunk;  ++i, ++n) {
            if ((n % 15) == 0) {
                p += sprintf(p, "FizzBuzz\n");
            } else if ((n % 5) == 0) {
                p += sprintf(p, "Buzz\n");
            } else if ((n % 3) == 0) {
                p += sprintf(p, "Fizz\n");
            } else {
                p += sprintf(p, "%d\n", n);
            }
            nl[i] = p;
        }
        write(1, format, nl[chunk] - format);
    }

    atomic_int shuffle = 0;
    for (;;) {
#pragma omp parallel for schedule(static)
        for (int i = 0;  i < chunk;  ++i) {
            if (nl[i+1][-2] == 'z') {
                /* fizz and/or buzz - not a number */
                continue;
            }
            /* else add 'chunk' to the number */
            static const int units_offset = sizeof chunk_str;
            static const int digit = chunk_str[0] - '0';
            char *p = nl[i+1] - units_offset;
            *p += digit;
            while (*p > '9') {
                *p-- -= 10;
                ++*p;
            }
            if (unlikely(p < nl[i])) {
                /* digit rollover */
                ++shuffle;
            }
        }
        if (unlikely(shuffle)) {
            /* add a leading one to each overflowing number */
            char **nlp = nl + chunk;
            char *p = *nlp;
            char *dest = p + shuffle;
            while (p < dest) {
                if (*p == '\n') {
                    *nlp-- = dest + 1;
                } else if (*p == '\n'+1) {
                    --*p;
                    *dest-- = '1';
                    *nlp-- = dest + 1;
                }
                *dest-- = *p--;
            }
            shuffle = 0;
        }
        write(1, format, nl[chunk] - format);
    }
}
\$\endgroup\$
7
  • \$\begingroup\$ Wouldn't memcpy(p,"Fizz\n",6); p+=5 be faster than sprintf? \$\endgroup\$ – EasyasPi Jan 19 at 22:05
  • 1
    \$\begingroup\$ Optimal with OMP_NUM_THREADS=1 🤔. @EasyasPi tried that, didn't make a noticeable difference \$\endgroup\$ – Omer Tuchfeld Jan 19 at 22:22
  • \$\begingroup\$ @EasyasPi, ITYM memcpy(p,"Fizz\n",5); to avoid pointlessly writing the null character each time? memcpy/sprintf tuning makes no measurable difference, as that's only the setup, outside the main loop. sprint() makes for more maintainable code. (I'm new to programming for all-out speed; in my day job that comes in third, after robustness and maintainability) \$\endgroup\$ – Toby Speight Jan 20 at 7:24
  • \$\begingroup\$ @Omer: yes, the poor parallelisation was a disappointment. I tried some other parallelisations, too (separate array of formatted numbers, and putting the serialisation and writing into its own thread). If I'm to get any real benefit, I might have to go low-level and hand-craft the threads and their synchronisation (probably switch to C++ for that). \$\endgroup\$ – Toby Speight Jan 20 at 7:31
  • \$\begingroup\$ I think I manage slightly better if I have atomic_int shuffle instead of the reduction. (time passes...) Yes, and I've updated to code that actually works faster in parallel, at last! \$\endgroup\$ – Toby Speight Jan 20 at 7:39
0
\$\begingroup\$

A C++ program for Linux. I use the same method of arithmetic as in my C answer, but here I create a team of threads by hand rather than using OpenMP.

We divide the problem into ranges of numbers, so that we don't have to touch the low-order digits each iteration.

The workers are arranged in a circular chain, and each is responsible for a subrange. We do all our addition while other threads are writing, then take a turn at writing. In order to write an exact number of pages with each write, there's generally one write that straddles two workers, so we combine writes using writev(), temporarily blocking the other worker from beginning its arithmetic. The timing diagram looks like this:

    +--------------------------------------------+
    |                                            |
    |   wait                                     |
------->                                         |
    |      write (end of prev, start of this)    |          +--------------------------------------------+
<-------                                         |          |                                            |
    |      write (just this one)                 |          |   wait                                     |
    |                                      -------------------->                                         |
    |                                  wait      |          |      write (end of prev, start of this)    |
    |                                      <--------------------                                         |
    |      update each number                    |          |      write (just this one)                 |
    |                                            |          |                                      ------+----->
    +--------------------------------------------+          |                                  wait      |
                                                            |                                      <------------
                                                            |      update each number                    |
                                                            |                                            |
                                                            +--------------------------------------------+

On my workstation (8 thread Ivybridge), I measured at around 90% the throughput of cat /dev/zero, or about ¾ that of dd if=/dev/zero bs=64K.

#include <cassert>
#include <condition_variable>
#include <iostream>
#include <memory>
#include <mutex>
#include <thread>
#include <vector>

#include <unistd.h>
#include <sys/sysinfo.h>
#include <sys/uio.h>

// Select a number of decimal digits to use.  If we produce one billion
// numbers per second, then we'll finish all the 18-digit numbers in
// just 30 years.  24 digits should suffice until the next geological
// epoch, at least.
static constexpr int numlen = 25; // 24 digits plus newline

static constexpr int write_size = 0x10000; // this is fastest on my system

static_assert('0' - '\n' > 1, "Character coding incompatible with the arithmetic");

#define unlikely(e) __builtin_expect((e), 0)


struct worker
{
    // Storage for the character string we maintain
    std::string lines{""};
    // Iterators to each newline in 'lines'
    std::vector<std::string::iterator> nl{};

    int units_offset{};         // significant figures in the step
    char digit{};               // the single non-zero digit of step

    // We coordinate with the next and previous threads in the ring.
    // The iovec is used for writing a block of lines that straddles
    // the previous thread and this one.
    std::mutex mutex{};
    std::condition_variable cv{};
    struct iovec iov[2] = { { 0, 0 }, { 0, 0 } };
    worker *next{};

    // The functions
    worker(std::size_t first, std::size_t count, std::size_t step);
    worker(const worker&) = delete;
    worker& operator=(const worker&) = delete;
    void loop();
};


static constexpr auto buf_len(std::size_t digits, std::size_t count)
{
    // each group of 15 lines has 8 numbers and 39 chars of Fizz and Buzz
    return (8 * digits + 39) * count / 15;
}

static constexpr std::size_t optimal_step(long thread_count)
{
    // We need each thread to produce at least write_size each iteration
    for (std::size_t tens = 1000;  tens < 10'000'000;  tens *= 10) {
        auto const digits = std::snprintf(0, 0, "%zu", tens);
        for (std::size_t digit = 3;  digit < 10;  digit += 3) {
            if (buf_len(digits, digit * tens) / thread_count > write_size) {
                return digit * tens;
            }
        }
    }
    return 9'000'000; // fallback (perhaps we should limit thread count?)
}

int main()
{
    // How many threads will we have?
    auto const nprocs = get_nprocs();
    auto const step = optimal_step(nprocs);

    // Write output the slow way, until we have enough digits for the
    // format strings.
    auto n = 1;
    const auto step_len = std::to_string(step).size();
    // Finish the loop just before a FizzBuzz, so that the lines buffer
    // doesn't start with a number (we need a newline preceding for it
    // to overflow correctly).
    for (;  std::to_string(n).size() <= step_len;  ++n) {
        if ((n % 15) == 0) {
            std::cout << "FizzBuzz\n";
        } else if ((n % 5) == 0) {
            std::cout << "Buzz\n";
        } else if ((n % 3) == 0) {
            std::cout << "Fizz\n";
        } else {
            std::cout << n << '\n';
        }
    }
    std::cout.flush();          // use Unix write() from here on

    // create the workers
    auto workers = std::vector<std::unique_ptr<worker>>{};
    workers.reserve(nprocs);
    for (int i = 0;  i < nprocs;  ++i) {
        auto const a = i * step / nprocs;
        auto const z = (i+1) * step / nprocs;
        workers.emplace_back(std::make_unique<worker>(n + a, z - a, step));
    }
    // and connect them in a loop
    workers.back()->next = workers.front().get();
    for (int i = 1;  i < nprocs;  ++i) {
        workers[i-1]->next = workers[i].get();
    }

    // a thread for each worker
    auto threads = std::vector<std::unique_ptr<std::thread>>{};
    threads.reserve(nprocs);
    auto const loop = [](worker *w) { w->loop(); };
    for (auto const& w: workers) {
        threads.emplace_back(std::make_unique<std::thread>(loop, w.get()));
    }

    // start them writing
    auto &first = workers.front();
    {
        std::unique_lock lock{first->mutex};
        first->iov[0] = { &first->lines.front(), 0 };
    }
    first->cv.notify_one();

    threads.front()->join();
}

worker::worker(std::size_t first, std::size_t count, std::size_t step)
{
    auto s = std::to_string(step);
    units_offset = s.size() + 1;
    digit = s.front() - '0';

    lines.reserve(buf_len(numlen, count) + 1);
    nl.reserve(count);
    assert(lines.capacity() >= write_size);

    for (auto n = first;  n < first + count;  ++n) {
        if ((n % 15) == 0) {
            lines += "FizzBuzz\n";
        } else if ((n % 5) == 0) {
            lines += "Buzz\n";
        } else if ((n % 3) == 0) {
            lines += "Fizz\n";
        } else {
            lines += std::to_string(n) + '\n';
        }
        nl.push_back(lines.end());
    }
    assert(lines.size() >= write_size);

    // Second half of a straddle write is always from the beginning of our buffer.
    iov[1].iov_base = &lines.front();
}

void worker::loop()
{
    assert(next);
    for (;;) {
        {
            // We can write when the previous thread passes its buffer offcut.
            std::unique_lock lock{mutex};
            cv.wait(lock, [this]{ return iov[0].iov_base; });

            iov[1].iov_len = write_size - iov[0].iov_len;
            assert(iov[1].iov_len < lines.size());
            writev(1, iov, 2);
            // Tell the previous thread that we've finished with its buffer.
            iov[0].iov_base = 0;
        }
        cv.notify_one();

        auto p = lines.begin() + iov[1].iov_len;
        while (unlikely(p + write_size < lines.end())) {
            ::write(1, &*p, write_size);
            p += write_size;
        }

        {
            // Tell the next thread that we have leftover data for it to write.
            std::unique_lock lock{next->mutex};
            next->iov[0] = { &*p, static_cast<std::size_t>(lines.end() - p) };
        }
        next->cv.notify_one();

        {
            // Now wait until next worker has written, and released buffer back to us.
            std::unique_lock lock{next->mutex};
            next->cv.wait(lock, [this]{ return !next->iov[0].iov_base; });
        }


        // Update the numbers in the buffer.
        auto rollover = 0u;
        for (auto const& i: nl) {
            if (i[-2] == 'z') {
                // fizz and/or buzz - not a number
                continue;
            }
            // else add 'step' to the number
            auto p = i - units_offset;
            *p += digit;
            while (*p > '9') {
                *p-- -= 10;
                ++*p;
            }
            if (unlikely(*p == '\n'+1)) {
                // digit rollover
                ++rollover;
            }
        }
        if (unlikely(rollover)) {
            // Add a leading one to each overflowing number.
            auto nlp = nl.end();
            auto p = lines.end();
            assert(lines.size() + rollover < lines.capacity());
            lines.resize(lines.size() + rollover);
            auto dest = lines.end();
            while (--p < --dest) {
                if (*p == '\n'+1) {
                    --*p;
                    *dest-- = '1';
                }
                if (*p == '\n') {
                    *nlp-- = dest + 1;
                }
                *dest = *p;
            }
        }
    }
}

Compile using g++-10 -std=c++2a -Wall -Wextra -Weffc++ -DNDEBUG -O3 -march=native -fno-exceptions -lpthread. No special arguments or environment are needed when running.

\$\endgroup\$
3
  • \$\begingroup\$ Neil + Kamila generates fizzbuzz About 50% faster than the kernel generates 0's on my machine (9 vs 6 gib/s, approx), so I wouldn't consider /dev/zero an upper limit. An interesting reference point, maybe. In any case, tried running your new code - optimal when I fake nproc to be 4 - but it just yields results as fast as your previous submission with only 1 core. \$\endgroup\$ – Omer Tuchfeld Jan 22 at 16:42
  • \$\begingroup\$ That's a shame - unmodified, it runs about 50% faster than my other one here. I really expected to come out ahead on your system too. \$\endgroup\$ – Toby Speight Jan 22 at 20:11
  • 1
    \$\begingroup\$ I've now spent far longer than I should on this. Time to bow out gracefully. \$\endgroup\$ – Toby Speight Jan 22 at 20:12

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.