Hacker News Reader

Comment by piinbinary | Hacker News Reader

I'm actually somewhat surprised it wasn't faster. I may play with this and see how fast I can get it to go.

Edit: After a number of attempts (such as using Golang's regexp library or strings.Contains()), I wasn't able to speed it up much. Interestingly, grep performs the same search in about 5ms on my machine.

View on HN

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-Aug...

2: 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

4: https://golang.org/src/strings/replace.go?h=stringFinder

And if you want an even faster version of grep, checkout ripgrep (which happens to be written in Rust).

https://github.com/BurntSushi/ripgrep

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.h...

Reply on news.ycombinator.com