7 ms·
Why GNU grep is fast (2010)
- myrandomcomment 12y agoThis has been posted in the past many times.
- tedunangst 12y agoWhich is curious. Some content you run into by accident and think needs reposting. But how does one stumble upon this post in 2015? Googling for "why is gnu grep fast" and then not noticing that two of the top four results are submissions to HN?
- danudey 12y agoFinding it linked from some other article or blog post, or having it sent to you from someone else and then assuming that a mail thread from 2010 has never been seen on HN before.
- werid 12y agothe source this time is probably twitter: https://twitter.com/b0rk/status/573535058797031424 https://twitter.com/b0rk/status/573535058797031424
- rivd 12y agomentioned article about fast string search: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.9460&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13....
- alayne 12y agoPrevious discussion https://news.ycombinator.com/item?id=6813937 https://news.ycombinator.com/item?id=6813937
- wglb 12y agoAmusingly, the top comment of which is a few of the other times that it has shown up.
- mparramon 12y agoRelated: http://www.developingandstuff.com/2013/07/grep-too-slow-tired-of-waiting-for-it.html http://www.developingandstuff.com/2013/07/grep-too-slow-tire...
- sltkr 12y agoObvious questions: 1. How do you extend Boyer-Moore to arbitrary regexps? 2. Does "not looking at every byte" really matter when the strings being searched for are typically so short that you're gonna hit every cache line anyway?
- kevinnk 12y ago> Does "not looking at every byte" really matter when the strings being searched for are typically so short that you're gonna hit every cache line anyway? You're not skipping bytes of the search string, you're skipping bytes of the file being searched.
- pacificmint 12y agoOf course, but you can never skip more bytes than the search string is long.
- aganders3 12y agoBut you get to skip those few bites (potentially) very many times.
- rcxdude 12y agoyes, but the point is that on modern CPUs checking those bytes is likely far from the bottleneck and thus skipping them saves you very little time, if any at all.
- taeric 12y agoYou might be surprised. Consider, counting to 2 million by 5 is significantly faster than counting by 1. Especially if you just go ahead and start some prefetching in the memory, I would expect that this can speed things up considerably. Edit: I should say I would still think things should be benchmarked to really know...
- lettergram 12y agoWow.. I had this exact question when I interviewed at a big tech company, then I had to implement it in pseudocode.
- cosarara97 12y agoYou were supposed to know why a particular implementation of a tool was fast beforehand? Or they gave you GNU grep and BSD grep to compare?
- taeric 12y agoYeah, this definitely falls into the absurd category of interviewing whiteboard questions. Ridiculously absurd. I have a book with this algorithm detailed in it, and I think I would still have trouble implementing it well. That or I am just dumb. Very likely.
- perdunov 12y agoI wonder where that douchebaggery culture among employers comes from.
- nikanj 12y agoThese are often the same companies that complain about how hard it is to find 'talent'
- tedunangst 12y ago"Let's implement BM" (with some hints/guidance) doesn't seem absurd. It's not much code; handwritten can fit on a piece of paper or two. "Why is GNU grep fast?" would definitely be an absurd question though.
- perdunov 12y agoOkay, let's suppose a software engineer cannot implement the BM off the top of their head. What would you make of that? How relevant is this kind of testing to the actual work of a software engineer?
- pekk 12y agoThis should probably have a (2010) in the title or so
- edwintorok 12y agoOn the topic of fast grep-like program there is jrep too: http://lwn.net/Articles/589009/ http://lwn.net/Articles/589009/
- Sevzi 12y agolettergram could do a faster version that would work without errors the first time.
- yan 12y agoMore required reading on this topic: http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
- jlarocco 12y agoText processing is actually a pretty neat area, with a lot of practical uses. A while back I found an out of print book, "Text Algorithms," available for download from the author in PDF and some other formats. It's not cutting edge at this point, but still covers all the basics (like Boyer-Moore) really well. http://igm.univ-mlv.fr/~mac/REC/B1.html http://igm.univ-mlv.fr/~mac/REC/B1.html
- sturakov 12y agoAwesome, thanks for the books!
- jmcphers 12y agoIf you want the very fastest "find strings in files, especially code files", I've become a big fan of ag, "the silver searcher": https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher In addition to all the tricks applied by GNU grep (such as Boyer-Moore), it also splits work among threads to take advantage of multi-core machines. Integrates with your favorite text editor, too!
- lsiebert 12y agoI've been finding the following very useful for understanding string matching algorithms. It has a bunch of different algorithms for exact string matching, details on them, drawings, descriptions, speed comparisons, and code in C http://www-igm.univ-mlv.fr/~lecroq/string/index.html http://www-igm.univ-mlv.fr/~lecroq/string/index.html
- dllthomas 12y ago"The key to making programs fast is to make them do practically nothing. ;-)" Very much the case.