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

81–90 of 211 posts

Re: Making Rust as Fast as Go

#81

Post by apta »

geofft wrote: post #72
BuckRogers wrote: post #69

Earlier quoted context omitted.

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

Depends what you mean by "systems language" (many common definitions turn out to be equivalent to "drop-in replacement for the platform language," which makes the argument circular), but the choice of Go as an implementation language for Docker and Kubernetes puts it pretty firmly in the "systems language" space IMO. Container management requires more systems-level functionality than C# and Java are really geared tow…

The original version of Docker was written in Python, and the original version of Kubernetes was written in Java, so your argument doesn't hold.

Re: Making Rust as Fast as Go

#82

Post by londons_explore »

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…

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?

Re: Making Rust as Fast as Go

#83

Post by savaki »

A few folks have commented that there were logic errors in the Go version. Specifically that

  len("föö") = 5
should instead have returned

  len("föö") = 3
I submitted a pull request, https://github.com/christianscott/levenshtein-distance-bench..., that fixes these issues in the Go implementation.

Interestingly enough, when I re-ran the benchmark, the Go version is roughly 19% faster than it was previously:

  old: 1.747889s
  new: 1.409262s (-19.3%)

Re: Making Rust as Fast as Go

#84

Post by otterley »

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…

> this post is probably Fake News

It's not Fake News. Fake News is the publication of intentionally false stories. This is just erroneous.

There's a yawning chasm between the two.

Re: Making Rust as Fast as Go

#85

Post by dan-robertson »

londons_explore wrote: post #82
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…

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.

Re: Making Rust as Fast as Go

#86

Post by [deleted] »

londons_explore wrote: post #82
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…

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?

[deleted]

Re: Making Rust as Fast as Go

#87

Post by burntsushi »

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…

Note that using bytes is a fundamentally different implementation that will produce different results on non-ASCII input. Using codepoints (or "runes") will better approximate edit distance based on visual characters. (And grapheme clusters would be even better. Although one could put the text in composed normal form to get more mileage out of the rune based algorithm.)

Re: Making Rust as Fast as Go

#88

Post by matklad »

drfuchs wrote: post #80
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…

Very few things have ever been measured accurately to ten significant digits. How much did these numbers change run to run? How many measurements did you take? Were the caches warmed up similarly? Still, point taken.

The excessive "precision" is because I've just copy-pasted what the original bench printed.

As for "is this a reliable result", I believe I've performed diligence, appropriate for a HN comment, to make sure that this is not a completely random result. As I've said, I did not investigate this particular bit of code thoroughly. You are welcome to read the linked blog posts, which study the issue in depth.

Re: Making Rust as Fast as Go

#89

Post by arcticbull »

londons_explore wrote: post #82
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…

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?

Part of the problem may be they re-implemented `std::cmp::min` at the bottom of the file, I wonder if there's a more optimized version in the stdlib.

Re: Making Rust as Fast as Go

#90

Post by gpm »

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.

Hmm, not sure what the llvm semantics look like, but you're right about the assembly semantics, vminsd (the instruction used in the post) is unfortunately not symettric in it's handling on NaN.

https://www.felixcloutier.com/x86/minsd

Post reply on HN