Hacker News Reader

Comment by sillysaurusx | Hacker News Reader

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

View on HN

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

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

It is very interesting if you have properly verified invariants and you can guarantee (with manual checking) that your code is correct. It's an order of magnitude harder than just letting the borrow checker do its job, but it's entirely possible (just like in any other language).

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.

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.

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.

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

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.

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.

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

Controlled CPU predictions, wow. That's a level of performance I've never even contemplated

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.

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

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.

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.

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.

You almost always know something about the data that a sorting function will operate on. Unless of course you are implementing a generic sorting algorithm. In practice you could train your compiler on real world data to allow it to optimize better for your environment. This is already happening with profile guided optimizations.

PGO is a thing for this reason.

(But no, I'm not expecting AI driven compilers anytime soon)

I think it's unfair that people downvoted this to gray. This person didn't claim that this was about to happen, and it seems likely to me that when/if AI surpasses human intelligence that something like this would be possible. It might require some additional way to describe expectations about the input data, and it might be many years away, but I would be disappointed if compilers couldn't do this in the far distant future. Look at the progress we've made in the last seventy years and try to extrapolate that out a thousand years forward. I obviously can't guarantee what will happen, but is it really that unreasonable to suggest progress like this as a strong possibility?

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

> why is the ASM version so much faster if the glue code doesn't make much difference

The remark on the glue code only applies to my entry (the second). The assembly entry uses a completely different (and much more complicated) algorithm than the C entry.

If you read the description you’ll see that it’s optimizing around certain syscalls like memcopy (which is otherwise limiting and reduces speed by 5x). I think it’s less language choice, and more low level optimization that is making a difference here.

(To check, I wrote a Go program that doen nothing else than fmt.Print($largebody) in a for loop and it tops out at around 10GB/s)

Note that memcpy is not a syscall. Common syscalls do copies. The fast implementation uses the vmsplice syscall as a clever way to pump a pipe with data, because it doesn't copy.

Indeed. Today for most systems memcpy is in fact a compiler intrinsic. C's standard library offers a memcpy but the reality is that your C standard library was likely supplied by your C compiler vendor, and when you ask for memcmp() in C you get their preferred intrinsic inlined into your program unless you've been very firm in declining that optimisation.

In Rust this memcpy intrinsic is required (for the core language, not just the standard library) because Rust clearly has arbitrarily large data structures you can literally copy, so, somebody has to take responsibility for doing that work, Rust says it's the compiler back-end's job. On a toy CPU the memcpy might really just be a trivial read->register->write loop because that's adequate.

Oops, I notice hours too late to edit it, that this says memcmp() in one place where it mostly says memcpy(). In fact your C compiler likely has intrinsics for both, but I did mean memcpy() everywhere in the comment.

The Python implementation posted among the answers is about 85 MiB/sec, under PyPy.

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

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

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

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!

"I just enjoy dosing the Rusties with reality every so often."

Aka troll.

Oh? Why is it trolling to say that Rust isn't as fast as C in this case?

If it were, you'd claim the prize. If you really want to hurt a troll, wouldn't you try to separate them from their $500?

You still assume I care. As stated above I don't care. It's in your head only that every Rust developer writes Rust because she thinks it's faster than C.

> to say that Rust isn't as fast as C in this case

That's not what the quoted statement is doing.

I think we'll have to agree to disagree. It's illustrative that a seemingly simple C program can't be easily ported to Rust. If it could be, someone would have already done it -- it's been a few hours.

It's also illustrative to examine exactly what the hangups are. You might even get more Rust converts if you acknowledge that there are serious engineering burdens to overcome when deciding to use Rust.

For the record, it's not the anti-Rust sentiment which people find annoying, it's the treatment of programming languages as though they were football teams.

If you want to make a case against Rust, then let's get concrete: why is one Turing-complete compiled language that can make arbitrary syscalls not capable of compiling down to the same assembly as another?

That would be an interesting discussion; this is not.

You can dig into it, but the details are mostly only relevant to people designing computer languages and tooling.

Aka Compilers, as long as the machine code is equivalent to the source code their output can be wildly different. However, someone needs to actually write them which means both linguistic differences and the sheer effort that was actually put into the compiler are both significant. You shouldn’t assume that every language is operating on an even playing field because their simply not. The obvious solution of compiling to a second language is never quite as capable as using the language directly.

> Compilers, as long as the machine code is equivalent to the source code their output can be wildly different

I don't understand what this means: the output of a compiler is the machine code from the source code, no?

Also, Rust uses LLVM as a backend, which has benefited from lots of work given its use for C, C++, ObjC, Swift, &c. Compiling the C with Clang/LLVM might give a more interesting insight into the differences between Rust and C.

> The obvious solution of compiling to a second language is never quite as capable as using the language directly.

I'm not sure what you mean by this, or rather how it's related to what we're talking about?

> The output is the machine code.

You get different machine code using different compilers on identical pieces of source code. In theory the results of running that source code should have equivalent results even if one is more efficient than another. If for example one compiler uses a ASM instruction that another never uses then nothing the programmer does can get the second compiler to be as efficient as the first. The same is true of various optimizations etc, sometimes a compiler is just better.

Bring a different language into the picture and things get even more divergent.

> how it’s related

It’s specifically in reference to rust use of LLVM not being sufficient to guarantee equivalence. Many languages target the JVM, that does not make them equivalent.

> You get different machine code using different compilers on identical pieces of source code.

Ah, right - well I'm certainly not denying that. (I'm familiar with the topic, to be clear: I've written compilers. I just wasn't clear what exactly you were saying.)

> It’s specifically in reference to rust use of LLVM not being sufficient to guarantee equivalence.

Formally, no. In practice, given that fact, given the experience of the maintainers of both languages, and given the 'compilability' of both languages, it would be surprising if there were a 10x gulf between them.

That kind of behaviour (edit: theirs, not yours) is usually ultimately motivated by fear. ;)

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

I don't know. I use Rust myself, but I've seen more people complaining about Rust evangelism than people actually doing that.

The RESF is a bad meme.

When there's a memory related bug (or CVE) in a program written in C or C++, there's almost always some comment about how the Rust compiler would've caught it

On HN there is often: A comment about Rust would catch this (sometimes sarcastic), an explanation about how the bug isn't "really" memory safety and so Rust wouldn't catch it, followed by a comment explaining actually Rust does catch it.

The recent Linux mutex security bug is an example. That's not a memory safety bug. Surely Rust doesn't help? But Rust's mutual exclusion design relies on the Rust type system to give us safer locks, in Rust you protect things by having "lock the mutex" be the way you get the reference to the protected object. Thus when the faulty code locks the wrong mutex in Rust it would get the wrong object, and either not compile (you lock variable A and then you're trying to change B but you don't even have B) or not work (you always lock variable A, then change variable A, but your code should change B, it does not work, trivially reproducible bug in your code)

From Rust developers or from app users? As an app user I would prefer if apps are written in Rust and Im reminded with every CVE for a C program.

Otoh. Being a dick, to majority of people because of acts of minority is worse.

No no, C is great for writing fast FizzBuzz implementations; any larger program is hard to get correct. :-)

Ultimately, your argument is a troll because you are trying to tell people what they should value in a programming language.

Pretty sure the fact its literally a speed contest is telling people what to value in a programming language.

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

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

What comment comes to your mind of a Rust developer who thinks Rust is faster than C and needs a dose of reality?

Rust is a memory safe systems programming language. As a systems programming language, it can be used in the same areas that C can (see Redox OS). I've seen quite a few Rust users online that have claimed that, because of that, it can be just as fast as C.

But it can be just as fast as C. The C program that's so much faster here isn't "really" a C program it's just a fancy way to shovel machine code, which you could of course also do (unsafely) in Rust if you chose to do so but why?

However what you were asked about is claims it's faster and there micro-benchmarks like this are not revealing. At scale you're obliged to limit yourself to what you can write that works and in Rust the safety lets you reach higher - which is how it achieves better performance. In fact that's what Mozilla used Rust for. They'd failed more than once to ship a concurrent CSS speed-up, finding it too hard to successfully get the bugs out and so returning to a single threaded CSS implementation - but the attempt in Rust (Quantum) worked just fine.

This is the same reason C++ is faster, a C++ iterator isn't faster than the naive C for loop, in fact they emit identical code, but the iterator is easier to think about, which means you can confidently write more complicated software using this abstraction. Rust just provides the safety to go higher still.

What is the opinion of Golang users on this?

This is really cool. It should be obvious that a few thousand hand-rolled assembly opcodes targeting a fixed architecture would win the race. If the size of the solution grew a couple of orders of magnitude larger though, I'd expect that the micro optimization challenge would overwhelm the author and compilers would be more competitive.

Is the Table of Contents of your upcoming book public?

No not yet, incorporating first draft feedback.

You made my evening for asking <3

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.

>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

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.

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),
            };
        }
    }

Well TIL that printf won't lock stdout.

Calling stdout.lock() by itself makes little difference for me. Using BufWriter as you have I get ~80 MiB/s (slightly ahead of PyPy).

My implementation also has/had a String allocation in the loop, kicking that out got me to 120 MiB/s. I tend to write it as though the numbers/strings could be changed by a product manager at any time.

Final edit/errata: I get up to 140 MiB/s by appending .to_string() in the integer case instead of format!(), which makes some sense.

I didn't bother saving my original C implementation, but in retrospect I think I didn't use string concatenation, as I have with other languages. Redoing it with string-concatenation, C is slightly slower than Rust, 110 MiBs. Also makes sense as concatenation in C is slow.

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

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

Do you mind sharing the Julia code? Seems odd that it's that far away from even Python.

by default Julia uses locking for writes to guarantee thread safety when multiple writes are happening. That said, it's totally possible to go way faster using buffered IO.

``` for i = 1:typemax(UInt64) s = "" if i % 3 == 0 s = s * "fizz" end if i % 5 == 0 s = s * "buzz" end if s == "" s = string(i) end println(s) end ```

Measured over 10 s after a 10 s burn-in period, Julia 1.7 on Ubuntu 21.10.

I think recent versions of Ruby include a optional JIT compiler. Did you try it?

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

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.

At the very least, the itoap crate being used there does divisions by and comparisons to powers of 10 as part of stringifying integers, which the C and ASM versions don't seem to be doing. A crate with a function for stringifying arbitrary integers cannot take advantage of the fact that it's going to be used for stringifying consecutive integers, as an inlined solution can.

As far as I understand, that #2 C program contains hardly any C code but mostly inlined assembly.

The program itself is 100% C, but it spends 99.9999% of the time in assembly code that is generated at runtime.

> That's shocking.

Not really. This is a hyper optimised microbenchmark. The actual work being done is so trivial that any "overhead" is really significant and you can get order of magnitude speedups by doing arcane things with caches, eliminating tiny inefficiencies and so on.

Complete speculation, but I think you'd find that's true for most problems. Very little CPU time is spent on the business logic, and the rest is overhead.

I'm curious, how did rust affect you so badly that you hate it so much? If it's just silly people suggesting it everywhere I think you have some personal issues you need to resolve, language choice isn't something to get emotional about.

I've not seen any indication that sillysaurusx hates Rust.

> Rustaceans

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

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

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

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

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.

Reply on news.ycombinator.com