There was a really interesting post on here a while back on GNU grep vs BSD grep (2010)[1]
The improvement mentioned here also has to do with the Boyer-Moore algorithm. When switching the locale from LANG=whatever to LANG=C, we're reducing the size of the lookup table to a fraction of what it previously was. In this case, the fraction is 1/50th, but, as the author said, this will vary between patterns and platforms.
[1] http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu...