4 ms·
#define FIZZ 1 #define BUZZ 2 static const uint8_t divs[] = {FIZZ+BUZZ,0,0,FIZZ,0,BUZZ,FIZZ,0,0,FIZZ,BUZZ,0,FIZZ,0,0}; static const char* strs[] = {
by dmitrygr 9y ago
#define FIZZ 1
#define BUZZ 2
static const uint8_t divs[] =
{FIZZ+BUZZ,0,0,FIZZ,0,BUZZ,FIZZ,0,0,FIZZ,BUZZ,0,FIZZ,0,0};
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[divs[state]], i);
if(++state == sizeof(divs) / sizeof(*divs))
state = 0;
}
No divisibility tests at all
One level of arrays may be skipped at cost of extra .rodata size (store string pointers directly in divs). But in a modern cpu cost of the extra load is small
- raphlinus 9y agoI should have stated extra constraints; you're not allowed to use either additional memory (memory accesses are slow) or an if statement to update your state (branch mispredicts are slow). Yes, these are arbitrary (and I know the total time would be dominated by the cost of printf), but the point is to shave nanoseconds. Also, you've still got the duplication of strings.
- dmitrygr 9y agoMemory accesses are not slow on modern CPUs. With speculative loads and large L1d caches these loads won't stall even a single cycle String duplication helps speed here. Branch misprediction will happen once every fifteen times worst case. Plus, if shaving nanoseconds, printing is a bad idea
- raphlinus 9y agoI 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 agoI 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 agoIt'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.