3 ms·

It's not just knowing exactly what the assembler is doing, but also what the kernel is doing (but maybe you also meant this). "This implementation only supports

by bartvk 5y ago

It's not just knowing exactly what the assembler is doing, but also what the kernel is doing (but maybe you also meant this). "This implementation only supports Linux", and then continues about the use of a bunch of system calls: * "asks the Kernel to defragment the physical memory it's using via the madvise system call" * "use 2 MB of RAM each even though neither need 2 MB. This keeps the page table orderly" * "Most competing FizzBuzz implementations call the write system call which can lead to data needing to be copied between user and Kernel space. So vmsplice is used instead." And then the most fascinating bit: "The CPU's L2 cache is split into two halves, one for calculating the output of FizzBuzz, the other storing the result of the last calculation batch. This means there is no need to use any slower L3 memory operations." "Slower L3 memory operations", I've not read that sentence before :D

MayeulC 5y ago
> the most fascinating bit It is really fascinating, but I disagree a bit with your pick :) To me, the most fascinating part is using a bytecode interpreter. It makes perfect sense, it's basically optimizing the code size to fits in the cache. It's also a bit like defining a whole new instruction set dedicated and optimized for Fizzbuzz! I think the approach was a bit similar to a VLIW https://en.wikipedia.org/wiki/Very_long_instruction_word https://en.wikipedia.org/wiki/Very_long_instruction_word where a single 32 bits word is loaded and interpreted at a time. Most of the state of the Fizzbuzz program is encoded in this bytecode. > "Slower L3 memory operations", I've not read that sentence before You hear it all the time when trying to optimize for speed in a hot loop. Keep your data structures in a way that fits in the cache. Align your data with cache boundaries. Code needs to be small too, hence the bytecode approach. This is also the reason why you can't unroll loops too much. If your implementation does not need to fetch (or write) data from(/to) higher levels of the memory hierarchy, you'll see tremendous gains. There's even this bit in the original source: "while waiting for writes to go through to the L2 cache" :) There are a few more very interesting hacks, such as the "high-decimal" format that skips the "need to do binary/decimal conversions."

by bartvk 5y ago

MayeulC 5y ago

> the most fascinating bit It is really fascinating, but I disagree a bit with your pick :) To me, the most fascinating part is using a bytecode interpreter. It makes perfect sense, it's basically optimizing the code size to fits in the cache. It's also a bit like defining a whole new instruction set dedicated and optimized for Fizzbuzz! I think the approach was a bit similar to a VLIW https://en.wikipedia.org/wiki/Very_long_instruction_word https://en.wikipedia.org/wiki/Very_long_instruction_word where a single 32 bits word is loaded and interpreted at a time. Most of the state of the Fizzbuzz program is encoded in this bytecode. > "Slower L3 memory operations", I've not read that sentence before You hear it all the time when trying to optimize for speed in a hot loop. Keep your data structures in a way that fits in the cache. Align your data with cache boundaries. Code needs to be small too, hence the bytecode approach. This is also the reason why you can't unroll loops too much. If your implementation does not need to fetch (or write) data from(/to) higher levels of the memory hierarchy, you'll see tremendous gains. There's even this bit in the original source: "while waiting for writes to go through to the L2 cache" :) There are a few more very interesting hacks, such as the "high-decimal" format that skips the "need to do binary/decimal conversions."