Hacker News Reader

Comment by p9idf | Hacker News Reader

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

View on HN

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). Is grep doing something unnecessarily suboptimal here, or is that RFC's comment correct but not the whole story?

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

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?

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.

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.

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.

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.

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

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

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

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.

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

Reply on news.ycombinator.com