12 ms·

For those curious about Rust optimization, the “optimized” version makes three changes compared to the “idiomatic” version: * It uses byte strings instead of U

For those curious about Rust optimization, the “optimized” version makes three changes compared to the “idiomatic” version: * It uses byte strings instead of UTF-8 strings. In my opinion, that’s not an optimization, that’s changing the problem. Depending on the question you’re asking, only one of the two can be correct. * It uses a faster hash algorithm. It’s not the first time this came up in a benchmark article. Rust’s decision to use a DOS-safe hash by default (and not provide a fast algorithm in the std, like other languages do) really seems to hurt it in that kind of microbenchmark. * It uses get_mut+insert instead of the more convenient HashMap::entry method, because the latter would require redundantly allocating the key even in the repeat case. I’ve hit this problem in the past as well. Maybe the upcoming HashMap::raw_entry_mut will make this kind of optimization cleaner.

coldtea 4y ago
>It uses byte strings instead of UTF-8 strings. In my opinion, that’s not an optimization, that’s changing the problem. Depending on the question you’re asking, only one of the two can be correct. For tons of questions, both can be correct.
tialaramex 4y ago
The problem specified declares the words we're counting are ASCII: > ASCII: it’s okay to only support ASCII for the whitespace handling and lowercase operation UTF-8 (quite deliberately) is a superset of ASCII. So a UTF-8 solution is correct for ASCII, but a bytes-as-ASCII solution works fine in Rust if you only need ASCII. This is why Rust provides ASCII variants of a lot of functions on strings, and the same functions are available on byte slices [u8] where ASCII could be what you have (whereas their Unicode cousins are not available on byte slices).
- codeflo 4y ago
  >> ASCII: it’s okay to only support ASCII for the whitespace handling and lowercase operation That's a somewhat specific list -- at least I didn't read that as a general "the program can assume that the input is only ASCII". But then, the author seems to have accepted solutions that crash on non-UTF8 sequences and ones that byte-compare them, so probably either behavior was meant to be fine. I just don't get that from this rule.
  - anonymoushn 4y ago
    > That's a somewhat specific list -- at least I didn't read that as a general "the program can assume that the input is only ASCII". I don't think it assumes the input is only ASCII. If the problem is "given UTF-8 text, split on ASCII whitespace and convert ASCII uppercase letters to lowercase," you can do that correctly (and produce correct UTF-8 output) without really being UTF-8 aware. For why, see here: https://en.wikipedia.org/wiki/UTF-8#Encoding https://en.wikipedia.org/wiki/UTF-8#Encoding > But then, the author seems to have accepted solutions that crash on non-UTF8 sequences and ones that byte-compare them, so probably either behavior was meant to be fine. I just don't get that from this rule. That's a separate concern right? The rules are only about the behavior when the program is given UTF-8 input.
    - nerdponx 4y ago
      The issue is that this is a weird requirement. I have seen real world data sets that had all manner of exotic whitespace like nonbreaking spaces and vertical tabs peppered throughout, so I am sympathetic. But this situation isn't common. That said, for a CLI program like this, usually approximate results are good enough anyway. And realistically, most text should use ASCII whitespace for pretty much all text.
      - anonymoushn 4y ago
        It is a context-specific requirement, but "fully general lowercasing" would be an impossible requirement. For e.g. Japanese text, I think you'd only have to add 1 or 2 characters to the set of whitespace characters. You also have to solve Japanese text segmentation, which is hard-to-impossible. If you want to canonicalize the words by transforming half-width katakana to full-width, transforming full-width romaji to ascii, etc., that's a lot of work, and which of those transformations are desired will be specific to the actual use of the program. If you want to canonicalize the text such that the same word written using kanji or using only hiragana end up in the same bucket, or that words that are written the same way in hiragana but written differently when using kanji end up in different buckets, or that names that are written the same way in kanji but written differently in hiragana end up in different buckets, or that loanwords incorrectly written using hiragana are bucketed with the katakana loanword, or that words written using katakana for emphasis are bucketed with the hiragana word (but katakana loanwords are not converted to hiragana and bucketed with the non-loanword that is made up of the same moras), well, that all sounds even more challenging than the hard-to-impossible problem you already had to solve to decide where words begin and end :) Edit: One of the first concerns I mentioned, about full width romaji and half width katakana, and additionally concerns about diacritics, can be addressed using unicode normalization, so these things are pretty easy[0]. An issue you may still face after normalizing is that you may receive inputs that have incorrectly substituted tsu ツ for sokuon ッ (these are pronounced differently), because for example Japanese banking software commonly transmits people's names using a set of characters that does not include sokuon. My point is that this is not just a hard problem but many different, incompatible problems, many of which are hard, and because of the incompatibilities you have to pick one and give up on the others. An English-speaking end user may not want their wordcount to perform full width romaji -> ascii conversion. [0]: https://towardsdatascience.com/difference-between-nfd-nfc-nfkd-and-nfkc-explained-with-python-code-e2631f96ae6c https://towardsdatascience.com/difference-between-nfd-nfc-nf...
saghm 4y ago
> It uses byte strings instead of UTF-8 strings. In my opinion, that’s not an optimization, that’s changing the problem. Depending on the question you’re asking, only one of the two can be correct. Sure, but is it changing the problem to something easier than what the other languages are already doing, or to something more similar? I'd imagine the C code is basically just using byte arrays as well, for instance.
SAI_Peregrinus 4y ago
The question as posed only cares about ASCII.
olalonde 4y ago
> * It uses byte strings instead of UTF-8 strings. In my opinion, that’s not an optimization, that’s changing the problem. Depending on the question you’re asking, only one of the two can be correct. To be fair, that's what the C version does as well.
stewbrew 4y ago
Ad uft8: it would change the problem only if the definition of word breaks changed. E.g., if a word break is defined by whitespace, then it probably doesn't.
- Conlectus 4y ago
  What happens when the ASCII character for space is embedded within a multibyte UTF-8 codepoint?
  - anyfoo 4y ago
    If UTF-8 allowed that, then a solution would split words wrong according to UTF-8 rules, but it still would not matter, since the problem statement says that "it's okay to only support ASCII for the whitespace handling and lowercase operation". So if your solution gets word splitting (or lowercasing) wrong for non-ASCII input, it still gets a pass according to my reading.
  - kd5bjo 4y ago
    UTF-8 is designed so that this doesn’t happen: All bytes in a multibyte codepoint have the high bit set, placing them outside of the ASCII range.
  - bitwize 4y ago
    This never happens. In UTF-8, bit 7 is set in all valid multibyte representations; ASCII characters cannot appear in them. Now, you can have an ASCII character in the middle of a multibyte sequence, but this isn't valid UTF-8 (and should be treated as an error by the decoder). "Words" generated by a splitter would also have invalid UTF-8 if they were split on a space coming in between bytes in a multibyte sequence, but these can detected. Word splitting will not generate invalid words from valid input, or vice versa; and if you know you have valid input, splitting on space, \t, \n, \r, etc. is perfectly cromulent in UTF-8. Now if you want to also split on U+200B (ZERO WIDTH SPACE), U+202F (NARROW NO-BREAK SPACE), etc... hoo boy.
  - Kiwikwi 4y ago
    Such "overlong" encodings are not valid UTF-8.
burntsushi 4y ago
> It uses byte strings instead of UTF-8 strings. In my opinion, that’s not an optimization, that’s changing the problem. Depending on the question you’re asking, only one of the two can be correct. No, that's very wrong. ripgrep has rich Unicode support for example, but represents file contents as byte strings. UTF-8 strings vs byte strings is an implementation detail. I think you might benefit from reading the "bonus" Rust submission: https://github.com/benhoyt/countwords/blob/8553c8f600c40a4626e966bc7e7e804097e6e2f4/rust/bonus/main.rs https://github.com/benhoyt/countwords/blob/8553c8f600c40a462... IMO, Ben kind of glossed over the bonus submission. But I personally think it was the biggest point in favor of Rust for a real world version of this task.

coldtea 4y ago

tialaramex 4y ago

The problem specified declares the words we're counting are ASCII: > ASCII: it’s okay to only support ASCII for the whitespace handling and lowercase operation UTF-8 (quite deliberately) is a superset of ASCII. So a UTF-8 solution is correct for ASCII, but a bytes-as-ASCII solution works fine in Rust if you only need ASCII. This is why Rust provides ASCII variants of a lot of functions on strings, and the same functions are available on byte slices [u8] where ASCII could be what you have (whereas their Unicode cousins are not available on byte slices).

codeflo 4y ago
>> ASCII: it’s okay to only support ASCII for the whitespace handling and lowercase operation That's a somewhat specific list -- at least I didn't read that as a general "the program can assume that the input is only ASCII". But then, the author seems to have accepted solutions that crash on non-UTF8 sequences and ones that byte-compare them, so probably either behavior was meant to be fine. I just don't get that from this rule.
- anonymoushn 4y ago
  > That's a somewhat specific list -- at least I didn't read that as a general "the program can assume that the input is only ASCII". I don't think it assumes the input is only ASCII. If the problem is "given UTF-8 text, split on ASCII whitespace and convert ASCII uppercase letters to lowercase," you can do that correctly (and produce correct UTF-8 output) without really being UTF-8 aware. For why, see here: https://en.wikipedia.org/wiki/UTF-8#Encoding https://en.wikipedia.org/wiki/UTF-8#Encoding > But then, the author seems to have accepted solutions that crash on non-UTF8 sequences and ones that byte-compare them, so probably either behavior was meant to be fine. I just don't get that from this rule. That's a separate concern right? The rules are only about the behavior when the program is given UTF-8 input.
  - nerdponx 4y ago
    The issue is that this is a weird requirement. I have seen real world data sets that had all manner of exotic whitespace like nonbreaking spaces and vertical tabs peppered throughout, so I am sympathetic. But this situation isn't common. That said, for a CLI program like this, usually approximate results are good enough anyway. And realistically, most text should use ASCII whitespace for pretty much all text.
    - anonymoushn 4y ago
      It is a context-specific requirement, but "fully general lowercasing" would be an impossible requirement. For e.g. Japanese text, I think you'd only have to add 1 or 2 characters to the set of whitespace characters. You also have to solve Japanese text segmentation, which is hard-to-impossible. If you want to canonicalize the words by transforming half-width katakana to full-width, transforming full-width romaji to ascii, etc., that's a lot of work, and which of those transformations are desired will be specific to the actual use of the program. If you want to canonicalize the text such that the same word written using kanji or using only hiragana end up in the same bucket, or that words that are written the same way in hiragana but written differently when using kanji end up in different buckets, or that names that are written the same way in kanji but written differently in hiragana end up in different buckets, or that loanwords incorrectly written using hiragana are bucketed with the katakana loanword, or that words written using katakana for emphasis are bucketed with the hiragana word (but katakana loanwords are not converted to hiragana and bucketed with the non-loanword that is made up of the same moras), well, that all sounds even more challenging than the hard-to-impossible problem you already had to solve to decide where words begin and end :) Edit: One of the first concerns I mentioned, about full width romaji and half width katakana, and additionally concerns about diacritics, can be addressed using unicode normalization, so these things are pretty easy[0]. An issue you may still face after normalizing is that you may receive inputs that have incorrectly substituted tsu ツ for sokuon ッ (these are pronounced differently), because for example Japanese banking software commonly transmits people's names using a set of characters that does not include sokuon. My point is that this is not just a hard problem but many different, incompatible problems, many of which are hard, and because of the incompatibilities you have to pick one and give up on the others. An English-speaking end user may not want their wordcount to perform full width romaji -> ascii conversion. [0]: https://towardsdatascience.com/difference-between-nfd-nfc-nfkd-and-nfkc-explained-with-python-code-e2631f96ae6c https://towardsdatascience.com/difference-between-nfd-nfc-nf...

saghm 4y ago

> It uses byte strings instead of UTF-8 strings. In my opinion, that’s not an optimization, that’s changing the problem. Depending on the question you’re asking, only one of the two can be correct. Sure, but is it changing the problem to something easier than what the other languages are already doing, or to something more similar? I'd imagine the C code is basically just using byte arrays as well, for instance.

SAI_Peregrinus 4y ago

The question as posed only cares about ASCII.

olalonde 4y ago

> * It uses byte strings instead of UTF-8 strings. In my opinion, that’s not an optimization, that’s changing the problem. Depending on the question you’re asking, only one of the two can be correct. To be fair, that's what the C version does as well.

stewbrew 4y ago

Ad uft8: it would change the problem only if the definition of word breaks changed. E.g., if a word break is defined by whitespace, then it probably doesn't.

Conlectus 4y ago
What happens when the ASCII character for space is embedded within a multibyte UTF-8 codepoint?
- anyfoo 4y ago
  If UTF-8 allowed that, then a solution would split words wrong according to UTF-8 rules, but it still would not matter, since the problem statement says that "it's okay to only support ASCII for the whitespace handling and lowercase operation". So if your solution gets word splitting (or lowercasing) wrong for non-ASCII input, it still gets a pass according to my reading.
- kd5bjo 4y ago
  UTF-8 is designed so that this doesn’t happen: All bytes in a multibyte codepoint have the high bit set, placing them outside of the ASCII range.
- bitwize 4y ago
  This never happens. In UTF-8, bit 7 is set in all valid multibyte representations; ASCII characters cannot appear in them. Now, you can have an ASCII character in the middle of a multibyte sequence, but this isn't valid UTF-8 (and should be treated as an error by the decoder). "Words" generated by a splitter would also have invalid UTF-8 if they were split on a space coming in between bytes in a multibyte sequence, but these can detected. Word splitting will not generate invalid words from valid input, or vice versa; and if you know you have valid input, splitting on space, \t, \n, \r, etc. is perfectly cromulent in UTF-8. Now if you want to also split on U+200B (ZERO WIDTH SPACE), U+202F (NARROW NO-BREAK SPACE), etc... hoo boy.
- Kiwikwi 4y ago
  Such "overlong" encodings are not valid UTF-8.

burntsushi 4y ago

> It uses byte strings instead of UTF-8 strings. In my opinion, that’s not an optimization, that’s changing the problem. Depending on the question you’re asking, only one of the two can be correct. No, that's very wrong. ripgrep has rich Unicode support for example, but represents file contents as byte strings. UTF-8 strings vs byte strings is an implementation detail. I think you might benefit from reading the "bonus" Rust submission: https://github.com/benhoyt/countwords/blob/8553c8f600c40a4626e966bc7e7e804097e6e2f4/rust/bonus/main.rs https://github.com/benhoyt/countwords/blob/8553c8f600c40a462... IMO, Ben kind of glossed over the bonus submission. But I personally think it was the biggest point in favor of Rust for a real world version of this task.