Why GNU grep is fast (2010)

I tested string searching algorithms a few years ago[0][1], and Brute Force was surprisingly performant, enough that picking a string searching algorithm becomes an engineering tradeoff. It found a sentence fragment at the end of Moby Dick within 8ms, 7 times slower than Boyer-Moore. But most of us aren't searching Moby Dick, but rather a HTTP header, some user input, or a paragraph of a document. Even long-winded users won't write Moby Dick into your <textarea>. Most languages and libraries…

It's probably worth pointing out that OS X is using BSD grep. You will see a phenomenal difference if you install the gnu grep via homebrew: $ homebrew info grep GNU grep, egrep and fgrep https://www.gnu.org/software/grep/ /usr/local/Cellar/grep/3.3 (21 files, 885.3KB) * Poured from bottle on 2019-01-03 at 12:23:37 From: https://github.com/Homebrew/homebrew-core/blob/master/Formula/grep.rb ... This is a very arbitrary example, but I've got 1.5Gb application log sitting on my machine right now that'll suffice. I'll…

If you use grep in OS X, and you use it a lot (even called through other programs/libraries) it pays in time to install GNU grep vs. the default OS X provided one. It's several times faster. Ran into this when benchmarking grep + GNU Parallel on OS X vs. Linux in my thesis (raftlib modeling) work. Results on my small MacPro cluster didn't match those on Linux. The OS X runs were orders of magnitude slower despite almost identical…

The key to making programs fast is to make them do practically nothing. This is the Ultimate Truth of optimizing computer programs, and it seems so few people understand it. "Why can't you make Python faster!?" Because Python does a lot of stuff without you asking.