Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Making Rust as Fast as Go

christianfscott.com

Post reply on HN
Print view View original

61–70 of 211 posts

Re: Making Rust as Fast as Go

#61

Post by chrfrasco »

burntsushi wrote: post #55
chrfrasco wrote: post #51

Earlier quoted context omitted.

> The second problem is that at least the Rust code is decoding UTF-8 every iteration of the inner loop instead of decoding once and saving the result, or even better interning the characters and having versions of the inner loop for 32-bit chars and 8-bit and 16-bit interned indexes. I tried this. Pulling the .chars() call out of the loop & collecting into a Vec made the performance even worse – the following balloo…

Indeed, it looks like doing the UTF-8 decoding up-front is exacerbating the performance difference in the allocator. I think this is where the GP's first suggestion comes into play. If one were writing this code _and_ cared about performance, then you'd usually find a way to reuse allocations. I submitted a PR to demonstrate this: https://github.com/christianscott/levenshtein-distance-bench...

Yeah, I can definitely see how that would be a more performant approach.

I suppose I wasn't so interested in figuring out how to make this algorithm as fast as possible as much I was interested in diving into why this particular implementation was slower.

I'm not totally convinced that this difference is down to the string being parsed over and over, though

> doing the UTF-8 decoding up-front is exacerbating the performance difference in the allocator

This seems to suggest that allocation might be dominating here. WDYT? Either way, I've added a disclaimer to the post.

Re: Making Rust as Fast as Go

#62

Post by heavenlyblue »

masklinn wrote: post #59
molf wrote: post #50

Earlier quoted context omitted.

> Implausible benchmark results are almost always an indicator of the incompetence of the person performing the benchmark. An ad hominem attack surely isn't needed.

And that's really too bad because I think the rest of the comment is spot-on as the fundamental issue is that Rust simply delegates to the system allocator, and MacOS's allocator is pretty slow. As a result, while Rust allows very explicitly and relatively easily removing allocations (compared to C or C++), getting the most performances out of your program also requires doing so, unless you use a non-system allocator…

But you can use a custom allocator in Rust: https://doc.rust-lang.org/1.9.0/book/custom-allocators.html

You don’t have that option in Go

Re: Making Rust as Fast as Go

#63

Post by rhinoceraptor »

codeflo wrote: post #5

I recently did some experiments with creating small static Rust binaries, custom linking, no_std et cetera. A lot of stuff around that kind of thing is unstable or unfinished, which might be somewhat expected. But I’ve also come to the conclusion that Rust relies on libc way too much. That might be fine on Linux, where GNU’s libc is well-maintained, is a bit questionable on MacOS (as seen in this article) and is a a…

Go’s pathological NIH syndrome does come with downsides. For example, there was an infamous memory corruption bug in the way they called into vDSO.

Re: Making Rust as Fast as Go

#64

Post by ishanjain28 »

I tried to benchmark Go/Rust versions as well.

I made 4 changes in Rust version.

1. Moved up the line that gets a value from cache[j+1] before any calls are made to cache[j]. This removes 1 bound check. (Improvement from 182,747ns down to 176,xyzns +-4800)

2. Moved from .chars().enumerate() to .as_bytes() and manually tracking current position with i/j variables. (Improvement from 176,xyz ns down to 140,xyz ns)

3. Moved to the standard benchmark suite from main + handrolled benchmark system.(File read + load + parse into lines was kept out of benchmark)

4. Replaced hand rolled min with std::cmp::min. (improvement from 140,xyz down to 139,xyz but the std deviation was about the same. So Could just be a fluke. Don't know)

In Go version, I made three changes.

1. Doing the same thing from #1 in Rust actually increased the runtime from 190,xyz to 232,xyz and quite consistently too. I ran it 10+ times to confirm)

2. Replaced []rune(source), []rune(target) to []byte(source), []byte(target). (Improvement from 214817ns to 190152 ns)

3. Replaced hand rolled bench mark system with a proper bench mark system in Go. (Again, File read + load + parse into lines was kept out of benchmark)

So, At the end of it, Rust version was about 50k ns faster than Go version.

Edit #1:

In rust version, I had also replaced the cache initialization to (0..=target.len()).collect() before doing anything els.. This also gave a good perf boost but I forgot to note down the exact value.

Re: Making Rust as Fast as Go

#65

Post by ishanjain28 »

matklad wrote: post #13

Note that Rust and Go programs differ in a seemingly insignificant, but actually important detail. Rust does this next_dist = std::cmp::min( dist_if_substitute, std::cmp::min(dist_if_insert, dist_if_delete), ); Go does this nextDist = min( distIfDelete, min(distIfInsert, distIfSubstitute) ) The order of minimums is important for this dynamic programming loop. If I change Rust version to take minimums in the same orde…

I think they made the rust version same as Go because I cloned it just now and they are both the same. Also, Thank you soo much for the blog posts! :)

Re: Making Rust as Fast as Go

#66

Post by adev_ »

rhinoceraptor wrote: post #63
codeflo wrote: post #5

I recently did some experiments with creating small static Rust binaries, custom linking, no_std et cetera. A lot of stuff around that kind of thing is unstable or unfinished, which might be somewhat expected. But I’ve also come to the conclusion that Rust relies on libc way too much. That might be fine on Linux, where GNU’s libc is well-maintained, is a bit questionable on MacOS (as seen in this article) and is a a…

Go’s pathological NIH syndrome does come with downsides. For example, there was an infamous memory corruption bug in the way they called into vDSO.

> Go’s pathological NIH syndrome does come with downsides.

Yes. And you can add the inability to use the glibc's nss modules under Linux.

Making it unable to use sssd properly and authenticate a posix user on a machine with LDAP authentication.

Getting completely independent from OS sys lib has consequences

Re: Making Rust as Fast as Go

#67

Post by steveklabnik »

heavenlyblue wrote: post #62
masklinn wrote: post #59

Earlier quoted context omitted.

And that's really too bad because I think the rest of the comment is spot-on as the fundamental issue is that Rust simply delegates to the system allocator, and MacOS's allocator is pretty slow. As a result, while Rust allows very explicitly and relatively easily removing allocations (compared to C or C++), getting the most performances out of your program also requires doing so, unless you use a non-system allocator…

But you can use a custom allocator in Rust: https://doc.rust-lang.org/1.9.0/book/custom-allocators.html You don’t have that option in Go

(those are very old docs, you want to link to https://doc.rust-lang.org/stable/std/alloc/trait.GlobalAlloc...)

Re: Making Rust as Fast as Go

#68

Post by geofft »

fluffything wrote: post #60
geofft wrote: post #27

Earlier quoted context omitted.

To me, a #![no_std] library is useful for contexts where there isn't a platform libc (embedded systems, kernels, etc.) and you can't assume things like the existence of stdin or processes. On those systems, there may still be a dynamic allocator, because that's a super common feature in all but the most spartan environments. For those use cases, a #![no_std] library that links liballoc (and documents that it needs it…

> To me, a #![no_std] library is useful for contexts where there isn't a platform libc (embedded systems, kernels, etc.) and you can't assume things like the existence of stdin or processes. "Could be useful for" (FTFY). Unfortunately, for the reasons mentioned above, most #![no_std] libraries aren't useful for that, because they link libc and other libraries. Most people don't do this intentionally. The compiler doe…

No, most #![no_std] libraries do not link libc in the way you describe (having a direct FFI dependency on malloc) - they link liballoc, which has a pluggable allocator interface. On some platforms and some configurations (including most normal userspace platforms), the default allocator used by liballoc uses malloc.

It's actually hard to go out of your way and call malloc directly, because FFI calls are unsafe. It's a lot easier to use Box/Vec/String/etc., all of which are defined in liballoc and use the pluggable allocator interface.

I know this because I've successfully used #![no_std] libraries in places where libc doesn't exist and no function named malloc exists, and they do work. If you're having a linker issue it's almost certainly because you haven't changed the default allocator - if you have an example of this I'd be happy to take a look at debugging it.

Re: Making Rust as Fast as Go

#69

Post by BuckRogers »

geofft wrote: post #29
codeflo wrote: post #24

Earlier quoted context omitted.

That’s true. But going the no_std route is very hard (the ecosystem isn’t big, and relying cargo and crates.io you’re almost guaranteed to link in the std or liballoc by accident at some point). Even when using the std intentionally, I really wouldn’t have expected that basic std functions like println require the libc.

I would not necessarily expect it but I appreciate it in a "systems" language where "systems" is defined as compatible with the existing traditional systems software on a machine. For example, it's nice if the stdbuf(1) command works on Rust binaries on glibc systems, and it's nice if a Rust binary calling a C library that writes with printf (or vice versa) don't maintain two separate output buffers. To me, Go is the…

Is Go widely used compared to the others as a systems language at this point?

Over the years I’ve gathered that it’s more of a competitor for C# & Java rather than Rust & C(++).

Re: Making Rust as Fast as Go

#70

Post by geofft »

codeflo wrote: post #39
geofft wrote: post #27

Earlier quoted context omitted.

To me, a #![no_std] library is useful for contexts where there isn't a platform libc (embedded systems, kernels, etc.) and you can't assume things like the existence of stdin or processes. On those systems, there may still be a dynamic allocator, because that's a super common feature in all but the most spartan environments. For those use cases, a #![no_std] library that links liballoc (and documents that it needs it…

There are lots of tiny practical annoyances you notice, starting with having to vet dependencies and transitive dependency upgrades extremely carefully. A major one is that dev-dependencies are very broken in a no_std environment. It’s obviously useful to have the std in your build.rs script, but unfortunately, Cargo merges dependencies and devDependencies in a way that’s simply incorrect. The good news is that every…

> unfortunately, Cargo merges dependencies and devDependencies in a way that’s simply incorrect.

Yeah, I've run into that, but IIRC this got solved super recently/is being solved. Probably https://github.com/rust-lang/cargo/pull/7820 ?

Post reply on HN