18 ms·

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 s

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_Law https://en.wikipedia.org/wiki/Ward_Cunningham#Cunningham's_L...

masklinn 6y ago
> 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 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.
- deleted 6y ago
  [deleted]
otterley 6y ago
> 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.
- Ar-Curunir 6y ago
  It’s a joke mate
  - arcticbull 6y ago
    Of course, but it chips away at the Overton window, normalizing it.
- arcticbull 6y ago
  "fake news" is an attempt at permanently damaging the American public's faith in the fifth estate. Nobody should ever use that term in the current political climate, ever.
  - deleted 6y ago
    [deleted]
  - FpUser 6y ago
    "damaging the American public's faith" - Really, just the American? You ever realize there are other human species on this planet?
    - arcticbull 6y ago
      That's a fair criticism if clumsily put. For the record, I'm Canadian, British and Polish. I called out America as by far the biggest perpetrator at the moment. So to address the second half of your post, I have indeed heard of "other countries" (just ask USCIS) although being a US resident at the moment I want to speak to what I know, not for anyone else. Though if we're being super pedantic, there's only one human species on this planet -- species of course being defined as animals who can mate and produce viable offspring.
arcticbull 6y ago
Thanks for following up. Just as an FYI, there's a few bugs in your implementation, the most obvious one is the use of ".len()" in a number of places interspersed with ".chars().count()". These two return different values. ".len()" returns then number of UTF-8 bytes in the input string, which for ASCII is the same as ".chars().count()" obviously, but if you do attempt any Unicode characters, your function won't work. ".chars()" provides Unicode Scalar Values (USVs) -- which is a subset of code points, excluding surrogate pairs [1]. Note also this is not the same as a Go rune, which is a code point including surrogate pairs. 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/2ff91041416eeff1b81f624ea585f83a 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. [1] http://www.unicode.org/glossary/#unicode_scalar_value http://www.unicode.org/glossary/#unicode_scalar_value
- arcticbull 6y ago
  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. 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.
  - derefr 6y ago
    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 to the Levenstein distance of a conventional (or explicitly specified) binary encoding of the two strings.

masklinn 6y ago

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

deleted 6y ago
[deleted]

otterley 6y ago

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

Ar-Curunir 6y ago
It’s a joke mate
- arcticbull 6y ago
  Of course, but it chips away at the Overton window, normalizing it.
arcticbull 6y ago
"fake news" is an attempt at permanently damaging the American public's faith in the fifth estate. Nobody should ever use that term in the current political climate, ever.
- deleted 6y ago
  [deleted]
- FpUser 6y ago
  "damaging the American public's faith" - Really, just the American? You ever realize there are other human species on this planet?
  - arcticbull 6y ago
    That's a fair criticism if clumsily put. For the record, I'm Canadian, British and Polish. I called out America as by far the biggest perpetrator at the moment. So to address the second half of your post, I have indeed heard of "other countries" (just ask USCIS) although being a US resident at the moment I want to speak to what I know, not for anyone else. Though if we're being super pedantic, there's only one human species on this planet -- species of course being defined as animals who can mate and produce viable offspring.

arcticbull 6y ago

Thanks for following up. Just as an FYI, there's a few bugs in your implementation, the most obvious one is the use of ".len()" in a number of places interspersed with ".chars().count()". These two return different values. ".len()" returns then number of UTF-8 bytes in the input string, which for ASCII is the same as ".chars().count()" obviously, but if you do attempt any Unicode characters, your function won't work. ".chars()" provides Unicode Scalar Values (USVs) -- which is a subset of code points, excluding surrogate pairs [1]. Note also this is not the same as a Go rune, which is a code point including surrogate pairs. 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/2ff91041416eeff1b81f624ea585f83a 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. [1] http://www.unicode.org/glossary/#unicode_scalar_value http://www.unicode.org/glossary/#unicode_scalar_value

arcticbull 6y ago
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. 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.
- derefr 6y ago
  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 to the Levenstein distance of a conventional (or explicitly specified) binary encoding of the two strings.