Item — HN Reader

I see your points; maybe I need to work on the storytelling in posing the puzzle. I do stand by the principle that avoiding branch mispredicts is worthwhile if you can replace the branch with 1 or 2 logic/arith C operations. In any case, the point of the puzzle is how to get a not-quite-trivial result from extremely efficient sequence of pure logic/arith operations.

1 comments

  #define FIZZ 1
  #define BUZZ 2


  struct {
    uint8_t flags;
    uint8_t next;
  } static const nfo[] = {
    {FIZZ+BUZZ,1},
    {0,2},
    {0,3},
    {FIZZ,4},
    {0,5},
    {BUZZ,6},
    {FIZZ,7},
    {0,8},
    {0,9},
    {FIZZ,10},
    {BUZZ,11},
    {0,12},
    {FIZZ,13},
    {0,14},
    {0,0}
  } __attribute__((align(YOUR_L1D_LINE_SIZE)));
  static const char* strs[] = {
    [0] = "%u\n",
    [FIZZ] = "fizz\n",
    [BUZZ] = "buzz\n",
    [FIZZ+BUZZ] = "fizzbuzz\n"
  };

  void fizzbuzz(uint32_t upTo)
  {
    uint32_t i, state;

    for(i = state = 0; i < upTo; i++) {
      printf(strs[nfo[state].flags], i);
      state = nfo[state].next;
    }
  }

No divisibility tests at all. No branches besides loop and printf call. Space can be saved by using a bitfield, but masking it will add speed costs.

  .data: 0
  .rodata: 30 + 4 * sizeof(void*) + strings
  .text: depending on arch, but not much

Assuming call to printf has no cost and the caches are hot, a modern x86 cpu could execute one iteration of this loop in 1 cycle (issuing 2 loads, one add, one cmp, one branch)

I have no compiler and am typing this on a phone so please forgive typos, if any

It's pretty ridiculous to pretend that printf is free. The crux of the matter is to concat string constants and string-representations of integers into a buffer. "buzz\n" is only 5 bytes, so you can store it in a uint64_t.

Also, no, a typical x86 CPU would take about 4 or 5 cycles per iteration even if printf (and the cost of moving its arguments into the right register) was free.

state = nfo[state].next is a pointer-chasing loop-carried dependency chain, so you will bottleneck on L1D load-use latency. (For Skylake, 5 cycles for a complex addressing mode: http://www.7-cpu.com/cpu/Skylake.html).

If out-of-order execution could overlap many of these loops then the throughput could be close to 1 iter per clock.

@raphlinus: well, if you can get it better than one iteration per cycle, I would love to see how (truly)

I see your point regarding pure cycle counting, but as I posed the puzzle it's still open :)

Don't want to be _that_ guy but your loop starts with 0 instead of 1