Rust does this
next_dist = std::cmp::min(
dist_if_substitute,
std::cmp::min(dist_if_insert, dist_if_delete),
);
nextDist = min(
distIfDelete,
min(distIfInsert, distIfSubstitute)
)
I haven't investigated this, but I would guess that this is the same effect I've observed in
* https://matklad.github.io/2017/03/12/min-of-three.html
* https://matklad.github.io/2017/03/18/min-of-three-part-2.htm...
(reposting my comment from reddit, as it's a rather unexpected observation)
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/...
In Go, beyond the limits of your imagination, you'll also hit other limits, like those of the garbage collector.
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.
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...
Secondly, you re-implemented "std::cmp::min" at the bottom of the file, and I'm not sure if the stdlib version is more optimized.
Lastly, well, you caught the issue with repeated passes over the string.
I've fixed the issues if you're curious: https://gist.github.com/martinmroz/2ff91041416eeff1b81f624ea...
Unrelated, I hate the term "fake news" as it's an intentional attempt to destroy the world public's faith in news media. It's a cancer on civilized society. Somewhere your civics teacher is crying into some whiskey, even though of course you're joking.
Based on some cursory research, the go version differs in a more subtle way too. A Rune is a Code Point, which is a superset of the Rust "char" type; it includes surrogate pairs.
If we (correctly) rely on the media to bring to public attentions relevant facts (both criminal and non-criminal) and keep a watchful eye on the nation who then keeps a watchful eye on the media?
is the model entirely based on always being there enough good journalist to spot the bad ones? how is this affected by the very precarious economics of current internet ads-based venture-funded media enterprises?
I just blurted too many questions... what I am trying to say is that similarly with the police there is not as easy answer in shoud-trust should-not-trust (in the US a supreme Court judge advised to "not talk to the police").
in that case I guess part of the problem is that the job of the police can be miscontrued as "arresting people". in the same way the job of a journalist can be miscontrued as "getting clicks"
overall I don't think we can pass an a priori moral judgement on that term, as essentially represent a statement that the default safety measures have failed.
(I want to reiterate that here I try not to intermingle my point with whether I believe or not that the current use is warranted, I am just trying to say that as a concept it needs to be part of an healthy democracy, the same as some distrust in electoral promises)
Common examples:
* Look at this dank "meme".
meme has come to mean "a picture shared on the internet that has words on it".
* Let's [have a] "cheers".
It's a toast. You say "cheers" when you toast.
* You missed Suzie and I's party last night.
It's Suzie and my party. This one is particularly annoying because it's made it way past editors and into writing, screenplay, etc.
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.
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.
When news organizations take other news organizations word for it and the story is false, that's fake news. We called it something different back then, but fake news led to the invasion of Iraq. Negligence is sufficient for fake news, malice not required.
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()` and `[]rune(...)`). My guess is that the implementation might not work correctly for certain non-ASCII strings, but I have not verified this.
Of course, if only ASCII strings are valid as input for this implementation then both versions will be a lot faster if they exclusively operate on bytes instead.
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.
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. :-/
I was a bit suspicious of the conclusion, but didn’t dig in myself. I imagine this would be a much larger source of difference.
edit: and if I switch to source.bytes().enumerate() it drops by 20% more
Unicode is hard, fams, and it's rare that anything that looks easy is actually what you want.
Doing this is quite easy from Rust.
cache := make([]int, len(targetChars)+1)
for i := 0; i < len(targetChars)+1; i++ {
cache[i] = i
}
1) incorrect if UTF-8-strings are supposed to be valid input, or
2) very inefficient if only ASCII-strings are supposed to be valid input.
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.
Except of course all the Plan 9 garbage (like Go's hand-rolled assembler) brought in to underpin Go from the 80s ;)
My understanding is that Go doesn’t use the libc at all and makes system calls directly, which IMO is the correct decision in a modern systems programming language that doesn’t want to be limited by 40 years of cruft.
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 need to statically link OpenSSL or a few other common libraries, I maintain https://github.com/emk/rust-musl-builder, and there's at least one similar image out there.)
> On macOS and iOS, the runtime now uses libSystem.dylib instead of calling the kernel directly. This should make Go binaries more compatible with future versions of macOS and iOS. The syscall package still makes direct system calls; fixing this is planned for a future release.
Source: https://golang.org/doc/go1.11
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.
C library => kernel32.dll => ntdll.dll => system calls
You don’t have to go via the C library - calling kernel32 directly is fine (I believe this is what Go does). However, it’s very rare to call ntdll or to make system calls directly.
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 linking against libc, against liballoc, against libm, .... or even the standard library itself...
So... if you are trying to build a binary that does not depend on libc or libstd, then there is no language feature to help you there.
#[no_std] binaries are not only unstable, but also probably not what you want, since that won't prevent you from linking any library that links libc, or the standard library, etc.
If you want to avoid libc, you have to enforce that, e.g., by checking in your build system that your binary doesn't contain any libc, libstd, etc. symbols (I just use nm for this). #![no_std] helps a bit here, but making sure you don't link any library that violates this is up to you.
The only case I think I've seen where a #![no_std] library ends up pulling in libc is if you haven't added a custom allocator and your platform's default allocator uses libc (and so you could switch to a libc-free allocator if you want). Are there other cases?
> My understanding is that Go doesn’t use the libc at all and makes system calls directly
Actually, the only system on which it's fine to "not use the libc at all and make system calls directly" is Linux. On MacOS, Windows, and most non-Linux Unix-like systems, you must to go through the libc or its equivalent (which on Windows is kernel32.dll and/or ntdll.dll), since the system call interface is unstable (the libc or its equivalent is distributed together with the kernel, so it's updated whenever the system call interface changes).
AFAIK, Go tried for a while to use system calls directly on MacOS; after being broken several times by operating system updates, they gave up and now go through the shared libraries like everyone else. They still insist on using direct system calls on Linux, where it works mostly fine (except for things like the DNS resolver, in which AFAIK they try to guess whether they can do directly network DNS requests, or have to go through libc; and that one time in which Go's small stacks conflicted with a misoptimized kernel VDSO using too much stack).
Edit: Not even the DLL name of Microsoft’s libc is stable (msvcrt140.dll etc.), leading to all kinds of wild goose chases when trying to run old binaries.
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
For instance, this code:
package main
import "net"
func main(){
net.Dial("tcp", "golang.org:80")
}
linux-vdso.so.1 (0x00007ffe3d7f0000)
libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007fc7ac05a000)
libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fc7abc69000)
/lib64/ld-linux-x86-64.so.2 (0x00007fc7ac279000)
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.
Furthermore the code rereads cache[j] instead of storing the previous value, and doesn't do anything to make sure that bound checks are elided in the inner loop (although perhaps the compiler can optimize that).
The code for computing the min seems to have been written mindlessly rather than putting serious thought towards whether to have branches or not and in what order (depending on an analysis of what the branch directions rates would be).
Implausible benchmark results are almost always an indicator of the incompetence of the person performing the benchmark.
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.
> Implausible benchmark results are almost always an indicator of the incompetence of the person performing the benchmark.
Come on. We can do better than this. Please don't make it personal. We all have to learn things at some point.
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.
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<char> = 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() {
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")
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...
An ad hominem attack surely isn't needed.
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.
#!/usr/bin/env bash
set -e
run() {
cargo build --release 2> /dev/null
./target/release/rust
}
run;
EDIT: I was just being stupid, don't mind me. The times were taken within each language and not externally.
Further, each time you call `.chars().count()` the entire string is re-enumerated at Unicode character boundaries, which is O(n) and hardly cheap, hence wrapping it in an iterator over char view.
Also, re-implementing std::cmp::min at the bottom there may well lead to a missed optimization.
Anyways, I cleaned it up here in case the author is curious: https://gist.github.com/martinmroz/2ff91041416eeff1b81f624ea...
So a solid ~15% by changing the allocator to jemalloc.
However, I now have a segfault w/o a stack trace when the data gets written at the end of the process.
Possibly something fishy in some `unsafe{}` code of a dependent crate of mine that the different allocator exposed. :]
Still – no stack trace at all is very strange in Rust when one runs a debug build with RUST_BACKTRACE=full.
[1] https://github.com/virtualritz/rust-diffusion-limited-aggreg...
Eg.:
> rdla dump foo.nsi
Is there a jemallocator ticked where to attach a report for this?
With Rust, you have much more control, but you also need a deep understanding of the language to get the most out of it. With Go, the way you think it should work is usually is Good Enough™.
The main area I'd expect to see performance benefits for rust (though I don't have experience here) is larger rust programs. Rust's zero-cost abstractions have more benefits as the abstractions nest more deeply. For a small program, you don't really have a lot of abstractions, so Go will do just fine.
I think Go has a number of nice performance tricks up it's sleeve, though, so I wouldn't rule out Go on performance grounds too quickly.
len("föö") = 5
len("föö") = 3
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%)The speed difference came from the allocator.
Rust switched from jemalloc to the system allocator per ticket #36963[0] for various reasons (like binary bloat, valgrind incompatibility, etc...).
Go uses a custom allocator[1] instead.
To make 'Rust Go fast' (pun intended), one can use the '#[global_allocator]' to use a custom allocator (in this case, with the jemallocator crate) to make allocations fast again.
edit: this has been pointed out as incorrect, Go ints are 8 bytes on 64bit systems -- thanks for the correction!
let mut cache: Vec<usize> = (0..=target.chars().count()).collect();
let mut cache: Vec<usize> = vec![0; target.len()];
cache := make([]int, len(target)+1)
for i := 0; i < len(target)+1; i++ {
cache[i] = i
}
So between doing more work and worse cache usage, it wouldn't be surprising if the Rust version was slower even with the faster allocator.