News for hackers. Stuff that matters.
Re:Why GNU grep is fast (2010) by userbinator on Thursday July 23, 2020 @12:02AM (#23924072)
GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the final letter of the target string, and uses a lookup table to tell it how far ahead it can skip in the input whenever it finds a non-matching character.

I wonder how many times that algorithm or its variants has been rediscovered, given that not everyone who writes code reads CS papers; I recall several decades ago, working in x86 Asm, and coming up with that "match the last element first and use an indexed skip table" idea when I had to do substring matching, and then much later, when I explained it to someone else who was interested to know how I made that functionality so fast, he basically told me I had rediscovered the https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Ho... .

As it turns out, BMH is more common in practice (even when the author doesn't realise it) than BM, and on average performs very well:

https://old.blog.phusion.nl/2010/12/06/efficient-substring-s...

I suspect at least some standard library's memmem() uses BMH, since it doesn't require dynamic allocation or other complexity unlike BM, and is otherwise a drop-in replacement for the naive algorithm.

Re:Why GNU grep is fast (2010) by burntsushi on Thursday July 23, 2020 @09:39AM (#23927239)
As the author of ripgrep, I'd like to add some more notes to your comment:

* Some libc implementations (at least, glibc and musl) use Two-Way (linked in a sibling comment). In particular, it also skips parts of the input like BM, uses constant space (no allocation needed) and formally has O(n) time.

* The advice in the OP is somewhat outdated. The fact that BM skips some of the input isn't really too important on modern hardware. What matters about BM is its skip loop. Most implementations use `memchr` on the last byte of the needle. If that last byte happens to occur infrequently in the haystack, then the vast majority of your search time will be in an extremely well optimized loop that uses SIMD. For that reason, BM is somewhat of a red herring, and can be easily beaten through heuristics that choose better bytes to feed into its skip loop. (For example, assume a frequency distribution of bytes and pick the rarest one in your needle.)

Re:Why GNU grep is fast (2010) by bberenberg on Thursday July 23, 2020 @10:40AM (#23927826)
OT but seriously thanks for rg, it makes massive log file analysis so much faster for me.
Re:Why GNU grep is fast (2010) by jjice on Thursday July 23, 2020 @02:37PM (#23930668)
Very interesting! Ripgrep is my favorite new wave Unix utility by far. Modern syntax, incredible speeds, and a ridiculous amount of options that come in handy quite a bit. Great work!
Re:Why GNU grep is fast (2010) by mehrdadn on Thursday July 23, 2020 @01:33AM (#23924443)