4 ms·

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

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.

dmitrygr 9y ago
#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
- raphlinus 9y ago
  I see your point regarding pure cycle counting, but as I posed the puzzle it's still open :)
- dmitrygr 9y ago
  @raphlinus: well, if you can get it better than one iteration per cycle, I would love to see how (truly)
- pcordes 9y ago
  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 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.
- beeswax 9y ago
  Don't want to be _that_ guy but your loop starts with 0 instead of 1

dmitrygr 9y ago

#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

raphlinus 9y ago
I see your point regarding pure cycle counting, but as I posed the puzzle it's still open :)
dmitrygr 9y ago
@raphlinus: well, if you can get it better than one iteration per cycle, I would love to see how (truly)
pcordes 9y ago
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 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.
beeswax 9y ago
Don't want to be _that_ guy but your loop starts with 0 instead of 1