14 ms·
The Fastest FizzBuzz Implementation
- richardwhiuk 5y ago> Before running the code, make sure your CPU does support AVX2. ... You should see "sse2" at a minimum. AVX2 is not SSE2 - SSE2 is much, much older. You want to check for the avx2 flag itself.
- 6510 5y agoI would like to propose (or remind) that for this type of problem the fastest implementation is paper.
- atorodius 5y agoRelevant: https://news.ycombinator.com/item?id=29031488 https://news.ycombinator.com/item?id=29031488
- dang 5y agoThanks! Macroexpanded: 55 GiB/s FizzBuzz - https://news.ycombinator.com/item?id=29031488 https://news.ycombinator.com/item?id=29031488 - Oct 2021 (255 comments)
- throw10920 5y agoIf I may ask, what's the default keybinding for dang-macroexpand-1?
- dang 5y agocrtl+alt+b
- sillysaurusx 5y ago> As of this writing, the 3rd fastest submission is written in Rust and produces out at a rate of 3 GB/s, 2nd is written in C and produces at a rate of 41 GB/s and the fastest is written in Assembler and produces at a rate of 56 GB/s. This makes me happy. The order is exactly as it should be, much to the disappointment of the Rustaceans. It's a nice reminder that for the ultimate performance, there is no substitute for knowing exactly what the assembler is doing. It's also a nice reminder that most of us will never want to do that. EDIT: Whoa. It's late, and I thought Rust was at 30 GB/s instead of 3, i.e. roughly neck and neck with C. I meant to make a good-natured joke. There must be something wrong with the Rust implementation to be 10x slower; I wonder what it is. As I mentioned further down in the comments, I'll donate $500 to Watsi if someone manages to displace the C implementation in Rust or any other language besides C/C++/ASM. Be sure to DM me on Twitter (https://twitter.com/theshawwn https://twitter.com/theshawwn) if you do, both so I'll see it and so that I can congratulate you. I'm sure it's possible, but it's sort of interesting that the activation energy is so high.
- gopiandcode 5y agoYou're totally right. I think a lot of rust developers are going to be absolutely distraught that rust isn't the fastest language for writing fizzbuzz programs. I guess they're just going to have to settle with rust being the best language to write safety-critical high performance concurrent low-level code.
- GrayShade 5y agoYou do seem to have an axe to grind with the people using Rust. I don't see any reason why the same thing [1] could not be implemented in Rust. EDIT: I got caught by an off-by-one there, the second fastest solution (doing JIT compilation) is actually [2]. [1]: https://codegolf.stackexchange.com/a/215231 https://codegolf.stackexchange.com/a/215231 [2]: https://codegolf.stackexchange.com/a/236737 https://codegolf.stackexchange.com/a/236737
- sillysaurusx 5y agoMuch like speedruns, it's up to you to prove it :) I just enjoy dosing the Rusties with reality every so often. If you write a Rust version that can beat the C version, I'll donate $500 to Watsi. Good luck!
- KingOfCoders 5y ago"I just enjoy dosing the Rusties with reality every so often." Aka troll.
- AnIdiotOnTheNet 5y agoNot necessarily. Language evangelists can be incredibly annoying... actually, evangelists in general can be really annoying. It is cathartic to prove annoying people wrong every once in a while.
- Ygg2 5y agoOtoh. Being a dick, to majority of people because of acts of minority is worse.
- recentdarkness 5y agointeresting for me was the fact, that the author talks about themselves in the third person. Very unusual for some content like this :D
- lifthrasiir 5y agoThe author of this post (Mark Litwintschik) is not same to the author of the assembly solution (Alex Smith, also known as ais523) :-)
- nickdothutton 5y agoThis chap is the developer. Kudos to him. https://www.wolframscience.com/prizes/tm23/alex_smith_bio.html https://www.wolframscience.com/prizes/tm23/alex_smith_bio.ht...
- Croftengea 5y ago> The developer behind the Assembler version goes by the handle "ais523". > I've been unable to uncover this person's real-life identity
- lifthrasiir 5y ago> The developer behind the Assembler version goes by the handle "ais523". Alex Smith [1] is also known for winning the Wolfram 2,3 Turing Machine Research Prize [2]. [1] https://www.cs.bham.ac.uk/~ais523/ https://www.cs.bham.ac.uk/~ais523/ [2] https://writings.stephenwolfram.com/2007/10/the-prize-is-won-the-simplest-universal-turing-machine-is-proved/ https://writings.stephenwolfram.com/2007/10/the-prize-is-won...
- DeathArrow 5y agoThe most interesting thing is the C version is almost as fast as assembler version.
- bonzini 5y agoThe most interesting thing is that it took one day to write the C version and several months for the assembly version, because the C version uses a simpler algorithm. Talk about diminishing returns. :)
- pokepim 5y agoAnd you could copy paste Python version from SO and have it running in less than a minute, so here’s the winner :)
- bonzini 5y agoIf the Python version is 2000 times slower, the breakeven would be after a few terabytes of FizzBuzz.
- DeathArrow 5y agoYes, but if you start the Python version and still have 5 minutes left from the day, the C version will overtake Python.
- trevyn 5y agoI wonder how an M1 Max assembly version would fare.
- faeyanpiraat 5y agoBefore running the code, make sure your CPU does support AVX2. Most 64-bit Intel and AMD CPUs should. ARM CPUs, like those found in newer Apple computers, Smartphones or Raspberry Pis, won't support AVX2.
- comonoid 5y agoARM CPUs have NEON. I cannot say if NEON has all equivalent commands, however, the threadstarter is talking about complete rewrite, not just running it as is.
- Tepix 5y agoThat sentence seems silly. ARM assembly and x86-64 assembly are two different beasts. Running the x86-64 code using Rosetta 2 emulation seems counter-intuitive as well if you want to get the fastest possible result on that machine.
- Croftengea 5y agoARM64 SIMD instructions perform in the same ballpark, see this: https://news.ycombinator.com/item?id=25408853 https://news.ycombinator.com/item?id=25408853
- 5y ago
- solmag 5y agoI think the original author said that it was harder to make this than his masters thesis.
- DeathArrow 5y agoIt seems there's a huge gap between what machine code compilers can generate and hand written optimized assembler. There's a lot of room left for compilers to be improved.
- bawolff 5y agoMost programs aren't fizzbuzz. This is basically hand optimizing a microbenchmark. While i'm sure compilers can always be better i'm not sure this particular example generalizes.
- londons_explore 5y agoBut hand optimizing a few microbenchmarks like this tells us how far we might be able to improve compilers. And from the looks of it, at least 100x is possible. It's a shame therefore that even a 1% performance increase in a compiler release is considered pretty noteworthy.
- anthony_r 5y agoThis is a very specific problem that lends itself to some fantastically cpu-friendly optimizations. Doing a single hash-map lookup here on the hot path would kill performance, and let's not even get started on any serious I/O (disk or network) as that would be multiple orders of magnitude slower. Not many problems are just "cat something extremely predictable into /dev/null".
- samhw 5y agoAnd so what? That's what this code does, and so a compiler should be able to generate the optimal assembly. Why would a compiler need to consider something that the code in question is not doing?
- bawolff 5y agoHow would the compiler know that? This code for example is only optimal if you are piping it somewhere instead of displaying on the terminal. There is no way, even in principle, for the compiler to know that this program is always run with stdout connected to a pipe. Moreover, if you mean optimal in the absolute sense, pretty sure that is equivalent to solving the halting problem. If what your asking is: why can't computers take all surounding fuzzy context into account and do precisely the right thing, the answer is: because we haven't invented strong AI yet.
- buro9 5y agoThe simplest change for performance even in Python, JavaScript, etc is to avoid the modulo function. All of the top contenders on https://codegolf.stackexchange.com/questions/215216/high-throughput-fizz-buzz/ https://codegolf.stackexchange.com/questions/215216/high-thr... do exactly this. Yes there is a lot of optimization specific to languages, OS, CPU... but the takeaway for me isn't that you have to go that extent to build an order of magnitude improvement, you can still achieve many order of magnitudes of improvement by understanding what is happening when you use something like the modulo function and that if you have requirements where you can avoid using it then that's the win. For FizzBuzz you are told it "iterates from 1 to <some number>"... and modulo would be perfect for "take a single number and produce Fizz, Buzz or FizzBuzz if it's divisable by 3, 5, or both 3 and 5"... but as we're iterating, counters are better suited to the task. I love seeing epic code golf (and the solution outlined in the article is it), but the takeaway for the majority of engineers is that significant improvements can be made with a readable and maintainable solution just by understanding the requirements and comp sci fundamentals.
- jiggawatts 5y agoThe really heavyweight use of div/mod is to produce the base-10 printed decimal numbers, not in the main control loop. The record-beating versions all do something clever to optimise the printing of the numbers between the "Fizz" and "Buzz" strings.
- bXVsbGVy 5y agoHow did they tested it? Is the data actually being delivered, and read, in order?
- andi999 5y agoI dont understand the FizzBuzz thingy. I mean isnt it just about who has the fastest print method? Correct me please, but this problem has period 15, so if you just write: for (i=1;i<n;i+=15) { print i; print i+1; print 'fizz' print i+3 ... } You have the fastest , dont you? (if the ending n is important then one can just write 15 of such loops/endgame depending on the modulus). Since there is no 'if' the branch predictor should be on your side.
- GnarfGnarf 5y ago581 lines of Assembler Interesting, but not very practical.
- chii 5y agois practicality really relevant to a competition to write the fastest FizzBuzz implementation?
- isodev 5y agoCome on now, are we really using fizzbuzz as a performance benchmark? Seriously, don't base a real-world decisions on this. PS. The Rust implementation is also not very optimal, for example, the stdout is not locked so... what are we even trying to show :-).
- tourist2d 5y agoCan you really not tell the difference between a fun challenge and a real world scenario?
- parhamn 5y agoWhen I saw this a few weeks ago it set off a lot of thinking about compilers and ML. Even the unoptimized C version is 10x slower than the one that is painstakingly optimized. Some of this performance gain will certain be achievable by ML/AI assisted compilers and translators. In that case, even a 2x speedup would be game changing. Is anyone using ML in compilers yet? The part where you verify the code still does what you wanted it to do seems trickiest.
- m3at 5y ago> Is anyone using ML in compilers yet? Yes :) Check out TVM for something mainstream: http://tvm.apache.org/ http://tvm.apache.org/ And LibNC for something esoteric (but elegant): https://bellard.org/libnc/ https://bellard.org/libnc/
- lovasoa 5y agoThe question was about the use of ML in compilers, not the use of compilers in ML. It was more about things like http://compilerai.apps.iitd.ac.in/ http://compilerai.apps.iitd.ac.in/
- m3at 5y agoOh indeed I misread, thanks for the correction. Note though that TVM is also using ML in the compiler: https://arxiv.org/abs/2006.06762 https://arxiv.org/abs/2006.06762
- sshb 5y agoI wonder about FPGA and io_uring implementations performances
- Terretta 5y agoYAWFB: Yet another wrong fizzbuzz. “fizz” % 3, “buzz” % 5, what is the % 15 for? You can blow a interviewee’s mind by saying, great, now “bang” % 7… and (hopefully!) watch the light dawn. // why so serious? :-)
- LeifCarrotson 5y agoThe % 15 is because they're using 'elif' or 'else if'; they only process each entry once and they exit the function when a successful comparison is made. It's true that you could do this with something like: result = '' if x % 3 == 0: result += 'fizz' if x % 5 == 0: result += 'buzz' if result == '': result += str(x) return result to append fizz when for 15 and also continue processing and append buzz, but this requires an extra comparison to check that you did neither of those to print the number.
- Terretta 5y agowe all know what the %15 is for. but note that if you do 3 comparisons, or 2 comparisons and an "extra" comparison, you've done the same number of comparisons, it's not really 'extra' then go ahead and keep adding factors and see which results in more comparisons as we rack up the actually extra comparisons for various combinations of factors btw and ftw, your modulo and string test example, more correct than the usual implementation, is among the most efficient: http://www.zoharbabin.com/which-fizzbuzz-solution-is-the-most-efficient/ http://www.zoharbabin.com/which-fizzbuzz-solution-is-the-mos... // still not so serious...
- opentokix 5y agoImagine writing this asm-implementation to the 22 y/o google recruiter and fail the interview. :D
- Maursault 5y agoNo machine code implementation? I wonder how much faster than assembler it could be.
- pxeger1 5y agoAssembler has basically no abstractions on top of machine code; just a human-readable syntax. So there would be no difference.
- hackater 5y agoHow do you learn about this? Does anyone have any good recommendation on books, where you learn how to do these kind of very low level optimizations?
- gumby 5y agoPfft. No machine learning was used?
- javier10e6 5y agoAsm 56 GB/s (you are reading Sanskrit) C 41 GB/s (you are reading US Tax Code) Rust 30 GB/s (you are reading English) Python (why bother) (you are speed reading ) So many tools, so many languages, life is great.
- pxeger1 5y agoThis looks like a pretty rubbish blogspam regurgitation of the original SE answer.
- w0mbat 5y agoI played with FizzBuzz when this was mentioned here a month ago, focusing on the algorithm not optimizations. I stopped once I could do it in simple code with no math except addition, 15 numbers at a time. for (int x = 0 ; x < 1000000 ; x+= 15) { printf("%d\n%d\nfizz\n%d\nbuzz\nfizz\n%d\n%d\nfizz\nbuzz\n%d\nfizz\n%d\n%d\nfizzbuzz\n", 1 + x, 2 + x, 4 + x, 7 + x, 8 + x, 11 + x, 13 + x, 14 + x); } That is simple enough and fast enough for me.
- WithinReason 5y agoDid you check what the throughput of this is?
- lovasoa 5y agoThat's around 300MiB/s on my computer.
- jprupp 5y agoHold my beer. Now were is that OpenCL programming book when I need it?