15 ms·

Why GNU grep is fast (2010)

417 points by mozumder 10y ago

lazyjones 10y ago
8 previous posts/discussions: https://hn.algolia.com/?query=Why%20GNU%20grep%20is%20fast&sort=byDate&dateRange=all&type=story&storyText=false&prefix&page=0 https://hn.algolia.com/?query=Why%20GNU%20grep%20is%20fast&s...
userbinator 10y ago
I wonder if the simpler Boyer-Moore-Horspool might be even faster, since in practice BMH beats regular BM except in the pathological cases: http://old.blog.phusion.nl/2010/12/06/efficient-substring-searching/ http://old.blog.phusion.nl/2010/12/06/efficient-substring-se... Also, unrolling loops may actually slow things down in modern x86 CPUs since they will automatically decode and cache very small loops. Some interesting discussion on that here: https://groups.google.com/d/topic/mechanical-sympathy/UFscifOU8AQ https://groups.google.com/d/topic/mechanical-sympathy/UFscif...
- ComputerGuru 10y ago
  Nope, or at least, not necessarily. Have fun reading this: http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
  - jcranmer 10y ago
    2006 is a bit old when talking about newer Intel CPUs.
    - goldenkey 10y ago
      Processor competition in the desktop market has been lackluster since that time. Intel has been sitting on their laurels mostly. The vectored primitives and bigger cache and core counts are nice but honestly you have been fooled by the branding and continual product lines. Loop unrolling still helps even with brand spankin new CPUs. Some intent cannot be inferred.
      - jcranmer 10y ago
        > Processor competition in the desktop market has been lackluster since that time. Intel has been sitting on their laurels mostly. The vectored primitives and bigger cache and core counts are nice but honestly you have been fooled by the branding and continual product lines. I might be inclined to agree with you... if I didn't know that Haswell: * implemented the computed goto transformation (for interpreter loops) in hardware * made unaligned cache hits crossing cache line boundaries have no latency penalty Both of those things are things that I would have told you were impossible(/infeasible) to do in hardware before finding out that Intel did them. There's actually quite a lot of amazing microarchitectural changes going on in Intel processors, you just don't hear a lot about them.
ComputerGuru 10y ago
I thought for a second this was one of my all-time favorites, which can also be summarized as "how is gnu grep so fast?" [0]. 0: http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
- goldenkey 10y ago
  That was great, thanks! I am not so sure the 70/8 tradeoff is worth it but it should probably be tested with code samples as well as english corpuses. Is grep primarily made for ascii?
- tghw 10y ago
  Came here to post exactly that article.
rusanu 10y ago
Previous discussions: - https://news.ycombinator.com/item?id=1626305 https://news.ycombinator.com/item?id=1626305 (115 comments, 2193 days ago) - https://news.ycombinator.com/item?id=2393587 https://news.ycombinator.com/item?id=2393587 (68 comments, 1972 days ago) - https://news.ycombinator.com/item?id=2860759 https://news.ycombinator.com/item?id=2860759 (43 comments, 1842 days ago) I'm sure there are more.
- throwawayReply 10y ago
  1842 days is over 5 years. At some point you have to consider the set of users here now is different to (if not distinct from) the set of users here 5 years ago.
  - TobbenTM 10y ago
    I don't think he meant anything by the comment, other than simplifying access to more (older) comments. ;)
    - rusanu 10y ago
      Correct. I've read the original post years ago, I do find it it fascinating, and I would like every new generation to read it. I don't have a quarrel with it making HN front page every now and then.
  - ffggvv 10y ago
    Probably this is why he put here those links, to redirect the new set of users to discussions from the old set of users.
  - dalbin 10y ago
    It's useful for the new users too because previous discussions has a lot of comments to read. By the way, it would be great if there would be a "Related" widget with the number of comments somewhere in the comment page.
    - 10y ago
burntsushi 10y ago
Some other details on GNU grep's performance: * The Boyer-Moore algorithm it uses has a skip loop, which is used to quickly search for the last byte in the needle before trying to do more checking. Specifically, the skip loop is implemented with memchr, which can be found in your libc and probably compiles down to SIMD instructions. (The trick here isn't actually skipping bytes, but processing many bytes in a single loop iteration.) This optimization works well in the common case, but can slow things down a bit if your skip byte is really common in the haystack. * When a pattern consists of an alternation of literals, like, `abc|mno|xyz`, then it uses an algorithm based on Commentz-Walter, which you can think of as a hybrid between Aho-Corasick and Boyer-Moore. That is, you get the byte skipping of Boyer-Moore even though you're searching for multiple patterns. The performance of Commentz-Walter degrades as the number of patterns increases because there's fewer opportunities for meaningful skips. Nevertheless, small/short alternations are probably the common case with GNU grep. (The state of the art has actually improved for this specific case and GNU grep could probably benefit. Specifically, the Hyperscan folks over at Intel have some really cool SIMD algorithms for matching multiple patterns. I implemented one here (the comments include a description with examples): https://github.com/rust-lang-nursery/regex/blob/master/src/simd_accel/teddy128.rs https://github.com/rust-lang-nursery/regex/blob/master/src/s...) * The actual regex engine is a lazy DFA (similar to RE2) in that its states are computed on-demand as needed. That is, some parts of the DFA that aren't used are never computed at all. If the DFA gets too big in memory, the existing states are dropped and re-computed as needed. In this way, GNU grep gets the performance of a DFA while preserving linear time matching. (At most one new DFA state is computed for each byte of input.) The inner DFA loop is unrolled. * To re-emphazie a point from the post: avoiding line-by-line matching is critical. This makes it much easier to extract literals from a pattern. For example, if your pattern is `\w+foobar\d+`, then GNU grep can still search for `foobar` because it can make an assumption that its haystack is generally a very small slice of the entire search space (i.e., a single line). This type of optimization is much harder to pull off in a general purpose regex engine. A general purpose regex engine might limit itself to looking for prefix or suffix literals only. * GNU grep really doesn't do all that well for multi-byte encodings. e.g., The time difference between `LC_ALL=C egrep -c '\w{5}'` and `LC_ALL=en_US.UTF-8 egrep -c '\w{5}'` on a large file is quite dramatic. (~3 seconds vs ~52 seconds for a ~2GB mostly-ASCII file that is warm in my page cache.) There's really no need for this slow down if you can bake UTF-8 decoding into your DFA (RE2 does this). However, you then lose the ability to `grep` over other character encodings without transcoding them to UTF-8 first. (In fact, GNU grep may be doing this transcoding step today anyway, so maybe baking UTF-8 into your DFA would be a strictly better solution since it would be much faster on a much larger number of inputs, but probably not slower than any inputs. However, I'm not terribly familiar with this part of GNU grep, so I could have this wrong.)
nachtigall 10y ago
What about concurrency? I have 4 CPU cores.
- esac 10y ago
  I'm pretty sure the bottleneck is disk I/O and not the CPU
  - exDM69 10y ago
    Even when disk caches are involved (ie. data in RAM, not cache), a typical grep application (short "needle" to search for) should saturate the memory bandwidth before CPU cores. Running a few threads/processes in parallel could improve throughput with latency hiding, but adding more shouldn't give any benefit.
  - ggreer 10y ago
    When searching for a literal string, the bottleneck tends to be memory bandwidth. When doing regex searches, the bottleneck is usually CPU. If caches are cold, then disk I/O is the limiting factor. Even in that case, technologies like NCQ allow some degree of concurrency. If you have ag[1], you can play around with the --workers option to see how various numbers of threads change performance. (The default is for ag to use #CPUs-1 workers.) 1. https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher
chukye 10y ago
I think this was already quoted in somewhere, but, its the best advice; "The key to making programs fast is to make them do practically nothing."
- reacweb 10y ago
  Yes and we underestimate how often this kind of rule can apply. To have fast network, reduces network utilisation (for example using cache). To have fast database, reduce number of queries (for example using more complex queries). To have fast memory allocation, avoid dynamic memory or preallocate...
- mozumder 10y ago
  Also useful: "If you want to make a fast program, use a slow computer."
  - laumars 10y ago
    Not really necessary in most cases. There's enough profiling tools available that can give response times in fractions of a second and in many cases you can add repetition to inflate the few processes that are still too small to measure. These will give you far more meaningful figures about the performance of your code than anecdotal evidence using a slow PC as a benchmark.
    - dr_zoidberg 10y ago
      I agree with both of you. Once I optimized a major Python project to avoid some bad disk access patterns. Nobody noticed them because everyone was using SSDs and those patterns didn't hurt (too much) performance on those, but I was running on an HDD and I had run times of hours (vs a couple of minutes for everyone else). But my optimizations were guided by the profiler and a (more or less) correct analysis of the results.
    - adrianN 10y ago
      Developers care more about performance if it's slow on their computers too.
danso 10y ago
OT, but along the same lines of how GNU has brought considerable performance improvements to what (in my naive layperson's mentality) seem like straightforward tools: Does anyone have an insight as to why GNU tail is, in at least one situation, considerably faster than FreeBSD's tail (at least the one that comes with OS X)? I'm referring to the use of: `tail -n +2` to skip the first line, versus using `sed '1d'`. To me, it makes intuitive sense how the latter could be faster, and on FreeBSD, it is, by at least one order of magnitude. However GNU tail is one order faster than sed. Is GNU tail using some heuristic to handle "skip the first line in a huge file" differently?
- glandium 10y ago
  I haven't read the code of neither sed nor tail, but I'd imagine sed is still reading line by line, while tail skips the number of lines it needs to skip, and then just goes on full throttle reading the remainder of the file. It might even be using sendfile(2) or splice(2).
skywhopper 10y ago
Always worth a re-read because it's short, interesting, and teaches a good lesson
SixSigma 10y ago
Try it in UTF8 mode and then you'll see a difference
jcbeard 10y ago
If you use grep in OS X, and you use it a lot (even called through other programs/libraries) it pays in time to install GNU grep vs. the default OS X provided one. It's several times faster. Ran into this when benchmarking grep + GNU Parallel on OS X vs. Linux in my thesis (raftlib modeling) work. Results on my small MacPro cluster didn't match those on Linux. The OS X runs were orders of magnitude slower despite almost identical hardware configurations. The culprit as it turned out was largely the implementation of grep. I compiled with the GNU version, re-ran and the rest of the mis-match was simply due to the lack of POSIX features like thread pinning, and NUMA control. <stepping up to soap box/> So yeah...as usual, algorithm matters. Implementation matters, and well....knowledge of the architecture/data-movement matter. These days the architecture/data-movement knowledge matters almost as much or more than the algorithm. Picking an algorithmically faster implementation that moves data more (e.g., tree traversals usually have poor cache behavior, more bursts required, etc.) is often the case b/c programmers don't really understand how the computer works, but are great at coding O(n logn) algorithms. We shouldn't stop teaching algorithms, but data-movement/access likely needs to be emphasized along with the understanding of algorithms.
- amelius 10y ago
  This makes me wonder: why would Apple implement its own version of grep, and not simply ship GNU's version?
  - pdpi 10y ago
    Because Apple avoids GPLv3 like the plague, basically. That's why the included bash is so old too, AFAIK
    - colejohnson66 10y ago
      Which in this case is ridiculous. There are valid reasons for businesses to avoid GPL, but if they use GNU grep, the only thing they have to open source is their copy of GNU grep. It's not like doing so will force them to make their kernel GPL
lubomir 10y ago
For those interested in the Boyer-Moore algorithm, this is an commented demonstration: http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html http://www.cs.utexas.edu/users/moore/best-ideas/string-searc... Compare to Knuth-Pratt-Morris: http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/kpm-example.html http://www.cs.utexas.edu/users/moore/best-ideas/string-searc...
asadjb 10y ago
Here's a link to the paper the article talks about ("Fast String Searching", by Andrew Hume and Daniel Sunday): 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....
0xmohit 10y ago
GNU grep is fast, but there are certain alternatives that are pretty fast (probably faster): - ack [0] - ag (also known as the silver searcher) [1] You could make `grep` faster by telling it to interpret the pattern as a fixed string (-F or --fixed-strings) is you're not using a regex. Setting to LANG to C would also probably make it faster. [0] http://beyondgrep.com/ http://beyondgrep.com/ [1] https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher
- burntsushi 10y ago
  I think it would be interesting to compare those utilities with GNU grep on a single file, because I understand them to be faster on many files because they (1) search files in parallel and (2) skip many uninteresting files automatically. I also don't think either of those tools are DFA based like GNU grep. One thing I'd like to see is combine many of the performance tricks found in GNU grep with the aforementioned (1)+(2) techniques. > You could make `grep` faster by telling it to interpret the pattern as a fixed string (-F or --fixed-strings) is you're not using a regex. That doesn't really make much sense. GNU grep can tell whether a pattern is just a literal or not. If it's a literal, it should be able to stay out of the main DFA engine entirely.
  - gpderetta 10y ago
    I use grep for single files (mostly because it is burned in my muscle memory). The silver searcher (from emacs) for bulk searches in a large directory tree (like a codebase).
  - nilved 10y ago
    It's pretty easy to use grep and search in parallel while skipping uninteresting files. `git ls-files | xargs -P4 -n8 grep whatever` is a good way to do this; or `git grep`, but that's using PCRE and not parallelized. > That doesn't really make much sense. GNU grep can tell whether a pattern is just a literal or not. If it's a literal, it should be able to stay out of the main DFA engine entirely. That would be clever but it doesn't do that.
primis 10y ago
The key to making programs fast is to make them do practically nothing. This is the Ultimate Truth of optimizing computer programs, and it seems so few people understand it. "Why can't you make Python faster!?" Because Python does a lot of stuff without you asking.
- 0xmohit 10y ago
  > "Why can't you make Python faster!?" You can. Use a Python wrapper to invoke a program written in another language. Python becomes faster.
amluto 10y ago
I wonder if all of these optimizations are still as helpful. For example, skipping bytes only saves memory bandwidth if you skip whole cachelines. Also, for --mmap, there are a couple of conflicting considerations. On newer CPUs, large memory copies are very fast. With mmap, though, unless you use MAP_POPULATE, you can get a page fault every few pages, and on CPUs with exception mechanisms as bad as x86's, page faults are very slow (probably 20 times as bad as a syscall).
- goldenkey 10y ago
  Does it use SIMD instructions? Some newer cpus can do up to 16 comparisons at once. That also might mean skipping will be branchy and not exactly divisible on word boundaries for best vectorization.
- adrianratnapala 10y ago
  The bottleneck is not reading the byte, it is the CPU clocks needed to figure out that it is safe to skip. Assuming cache prefetching works well thanks to the sequential search, you can try to max out the memory bandwidth. But even DDR3 has best-case transfer rates from 6-17 GB/second. So to max it out on a 3GHz CPU, you need to eliminate 2-6 bytes on every tick of the clock.
- ksk 10y ago
  Memory bandwidth is not the main concern here since they explicitly mention that executing more CPU instructions kill performance far quicker - in this case. As for mmap, perhaps you would like to present your own benchmark that contradicts the article. But anyway, I highly doubt that either of the basic things you mentioned are news to the implementors. The implementation is supposed to run on all kinds of processors with varying architectures so making the implementation portable is bound to leave performance on the table. Not to mention other constraints like maintainability and meeting the performance criteria for the common use case/workload.
dubmax123 10y ago
Wisdom: "The key to making programs fast is to make them do practically nothing. ;-)"
josuah 10y ago
I believed busybox's grep to be faster as it was very small, with GNU version slower due to the many features added over the time, but it is quite not true! On a slow device as some evoked said, the difference is highly noticeable.
- mcguire 10y ago
  That's actually an important point. It's easy to misinterpret "The key to making programs fast is to make them do practically nothing." Busybox's grep is small and simple. GNU grep is big and complex, which is actually why it's faster. It does a lot of work to avoid doing a lot of work.
  - josuah 10y ago
    Oh, so 'do practically nothing' rather than 'be practically nothing'. I understand now.
hossbeast 10y ago
For fast grep, consider ag https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher
- bsg75 10y ago
  Faster than Ack, not always faster than grep.
  - shandor 10y ago
    Really? My completely anecdotal experience is that ag kills grep. Stuff like searching usages of variables in Linux kernel seems to take ages with grep, whereas ag search on the whole repository doesn't take annoyingly long. I'll need to test this, just to see how wrong my "feeling" on the matter may be.
    - ggreer 10y ago
      I'm the author of ag. On a single file, ag is slower than GNU grep. The main reason is that ag prints line numbers when showing matches. Printing line numbers means going through the whole file and searching for \n's. For large files, this can be very resource-intensive. Here are the numbers (median of 5 runs, caches hot) for an 8GB file: % time ag hello4294967296 big_file.txt 134217728:hello4294967296 ag hello4294967296 big_file.txt 7.83s user 0.44s system 99% cpu 8.275 total % time grep hello4294967296 big_file.txt hello4294967296 grep hello4294967296 big_file.txt 2.17s user 0.91s system 99% cpu 3.085 total If you enable line numbers with grep -n, grep still wins, probably because ag's printing code is ridiculously inefficient: % time grep -n hello4294967296 big_file.txt 134217728:hello4294967296 grep -n hello4294967296 big_file.txt 3.37s user 0.97s system 99% cpu 4.338 total Unfortunately, I didn't write ag's printing code very sanely. It grew organically from users asking for small features here and there, and now it's a giant hairball. I've added some tests to reduce the chance of breaking changes, but it'll probably be a while before I fix this performance issue. Despite these limitations, ag tends to be much faster than grep -r in real-world use. There are several reasons why: 1. Ag has a multi-threaded architecture that can search multiple files at once. Grep is single-threaded. 2. Ag ignores binary and hidden files by default. Grep doesn't. 3. Ag obeys .gitignore/agignore/hgignore. Grep doesn't. These things really add up. For example, when searching my 20GB ~/code directory: ggreer@lithium:~/code% time ag instantiationname ... ag instantiationname 3.82s user 2.16s system 157% cpu 3.797 total ggreer@lithium:~/code% time grep -n -i -r instantiationname ... grep -n -i -r instantiationname 42.77s user 2.62s system 99% cpu 45.403 total Both find the same matches (some tests in the Node.js source), but ag does it 12x faster.
SunboX 10y ago
Another rule to make programs fast: break early, break often.
kuharich 10y ago
Previous discussions: http://news.ycombinator.com/item?id=1626305 http://news.ycombinator.com/item?id=1626305 http://news.ycombinator.com/item?id=2860759 http://news.ycombinator.com/item?id=2860759 https://news.ycombinator.com/item?id=6813937 https://news.ycombinator.com/item?id=6813937 https://news.ycombinator.com/item?id=9153203 https://news.ycombinator.com/item?id=9153203 http://news.ycombinator.com/item?id=2393587 http://news.ycombinator.com/item?id=2393587 https://news.ycombinator.com/item?id=9446382 https://news.ycombinator.com/item?id=9446382
underyx 10y ago
Wait, I always tried to make my pattern as short as possible and I thought it would speed up the searches. So I guess this means I'm actually better off searching for the longest possible match then?
- burntsushi 10y ago
  Pretty much, yes. Longer strings should also match fewer times than short strings, which should also speed things up (because reporting a match has its own overhead associated with it, like printing text to the terminal).
gumby 10y ago
Great bit of wisdom buried at the very end: > The key to making programs fast is to make them do practically nothing. ;-)

417 points by mozumder 10y ago

8 previous posts/discussions: https://hn.algolia.com/?query=Why%20GNU%20grep%20is%20fast&sort=byDate&dateRange=all&type=story&storyText=false&prefix&page=0 https://hn.algolia.com/?query=Why%20GNU%20grep%20is%20fast&s...

userbinator 10y ago

I wonder if the simpler Boyer-Moore-Horspool might be even faster, since in practice BMH beats regular BM except in the pathological cases: http://old.blog.phusion.nl/2010/12/06/efficient-substring-searching/ http://old.blog.phusion.nl/2010/12/06/efficient-substring-se... Also, unrolling loops may actually slow things down in modern x86 CPUs since they will automatically decode and cache very small loops. Some interesting discussion on that here: https://groups.google.com/d/topic/mechanical-sympathy/UFscifOU8AQ https://groups.google.com/d/topic/mechanical-sympathy/UFscif...

ComputerGuru 10y ago
Nope, or at least, not necessarily. Have fun reading this: http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
- jcranmer 10y ago
  2006 is a bit old when talking about newer Intel CPUs.
  - goldenkey 10y ago
    Processor competition in the desktop market has been lackluster since that time. Intel has been sitting on their laurels mostly. The vectored primitives and bigger cache and core counts are nice but honestly you have been fooled by the branding and continual product lines. Loop unrolling still helps even with brand spankin new CPUs. Some intent cannot be inferred.
    - jcranmer 10y ago
      > Processor competition in the desktop market has been lackluster since that time. Intel has been sitting on their laurels mostly. The vectored primitives and bigger cache and core counts are nice but honestly you have been fooled by the branding and continual product lines. I might be inclined to agree with you... if I didn't know that Haswell: * implemented the computed goto transformation (for interpreter loops) in hardware * made unaligned cache hits crossing cache line boundaries have no latency penalty Both of those things are things that I would have told you were impossible(/infeasible) to do in hardware before finding out that Intel did them. There's actually quite a lot of amazing microarchitectural changes going on in Intel processors, you just don't hear a lot about them.

ComputerGuru 10y ago

I thought for a second this was one of my all-time favorites, which can also be summarized as "how is gnu grep so fast?" [0]. 0: http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...

goldenkey 10y ago
That was great, thanks! I am not so sure the 70/8 tradeoff is worth it but it should probably be tested with code samples as well as english corpuses. Is grep primarily made for ascii?
tghw 10y ago
Came here to post exactly that article.

rusanu 10y ago

Previous discussions: - https://news.ycombinator.com/item?id=1626305 https://news.ycombinator.com/item?id=1626305 (115 comments, 2193 days ago) - https://news.ycombinator.com/item?id=2393587 https://news.ycombinator.com/item?id=2393587 (68 comments, 1972 days ago) - https://news.ycombinator.com/item?id=2860759 https://news.ycombinator.com/item?id=2860759 (43 comments, 1842 days ago) I'm sure there are more.

throwawayReply 10y ago
1842 days is over 5 years. At some point you have to consider the set of users here now is different to (if not distinct from) the set of users here 5 years ago.
- TobbenTM 10y ago
  I don't think he meant anything by the comment, other than simplifying access to more (older) comments. ;)
  - rusanu 10y ago
    Correct. I've read the original post years ago, I do find it it fascinating, and I would like every new generation to read it. I don't have a quarrel with it making HN front page every now and then.
- ffggvv 10y ago
  Probably this is why he put here those links, to redirect the new set of users to discussions from the old set of users.
- dalbin 10y ago
  It's useful for the new users too because previous discussions has a lot of comments to read. By the way, it would be great if there would be a "Related" widget with the number of comments somewhere in the comment page.
  - 10y ago

burntsushi 10y ago

Some other details on GNU grep's performance: * The Boyer-Moore algorithm it uses has a skip loop, which is used to quickly search for the last byte in the needle before trying to do more checking. Specifically, the skip loop is implemented with memchr, which can be found in your libc and probably compiles down to SIMD instructions. (The trick here isn't actually skipping bytes, but processing many bytes in a single loop iteration.) This optimization works well in the common case, but can slow things down a bit if your skip byte is really common in the haystack. * When a pattern consists of an alternation of literals, like, `abc|mno|xyz`, then it uses an algorithm based on Commentz-Walter, which you can think of as a hybrid between Aho-Corasick and Boyer-Moore. That is, you get the byte skipping of Boyer-Moore even though you're searching for multiple patterns. The performance of Commentz-Walter degrades as the number of patterns increases because there's fewer opportunities for meaningful skips. Nevertheless, small/short alternations are probably the common case with GNU grep. (The state of the art has actually improved for this specific case and GNU grep could probably benefit. Specifically, the Hyperscan folks over at Intel have some really cool SIMD algorithms for matching multiple patterns. I implemented one here (the comments include a description with examples): https://github.com/rust-lang-nursery/regex/blob/master/src/simd_accel/teddy128.rs https://github.com/rust-lang-nursery/regex/blob/master/src/s...) * The actual regex engine is a lazy DFA (similar to RE2) in that its states are computed on-demand as needed. That is, some parts of the DFA that aren't used are never computed at all. If the DFA gets too big in memory, the existing states are dropped and re-computed as needed. In this way, GNU grep gets the performance of a DFA while preserving linear time matching. (At most one new DFA state is computed for each byte of input.) The inner DFA loop is unrolled. * To re-emphazie a point from the post: avoiding line-by-line matching is critical. This makes it much easier to extract literals from a pattern. For example, if your pattern is `\w+foobar\d+`, then GNU grep can still search for `foobar` because it can make an assumption that its haystack is generally a very small slice of the entire search space (i.e., a single line). This type of optimization is much harder to pull off in a general purpose regex engine. A general purpose regex engine might limit itself to looking for prefix or suffix literals only. * GNU grep really doesn't do all that well for multi-byte encodings. e.g., The time difference between `LC_ALL=C egrep -c '\w{5}'` and `LC_ALL=en_US.UTF-8 egrep -c '\w{5}'` on a large file is quite dramatic. (~3 seconds vs ~52 seconds for a ~2GB mostly-ASCII file that is warm in my page cache.) There's really no need for this slow down if you can bake UTF-8 decoding into your DFA (RE2 does this). However, you then lose the ability to `grep` over other character encodings without transcoding them to UTF-8 first. (In fact, GNU grep may be doing this transcoding step today anyway, so maybe baking UTF-8 into your DFA would be a strictly better solution since it would be much faster on a much larger number of inputs, but probably not slower than any inputs. However, I'm not terribly familiar with this part of GNU grep, so I could have this wrong.)

nachtigall 10y ago

What about concurrency? I have 4 CPU cores.

esac 10y ago
I'm pretty sure the bottleneck is disk I/O and not the CPU
- exDM69 10y ago
  Even when disk caches are involved (ie. data in RAM, not cache), a typical grep application (short "needle" to search for) should saturate the memory bandwidth before CPU cores. Running a few threads/processes in parallel could improve throughput with latency hiding, but adding more shouldn't give any benefit.
- ggreer 10y ago
  When searching for a literal string, the bottleneck tends to be memory bandwidth. When doing regex searches, the bottleneck is usually CPU. If caches are cold, then disk I/O is the limiting factor. Even in that case, technologies like NCQ allow some degree of concurrency. If you have ag[1], you can play around with the --workers option to see how various numbers of threads change performance. (The default is for ag to use #CPUs-1 workers.) 1. https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher

chukye 10y ago

I think this was already quoted in somewhere, but, its the best advice; "The key to making programs fast is to make them do practically nothing."

reacweb 10y ago
Yes and we underestimate how often this kind of rule can apply. To have fast network, reduces network utilisation (for example using cache). To have fast database, reduce number of queries (for example using more complex queries). To have fast memory allocation, avoid dynamic memory or preallocate...
mozumder 10y ago
Also useful: "If you want to make a fast program, use a slow computer."
- laumars 10y ago
  Not really necessary in most cases. There's enough profiling tools available that can give response times in fractions of a second and in many cases you can add repetition to inflate the few processes that are still too small to measure. These will give you far more meaningful figures about the performance of your code than anecdotal evidence using a slow PC as a benchmark.
  - dr_zoidberg 10y ago
    I agree with both of you. Once I optimized a major Python project to avoid some bad disk access patterns. Nobody noticed them because everyone was using SSDs and those patterns didn't hurt (too much) performance on those, but I was running on an HDD and I had run times of hours (vs a couple of minutes for everyone else). But my optimizations were guided by the profiler and a (more or less) correct analysis of the results.
  - adrianN 10y ago
    Developers care more about performance if it's slow on their computers too.

danso 10y ago

OT, but along the same lines of how GNU has brought considerable performance improvements to what (in my naive layperson's mentality) seem like straightforward tools: Does anyone have an insight as to why GNU tail is, in at least one situation, considerably faster than FreeBSD's tail (at least the one that comes with OS X)? I'm referring to the use of: `tail -n +2` to skip the first line, versus using `sed '1d'`. To me, it makes intuitive sense how the latter could be faster, and on FreeBSD, it is, by at least one order of magnitude. However GNU tail is one order faster than sed. Is GNU tail using some heuristic to handle "skip the first line in a huge file" differently?

glandium 10y ago
I haven't read the code of neither sed nor tail, but I'd imagine sed is still reading line by line, while tail skips the number of lines it needs to skip, and then just goes on full throttle reading the remainder of the file. It might even be using sendfile(2) or splice(2).

skywhopper 10y ago

Always worth a re-read because it's short, interesting, and teaches a good lesson

SixSigma 10y ago

Try it in UTF8 mode and then you'll see a difference

jcbeard 10y ago

If you use grep in OS X, and you use it a lot (even called through other programs/libraries) it pays in time to install GNU grep vs. the default OS X provided one. It's several times faster. Ran into this when benchmarking grep + GNU Parallel on OS X vs. Linux in my thesis (raftlib modeling) work. Results on my small MacPro cluster didn't match those on Linux. The OS X runs were orders of magnitude slower despite almost identical hardware configurations. The culprit as it turned out was largely the implementation of grep. I compiled with the GNU version, re-ran and the rest of the mis-match was simply due to the lack of POSIX features like thread pinning, and NUMA control. <stepping up to soap box/> So yeah...as usual, algorithm matters. Implementation matters, and well....knowledge of the architecture/data-movement matter. These days the architecture/data-movement knowledge matters almost as much or more than the algorithm. Picking an algorithmically faster implementation that moves data more (e.g., tree traversals usually have poor cache behavior, more bursts required, etc.) is often the case b/c programmers don't really understand how the computer works, but are great at coding O(n logn) algorithms. We shouldn't stop teaching algorithms, but data-movement/access likely needs to be emphasized along with the understanding of algorithms.

amelius 10y ago
This makes me wonder: why would Apple implement its own version of grep, and not simply ship GNU's version?
- pdpi 10y ago
  Because Apple avoids GPLv3 like the plague, basically. That's why the included bash is so old too, AFAIK
  - colejohnson66 10y ago
    Which in this case is ridiculous. There are valid reasons for businesses to avoid GPL, but if they use GNU grep, the only thing they have to open source is their copy of GNU grep. It's not like doing so will force them to make their kernel GPL

lubomir 10y ago

For those interested in the Boyer-Moore algorithm, this is an commented demonstration: http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html http://www.cs.utexas.edu/users/moore/best-ideas/string-searc... Compare to Knuth-Pratt-Morris: http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/kpm-example.html http://www.cs.utexas.edu/users/moore/best-ideas/string-searc...

asadjb 10y ago

Here's a link to the paper the article talks about ("Fast String Searching", by Andrew Hume and Daniel Sunday): 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....

0xmohit 10y ago

GNU grep is fast, but there are certain alternatives that are pretty fast (probably faster): - ack [0] - ag (also known as the silver searcher) [1] You could make `grep` faster by telling it to interpret the pattern as a fixed string (-F or --fixed-strings) is you're not using a regex. Setting to LANG to C would also probably make it faster. [0] http://beyondgrep.com/ http://beyondgrep.com/ [1] https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher

burntsushi 10y ago
I think it would be interesting to compare those utilities with GNU grep on a single file, because I understand them to be faster on many files because they (1) search files in parallel and (2) skip many uninteresting files automatically. I also don't think either of those tools are DFA based like GNU grep. One thing I'd like to see is combine many of the performance tricks found in GNU grep with the aforementioned (1)+(2) techniques. > You could make `grep` faster by telling it to interpret the pattern as a fixed string (-F or --fixed-strings) is you're not using a regex. That doesn't really make much sense. GNU grep can tell whether a pattern is just a literal or not. If it's a literal, it should be able to stay out of the main DFA engine entirely.
- gpderetta 10y ago
  I use grep for single files (mostly because it is burned in my muscle memory). The silver searcher (from emacs) for bulk searches in a large directory tree (like a codebase).
- nilved 10y ago
  It's pretty easy to use grep and search in parallel while skipping uninteresting files. `git ls-files | xargs -P4 -n8 grep whatever` is a good way to do this; or `git grep`, but that's using PCRE and not parallelized. > That doesn't really make much sense. GNU grep can tell whether a pattern is just a literal or not. If it's a literal, it should be able to stay out of the main DFA engine entirely. That would be clever but it doesn't do that.

primis 10y ago

The key to making programs fast is to make them do practically nothing. This is the Ultimate Truth of optimizing computer programs, and it seems so few people understand it. "Why can't you make Python faster!?" Because Python does a lot of stuff without you asking.

0xmohit 10y ago
> "Why can't you make Python faster!?" You can. Use a Python wrapper to invoke a program written in another language. Python becomes faster.

amluto 10y ago

I wonder if all of these optimizations are still as helpful. For example, skipping bytes only saves memory bandwidth if you skip whole cachelines. Also, for --mmap, there are a couple of conflicting considerations. On newer CPUs, large memory copies are very fast. With mmap, though, unless you use MAP_POPULATE, you can get a page fault every few pages, and on CPUs with exception mechanisms as bad as x86's, page faults are very slow (probably 20 times as bad as a syscall).

goldenkey 10y ago
Does it use SIMD instructions? Some newer cpus can do up to 16 comparisons at once. That also might mean skipping will be branchy and not exactly divisible on word boundaries for best vectorization.
adrianratnapala 10y ago
The bottleneck is not reading the byte, it is the CPU clocks needed to figure out that it is safe to skip. Assuming cache prefetching works well thanks to the sequential search, you can try to max out the memory bandwidth. But even DDR3 has best-case transfer rates from 6-17 GB/second. So to max it out on a 3GHz CPU, you need to eliminate 2-6 bytes on every tick of the clock.
ksk 10y ago
Memory bandwidth is not the main concern here since they explicitly mention that executing more CPU instructions kill performance far quicker - in this case. As for mmap, perhaps you would like to present your own benchmark that contradicts the article. But anyway, I highly doubt that either of the basic things you mentioned are news to the implementors. The implementation is supposed to run on all kinds of processors with varying architectures so making the implementation portable is bound to leave performance on the table. Not to mention other constraints like maintainability and meeting the performance criteria for the common use case/workload.

dubmax123 10y ago

Wisdom: "The key to making programs fast is to make them do practically nothing. ;-)"

josuah 10y ago

I believed busybox's grep to be faster as it was very small, with GNU version slower due to the many features added over the time, but it is quite not true! On a slow device as some evoked said, the difference is highly noticeable.

mcguire 10y ago
That's actually an important point. It's easy to misinterpret "The key to making programs fast is to make them do practically nothing." Busybox's grep is small and simple. GNU grep is big and complex, which is actually why it's faster. It does a lot of work to avoid doing a lot of work.
- josuah 10y ago
  Oh, so 'do practically nothing' rather than 'be practically nothing'. I understand now.

hossbeast 10y ago

For fast grep, consider ag https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher

bsg75 10y ago
Faster than Ack, not always faster than grep.
- shandor 10y ago
  Really? My completely anecdotal experience is that ag kills grep. Stuff like searching usages of variables in Linux kernel seems to take ages with grep, whereas ag search on the whole repository doesn't take annoyingly long. I'll need to test this, just to see how wrong my "feeling" on the matter may be.
  - ggreer 10y ago
    I'm the author of ag. On a single file, ag is slower than GNU grep. The main reason is that ag prints line numbers when showing matches. Printing line numbers means going through the whole file and searching for \n's. For large files, this can be very resource-intensive. Here are the numbers (median of 5 runs, caches hot) for an 8GB file: % time ag hello4294967296 big_file.txt 134217728:hello4294967296 ag hello4294967296 big_file.txt 7.83s user 0.44s system 99% cpu 8.275 total % time grep hello4294967296 big_file.txt hello4294967296 grep hello4294967296 big_file.txt 2.17s user 0.91s system 99% cpu 3.085 total If you enable line numbers with grep -n, grep still wins, probably because ag's printing code is ridiculously inefficient: % time grep -n hello4294967296 big_file.txt 134217728:hello4294967296 grep -n hello4294967296 big_file.txt 3.37s user 0.97s system 99% cpu 4.338 total Unfortunately, I didn't write ag's printing code very sanely. It grew organically from users asking for small features here and there, and now it's a giant hairball. I've added some tests to reduce the chance of breaking changes, but it'll probably be a while before I fix this performance issue. Despite these limitations, ag tends to be much faster than grep -r in real-world use. There are several reasons why: 1. Ag has a multi-threaded architecture that can search multiple files at once. Grep is single-threaded. 2. Ag ignores binary and hidden files by default. Grep doesn't. 3. Ag obeys .gitignore/agignore/hgignore. Grep doesn't. These things really add up. For example, when searching my 20GB ~/code directory: ggreer@lithium:~/code% time ag instantiationname ... ag instantiationname 3.82s user 2.16s system 157% cpu 3.797 total ggreer@lithium:~/code% time grep -n -i -r instantiationname ... grep -n -i -r instantiationname 42.77s user 2.62s system 99% cpu 45.403 total Both find the same matches (some tests in the Node.js source), but ag does it 12x faster.

SunboX 10y ago

Another rule to make programs fast: break early, break often.

kuharich 10y ago

Previous discussions: http://news.ycombinator.com/item?id=1626305 http://news.ycombinator.com/item?id=1626305 http://news.ycombinator.com/item?id=2860759 http://news.ycombinator.com/item?id=2860759 https://news.ycombinator.com/item?id=6813937 https://news.ycombinator.com/item?id=6813937 https://news.ycombinator.com/item?id=9153203 https://news.ycombinator.com/item?id=9153203 http://news.ycombinator.com/item?id=2393587 http://news.ycombinator.com/item?id=2393587 https://news.ycombinator.com/item?id=9446382 https://news.ycombinator.com/item?id=9446382

underyx 10y ago

Wait, I always tried to make my pattern as short as possible and I thought it would speed up the searches. So I guess this means I'm actually better off searching for the longest possible match then?

burntsushi 10y ago
Pretty much, yes. Longer strings should also match fewer times than short strings, which should also speed things up (because reporting a match has its own overhead associated with it, like printing text to the terminal).

gumby 10y ago

Great bit of wisdom buried at the very end: > The key to making programs fast is to make them do practically nothing. ;-)