Making Rust as Fast as Go • Hacker News Board

Re: Making Rust as Fast as Go

#51

Post by chrfrasco » Sun, May 03, 2020, 3:29 PM UTC

devit wrote: post #47

The main problem is that allocating a vector for each evaluation is completely wrong: instead, it needs to be allocated once by making the function a method on a struct containing a Vec; which makes the allocator moot. 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…

> 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 balloons the runtime from ~2.7s to ~5s:

    let target_chars: Vec = target.chars().collect();
    for (i, source_char) in source.chars().enumerate() {
        let mut next_dist = i + 1;

        for (j, target_char) in target_chars.iter().enumerate()  {

> written mindlessly > incompetence of the person

No challenge there :P I am operating under the assumption that I don't need to understand how compilers work to get good performance from rust (where good is "similar enough to an equivalent go program")

Re: Making Rust as Fast as Go

#52

Post by chrfrasco » Sun, May 03, 2020, 3:39 PM UTC

Hey all, as some keen-eyed commenters have pointed out, it looks like the rust program is not actually equivalent to the go program. The go program parses the string once, while the rust program parses it repeatedly inside every loop. It's quite late in Sydney as I write this so I'm not up for a fix right now, but this post is probably Fake News. The perf gains from jemalloc are real, but it's probably not the allocators fault. I've updated the post with this message as well.

The one-two combo of 1) better performance on linux & 2) jemalloc seeming to fix the issue lured me into believing that the allocator was to blame. I’m not sure what the lesson here is – perhaps more proof of Cunningham’s law? https://en.wikipedia.org/wiki/Ward_Cunningham#Cunningham's_L...

Re: Making Rust as Fast as Go

#53

Post by masklinn » Sun, May 03, 2020, 3:42 PM UTC

ekidd wrote: post #19

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…

As far as I know, the official system interface on Windows and several Unix systems is via the standard library, not via direct syscalls. I don't know about the MacOS. But in general, you may be required to dynamically link the standard library on many platforms. Linux guarantees syscalls are stable. And on Linux, you have the option of telling Rust to cross-compile using a statically-linked musl-libc. (If you also n…

> I don't know about the MacOS.

MacOS literally forbids statically linking to libSystem.

Go finally had to bow down and accept that they just could not perform raw syscalls on MacOS after gettimeofday (IIRC) changed ABI multiple times during the Sierra beta.

Re: Making Rust as Fast as Go

#54

Post by masklinn » Sun, May 03, 2020, 3:48 PM UTC

burntsushi wrote: post #49

devit wrote: post #47

The main problem is that allocating a vector for each evaluation is completely wrong: instead, it needs to be allocated once by making the function a method on a struct containing a Vec; which makes the allocator moot. 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…

> 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 Indeed. This is a pretty damning difference. The `target` string is being repeatedly UTF-8 decoded where as the same is not true in the Go version. The Go version even goes out of its way to do UTF-8 decoding exactly once for each of `source` and `target`, but then doe…

> Indeed. This is a pretty damning difference. The `target` string is being repeatedly UTF-8 decoded where as the same is not true in the Go version. The Go version even goes out of its way to do UTF-8 decoding exactly once for each of `source` and `target`, but then doesn't do the same for the Rust program.

I'm really not sure that's an issue, utf8 decoding is very, very cheap and it's iterating either way.

It would have to be benched, but I wouldn't be surprised if allocating the caches (at least one allocation per line of input) had way more overhead, especially given the inputs are so very short.

I'm not going to claim Rust's utf8 decoder is the fastest around, but it's very fast.

Re: Making Rust as Fast as Go

#55

Post by burntsushi » Sun, May 03, 2020, 3:50 PM UTC

chrfrasco wrote: post #51

devit wrote: post #47

The main problem is that allocating a vector for each evaluation is completely wrong: instead, it needs to be allocated once by making the function a method on a struct containing a Vec; which makes the allocator moot. 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…

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

Re: Making Rust as Fast as Go

#56

Post by burntsushi » Sun, May 03, 2020, 3:53 PM UTC

masklinn wrote: post #54

burntsushi wrote: post #49

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 Indeed. This is a pretty damning difference. The `target` string is being repeatedly UTF-8 decoded where as the same is not true in the Go version. The Go version even goes out of its way to do UTF-8 decoding exactly once for each of `source` and `target`, but then doe…

> Indeed. This is a pretty damning difference. The `target` string is being repeatedly UTF-8 decoded where as the same is not true in the Go version. The Go version even goes out of its way to do UTF-8 decoding exactly once for each of `source` and `target`, but then doesn't do the same for the Rust program. I'm really not sure that's an issue, utf8 decoding is very, very cheap and it's iterating either way. It would…

It's cheap, but not _that_ cheap. It shouldn't be as cheap as just iterating over a sequence of 32-bit integers.

But yes, I did benchmark this, even after reusing allocations, and I can't tell a difference. The benchmark is fairly noisy.

I agree with your conclusion, especially after looking at the input[1]. The strings are so small that the overhead of caching the UTF-8 decoding is probably comparable to the cost of doing UTF-8 decoding.

[1] - https://github.com/christianscott/levenshtein-distance-bench...

Re: Making Rust as Fast as Go

#57

Post by masklinn » Sun, May 03, 2020, 3:54 PM UTC

chrfrasco wrote: post #52

Hey all, as some keen-eyed commenters have pointed out, it looks like the rust program is not actually equivalent to the go program. The go program parses the string once, while the rust program parses it repeatedly inside every loop. It's quite late in Sydney as I write this so I'm not up for a fix right now, but this post is probably Fake News. The perf gains from jemalloc are real, but it's probably not the alloca…

> Hey all, as some keen-eyed commenters have pointed out, it looks like the rust program is not actually equivalent to the go program. The go program parses the string once, while the rust program parses it repeatedly inside every loop. […] The perf gains from jemalloc are real, but it's probably not the allocators fault. I've updated the post with this message as well.

I don't know that it would be a gain: Rust is pretty good at decoding UTF8 quickly given how absolutely fundamental that operation is, and "caching" the decoded data would increase pressure on the allocator.

Unless you also changed the interface of the levenshtein to hand it preallocated cache, source and destination buffers (or the caller did that).

edit: to the downvoter, burntsushi did the legwork of actually looking at this[0] and found caching the decoding to have no effect at best, unless the buffers get lifted out of the function entirely, which matches my comment's expectations.

[0] https://news.ycombinator.com/item?id=23059753

> But yes, I did benchmark this, even after reusing allocations, and I can't tell a difference. The benchmark is fairly noisy.

Re: Making Rust as Fast as Go

#58

Post by ttd » Sun, May 03, 2020, 3:58 PM UTC

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…

Those are two really well written articles -- taking a complicated topic and making it very accessible. Thanks! FWIW I think a companion article on how to effectively use perf for tasks like this would be a great addition, since it can be a bit novice-unfriendly.

Re: Making Rust as Fast as Go

#59

Post by masklinn » Sun, May 03, 2020, 4:02 PM UTC

molf wrote: post #50

devit wrote: post #47

The main problem is that allocating a vector for each evaluation is completely wrong: instead, it needs to be allocated once by making the function a method on a struct containing a Vec; which makes the allocator moot. 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…

> 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 with better support for the workload.

Re: Making Rust as Fast as Go

#60

Post by fluffything » Sun, May 03, 2020, 4:11 PM UTC

geofft wrote: post #27

fluffything wrote: post #17

Earlier quoted context omitted.

> But I’ve also come to the conclusion that Rust relies on libc way too much. How did you come to this conclusion? People using Rust rely on libc a lot. For example, #![no_std] means "no standard-library", but it doesn't mean "no libc, no libunwind, etc.". So a lot of people like to advertise their crates as "#![no_std]" compatible, because they compile with #![no_std], but then the first thing the crate does is link…

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 doesn't complain about:

    #![no_std]
    extern "C" { fn malloc(...) -> ...; }

so when somebody does it accidentally, everything works and they get no feedback.

When you then go and build a #![no_std] binary, and run it in a platform when libc is not available, only then you get an error. And at that point, good luck figuring out which of your 200 dependencies has the error.

In particular, if you are running `#[test]`s, doing that links standard, so if your program implicitly depends on libc somewhere, tests won't reveal that, because while testing, libc will be linked.