3 ms·

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 Gol

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.

selljamhere 8y ago
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...

3 ms·

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 Gol

by piinbinary 8y ago

selljamhere 8y ago
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...