Why GNU grep is fast (2010)
lists.freebsd.org
lists.freebsd.org
<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.
sudo mv /bin/echo /bin/e
mv: rename echo to e: Operation not permitted
1. Hold Cmd-R as you reboot. That puts you in recovery mode.
2. Bring up a terminal.
3. Run 'csrutil disable'
4. Reboot back into regular mode
It is possible to disable it and even if you couldn't I don't think it has any impact on licensing.
It's easy enough for people who want GNU grep to install it themselves.
If they use GNU grep as part of a distribution that might be included with hardware, it means the GPLv3 anti-tivoization clauses affect any hardware that that distribution is on. Apple being first and foremost a consumer hardware manufacturer whose software exists to add value to that hardware, and wanting to maintain its ability to do what it wants with that hardware including not being constrained by the GPLv3's anti-tivoization clause (even if they aren't doing anything now that would fall afoul of it, they might want to in the future, and don't want to tie their hands in advance), has a very good reason not to touch GPLv3 at all.
(There's other GPLv3 provisions that might be problematic, too, GPLv3 involves more than just a requirement to provide source also licensed under the GPLv3.)
No, they could not. The GPLv3 requires modification information be provided to the "user" by whom a consumer product is "received", not only the "owner" by whom it is "purchased", so lease vs. sell has no effect on the obligations (at least no effect clear from the text of the license.)
For example. A car rental service buys a modern car that has software in it. Does they need additional copyright permission on top of the purchase in order to lease the car out?
A taxi driver buys a modern car with the intention to rent out his service with the car. Is additional copyright permission required?
A school provides students with access to the school computers. Is that conveying a copy of software? What if its "open door day", where the public is invited?
A public library want to have public available computers. Are they conveying copies of software through that?
If you looked at WIPO, it explicitly say no. If you looked at Information Society Directive 2001/29/EC, they explicitly say yes, under the condition that the offer is directed to the public. If you looked at the court cases that has interpreted those texts, then they are inconclusive.
If its intended as a "Consumer Product" as defined in the license, you need copyright permission to put the copy of the software in the product; at that point you either except the condition of providing the required information and functionality to the user to whom you will eventually provide the product -- whether by rental or sale -- or you violate the GPLv3 by putting the copy in the device.
Once you have accepted that condition, you are bound by it.
> For example. A car rental service buys a modern car that has software in it. Does they need additional copyright permission on top of the purchase in order to lease the car out?
They don't need "additional copyright permission", but if the initial copyright license accepted when acquiring the car has restrictions that apply to the use of the software in rentals, then they are bound by those restrictions.
FYI: OS X's grep is FreeBSD's bsdgrep. However, FreeBSD's default grep is still an ancient version of GNU grep (bsdgrep is only available as bsdgrep.).
Also, older versions of OS X used to have GNU grep [1]. So the more likely explanation is Apple's purge of GPL code from OS X. Since later grep versions use GPLv3, GNU grep was a dead end for them.
Unfortunately, FreeBSD's bsdgrep has some very annoying bugs (that are also present in OS X). No one seems to care about them, even when a patch is provided [2].
[1] http://opensource.apple.com/release/mac-os-x-1075/ [2] https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=201650
On occasion I search for bsdgrep bugs, and did not find the comment / patch in [2]. Thank you for pointing it out, I'll look at it when I can.
I FreeBSD developer requested that I added a report to that bug [1]. After adding the patch to the report, I also reported this to the list [2]. I have also tried to contact the maintainer of bsdgrep with no luck. At some point you just give up ;).
[1] https://lists.freebsd.org/pipermail/freebsd-questions/2016-J... [2] https://lists.freebsd.org/pipermail/freebsd-questions/2016-J...
Also, GNU's bulletin on Apple Boycott: https://www.gnu.org/bulletins/bull18.html#SEC13
And also this article which explains why apple is BSD mostly: https://scalibq.wordpress.com/2012/08/02/apples-os-x-is-not-...
raw text: http://hastebin.com/raw/zohoxaxuyi
- https://news.ycombinator.com/item?id=1626305 (115 comments, 2193 days ago)
- https://news.ycombinator.com/item?id=2393587 (68 comments, 1972 days ago)
- https://news.ycombinator.com/item?id=2860759 (43 comments, 1842 days ago)
I'm sure there are more.
By the way, it would be great if there would be a "Related" widget with the number of comments somewhere in the comment page.
"The key to making programs fast is to make them do practically nothing."
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...
But my optimizations were guided by the profiler and a (more or less) correct analysis of the results.
However that requires a level of process that is either too costly, or too rigid for many IT companies to follow.
I wish more places would try this. Sure, your app works in downtown SF, but if your customer is in Nowheresville, AL, you should probably spend more time optimizing.
All of your apps will say "I have data access!" and send a million requests for tens of megabytes, which will never finish, melting your battery as it waits on timeouts and completely choking the access you do have preventing you from doing anything useful.
Why making program faster when it works fine on their top of the line desktop machines?
Basically means only do exactly what's required, nothing more, nothing less.
> The only bug-free line of code is the line of code that is never written.
I've heard about PEP484 and hope it catches on, but unfortunately it's for python3 and a lot of people are still stuck on python2 for many reasons.
0: http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
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?
Compare to Knuth-Pratt-Morris: http://www.cs.utexas.edu/users/moore/best-ideas/string-searc...
I'll need to test this, just to see how wrong my "feeling" on the matter may be.
% 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
% 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
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
Wouldn't it be more accurate to say that ag is slower than grep because it does line-by-line searching where as grep does not? What would happen if ag adopted grep's method of searching where it doesn't do line-by-line? Is that possible with PCRE?
I think it would be very interesting to combine the tricks used by grep with the tricks used by ag. I don't think it has been done yet!
Also, ag only uses PCRE if the query looks like a regex. Otherwise, it uses Boyer-Moore strstr.
Really? Am I misunderstanding this code that very much appears to search line by line? https://github.com/ggreer/the_silver_searcher/blob/master/sr...
GNU grep never does "throw line into buffer and then search it." GNU grep just searches the entire buffer at once.
I guess that explains my experience really well, since I'm always searching from a big amount of small files like huge codebases and config files, and almost never from files bigger than several megabytes.
ag has tremendously improved my quality of life in that regard, so please accept my sincere Thank You for making ag :)
Interesting. I would have guessed you were i/o bound there, and file systems usually give higher throughput on sequential reads. Tried it on my bog standard Linux box but couldn't get it close to grep performance wise. Can you share how you did it?
> Ag ignores binary and hidden files by default
Like grep -I? That could easily cause unexpected results. Many files are treated as binary just because they contain parts of a non native character set (such as latin-1 files on a utf-8 system).
Also, modern SSDs (and even HDDs) have tricks like NCQ. With caches cleared (cold reads), multi-threaded ag is 2x faster on SSDs. Disabling NCQ makes multi-threaded perform the same as single-threaded.[2] (Again, with caches cleared.)
> … That could easily cause unexpected results. …
I've received very few complaints about ag's binary detection. It does a nice job of balancing false positives, false negatives, and performance. See is_binary() in src/utils.c for the exact code[3].
1. http://geoff.greer.fm/ag#related-posts
2. http://geoff.greer.fm/2012/09/07/the-silver-searcher-adding-...
3. https://github.com/ggreer/the_silver_searcher/blob/7d52078cb...
"The Silver Searcher is a tool for searching code." (http://geoff.greer.fm/ag/)
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/UFscif...
Loop unrolling still helps even with brand spankin new CPUs. Some intent cannot be inferred.
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.
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.
You can. Use a Python wrapper to invoke a program written in another language. Python becomes faster.
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?
- ack [0]
- ag (also known as the silver searcher) [1]
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.
> 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.
Really? Pretty sure it does. Have you read the source code? There is a specific part that looks to see if it has a literal and will use that. If it has an exact match, then it will skip the DFA completely.
It does help when the search string comprises of regex metacharacters and you actually wanted a literal search.
It searches code about 3–5× faster than ack.
It searches code as fast as the_silver_searcher(ag).
It ignores file patterns from your .gitignore.
It searches UTF-8, EUC-JP and Shift_JIS files.
It provides binaries for multi platform (Mac OS X, Windows, Linux).
But even more so, sensible defaults that work nicely for code search use cases. And written in Go, without accumulated cruft for 200 platforms and POSIX subtleties like grep, so even someone like me can hack it to do something special if I want to.
$ time ag zmq | wc -l
63
real 0m0.017s
user 0m0.022s
sys 0m0.016s
$ time pt zmq | wc -l
296
real 0m0.013s
user 0m0.014s
sys 0m0.017s
ggreer@lithium:~/code% time ag instantiationname
...
ag instantiationname 3.82s user 2.16s system 157% cpu 3.797 total
ggreer@lithium:~/code% time pt -i instantiationname
...
pt -i instantiationname 136.65s user 0.77s system 773% cpu 17.761 total
Another issue is that pt tends to bail on errors. If you tell it to follow symlinks (-f) and it encounters a single broken symlink, it will exit without finishing the search. Every other search tool I know of (grep, ag, ack) will keep on truckin'.
That said, pt is faster than ag for case-sensitive matches. It looks like much of that comes from a parallelized directory traversal. The architecture of ag is different. It has many worker threads, but only one thread going through dirs. Looks like I'll have to step-up my game. :)
% time pt -i hello4294967296 big_file.txt
big_file.txt
134217728:hello4294967296
pt -i hello4294967296 big_file.txt 535.86s user 1.35s system 100% cpu 8:56.97 total
Also, it looks like pt was beating ag because it defaults to case-sensitive search. If I make ag do the same case-sensitive search, it's slightly faster in my benchmarks (0.63s to search my ~/code directory vs pt's 0.65s).
My main beef with ag was probably due to some older distribution or worse packager (tried it a few years ago), because I tried it again now from "brew" and it's pretty much just as convenient as pt -- and with some more features.
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).
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.
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.
* 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/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.)
I might be wrong, but I have a recollection that this was massively improved somewhat recently, maybe a year or so back. Are you using a recent-ish version?
This might also be to do with the needle - I think I was testing with a fixed ASCII string, which should work the same in either the UTF-8 or C locales (assuming a UTF-8 file). But \w I guess should behave differently depending on locale, e.g. I'd expect it to match ß in UTF-8 but not C.
> I might be wrong, but I have a recollection that this was massively improved somewhat recently, maybe a year or so back.
I seem to recall hearing that too. A brief skim of the commit log shows multiple possible improvements, but I don't have time to drill down further into that.
It could just be that it used to be worse. :-)
(If you look in the core DFA loop, which is in the `dfaexec_main` function inside `dfa.c`, then you can see that there is a completely different path through the DFA if it needs to use multibyte encodings.)
> But \w I guess should behave differently depending on locale, e.g. I'd expect it to match ß in UTF-8 but not C.
Exactly. But this doesn't have to have a measurable performance impact, assuming the number of matches doesn't radically change. (Well, this is a bit of a lie, because a Unicode aware \w is much bigger than an ASCII-only \w, which implies the DFA needs more memory, which could lead to a more general slowdown if the state cache needs to get emptied more frequently.)
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13....
Running a few threads/processes in parallel could improve throughput with latency hiding, but adding more shouldn't give any benefit.
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.)
"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.
> The key to making programs fast is to make them do practically nothing. ;-)