3 ms·

grep is the product of a lot of thought and engineering. There's a great rundown by GNU grep's author, if you're interested [1]. One big takeaway is that grep

grep is the product of a lot of thought and engineering. There's a great rundown by GNU grep's author, if you're interested [1]. One big takeaway is that grep doesn't simply traverse the string linearly, instead using the Boyer-Moore algorithm [2]. 1: https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html# https://lists.freebsd.org/pipermail/freebsd-current/2010-Aug... 2: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_sea... EDIT: Interestingly, there seems to be an internal Boyer-Moore implementation in Golang's strings package[3], though it only appears to be used in strings.Replace("")[4] 3: https://golang.org/src/strings/search.go https://golang.org/src/strings/search.go 4: https://golang.org/src/strings/replace.go?h=stringFinder https://golang.org/src/strings/replace.go?h=stringFinder

Teknoman117 8y ago
And if you want an even faster version of grep, checkout ripgrep (which happens to be written in Rust). https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep
Jach 8y ago
That's a nice overview by the author. I've been fond of this blog post which goes into the main trick grep does besides Boyer-Moore and unrolling the loop that'll make it beat a by-the-book implementation with unrolling: http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...