Everyone knows grep is faster in the C locale

Index, feed.

It is a well-known "fact", in some circles, that running grep in the C locale is much faster than in UTF-8 locales, the latter being a common default on current client systems.

Indeed, just the other day, a colleague of mine was running something akin to:

grep '"event-type-id":4727' app.log

where app.log is a multi-gigabyte file of JSON lines¹, the goal being to quickly see whether a newly-added type of event is seen. Almost immediately, someone jumped in to recommend running grep in the C locale, instead of the default UTF-8 locale, for Guaranteed Extra Speediness™.

I wondered whether this was indeed good advice. (TL;DR: using the C locale does not help performance in general, or jump to conclusions.)

Searching for a fixed string

This is my most common real-world use case at the moment: search for a small fragment of JSON within a file of JSON lines, both of them in practice ASCII.

In the following benchmark runs:

• the file being searchd, json10g, is made of 10GB of JSON lines, each about a kilobyte in length;

• the search string is just "event-type-id":4727;

• the search string does not match anywhere in the input;

• grep is the native version of grep for the system used; GNU grep version 2.25 from Ubuntu 16.04 LTS;

• the host has an Intel Kaby Lake processor (i7-7500U), simultaneous multithreading disabled, with 16GB of RAM;

• the storage is SSD, which does not matter since the inputs fits in the buffer cache.

On to the results:

This is how hyperfine summarizes these results:

Summary
  'LC_ALL=en_US.UTF-8 grep -f json-fixed.pat json10g' ran
    1.02 ± 0.04 times faster than 'LC_ALL=C grep ...'

Section conclusion: setting LC_ALL=C did not help improve performance.

Searching using a simple non-fixed regexp string

Of course, it is possible that things get hairier when one uses more of grep's power, which accepts a language of full regular expressions as search patterns, and not only fixed strings. Let us put this to the test; the search string is now the non-fixed regular expression event-type-id":4[0-7].[0-9]:

Summary
  'LC_ALL=C grep  -f json-simple-re.pat json10g' ran
    1.00 ± 0.00 times faster than 'LC_ALL=en_US.UTF-8 grep ...'

Section conclusion: setting LC_ALL=C did not help improve performance.

Caveat: the regular expression used here is fixed-length and does not use very many of grep's features; perhaps more complex examples would fare differently.

Searching using a less simple non-fixed regexp string

The performance section from the GNU grep documentation says the following²:

Generally speaking grep operates more efficiently in single-byte locales, since it can avoid the special processing needed for multi-byte characters. If your patterns will work just as well that way, setting LC_ALL to a single-byte locale can help performance considerably. Setting LC_ALL='C' can be particularly efficient, as grep is tuned for that locale.

Outside the C locale, case-insensitive search, and search for bracket expressions like [a-z] and [[=a=]b], can be surprisingly inefficient due to difficulties in fast portable access to concepts like multi-character collating elements.

Wow! The blanket LC_ALL=C advice appears a bit misleading since, as far as I can tell, when the locale does not make a difference to the pattern, neither does it make a difference to performance. It is however interesting to note that this snippet points us directly to a pattern on which grep should not perform the same with varying locales:

Summary
  'LC_ALL=C grep -f json-complex-re.pat json10g' ran
   14.45 ± 0.13 times faster than 'LC_ALL=en_US.UTF-8 grep ...'

Section conclusion: setting LC_ALL=C did help improve performance, tremendously.

Conclusion

In the use cases I tested, setting LC_ALL=C either:

• did not make any performance difference at all, when the pattern was a fixed string, or a "simple" regular expression; or

• made a notable performance improvement, when the regular expression contained an alphabetic character range.

Note that, in the second case, changing the locale also changes the results, so that one cannot just blindly set it to C. It is fine to use the C locale if, say, [a-f] is meant to be exactly [abcdef], but the range could include more characters in different locales:

$ echo 012@épaulées%DEF | grep -o '[a-z]*'
épaulées

$ echo 012@épaulées%DEF | LC_ALL=C grep -o '[a-z]*'
paul
es

Theories

Why would the apparently rarely-relevant LC_ALL=C advice be so prevalent?

Is it a matter of old vs current versions of GNU grep?

Perhaps older versions³ of GNU grep behaved differently from the one that comes with my current system, and they were indeed helped by running in the C locale, regardless of pattern?

All runs below use the same 10GB JSON input json10g as in the previous section, and the same two search strings (fixed, and bona-fide regexp "re").

Looking at pairs of runs of each version of GNU grep with the locale changing from C to UTF-8, we can see that setting LC_ALL=C did not help improve performance.

We can also see that GNU grep version 3.3 was much slower than all other versions tested; this could be a bona fide regression, a fix for a long-standing correctness bug with performance implications, or something else; I did not investigate the matter.

Is it a matter of BSD grep vs GNU grep?

I ran a FreeBSD 12.0-RELEASE virtual machine on the same hardware as previously⁴, same search strings and input:

Again, setting LC_ALL=C did not help improve performance here.

Side note: on this system, GNU grep is much faster than BSD grep. A quick win is therefore to favor the GNU version of grep, on systems where it is not already the default.

Is this a matter of string that matches versus string that does not match?

No:

Summary
  'LC_ALL=C grep "event-type-id":4727472747 json1g' ran
    1.01 ± 0.02 times faster than
      'LC_ALL=en_US.UTF-8 grep "event-type-id":4727472747 json1g'
    1.24 ± 0.01 times faster than
      'LC_ALL=en_US.UTF-8 grep "boundingPoly":{"vertices": json1g'
    1.26 ± 0.02 times faster than
      'LC_ALL=C grep "boundingPoly":{"vertices": json1g'

While searching for a matching string ran more slowly than searching for a string that does not match, presumably because of the increased amount of output to be written, the locale setting did not make a difference.

Is this a matter of short search string vs long search string?

In all previous benchmarks, I looked for relatively short strings. Would the locale influence performance when the search string is longer?

In the following, the search string $s is abcdefghijklmnopqrstuvwxyz012345 repeated four times, for a total of 128 characters.

Summary
  'LC_ALL=en_US.UTF-8 grep $s json10g' ran
    1.00 ± 0.01 times faster than 'LC_ALL=C grep ...'

Setting LC_ALL=C did not help improve performance.

Is this a matter of ASCII encoding versus multibyte?

In the following, the search string $s is 任天堂株式会社／ソニー株 式会社／キヤノン株式会社.

Summary
  'LC_ALL=en_US.UTF-8 grep $s json10g' ran
    1.00 ± 0.01 times faster than 'LC_ALL=C grep ...'

Setting LC_ALL=C did not help improve performance.

Reference material

Files used to generate inputs and run benchmarks: grepbench.tar.xz

www.kurokatta.org

David Haguenauer <www@kurokatta.org>
$Id: grep-c-locale-speed.malblog,v 1.37 2021/07/16 13:53:56 homer Exp $