7 ms·

FizzBuzz has many properties that make it very suitable for these kinds of optimizations that might not be applicable to general purpose code: + extremely smal

FizzBuzz has many properties that make it very suitable for these kinds of optimizations that might not be applicable to general purpose code: + extremely small working set (a few registers worth of state) + extremely predictable branching behavior + no I/O These properties however don't diminish the achievement of leveraging AVX-2 (or any vectorization) for a problem that doesn't immediately jump out as SIMD.

deleted 5y ago
[deleted]
cogman10 5y ago
> no I/O The problem description is writing out bytes which is probably some of the more expensive part of this. In fact, if you read the winning solution description, IO is the primary problem here. > doesn't immediately jump out as SIMD. IDK that I agree with this assessment. Very naively, I see no reason you'd not take the 512 SIMD registers and split them into 16 32 bit lanes. From there, it's a relatively simple matter of using 2 registers for the divisors, pulling out the results, and transforming them into the text to print. In other words, you be chunking this up into 16 iterations per loop. (vs 1 with the naive assembly). This is the sort of thing that jumps out as easily vectorizable. Now, the fastest answer very obviously does not take this approach because I'm certain they realized the same thing, that the difficult part here isn't the actual division, but instead pumping out the correct text at the highest speed possible. If you read through it, most of the code is dedicated to converting binary numbers into ascii :D
- loser777 5y ago
  Maybe I should be more clear; no data needs to be fetched from disk/network, and the "writes" don't need to go past memory. As for the second point, you might have a different definition of "naive" and "relatively simple" as my brain has rotted too much from only thinking about SIMD for numerical computation. While determining divisibility be relatively clear, it wasn't clear how the printing would be easily vectorizable as the output-per-number is variable in length.
- dvt 5y ago
  > transforming them into the text to print I think this nails it. Vectorizing the math problem is "easy" (send batches of numbers to cores, do the division) but then you have to re-order it for printing (not to mention actually print it), so paradoxically, it probably makes more sense for the program to be single-threaded.
  - yuliyp 5y ago
    You don't even need to do division. There are only 3 patterns that repeat for every set of 10 numbers. You just need to track which one you're on.
    - hasmanean 5y ago
      Yes the patterns repeat every 15 integers. So you only need to do one division operation, get the index modulo-15. I was bored once at work and figured out a way to compute this without doing much arithmetic. It only requires 1 modulo operation. for (int i=1; i<100;i++) { // make a bit vector with a 1 in ith bit, modulo 15. unsigned int i_as_bitvector = 1 << (i % 15); // Check it against the valid positions for FizzBuzz // 0ctal 011111 is binary 1001001001001 // Octal 02041 is binary 10000100001 printf("%d ", i); if (i_as_bitvector & 011111 ) printf("Fizz"); if (i_as_bitvector & 02041 ) printf("Buzz"); printf("\n"); } I also have a version which has NO magic constants anywhere in the program, except 3 and 5. I'll post it if someone is interested.
    - bonzini 5y ago
      Also, after printing 1 to 9, you have a single pattern of 30 numbers that repeats exactly 3 times from 10 to 99, then 30 times from 100 to 999, then 300 times from 1000 to 9999, and so on. That lets you extract lots of code from the loop and run it roughly once every 10^n numbers.
    - dvt 5y ago
      > There are only 3 patterns that repeat for every set of 10 numbers Ah, yep, good point!
- boibombeiro 5y ago
  Using AVX 512 is not suitable for programs that takes very small time to run. There is a penalty in the ms range to "warm up" the CPU (it is more a cool down, actually). As OP stated, the limiting factor is on the memory access. That's why he kept saying 64B every four cycles. But OP likely didn't use because most CPU lacks support for AVX512. The new Intel CPU introduced many changes for the frontend. This will likely improve the speed. There might also be possible to try make the CPU operate at higher clockspeed. Code looks a bit long. Not sure if the unrolling actually helps. EDIT: Just look at the agner microarchitecture doc. Ice Lake and Tiger Lake can do 64 bytes/cycle. In theory, it can run 4x faster (on bare metal, maybe).
yumraj 5y ago
I think you're missing the point. The issue is that with the advent of higher level languages, starting from Java, Javascript and on to Python and so on, most people have forgotten or have never learnt the skills to optimize code. I'll argue that, as a percent, the number of people who can write proper multi-threaded code has only diminished over the years. And we see the result, despite the massive increase in computing power, software in general has become slower and bloated.
- foota 5y ago
  I think the kind of optimization here is beyond that which people used to do. AVX didn't exist when it was common to write assembly.
  - yumraj 5y ago
    Yes, this is extreme and way beyond my C capabilities at any point in time. I was making a general point which I do believe is valid.
- Zababa 5y ago
  There's a law that says that as resources becomes easier to consume, people consume them more. Like when increasing the capacity of a road doesn't reduce the time spent in traffic. Wouldn't that apply to software? I feel like it's a bit unfair to call software "slower and bloated" when you wouldn't call a road "bloated" because it has a new lane. People can do more things now.
  - Dma54rhs 5y ago
    More like I start manufacturing 3 lane wide cars because the material im using is cheaper than cutting and engineering it to normal size - the way I see modern software analogy in this context.
    - Zababa 5y ago
      I don't think that's fair, we do way more things now with computers than before.
einpoklum 5y ago
> for a problem that doesn't immediately jump out as SIMD. It's a single transformation applied to elements of a large array. Parallelization is obvious, and maybe the exact SIMDization is not obvious, one is certainly motivated to formulate it. And a scatter-like approach does spring to mind right away, I believe.
brudgers 5y ago
FizzBuzz is a constant. It should never branch.
- boibombeiro 5y ago
  It is possible to instrument the code to see how much overhead those branchs add.
- saagarjha 5y ago
  Unrolling FizzBuzz is generally not a feasible solution.
  - bonzini 5y ago
    Sure it is: https://codegolf.stackexchange.com/questions/215216/high-throughput-fizz-buzz/236737#236737 https://codegolf.stackexchange.com/questions/215216/high-thr... It executes just one (well predicted) branch every 30 numbers written, and incrementing/printing the line number is branchless too. It's not as fast as the subject of the post (40 GB/s) but it's only a few hours of work.
    - saagarjha 5y ago
      The parent comment asserted that FizzBuzz should never branch. This would require it to not have any backwards control flow, and thus require full unrolling of an infinite sequence. Hence the infeasibility.
      - brudgers 5y ago
        FizzBuzz is limited to [1…100]. Output as an ASCII string, it is fewer than 400 bytes including \n’s. If you’re counting GB/S, you’ve failed to understand the specification. One of the sophisticated engineering aspects of FizzBuzz is that all optimizations are premature. It is a boring problem. People being people invent different problems to provide a chance to be clever.
      - bonzini 5y ago
DeathArrow 5y ago
>FizzBuzz has many properties that make it very suitable for these kinds of optimizations that might not be applicable to general purpose code: + extremely small working set (a few registers worth of state) + extremely predictable branching behavior + no I/O The working set depends on how you organize the data. I/o can be made in larger chunks most of the times. You have to consider about the data you need and when you need it. As for branching, that most of the time depends on programmer rather than on the problem being solved. The situation where you need very complicate branching to solve a problem are rare. And I've seen O(n log n) algorithms beating clever O(n) algorithms because they could be better optimized for the CPU.

deleted 5y ago

[deleted]

cogman10 5y ago

> no I/O The problem description is writing out bytes which is probably some of the more expensive part of this. In fact, if you read the winning solution description, IO is the primary problem here. > doesn't immediately jump out as SIMD. IDK that I agree with this assessment. Very naively, I see no reason you'd not take the 512 SIMD registers and split them into 16 32 bit lanes. From there, it's a relatively simple matter of using 2 registers for the divisors, pulling out the results, and transforming them into the text to print. In other words, you be chunking this up into 16 iterations per loop. (vs 1 with the naive assembly). This is the sort of thing that jumps out as easily vectorizable. Now, the fastest answer very obviously does not take this approach because I'm certain they realized the same thing, that the difficult part here isn't the actual division, but instead pumping out the correct text at the highest speed possible. If you read through it, most of the code is dedicated to converting binary numbers into ascii :D

loser777 5y ago
Maybe I should be more clear; no data needs to be fetched from disk/network, and the "writes" don't need to go past memory. As for the second point, you might have a different definition of "naive" and "relatively simple" as my brain has rotted too much from only thinking about SIMD for numerical computation. While determining divisibility be relatively clear, it wasn't clear how the printing would be easily vectorizable as the output-per-number is variable in length.
dvt 5y ago
> transforming them into the text to print I think this nails it. Vectorizing the math problem is "easy" (send batches of numbers to cores, do the division) but then you have to re-order it for printing (not to mention actually print it), so paradoxically, it probably makes more sense for the program to be single-threaded.
- yuliyp 5y ago
  You don't even need to do division. There are only 3 patterns that repeat for every set of 10 numbers. You just need to track which one you're on.
  - hasmanean 5y ago
    Yes the patterns repeat every 15 integers. So you only need to do one division operation, get the index modulo-15. I was bored once at work and figured out a way to compute this without doing much arithmetic. It only requires 1 modulo operation. for (int i=1; i<100;i++) { // make a bit vector with a 1 in ith bit, modulo 15. unsigned int i_as_bitvector = 1 << (i % 15); // Check it against the valid positions for FizzBuzz // 0ctal 011111 is binary 1001001001001 // Octal 02041 is binary 10000100001 printf("%d ", i); if (i_as_bitvector & 011111 ) printf("Fizz"); if (i_as_bitvector & 02041 ) printf("Buzz"); printf("\n"); } I also have a version which has NO magic constants anywhere in the program, except 3 and 5. I'll post it if someone is interested.
  - bonzini 5y ago
    Also, after printing 1 to 9, you have a single pattern of 30 numbers that repeats exactly 3 times from 10 to 99, then 30 times from 100 to 999, then 300 times from 1000 to 9999, and so on. That lets you extract lots of code from the loop and run it roughly once every 10^n numbers.
  - dvt 5y ago
    > There are only 3 patterns that repeat for every set of 10 numbers Ah, yep, good point!
boibombeiro 5y ago
Using AVX 512 is not suitable for programs that takes very small time to run. There is a penalty in the ms range to "warm up" the CPU (it is more a cool down, actually). As OP stated, the limiting factor is on the memory access. That's why he kept saying 64B every four cycles. But OP likely didn't use because most CPU lacks support for AVX512. The new Intel CPU introduced many changes for the frontend. This will likely improve the speed. There might also be possible to try make the CPU operate at higher clockspeed. Code looks a bit long. Not sure if the unrolling actually helps. EDIT: Just look at the agner microarchitecture doc. Ice Lake and Tiger Lake can do 64 bytes/cycle. In theory, it can run 4x faster (on bare metal, maybe).

yumraj 5y ago

I think you're missing the point. The issue is that with the advent of higher level languages, starting from Java, Javascript and on to Python and so on, most people have forgotten or have never learnt the skills to optimize code. I'll argue that, as a percent, the number of people who can write proper multi-threaded code has only diminished over the years. And we see the result, despite the massive increase in computing power, software in general has become slower and bloated.

foota 5y ago
I think the kind of optimization here is beyond that which people used to do. AVX didn't exist when it was common to write assembly.
- yumraj 5y ago
  Yes, this is extreme and way beyond my C capabilities at any point in time. I was making a general point which I do believe is valid.
Zababa 5y ago
There's a law that says that as resources becomes easier to consume, people consume them more. Like when increasing the capacity of a road doesn't reduce the time spent in traffic. Wouldn't that apply to software? I feel like it's a bit unfair to call software "slower and bloated" when you wouldn't call a road "bloated" because it has a new lane. People can do more things now.
- Dma54rhs 5y ago
  More like I start manufacturing 3 lane wide cars because the material im using is cheaper than cutting and engineering it to normal size - the way I see modern software analogy in this context.
  - Zababa 5y ago
    I don't think that's fair, we do way more things now with computers than before.

einpoklum 5y ago

> for a problem that doesn't immediately jump out as SIMD. It's a single transformation applied to elements of a large array. Parallelization is obvious, and maybe the exact SIMDization is not obvious, one is certainly motivated to formulate it. And a scatter-like approach does spring to mind right away, I believe.

brudgers 5y ago

FizzBuzz is a constant. It should never branch.

boibombeiro 5y ago
It is possible to instrument the code to see how much overhead those branchs add.
saagarjha 5y ago
Unrolling FizzBuzz is generally not a feasible solution.
- bonzini 5y ago
  Sure it is: https://codegolf.stackexchange.com/questions/215216/high-throughput-fizz-buzz/236737#236737 https://codegolf.stackexchange.com/questions/215216/high-thr... It executes just one (well predicted) branch every 30 numbers written, and incrementing/printing the line number is branchless too. It's not as fast as the subject of the post (40 GB/s) but it's only a few hours of work.
  - saagarjha 5y ago
    The parent comment asserted that FizzBuzz should never branch. This would require it to not have any backwards control flow, and thus require full unrolling of an infinite sequence. Hence the infeasibility.
    - brudgers 5y ago
      FizzBuzz is limited to [1…100]. Output as an ASCII string, it is fewer than 400 bytes including \n’s. If you’re counting GB/S, you’ve failed to understand the specification. One of the sophisticated engineering aspects of FizzBuzz is that all optimizations are premature. It is a boring problem. People being people invent different problems to provide a chance to be clever.
    - bonzini 5y ago

DeathArrow 5y ago

>FizzBuzz has many properties that make it very suitable for these kinds of optimizations that might not be applicable to general purpose code: + extremely small working set (a few registers worth of state) + extremely predictable branching behavior + no I/O The working set depends on how you organize the data. I/o can be made in larger chunks most of the times. You have to consider about the data you need and when you need it. As for branching, that most of the time depends on programmer rather than on the problem being solved. The situation where you need very complicate branching to solve a problem are rare. And I've seen O(n log n) algorithms beating clever O(n) algorithms because they could be better optimized for the CPU.