4 ms·

Fun fact: Gnu grep is slow at UTF8. Try time LANG=C grep asdf < les_misérables.txt > /dev/null versus time LANG=en_US.UTF-8 grep asdf < les_misérables.tx

by p9idf 15y ago

Fun fact: Gnu grep is slow at UTF8. Try time LANG=C grep asdf < les_misérables.txt > /dev/null versus time LANG=en_US.UTF-8 grep asdf < les_misérables.txt > /dev/null

_delirium 15y ago
Hmm, strange. One of the stated design features of UTF-8 was that Boyer-Moore could still be directly applied (http://www.ietf.org/rfc/rfc2279.txt http://www.ietf.org/rfc/rfc2279.txt). Is grep doing something unnecessarily suboptimal here, or is that RFC's comment correct but not the whole story?
- Sharlin 15y ago
  The problem is probably that deciding whether two Unicode characters (where one character may be composed of multiple code points) are equivalent in general case is MUCH more involved than doing a simple byte comparison. http://en.wikipedia.org/wiki/Unicode_equivalence http://en.wikipedia.org/wiki/Unicode_equivalence
  - _delirium 15y ago
    True, but in the special case where your search string is composed entirely of 7-bit ASCII characters (the characters representable as 1-byte in UTF-8), like the example, shouldn't the character-equivalence logic still be easy?
    - Someone 15y ago
      I do not think that accented e is a 7-bit ASCII character. Even if it is, the text being searched may contain the character coded as a multi-byte sequence.
      - _delirium 15y ago
        That was just in the filename; the search string in the example is 'asdf'. And UTF-8 I believe is purposely designed so that 7-bit ASCII characters can't appear anywhere else in the stream except when representing themselves (even as part of multibyte characters)--- every other byte in a UTF-8 stream must have the high-order bit set. My guess is that p9idf has it right, and grep is just converting everything to wchar_t first, rather than trying to do any sort of clever searching directly on the UTF-8 byte stream.
        forgotusername 15y ago
        There's nothing to prevent this from being implemented, other than it'd be a huge hacky mess. It would require sidestepping iconv (or however grep does it) when LC_ALL is one of a specific set of strings, activating some special cases, and then additionally, building on those special cases, further scanning the input pattern (which may not just be a literal string - how might this work with character classes/ranges?) to ensure it is 7bit, in order to achieve the desired speedup. Or if your input data is sufficiently ASCII-ish, and so is your search pattern, then why not just force the process locale to C and avoid the whole mess to begin with. I'm suddenly left wondering how the "." regex syntax functions in the face of surrogates when handling UTF-8.
        Someone 15y ago
        Oops. I sort-of guessed at what the example was about, and did not read it. However, if you find four bytes 'asdf' in the input, you still have to check whether a combining mark follows the 'f'. For this example, that is simple, but I guess things get hairy for many regexes found in real life, such as ones containing even a single period.
    - btilly 15y ago
      Not unless you are explicitly told that it is composed entirely of 7-bit ASCII characters. The UTF standard used to allow non-conformant representations of ASCII characters. As http://www.schneier.com/crypto-gram-0008.html http://www.schneier.com/crypto-gram-0008.html notes, this lead to security problems. Now the standard says that you can't allow non-conformant representations of ASCII characters. And if you look at http://www.unicode.org/versions/Unicode6.0.0/ch03.pdf http://www.unicode.org/versions/Unicode6.0.0/ch03.pdf and scroll to page 94 you'll find that you can't be said to be conformant unless you explicitly reject non-conforming input. Therefore UTF-8 decoders cannot be considered conformant unless they actually examine each and every byte to verify that there is nothing dodgy.
- p9idf 15y ago
  The rumor is that Gnu grep does a slow conversion of each input character into a wchar_t. I haven't personally read the code and verified it, but I consider the following sources reliable enough to believe it. http://9fans.net/archive/?q=%27gnu+grep%27+UTF-8+malloc&go=Grep http://9fans.net/archive/?q=%27gnu+grep%27+UTF-8+malloc&...
dfc 15y ago
What version of grep are you using? Not too long ago the grep in debian/unstable was awful with UTF strings. pg135.txt is project gutenberg's les mis. What were your times? I no longer notice this behavior: dfc@motherjones:~$ grep --version grep (GNU grep) 2.9 dfc@motherjones:~$ time LANG=C grep asdf < pg135.txt > /dev/null real 0m0.017s user 0m0.008s sys 0m0.004s dfc@motherjones:~$ time LANG=UTF8 grep asdf < pg135.txt > /dev/null real 0m0.017s user 0m0.012s sys 0m0.004s dfc@motherjones:~$ time LANG=en_us.UTF8 grep asdf < pg135.txt > /dev/null real 0m0.012s user 0m0.004s sys 0m0.004s There is not a lot of info about this in debian bug 604408 http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=604408 http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=604408 If memory serves me correctly this upstream fixed this sometime after 2.7.1 or 2.7.3 Funner fact: GNU grep used to be slow with UTF.
- p9idf 15y ago
  ; grep --version GNU grep 2.5.3 ; time LANG=C grep asdf < lesms10.txt > /dev/null real 0m0.025s user 0m0.011s sys 0m0.014s ; time /usr/local/plan9/bin/grep asdf < lesms10.txt > /dev/null real 0m0.082s user 0m0.043s sys 0m0.013s ; time LANG=en_US.UTF-8 grep adsf < lesms10.txt > /dev/null real 0m1.209s user 0m0.818s sys 0m0.018s Those are the only two grep implementations I have handy. GNU grep 2.6.3 takes the same amount of time searching for 'asdf' in both locales, but searching for '.' is still slow. Thanks for pointing that out.

by p9idf 15y ago

Fun fact: Gnu grep is slow at UTF8. Try time LANG=C grep asdf < les_misérables.txt > /dev/null versus time LANG=en_US.UTF-8 grep asdf < les_misérables.txt > /dev/null

_delirium 15y ago

Hmm, strange. One of the stated design features of UTF-8 was that Boyer-Moore could still be directly applied (http://www.ietf.org/rfc/rfc2279.txt http://www.ietf.org/rfc/rfc2279.txt). Is grep doing something unnecessarily suboptimal here, or is that RFC's comment correct but not the whole story?

Sharlin 15y ago
The problem is probably that deciding whether two Unicode characters (where one character may be composed of multiple code points) are equivalent in general case is MUCH more involved than doing a simple byte comparison. http://en.wikipedia.org/wiki/Unicode_equivalence http://en.wikipedia.org/wiki/Unicode_equivalence
- _delirium 15y ago
  True, but in the special case where your search string is composed entirely of 7-bit ASCII characters (the characters representable as 1-byte in UTF-8), like the example, shouldn't the character-equivalence logic still be easy?
  - Someone 15y ago
    I do not think that accented e is a 7-bit ASCII character. Even if it is, the text being searched may contain the character coded as a multi-byte sequence.
    - _delirium 15y ago
      That was just in the filename; the search string in the example is 'asdf'. And UTF-8 I believe is purposely designed so that 7-bit ASCII characters can't appear anywhere else in the stream except when representing themselves (even as part of multibyte characters)--- every other byte in a UTF-8 stream must have the high-order bit set. My guess is that p9idf has it right, and grep is just converting everything to wchar_t first, rather than trying to do any sort of clever searching directly on the UTF-8 byte stream.
      - forgotusername 15y ago
        There's nothing to prevent this from being implemented, other than it'd be a huge hacky mess. It would require sidestepping iconv (or however grep does it) when LC_ALL is one of a specific set of strings, activating some special cases, and then additionally, building on those special cases, further scanning the input pattern (which may not just be a literal string - how might this work with character classes/ranges?) to ensure it is 7bit, in order to achieve the desired speedup. Or if your input data is sufficiently ASCII-ish, and so is your search pattern, then why not just force the process locale to C and avoid the whole mess to begin with. I'm suddenly left wondering how the "." regex syntax functions in the face of surrogates when handling UTF-8.
      - Someone 15y ago
        Oops. I sort-of guessed at what the example was about, and did not read it. However, if you find four bytes 'asdf' in the input, you still have to check whether a combining mark follows the 'f'. For this example, that is simple, but I guess things get hairy for many regexes found in real life, such as ones containing even a single period.
  - btilly 15y ago
    Not unless you are explicitly told that it is composed entirely of 7-bit ASCII characters. The UTF standard used to allow non-conformant representations of ASCII characters. As http://www.schneier.com/crypto-gram-0008.html http://www.schneier.com/crypto-gram-0008.html notes, this lead to security problems. Now the standard says that you can't allow non-conformant representations of ASCII characters. And if you look at http://www.unicode.org/versions/Unicode6.0.0/ch03.pdf http://www.unicode.org/versions/Unicode6.0.0/ch03.pdf and scroll to page 94 you'll find that you can't be said to be conformant unless you explicitly reject non-conforming input. Therefore UTF-8 decoders cannot be considered conformant unless they actually examine each and every byte to verify that there is nothing dodgy.
p9idf 15y ago
The rumor is that Gnu grep does a slow conversion of each input character into a wchar_t. I haven't personally read the code and verified it, but I consider the following sources reliable enough to believe it. http://9fans.net/archive/?q=%27gnu+grep%27+UTF-8+malloc&go=Grep http://9fans.net/archive/?q=%27gnu+grep%27+UTF-8+malloc&...

dfc 15y ago

What version of grep are you using? Not too long ago the grep in debian/unstable was awful with UTF strings. pg135.txt is project gutenberg's les mis. What were your times? I no longer notice this behavior: dfc@motherjones:~$ grep --version grep (GNU grep) 2.9 dfc@motherjones:~$ time LANG=C grep asdf < pg135.txt > /dev/null real 0m0.017s user 0m0.008s sys 0m0.004s dfc@motherjones:~$ time LANG=UTF8 grep asdf < pg135.txt > /dev/null real 0m0.017s user 0m0.012s sys 0m0.004s dfc@motherjones:~$ time LANG=en_us.UTF8 grep asdf < pg135.txt > /dev/null real 0m0.012s user 0m0.004s sys 0m0.004s There is not a lot of info about this in debian bug 604408 http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=604408 http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=604408 If memory serves me correctly this upstream fixed this sometime after 2.7.1 or 2.7.3 Funner fact: GNU grep used to be slow with UTF.

p9idf 15y ago
; grep --version GNU grep 2.5.3 ; time LANG=C grep asdf < lesms10.txt > /dev/null real 0m0.025s user 0m0.011s sys 0m0.014s ; time /usr/local/plan9/bin/grep asdf < lesms10.txt > /dev/null real 0m0.082s user 0m0.043s sys 0m0.013s ; time LANG=en_US.UTF-8 grep adsf < lesms10.txt > /dev/null real 0m1.209s user 0m0.818s sys 0m0.018s Those are the only two grep implementations I have handy. GNU grep 2.6.3 takes the same amount of time searching for 'asdf' in both locales, but searching for '.' is still slow. Thanks for pointing that out.