15 ms·

The amount of low level CPU architecture knowledge to write such a program is mind boggling. Just goes to show how much room for improvement a lot of programs h

The amount of low level CPU architecture knowledge to write such a program is mind boggling. Just goes to show how much room for improvement a lot of programs have.

SavantIdiot 5y ago
At some point I believe we will start to bump up against the limits we saw in the first three computer revolutions (tubes, transistors, integrated circuits). This will cause the pendulum to swing from commodification to optimization. What I mean is, you won't be able to snap your fingers and scale up or out, thus optimization will begin again in earnest. Clearly this isn't always the case: GPU shaders, crypto ASICs, video processing... there are plenty of places where optimization is crucial for high performance loop tuning. But optimization hasn't been required across the board like there was just before the three big innovations I described hit.
- c9fc42ad 5y ago
  This tends to happen at a smaller scale with gaming consoles. Towards the end of a generation, the games coming out usually perform/look a lot better than the ones at the beginning of the generation. I'm assuming due to a lot more careful optimizations due to not being able to change the hardware. I've always been curious about how far we could really push modern computers if somebody wanted to spend the time going to the lengths in the original post when creating practical software. Of course it's usually not worth the tradeoff, but it's interesting to think about.
- hackbinary 5y ago
  Protip: while you made a great comment, ND people like me, and even most NT people have diffivulty ingesting walls of text like what you just wrote. Please, therefore, breakup your text into paragraphs every 3 sentences. It does wonders for readability for just about everyone. :)
  - saagarjha 5y ago
    …it’s literally four sentences.
  - SavantIdiot 5y ago
    You have multiple paragraphs longer than mine in your history.
    - hackbinary 5y ago
      This is what we call shifting the the goalposts and tu quoque fallacious attacks. Just because I have erred in the past does not mean I cannot suggest to you to improve your outputs. Or, I have had learnings previously, and I am simply trying to pass them along to you. Here is another protip: dinae be so defensive. I was not attacking you personally, but your reply clearly was an attempt to attack me.
loser777 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 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.
  - 5y ago
golergka 5y ago
Also goes to show how much would it cost.
- dorianmariefr 5y ago
  And maintain and evolve and debug and work on different machines, etc.
  - mhh__ 5y ago
    If you have talented staff then you'd be surprised how far you can get just buy giving someone who already does that particular application as a hobby an unlimited supply of coffee. Obviously finding talented staff is very hard, but once you have your tribe you can go a very long way i.e. I look at apps made by some people I work with (fast, lightweight etc.) then compare with crap pumped out by startups with literal billions in capital. I think it's a question of confidence more than competence.
tester756 5y ago
It shows that abstractions are leaky as f :)
- munchler 5y ago
  No, this simply shows that abstraction slows performance, which is usually a worthwhile tradeoff. Leaky abstractions are a different problem altogether.
  - bigiain 5y ago
    Yep. I suspect most people here could write a working fizzbuzz on a whiteboard in language of choice in under 5 mins during a job interview. Sure your Python/JavaScript/Haskell/Rust version builds on a bunch of abstractions, but it’ll run on just about anything, and … “I've spent months working on this program” That’s not what your boss wants to hear.
    - deleted 5y ago
      [deleted]
    - snovv_crash 5y ago
      You can pump out a Modern C++ version in 5 minutes too that will run loops (haha) around the higher level languages. The readability won't even be very different...
      - bigiain 5y ago
        True. I bet the Rust guys would come close too. But realistically? For anything except code golf and nerd fights, the actual client requirement is probably better met by a WordPress widget written in php/html, because what they asked for is something that'll print the fizz buzz all the way up to the person's age when they log into the company website... Nobody is even going to notice if it takes a whole second to fizz buzz all the way to 95 :-) (Now I'm wondering if that guy's raw hyper optimised x86 assembly can get transpiled to WASM... Because nerd fights are fun.)
999900000999 5y ago
Just put everything inside an electron container. Unless your talking about micro controller programing Ram is basically free.
- mhh__ 5y ago
  Cache however is not
- Delk 5y ago
  It could be, but in most cases it's not due to RAM commonly being unupgradable in laptops. A larger amount of RAM might still be cheap to install in the first place, but that choice is not always directly up to the consumer.
  - 999900000999 5y ago
    Correct, but Slack is based off electron and is widely successful. End users are used to tolerating a basic chat application eating an indefinite amount of ram. From a business pov it doesn't make sense to spend time optimizing since most users don't seem to mind.
haliskerbas 5y ago
And imagine not coming up with this solution in your next MANGA interview!
DeathArrow 5y ago
It pays of to understand the CPU architecture even if you are not using the assembler: https://blog.cloudflare.com/branch-predictor/ https://blog.cloudflare.com/branch-predictor/ Once upon a time most software was highly optimized with hot code paths written in assembly. If you look at DOS source code, DOOM source code you will see lots of optimization. When CPUs got more powerful, people got lazy and they thought they can spend the improvements on conveniences. Now we are at the point that we run "desktop" apps written in Javascript on top of embedded browsers.
- colonelxc 5y ago
  I think you meant https://blog.cloudflare.com/branch-predictor/ https://blog.cloudflare.com/branch-predictor/
  - DeathArrow 5y ago
    Yes, thank you for mentioning it.
- alephu5 5y ago
  Not lazy, sensible. The market has spoken and it wants bloated electron apps with rapid development, rather than performant C/assembly apps that hardly ever change.
  - dijit 5y ago
    “The market”? The power dynamics of companies/customers are often not as dynamic as all that. If slack is electron and I work at a company that uses slack: I must use it. The competition in that space is all electron, you can’t choose. It’s like saying that “the market chose non-ECC ram”. No, Intel chose for you and you don’t get much choice except to suck it up (or pay well above the odds.) It takes a lot to avoid using a product. I mean people still use Oracle products!
  - vletal 5y ago
    That does not actually contradict the point. We got stuck in a suboptimal local maxima due to the all early design decisions of browsers and JavaScript. The original inventors did not expect anyone wiring web version of Google Drive on the web. The market surely pushes against the bloated electron apps, yet the convenience of having the same app on web as well as "native" and the amount of man years which went to make HTML+JS the richest multi-platform UI framework on the market is more important.
fulafel 5y ago
It takes a lot to to correctly explain exactly why the set of design choices is fastest, but writing just takes quite a simple model of the CPU internals, knowledge of the insturction set, focus on constantly measuring performance, and an agility to iterate quickly with different approaches.
- fulafel 5y ago
  And reading more closely, beating the competition low level OS knowledge and understanding peculiarities of the benchmark in question. The benchmark was about getting the output to a pipe as fast as possible, and there's this great pipe speed hack: // To produce output without losing speed, the program therefore needs // to avoid copies, or at least do them in parallel with calculating // the next block of output. This can be accomplished with the // `vmsplice` system call, which tells the kernel to place a reference // to a buffer into a pipe (as opposed to copying the data into the // pipe); the program at the other end of this pipe will then be able // to read the output directly out of this program's memory, with no // need to copy the data into kernelspace and then back into // userspace.

The amount of low level CPU architecture knowledge to write such a program is mind boggling. Just goes to show how much room for improvement a lot of programs have.

SavantIdiot 5y ago

At some point I believe we will start to bump up against the limits we saw in the first three computer revolutions (tubes, transistors, integrated circuits). This will cause the pendulum to swing from commodification to optimization. What I mean is, you won't be able to snap your fingers and scale up or out, thus optimization will begin again in earnest. Clearly this isn't always the case: GPU shaders, crypto ASICs, video processing... there are plenty of places where optimization is crucial for high performance loop tuning. But optimization hasn't been required across the board like there was just before the three big innovations I described hit.

c9fc42ad 5y ago
This tends to happen at a smaller scale with gaming consoles. Towards the end of a generation, the games coming out usually perform/look a lot better than the ones at the beginning of the generation. I'm assuming due to a lot more careful optimizations due to not being able to change the hardware. I've always been curious about how far we could really push modern computers if somebody wanted to spend the time going to the lengths in the original post when creating practical software. Of course it's usually not worth the tradeoff, but it's interesting to think about.
hackbinary 5y ago
Protip: while you made a great comment, ND people like me, and even most NT people have diffivulty ingesting walls of text like what you just wrote. Please, therefore, breakup your text into paragraphs every 3 sentences. It does wonders for readability for just about everyone. :)
- saagarjha 5y ago
  …it’s literally four sentences.
- SavantIdiot 5y ago
  You have multiple paragraphs longer than mine in your history.
  - hackbinary 5y ago
    This is what we call shifting the the goalposts and tu quoque fallacious attacks. Just because I have erred in the past does not mean I cannot suggest to you to improve your outputs. Or, I have had learnings previously, and I am simply trying to pass them along to you. Here is another protip: dinae be so defensive. I was not attacking you personally, but your reply clearly was an attempt to attack me.

loser777 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 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.
- 5y ago

golergka 5y ago

Also goes to show how much would it cost.

dorianmariefr 5y ago
And maintain and evolve and debug and work on different machines, etc.
- mhh__ 5y ago
  If you have talented staff then you'd be surprised how far you can get just buy giving someone who already does that particular application as a hobby an unlimited supply of coffee. Obviously finding talented staff is very hard, but once you have your tribe you can go a very long way i.e. I look at apps made by some people I work with (fast, lightweight etc.) then compare with crap pumped out by startups with literal billions in capital. I think it's a question of confidence more than competence.

tester756 5y ago

It shows that abstractions are leaky as f :)

munchler 5y ago
No, this simply shows that abstraction slows performance, which is usually a worthwhile tradeoff. Leaky abstractions are a different problem altogether.
- bigiain 5y ago
  Yep. I suspect most people here could write a working fizzbuzz on a whiteboard in language of choice in under 5 mins during a job interview. Sure your Python/JavaScript/Haskell/Rust version builds on a bunch of abstractions, but it’ll run on just about anything, and … “I've spent months working on this program” That’s not what your boss wants to hear.
  - deleted 5y ago
    [deleted]
  - snovv_crash 5y ago
    You can pump out a Modern C++ version in 5 minutes too that will run loops (haha) around the higher level languages. The readability won't even be very different...
    - bigiain 5y ago
      True. I bet the Rust guys would come close too. But realistically? For anything except code golf and nerd fights, the actual client requirement is probably better met by a WordPress widget written in php/html, because what they asked for is something that'll print the fizz buzz all the way up to the person's age when they log into the company website... Nobody is even going to notice if it takes a whole second to fizz buzz all the way to 95 :-) (Now I'm wondering if that guy's raw hyper optimised x86 assembly can get transpiled to WASM... Because nerd fights are fun.)

999900000999 5y ago

Just put everything inside an electron container. Unless your talking about micro controller programing Ram is basically free.

mhh__ 5y ago
Cache however is not
Delk 5y ago
It could be, but in most cases it's not due to RAM commonly being unupgradable in laptops. A larger amount of RAM might still be cheap to install in the first place, but that choice is not always directly up to the consumer.
- 999900000999 5y ago
  Correct, but Slack is based off electron and is widely successful. End users are used to tolerating a basic chat application eating an indefinite amount of ram. From a business pov it doesn't make sense to spend time optimizing since most users don't seem to mind.

haliskerbas 5y ago

And imagine not coming up with this solution in your next MANGA interview!

DeathArrow 5y ago

It pays of to understand the CPU architecture even if you are not using the assembler: https://blog.cloudflare.com/branch-predictor/ https://blog.cloudflare.com/branch-predictor/ Once upon a time most software was highly optimized with hot code paths written in assembly. If you look at DOS source code, DOOM source code you will see lots of optimization. When CPUs got more powerful, people got lazy and they thought they can spend the improvements on conveniences. Now we are at the point that we run "desktop" apps written in Javascript on top of embedded browsers.

colonelxc 5y ago
I think you meant https://blog.cloudflare.com/branch-predictor/ https://blog.cloudflare.com/branch-predictor/
- DeathArrow 5y ago
  Yes, thank you for mentioning it.
alephu5 5y ago
Not lazy, sensible. The market has spoken and it wants bloated electron apps with rapid development, rather than performant C/assembly apps that hardly ever change.
- dijit 5y ago
  “The market”? The power dynamics of companies/customers are often not as dynamic as all that. If slack is electron and I work at a company that uses slack: I must use it. The competition in that space is all electron, you can’t choose. It’s like saying that “the market chose non-ECC ram”. No, Intel chose for you and you don’t get much choice except to suck it up (or pay well above the odds.) It takes a lot to avoid using a product. I mean people still use Oracle products!
- vletal 5y ago
  That does not actually contradict the point. We got stuck in a suboptimal local maxima due to the all early design decisions of browsers and JavaScript. The original inventors did not expect anyone wiring web version of Google Drive on the web. The market surely pushes against the bloated electron apps, yet the convenience of having the same app on web as well as "native" and the amount of man years which went to make HTML+JS the richest multi-platform UI framework on the market is more important.

fulafel 5y ago

It takes a lot to to correctly explain exactly why the set of design choices is fastest, but writing just takes quite a simple model of the CPU internals, knowledge of the insturction set, focus on constantly measuring performance, and an agility to iterate quickly with different approaches.

fulafel 5y ago
And reading more closely, beating the competition low level OS knowledge and understanding peculiarities of the benchmark in question. The benchmark was about getting the output to a pipe as fast as possible, and there's this great pipe speed hack: // To produce output without losing speed, the program therefore needs // to avoid copies, or at least do them in parallel with calculating // the next block of output. This can be accomplished with the // `vmsplice` system call, which tells the kernel to place a reference // to a buffer into a pipe (as opposed to copying the data into the // pipe); the program at the other end of this pipe will then be able // to read the output directly out of this program's memory, with no // need to copy the data into kernelspace and then back into // userspace.