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

111–120 of 211 posts

Re: Making Rust as Fast as Go

#111

Post by arcticbull »

earthboundkid wrote: post #73
eis wrote: post #8

Earlier quoted context omitted.

Yep. Here a Go playground example showing that the result is indeed wrong: https://play.golang.org/p/vmctMFUevPc It should output 3 but outputs 5 because each ö is two bytes, len("föö") = 5. I would suggest using "range" to iterate over the unicode characters.

If you diff föö and f though, it correctly gives an edit distance of 2. The code is weird because someone knew enough to convert the strings to slices of runes but not enough to use the rune slices consistently. :-/

Not to mention Rune slices are insufficient for things like Flag emoji and Family emoji, which is going to be a ton of separate runes put together. The latter of which, apparently deletes one family member at a time when you hit "backspace".

Re: Making Rust as Fast as Go

#112

Post by grantwu »

derefr wrote: post #105
arcticbull wrote: post #104

Earlier quoted context omitted.

This doesn't even begin to get into the question of what Levenshtein Distance even means in a Unicode context. What's the Levenshtein Distance of 3 emoji flags? I suppose we should be segmenting by grapheme clusters and utilizing a consistent normalization form when comparing, but Rust has no native support for processing grapheme clusters -- or for normalizations I believe. The UnicodeSegementation crate might help.…

Levenstein (edit) distance is fundamentally an information-theoretical concept defined on bitstreams, as insertions/deletions/swaps of individual bits within a stream. It has a lot in common with error-correcting codes, fountain codes, and compression, which all also operate on bitstreams. Any higher-level abstract mention of Levenstein distances (e.g. of Unicode codepoints) is properly supposed to be taken to refer…

Can you point to a source that defines Levenstein distance as only referring to bitstreams?

A translation of the original article [1] that introduced the concept notes in a footnote that "the definitions given below are also meaningful if the code is taken to mean an arbitrary set of words (possibly of different lengths) in some alphabet containing r letters (r >= 2)".

And if you wish to strictly stick to how it was originally defined, you'd need to only use strings of the same length.

More recent sources [2] say instead "over some alphabet", and even in the first footnote, describe results for "arbitrarily large alphabets"!

[1] https://nymity.ch/sybilhunting/pdf/Levenshtein1966a.pdf

[2] https://arxiv.org/pdf/1005.4033.pdf

Re: Making Rust as Fast as Go

#113

Post by fluffything »

_____smurf_____ wrote: post #106
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…

Given this information, and for general parsing functionalities, which one is faster, Go or Rust?

You can write a parser as far as the limits of your imagination allow in Rust, or C, or any other baremetal language without a thick run-time.

In Go, beyond the limits of your imagination, you'll also hit other limits, like those of the garbage collector.

Re: Making Rust as Fast as Go

#114

Post by fluffything »

dan-robertson wrote: post #85
londons_explore wrote: post #82

Earlier quoted context omitted.

Since min(a, min(b,c)) == min(b, min(a,c)), perhaps the compiler should be smart enough to swap the comparisons around if it makes it quicker?

I suspect that statement is not true for floats. Possibly you don’t get the same float from min(0,-0) as min(-0,0), and similarly with NaNs. Rust specifies that if one input is NaN then the other is returned but doesn’t say what happens if both are NaN.

> Rust specifies that if one input is NaN then the other is returned but doesn’t say what happens if both are NaN.

It does. If both are NaN a NaN is returned. Note, however, that when Rust says that a NaN is returned, this means that any NaN can be returned. So if you have min(NaN0, NaN0) the result isn't necessarily NaN0, it might be another NaN with a different payload.

Re: Making Rust as Fast as Go

#115

Post by fluffything »

londons_explore wrote: post #109
dan-robertson wrote: post #85

Earlier quoted context omitted.

I suspect that statement is not true for floats. Possibly you don’t get the same float from min(0,-0) as min(-0,0), and similarly with NaNs. Rust specifies that if one input is NaN then the other is returned but doesn’t say what happens if both are NaN.

NaN's are rarely required on the fast path of any code... The compiler ought to make a 2nd slow implementation for if any NaNs are seen.

Sure, but then it needs to add a branch to detect the inputs, and maybe keep around some state to switch between implementations at run-time.

Its far from clear that doing that is, in general, worth it.

Re: Making Rust as Fast as Go

#116

Post by fluffything »

arcticbull wrote: post #108
molf wrote: post #3

The Rust version uses `target.chars().count()` to initialise the cache, while the Go version counts up to `len(target)`. These are not equivalent: the Rust version counts Unicode code points, the Go version counts bytes. I am confused by the implementations, although I have not spent any time testing them. Both versions contain a mix of code that counts bytes (`.len()` and `len(...)`) and Unicode code points (`chars(…

Go's version and the Rust version differ in yet more subtle ways. It appears that Go's "rune" type is a Code Point, but Rusts's "char" type is a Unicode Scalar Value, a subset of Code Point that excludes surrogate pairs. Both versions will not work with complex Unicode input unless you perform both segmentation by Grapheme Cluster [1] and utilize a consistent Normalization [2] when comparing clusters. Unicode is hard…

> Both versions will not work with complex Unicode input unless you perform both segmentation by Grapheme Cluster [1] and utilize a consistent Normalization [2] when comparing clusters

Doing this is quite easy from Rust.

Re: Making Rust as Fast as Go

#117

Post by arcticbull »

blablabla123 wrote: post #94
ishanjain28 wrote: post #64

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

I'd be really surprised to hear that Go is supposed to be faster than Rust. Of course Rust is a bit newer but to me it always sounded like Go is fast because it's static but it doesn't have to be high-speed if that would sacrifice conciseness. Given that this is an artifical example, this here looks more realistic: https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

Rust and Go are contemporaries. Rust started in 2006 at Mozilla, and the first Go public release from Google was in 2009, meaning it probably started at the same time.

Except of course all the Plan 9 garbage (like Go's hand-rolled assembler) brought in to underpin Go from the 80s ;)

Re: Making Rust as Fast as Go

#118

Post by fluffything »

geofft wrote: post #68
fluffything wrote: post #60

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

> and they do work.

Maybe you are just using different no_std libraries that I am using, but pretty much all of the no_std libraries that I use have `libc` as a direct dependency.

Not only for malloc, many of them just needs to write something to stdout or a file, generate random numbers, ..., and that's hard to do without libc. Why they advertise themselves as no_std escapes my comprehension.

Re: Making Rust as Fast as Go

#119

Post by arcticbull »

_____smurf_____ wrote: post #106
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…

Given this information, and for general parsing functionalities, which one is faster, Go or Rust?

As always, it depends on what your goals are. String processing is usually not the long pole when you're building something that consumes the output of a parser. Based on micro and macro benchmarks, Rust is typically substantially faster than Go and pretty much always uses less RAM [1].

But again, depends what you're doing with the output, and if these deltas even matter in your context.

[1] https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

Re: Making Rust as Fast as Go

#120

Post by arcticbull »

fluffything wrote: post #116
arcticbull wrote: post #108

Earlier quoted context omitted.

Go's version and the Rust version differ in yet more subtle ways. It appears that Go's "rune" type is a Code Point, but Rusts's "char" type is a Unicode Scalar Value, a subset of Code Point that excludes surrogate pairs. Both versions will not work with complex Unicode input unless you perform both segmentation by Grapheme Cluster [1] and utilize a consistent Normalization [2] when comparing clusters. Unicode is hard…

> Both versions will not work with complex Unicode input unless you perform both segmentation by Grapheme Cluster [1] and utilize a consistent Normalization [2] when comparing clusters Doing this is quite easy from Rust.

There's no standard library API in Rust for either grapheme cluster segmentation or for normalization. You'd need a third-party crate, at which point it's less "easy in Rust" and more "someone did the hard work for you" because, its really not easy anywhere haha.
Post reply on HN