4 ms·

So what we're seeing is that a specialized handcoded assembler version is 10x faster than a generic C version? If so that makes me a bit sad, because in the mo

So what we're seeing is that a specialized handcoded assembler version is 10x faster than a generic C version? If so that makes me a bit sad, because in the modern day we'd want to assume that compilers have gotten a little better at optimization.

jiggawatts 5y ago
Read the assembly. Seriously. It's eye-popping. It's eldritch madness. It's black wizardry. The blackest of the black arts. The "fastest FizzBuzz" implementation isn't merely "fast". It's faster than memcpy()!!! Expecting compilers to outperform this tour-de-force is asking a tad too much from compiler writers...
- btilly 5y ago
  From the article, "The application produced 64 bytes of FizzBuzz for every 4 CPU clock cycles. The author states the ultimate bottleneck of performance is based on the throughput of the CPU's L2 cache." For comparison, that time is on par with integer multiplication.
- noduerme 5y ago
  It's actually really nice the way the author commented it. It's a cool insight into their mental process. I've never coded in Assembly and I can't normally follow it. But reading these comments I can understand how the author is surgically managing registers and operating off a complete mental map of what's there, the same way a coder would with, say, a very large database they have a complete mental model of. All I mean is that I appreciate the author making their thought process accessible. It certainly looks like virtuosity, but I'm not competent enough to judge.
bonzini 5y ago
> assume that compilers have gotten a little better at optimization Again: you're comparing the performance of different algorithms. A compiler won't turn bubblesort into quicksort.
- tialaramex 5y ago
  I mean, this is importantly true as a generalisation, but, it's worth knowing modern compilers know about idioms. If you show a modern compiler the typical idiomatic blob of code for counting the set bits in a word in a language like C, the compiler goes "Oh, popcount I know this" and when targeting modern CPUs it emits a single instruction, the popcount instruction for that CPU. In APL idiom recognition was essential to making even a halfway decent compiler. It's easy, and idiomatic, to write APL which would be tremendously wasteful if implemented naively, while recognising common idioms could remove lots of that waste without needing the level of sophistication modern compilers have during optimisation. Because the compiler knows about idioms you should not try to optimise your programs by writing non-idiomatic code until you've determined you have a performance problem and the non-idiomatic code is identified as a way to fix it. Otherwise it may be that the compiler improves and now your code is not only harder to maintain it also has worse performance than the idiomatic solution.
- rowanG077 5y ago
  Not yet. But I have no doubt in my mind that a once we have smarter then human AI there will be compilers that absolutely can turn bubblesort into quicksort.
  - marginalia_nu 5y ago
    Seems fairly unlikely. The best sorting algorithm is a function of the data. The compiler can't know this. There are pathological data sets where quicksort is O(n^2). For small n, quick sort is also a bad choice. The programmer can understand these domain characteristics but the compiler certainly can't. If code isn't running qsort(), this could be a mistake, but may also be an optimization.
    - gpderetta 5y ago
      PGO is a thing for this reason. (But no, I'm not expecting AI driven compilers anytime soon)
    - rowanG077 5y ago
nojs 5y ago
The assembly is ridiculous. Random section: // The bytecode generation loop is unrolled to depth 30, allowing the // units digits to be hardcoded. The tens digit is stored in %al, and // incremented every ten lines of output. The parity of the hundreds // digit is stored in %ymm2: one half predicts the hundreds digit to // be even, the other to be odd, and the halves are swapped every time // the tens digit carries (ensuring the predictions are correct).
- entropicdrifter 5y ago
  Controlled CPU predictions, wow. That's a level of performance I've never even contemplated
  - bonzini 5y ago
    It's not CPU predictions, it means that it computes in parallel one result that is correct and one that is wrong, and picks the right one by swapping the two halves every now and then.

jiggawatts 5y ago

Read the assembly. Seriously. It's eye-popping. It's eldritch madness. It's black wizardry. The blackest of the black arts. The "fastest FizzBuzz" implementation isn't merely "fast". It's faster than memcpy()!!! Expecting compilers to outperform this tour-de-force is asking a tad too much from compiler writers...

btilly 5y ago
From the article, "The application produced 64 bytes of FizzBuzz for every 4 CPU clock cycles. The author states the ultimate bottleneck of performance is based on the throughput of the CPU's L2 cache." For comparison, that time is on par with integer multiplication.
noduerme 5y ago
It's actually really nice the way the author commented it. It's a cool insight into their mental process. I've never coded in Assembly and I can't normally follow it. But reading these comments I can understand how the author is surgically managing registers and operating off a complete mental map of what's there, the same way a coder would with, say, a very large database they have a complete mental model of. All I mean is that I appreciate the author making their thought process accessible. It certainly looks like virtuosity, but I'm not competent enough to judge.

bonzini 5y ago

> assume that compilers have gotten a little better at optimization Again: you're comparing the performance of different algorithms. A compiler won't turn bubblesort into quicksort.

tialaramex 5y ago
I mean, this is importantly true as a generalisation, but, it's worth knowing modern compilers know about idioms. If you show a modern compiler the typical idiomatic blob of code for counting the set bits in a word in a language like C, the compiler goes "Oh, popcount I know this" and when targeting modern CPUs it emits a single instruction, the popcount instruction for that CPU. In APL idiom recognition was essential to making even a halfway decent compiler. It's easy, and idiomatic, to write APL which would be tremendously wasteful if implemented naively, while recognising common idioms could remove lots of that waste without needing the level of sophistication modern compilers have during optimisation. Because the compiler knows about idioms you should not try to optimise your programs by writing non-idiomatic code until you've determined you have a performance problem and the non-idiomatic code is identified as a way to fix it. Otherwise it may be that the compiler improves and now your code is not only harder to maintain it also has worse performance than the idiomatic solution.
rowanG077 5y ago
Not yet. But I have no doubt in my mind that a once we have smarter then human AI there will be compilers that absolutely can turn bubblesort into quicksort.
- marginalia_nu 5y ago
  Seems fairly unlikely. The best sorting algorithm is a function of the data. The compiler can't know this. There are pathological data sets where quicksort is O(n^2). For small n, quick sort is also a bad choice. The programmer can understand these domain characteristics but the compiler certainly can't. If code isn't running qsort(), this could be a mistake, but may also be an optimization.
  - gpderetta 5y ago
    PGO is a thing for this reason. (But no, I'm not expecting AI driven compilers anytime soon)
  - rowanG077 5y ago

nojs 5y ago

The assembly is ridiculous. Random section: // The bytecode generation loop is unrolled to depth 30, allowing the // units digits to be hardcoded. The tens digit is stored in %al, and // incremented every ten lines of output. The parity of the hundreds // digit is stored in %ymm2: one half predicts the hundreds digit to // be even, the other to be odd, and the halves are swapped every time // the tens digit carries (ensuring the predictions are correct).

entropicdrifter 5y ago
Controlled CPU predictions, wow. That's a level of performance I've never even contemplated
- bonzini 5y ago
  It's not CPU predictions, it means that it computes in parallel one result that is correct and one that is wrong, and picks the right one by swapping the two halves every now and then.