Geek Blight

Update on 2010/10/28: GNU grep is no longer slow on UTF-8. The problem was fixed with the release of GNU grep 2.7. The rest of the article can now be considered obsolete.

Thanks to someone on the ##slackware FreeNode IRC channel that mentioned the problem some weeks ago, I discovered that GNU grep is very slow when working on UTF-8 files, and possibly other Unicode encodings. This, apparently, is a long-standing bug that hasn’t been officially fixed yet. The problem manifests itself when you run grep using locale settings that involve using UTF-8. Let’s see the following example:

In the previous text, /usr/share/dict/words is a file part of the bsd-games package in my Slackware system. It contains a list of English words and it’s not too long. It has below 40000 lines, each line having a word, and weights about 345 KB. Still, as you can see in the previous example, it takes more than 2 minutes in my computer to search for words having at least 4 characters. When I change my locale settings to "C" (ASCII), it only takes 31 milliseconds. The difference is amazing. Does grep behave differently in both cases? The answer is yes.

When grep runs in UTF-8 mode, the dot character, for example, represents any multi-byte character, while in ASCII mode the dot represents a single byte. See for example the following, using an accented Spanish character to form a 5-letter word.

The á character is represented using two bytes in UTF-8. Using the UTF-8 locale, grep correctly identifies it as a single character. Hence, my search for a 5-character word inside the file correctly returns 1 result. With LANG=C, no results are found. This feature is not, however, worth making grep so slow.

If you try to reproduce the problem above, probably you will not succeed, at least in your Linux system. This is because most Linux distributions are well aware of the problem and ship a patched GNU grep, and have been doing so for years. Debian does it (and with it, Ubuntu), Archlinux does it, Fedora does it, etc. Other distributions like Slackware traditionally ship software as vanilla as possible, and the problem shows, as seen above. Slackware’s GNU grep is completely vanilla. Most distributions use slightly different versions of the same patch, which replaces the MBS (Multi-Byte Sequence) treatment almost completely.

In my most recent scripts, I avoid GNU grep altogether, and use the fantastic and very efficient PCRE library (Perl Compatible Regular Expressions), used by many open source software projects (e.g. the Apache web server). The pcre package is present in most Linux distributions and BSD ports systems. It will probably ship the pcregrep tool inside. This is an alternative grep which features compatibility option-wise with the most common POSIX and GNU options, like -n, -l, -r, -w, etc. It expects, however, a Perl regular expression. They are, in the most common cases, like every other regular expression syntax out there, but closer to egrep than grep. By default, pcregrep behaves like grep with the LANG=C locale, even if your locale specifies that you are using UTF-8. It’s this fast:

A bit slower than grep with C locale, yes, but not a problem. In addition, you can activate UTF-8 mode to enable compatibility with multi-byte characters by using the -u option, explicitly. In this mode, pcregrep is not much slower:

Of course, it’s able to behave correctly in the previous UTF-8 test with the -u flag:

Moving away from GNU grep to pcregrep is not a bad option. You get consistently fast behavior, regular expression syntax compatible with Perl, and get to choose if you want UTF-8 compatibility or not by providing an explicit option. So long, GNU grep! Welcome, pcregrep!

Final note: GNU awk suffers from this problem too, but its behavior with a UTF-8 locale is more or less equivalent to a patched grep. Still a bit slow, though.