The Fastest FizzBuzz Implementation

https://tech.marksblogg.com/fastest-fizz-buzz.html

by Croftengea • 5 years ago

261 159 5 years ago

tech.marksblogg.com

atorodius• 5 years ago

Relevant: https://news.ycombinator.com/item?id=29031488

dang2• 5 years ago

Thanks! Macroexpanded:

55 GiB/s FizzBuzz - https://news.ycombinator.com/item?id=29031488 - Oct 2021 (255 comments)

throw10920• 5 years ago

If I may ask, what's the default keybinding for dang-macroexpand-1?

sillysaurusx6• 5 years 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) 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.

GrayShade2• 5 years ago

You 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

[2] https://codegolf.stackexchange.com/a/236737

sillysaurusx6• 5 years ago

Much 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!

bartvk• 5 years 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• 5 years 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 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."

lawn• 5 years ago

So you think that it's expected that C is 10 times faster than Rust?

sillysaurusx6• 5 years ago

Wow. Perhaps I should be embarrassed, but I mentally filled in "30 GB/s" instead of 3 GB/s. I thought Rust was mostly neck and neck with C. I see now why a lot of fellows responded in a defensive way.

What's it doing to be so much slower? That's shocking. I may not enjoy Rust, but I do respect its ability to approach C++ performance.

Arnavion2• 5 years ago

It's a nice reminder that for the ultimate performance, there is no substitute for knowing exactly what the assembler is doing.

I didn't realize viewing the assembly of a compiled binary was something reserved for C. Someone should tell rust.godbolt.org that it's not supposed to exist.

samhw9• 5 years ago

I think their point is that C is sufficiently close to assembler that you know exactly what assembly any given line of C will produce. This is an old canard which is not really true (https://zenhack.net/2015/08/02/c-is-not-portable-assembly.ht...), but it's common among people who derive a sense of identity from writing C.

dahfizz• 5 years ago

Go read the second place C entry[1]. Its a JIT for assembly code.

[1] https://codegolf.stackexchange.com/questions/215216/high-thr...

bonzini9• 5 years ago

The second one (written by me) is actually JIT-compiled assembly. So little of the runtime is spent in the C code that -O0 vs -O3 makes no difference at all; and even if you wrote the glue code in Python it would not be much slower than the C code.

Also the third entry is not the one in Rust. It's just that the Rust entry came later and thus was not included in the plot. The third entry is https://codegolf.stackexchange.com/a/215236/56694; it is also C.

displace the C implementation in Rust or any other language besides C/C++/ASM

This is not a language contest, it's an algorithmic contest: that is, it's the best algorithm that wins, not the best compiler. The top entry, converted into C or Rust by mostly menial work, would probably be only a few % slower and would displace the C implementation.

stavros• 5 years ago

Now I'm kind of hoping that someone will rewrite the glue in Python so that Python is the second fastest implementation of them all, just for the laughs.

sillysaurusx6• 5 years ago

I would love to see a Python implementation that approaches the C code. It would be educational on so many levels. Would anyone be interested in trying?

Also, why is the ASM version so much faster if the glue code doesn't make much difference? I suppose it matters at the margins...

animal531• 5 years ago

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.

yodelshady4• 5 years ago

FYI, on my machine a naive Rust implementation (modulo plus println!) runs at the same speed as a naive Python implemention (16-17 MB/s), even compiled with --release. Naive C manages 160-170 MB/s. (And I fully admit the naive implementations are pretty much as far as I'm going with this).

I would guess it's the println! macro eating the time.

pcwalton2• 5 years ago

It's probably stdout locking. Call Stdout::lock.

yodelshady4• 5 years ago

edit: weirder, naive Julia (1.7 on Linux) is terrible. 45 KB/s.

Ruby is slightly slower than Python or Rust, 11 MB/s. I was expecting Python to be slowest among the interpreted languages, apparently not. Pypy yields a speedup to 70 MB/s.

Summing naive implementations (for each i: start with empty string, append fizz/buzz based on the modulus of each, then conditionally append i and print):

Julia 45 KB/s Ruby 11 MB/s CPython 15 MB/s Rust 16 MB/s Pypy 70 MB/s C 160 MB/s

beltsazar• 5 years ago

There are two reasons: 1) The println! macro will lock and unlock the stdout every time it's called. 2) Rust's stdout is line-buffered by default.

In my machine the naive C implementation achieves 81.7 MiB/s, whereas a naive Rust implementation with println achieves 7.58 MiB/s.

When I acquired the stdout's lock once and use writeln!(&mut stdout, ...) instead of println, I got 8.15 MiB/s.

When I wrapped stdout with BufWriter, I got 299 MiB/s.

    use std::io::{BufWriter, Write};

    fn main() {
        let stdout = std::io::stdout();
        let stdout = stdout.lock();
        let mut stdout = BufWriter::with_capacity(32 * 1024, stdout);

        for i in 1..1_000_000_000 {
            let _ = match (i % 3 == 0, i % 5 == 0) {
                (true, true) => writeln!(&mut stdout, "FizzBuzz"),
                (true, false) => writeln!(&mut stdout, "Fizz"),
                (false, true) => writeln!(&mut stdout, "Buzz"),
                (false, false) => writeln!(&mut stdout, "{}", i),
            };
        }
    }

pcwalton2• 5 years ago

You can basically take any LLVM IR that Clang would produce and produce Rust that compiles down to it (modulo irreducible control flow, I think, but the C++ doesn't have that). Because of that, C++ vs. Rust language (as opposed to library) performance comparisons are uninteresting.

It's a nice reminder that for the ultimate performance, there is no substitute for knowing exactly what the assembler is doing.

C and C++ do not let you know exactly what the assembler is doing. I work on compilers for a living and despite that--perhaps because of that--I have no confidence that I can predict what instructions the compiler will generate ahead of time. If I need to know the actual instructions, I run my code through Godbolt and check. C, C++, and Rust are all millions of lines of LLVM optimization passes away from the metal.

Based on some other comments, I suspect that all the time is being spent in locking stdout, which you can amortize by using Stdout::lock [1]. As is so often the case when microbenchmarks are discussed online, this has nothing to do with the language.

Also, it shouldn't need to be said, but FizzBuzz is so totally unrepresentative of real workloads that you shouldn't draw any conclusions about language performance from it.

[1] https://doc.rust-lang.org/stable/std/io/struct.Stdout.html#m...

parhamn2• 5 years ago

LLVM IR that Clang would produce

You most certainly can’t unless your code is unsafe and in that case the comparison isn’t so interesting anymore.

KingOfCoders7• 5 years ago

"disappointment of the Rustaceans."

I'm using Rust and I'm not dissappointed. Why should I?

But I do appreciate how you create imaginary people in your head, troll them and mentally pad yourself for doing so.

isoprophlex• 5 years ago

All the rust users rising to the bait in this thread sure aren't imaginary

tester34• 5 years ago

This makes me happy. The order is exactly as it should be, much to the disappointment of the Rustaceans.

Why it makes you happy? it's a reminder how much we're losing performance, energy and stuff when we're writing in safe/expressive/easy to use languages like Java, C#, Python yada yada

gopiandcode• 5 years ago

You'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.

jedimastert• 5 years ago

Rustaceans

Completely off topic, but suddenly all of the crab branding makes a ton more sense

recentdarkness• 5 years ago

interesting for me was the fact, that the author talks about themselves in the third person. Very unusual for some content like this :D

lifthrasiir2• 5 years ago

The author of this post (Mark Litwintschik) is not same to the author of the assembly solution (Alex Smith, also known as ais523) :-)

nickdothutton• 5 years ago

This chap is the developer. Kudos to him. https://www.wolframscience.com/prizes/tm23/alex_smith_bio.ht...

Croftengea2• 5 years ago

The developer behind the Assembler version goes by the handle "ais523". I've been unable to uncover this person's real-life identity

lifthrasiir2• 5 years 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/

[2] https://writings.stephenwolfram.com/2007/10/the-prize-is-won...

trevyn2• 5 years ago

I wonder how an M1 Max assembly version would fare.

faeyanpiraat• 5 years ago

Before 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.

comonoid2• 5 years ago

ARM 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.

Tepix2• 5 years ago

That 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.

Croftengea2• 5 years ago

ARM64 SIMD instructions perform in the same ballpark, see this: https://news.ycombinator.com/item?id=25408853

SekstiNi• 5 years ago

The Firestorm cores are capable of issuing two 128bit stores per cycle [1], giving a bandwidth of 102.4 GBps. This matches the experiments by Andrei with mixed reads/writes [2], and I have personally verified that it is attainable for pure write workloads to L1 as well as L2.

This does not mean 102.4 GBps is achievable on a single core, but if L2 bandwidth is the limiting factor it very well could be.

[1] https://dougallj.github.io/applecpu/firestorm.html [2] https://www.anandtech.com/show/17024/apple-m1-max-performanc...

solmag• 5 years ago

I think the original author said that it was harder to make this than his masters thesis.

DeathArrow3• 5 years ago

The most interesting thing is the C version is almost as fast as assembler version.

bonzini9• 5 years ago

The 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• 5 years ago

And you could copy paste Python version from SO and have it running in less than a minute, so here’s the winner :)

DeathArrow3• 5 years ago

It 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.

bawolff4• 5 years ago

Most 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_explore2• 5 years ago

But 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.

bonzini9• 5 years ago

The top 3 entries use completely different algorithms. The use of assembly might help a bit, but not as much as the raw numbers suggest.

andrewaylett• 5 years ago

Back when I was employed to work on a compiler, our approach to such things was to implement our run-time libraries in C and fix the compiler so it was able to produce the desired output.

In this case, though, the biggest differences aren't coming from C vs assembler but from walking away from platform conventions -- ABI, memory layout, CPU compatibility. It might be easier to write assembly than to teach the compiler how to generate code that does this, but that's largely because you don't need these optimisations in most cases. If the methods used provided a general speedup, it would be worth implementing them in compilers.

pjc50• 5 years ago

Producing this solution requires not merely a clever compiler but an extraordinary amount of creative intelligence.

btilly2• 5 years ago

I suspect that a compiler which produced code that will crash when you attempt to write to a file would be declared buggy and unusable.

And yet, that is one of the optimizations that helps get this one the speed crown.

buro9• 5 years ago

The 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-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.

jiggawatts2• 5 years ago

The 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• 5 years ago

How did they tested it? Is the data actually being delivered, and read, in order?

andi9992• 5 years ago

I 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.

zkldi• 5 years ago

Did you even read the OP?

andi9992• 5 years ago

The OP is great. And basically it is about how to print faster. I was more commenting on the fast fizzbuzz challenge itself.

Tepix2• 5 years ago

You're printing the number too so, no, it does not heave a period of 15.

GnarfGnarf• 5 years ago

581 lines of Assembler

Interesting, but not very practical.

chii• 5 years ago

is practicality really relevant to a competition to write the fastest FizzBuzz implementation?

isodev• 5 years ago

Come 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• 5 years ago

Can you really not tell the difference between a fun challenge and a real world scenario?

parhamn2• 5 years ago

When 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.

m3at2• 5 years ago

Is anyone using ML in compilers yet?

Yes :)

Check out TVM for something mainstream: http://tvm.apache.org/

And LibNC for something esoteric (but elegant): https://bellard.org/libnc/

lovasoa2• 5 years ago

The 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/

richardwhiuk• 5 years 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.

sshb• 5 years ago

I wonder about FPGA and io_uring implementations performances

Terretta2• 5 years ago

YAWFB: 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• 5 years ago

The % 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.

Terretta2• 5 years ago

we 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-mos...

// still not so serious...

opentokix• 5 years ago

Imagine writing this asm-implementation to the 22 y/o google recruiter and fail the interview. :D

Maursault• 5 years ago

No machine code implementation? I wonder how much faster than assembler it could be.

pxeger12• 5 years ago

Assembler has basically no abstractions on top of machine code; just a human-readable syntax. So there would be no difference.

hackater• 5 years ago

How 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• 5 years ago

Pfft. No machine learning was used?

javier10e6• 5 years ago

Asm 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.

pxeger12• 5 years ago

This looks like a pretty rubbish blogspam regurgitation of the original SE answer.

w0mbat• 5 years ago

I 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• 5 years ago

Did you check what the throughput of this is?

lovasoa2• 5 years ago

That's around 300MiB/s on my computer.

jprupp• 5 years ago

Hold my beer. Now were is that OpenCL programming book when I need it?

6510• 5 years ago

I would like to propose (or remind) that for this type of problem the fastest implementation is paper.

The Fastest FizzBuzz Implementation

Related Stories