6 ms·

GNU grep is 10x faster than Mac grep

122 points by jlebar 14y ago

martinp 14y ago
'why GNU grep is fast' from the FreeBSD mailing list: http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu...
- georgebashi 14y ago
  Which was discussed previously on HN, here: http://news.ycombinator.com/item?id=1626305 http://news.ycombinator.com/item?id=1626305
- chanux 14y ago
  Also relevant: The Treacherous Optimization http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
- haberman 14y ago
  Also classic: http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
- Mordor 14y ago
  > The key to making programs fast is to make them do practically nothing.
- deleted 14y ago
  [deleted]
- achille 14y ago
  I just replicated the test and I can confirm the FreeBSD grep compiled on Darwin is about 30x slower. % /usr/local/bin/grep --version /usr/local/bin/grep (GNU grep) 2.14 <snip> % time find . -type f | xargs /usr/local/bin/grep 83ba find . -type f 0.01s user 0.06s system 8% cpu 0.870 total xargs /usr/local/bin/grep 83ba 0.66s user 0.31s system 95% cpu 1.017 total % /usr/bin/grep --version grep (BSD grep) 2.5.1-FreeBSD % time find . -type f | xargs /usr/bin/grep 83ba find . -type f 0.01s user 0.06s system 0% cpu 28.434 total xargs /usr/bin/grep 83ba 31.65s user 0.40s system 99% cpu 32.113 total
- jasomill 14y ago
  There was also some discussion about this on one of the Apple mailing lists a few months ago, and it turns out there are major differences in how the two grep implementations on OS X interact with the buffer cache. In particular, empirical evidence suggests 10.6's GNU grep build caches its input, while 10.7+ BSD grep does not. Incidentally, on OS X, you can commonly get another order of magnitude improvement over even GNU grep with Spotlight's index: use xargs to grep only through files that pass a looser mdfind "pre-screen".
mattparlane 14y ago
For those using homebrew: brew install https://raw.github.com/Homebrew/homebrew-dupes/master/grep.rb
- paxswill 14y ago
  If you tap the `homebrew-dupes` repository, you will get updates in the future: brew tap homebrew/dupes brew install grep
  - lyso 14y ago
    Are there any other utils worth installing from that tap? Awk? OpenSSH?
    - paxswill 14y ago
      The repository with all of the formulas is here: https://github.com/homebrew/homebrew-dupes https://github.com/homebrew/homebrew-dupes The two I end up using semi-frequently are gcc and apple-gcc, for those projects that Clang just won't compile.
    - deleted 14y ago
      [deleted]
X-Istence 14y ago
This may also be because the default grep, i.e. BSD grep actually pays attention to what you have set in your environment variable LANG. Default on OS X is en_US.UTF-8. If the author were to set LANG to c. He would find that BSD grep suddenly speeds up tremendously.
- pdw 14y ago
  GNU grep certainly honors locale settings, and recent versions are fast even when you're using UTF-8 (since release 2.7 or so).
  - X-Istence 14y ago
    Hmm, interesting. Work is being done on BSD grep to make it faster than it is, so hopefully in the near future the two will be on par.
tehwalrus 14y ago
just tried on snow leopard, not quite 10x but nearly 2x faster, certainly. (admittedly, by firefox checkout is mercurial, and hg locate seems to pass something invalid to xargs half way through, but I guess the first chunk of files are the same.) Someone commented on the article that this might be caused by missing off the -F flag; I tried this, and -F makes both versions slightly faster again.
buster 14y ago
Obviously this means, Linux is 10x faster then Mac, ha! Seriously though, it's really amazing what performance they squeezed of that tool. Always amazing to grep through gigabytes of files in a few seconds.
deleted 14y ago
[deleted]
pooriaazimi 14y ago
I once tried a sed script on a couple million text files (60 GB in total) - they were web pages downloaded in some format (WARC? I don't remember what it was called) and I needed to change the formatting slightly (to feed them to Nutch) - Mac's default sed was literally 50 times slower than gsed (on the same machine). If I remember correctly, gsed finished the task in under two hours.
xtrahotsauce 14y ago
Does "git grep" use a system grep or does it implement grep on its own?
- meaty 14y ago
  It uses its own. See https://github.com/git/git/blob/master/builtin/grep.c https://github.com/git/git/blob/master/builtin/grep.c
  - unwind 14y ago
    That seems to be the "command infrastructure" for the grep builtin. The actual grep engine is in https://github.com/git/git/blob/master/grep.c https://github.com/git/git/blob/master/grep.c.
- drothlis 14y ago
  The article has an answer to that. I'm not sure if you're challenging the article's answer or if you just missed it...
  - xtrahotsauce 14y ago
    Oops, missed that part of the article, thanks!
pooriaazimi 14y ago
I'm not trying to start a theological war about grep/ack here, I'm just mentioning it in case someone hasn't heard about 'ack' before and they (like me) might find it extremely useful: http://betterthangrep.com http://betterthangrep.com It's grep, just better. It highlights the selected text, it shows which files, and in what line the text was found (and uses vivid colors so you can distinguish them easily), ignores .git and .hg directories (among others, that shouldn't be searched) by default, you can tell it to search, for example for only `--cpp` or `--objc` or `--ruby` or `--text` files (with a flag, not a filename pattern), and many many other neat features that I'm sure grep has, but you have to remember and memorize them. ack has sensible defaults. Why ack? http://betterthangrep.com/why-ack/ http://betterthangrep.com/why-ack/ manpage: http://betterthangrep.com/documentation/ http://betterthangrep.com/documentation/ Oh, and ack is written in perl and doesn't require admin privileges to install.
- Mordor 14y ago
  Not trying to start a war here either, but is it faster?
  - pooriaazimi 14y ago
    It's faster than BSD grep, but (in my experience) slightly slower than GNU grep. The productivity boost though, is enormous.
- ComputerGuru 14y ago
  Do you know of any C ports of ack? Ack is beautiful and productive, but nowhere near as fast as grep (orders of magnitude slower, in fact). gfind . -type f -exec grep -i mbr {} \; >| /dev/null 1.10s user 0.81s system 90% cpu 2.113 total gfind . -type f -exec ack -i mbr {} \; >| /dev/null 24.34s user 4.17s system 96% cpu 29.678 total (Yes, I know about the flag to search recursively. This is the most fair comparison.)
  - pooriaazimi 14y ago
    I'm not on a machine that I can use freely to test, but maybe you shouldn't use -exec? use xargs instead. I don't remember it being slower than grep that much...
eik3_de 14y ago
You should tack a "LC_CTYPE=C" in front of grep to get comparable results. A multibyte CTYPE can slow down grep up to factor 30.
pixelbeat 14y ago
I notice these Mac tools becoming a bit stale. sort is derived GNU sort, but from some ancient version. I guess this might be due in part to these tools now being GPLv3 ?
- saurik 14y ago
  https://news.ycombinator.com/item?id=3559990 https://news.ycombinator.com/item?id=3559990
- paxswill 14y ago
  Almost certainly. Apple stopped updating their tools past the GPLv2 versions, with the most noticeable example being gcc, which was frozen at 4.2 until they removed it.
wildranter 14y ago
Or... brew install ack
emidln 14y ago
Is speed really that much of a concern with grep? I typically use :vimgrep inside of vim, not because it's faster (it's orders of magnitude slower due to being interpreted vimscript), but because I hate remembering the differences between pcre/vim/gnu/posix regex syntax.
- jlebar 14y ago
  I regularly search my whole Firefox clone for keywords. If this takes 2s, that's plenty fast; if it takes 20s, I'd have to come up with some other way of doing it.
  - Evbn 14y ago
    Ctags?
    - jlebar 14y ago
      Firefox is quite complicated; we have code written in C, C++, JS, Python, Make, m4, plus at least three custom IDL formats. grep handles these with ease.
- _delirium 14y ago
  I use grep in some pipelines to bulk-process data, because if you have a fast grep, using it to pre-filter input files to remove definitely-not-matching lines is one of the quickest ways to speed up some kinds of scripts without rewriting the whole thing. And in that case, sometimes processing gigabytes+ of data, it's nice if it's fast. One common case: I have a Perl script processing a giant file, but it only processes certain lines that match a test. You can move that test to grep, to remove nonmatching lines before Perl even hits them, which will typically be much faster than making Perl loop through them. Say your script.pl is doing something like: next unless /relevant/; You can replace that with: grep "relevant" filename | perl ./script.pl
  - niggler 14y ago
    At the scale you are talking about (10Gb+ files), it's far more efficient to put primitive filtering in the application generating the lines in the first place. you pay two penalties for using grep: having another process touch the data and having to generate superfluous lines in the first place.

122 points by jlebar 14y ago

'why GNU grep is fast' from the FreeBSD mailing list: http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu...

georgebashi 14y ago
Which was discussed previously on HN, here: http://news.ycombinator.com/item?id=1626305 http://news.ycombinator.com/item?id=1626305
chanux 14y ago
Also relevant: The Treacherous Optimization http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
haberman 14y ago
Also classic: http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
Mordor 14y ago
> The key to making programs fast is to make them do practically nothing.
deleted 14y ago
[deleted]
achille 14y ago
I just replicated the test and I can confirm the FreeBSD grep compiled on Darwin is about 30x slower. % /usr/local/bin/grep --version /usr/local/bin/grep (GNU grep) 2.14 <snip> % time find . -type f | xargs /usr/local/bin/grep 83ba find . -type f 0.01s user 0.06s system 8% cpu 0.870 total xargs /usr/local/bin/grep 83ba 0.66s user 0.31s system 95% cpu 1.017 total % /usr/bin/grep --version grep (BSD grep) 2.5.1-FreeBSD % time find . -type f | xargs /usr/bin/grep 83ba find . -type f 0.01s user 0.06s system 0% cpu 28.434 total xargs /usr/bin/grep 83ba 31.65s user 0.40s system 99% cpu 32.113 total
jasomill 14y ago
There was also some discussion about this on one of the Apple mailing lists a few months ago, and it turns out there are major differences in how the two grep implementations on OS X interact with the buffer cache. In particular, empirical evidence suggests 10.6's GNU grep build caches its input, while 10.7+ BSD grep does not. Incidentally, on OS X, you can commonly get another order of magnitude improvement over even GNU grep with Spotlight's index: use xargs to grep only through files that pass a looser mdfind "pre-screen".

mattparlane 14y ago

For those using homebrew: brew install https://raw.github.com/Homebrew/homebrew-dupes/master/grep.rb

paxswill 14y ago
If you tap the `homebrew-dupes` repository, you will get updates in the future: brew tap homebrew/dupes brew install grep
- lyso 14y ago
  Are there any other utils worth installing from that tap? Awk? OpenSSH?
  - paxswill 14y ago
    The repository with all of the formulas is here: https://github.com/homebrew/homebrew-dupes https://github.com/homebrew/homebrew-dupes The two I end up using semi-frequently are gcc and apple-gcc, for those projects that Clang just won't compile.
  - deleted 14y ago
    [deleted]

X-Istence 14y ago

This may also be because the default grep, i.e. BSD grep actually pays attention to what you have set in your environment variable LANG. Default on OS X is en_US.UTF-8. If the author were to set LANG to c. He would find that BSD grep suddenly speeds up tremendously.

pdw 14y ago
GNU grep certainly honors locale settings, and recent versions are fast even when you're using UTF-8 (since release 2.7 or so).
- X-Istence 14y ago
  Hmm, interesting. Work is being done on BSD grep to make it faster than it is, so hopefully in the near future the two will be on par.

tehwalrus 14y ago

just tried on snow leopard, not quite 10x but nearly 2x faster, certainly. (admittedly, by firefox checkout is mercurial, and hg locate seems to pass something invalid to xargs half way through, but I guess the first chunk of files are the same.) Someone commented on the article that this might be caused by missing off the -F flag; I tried this, and -F makes both versions slightly faster again.

buster 14y ago

Obviously this means, Linux is 10x faster then Mac, ha! Seriously though, it's really amazing what performance they squeezed of that tool. Always amazing to grep through gigabytes of files in a few seconds.

deleted 14y ago

[deleted]

pooriaazimi 14y ago

I once tried a sed script on a couple million text files (60 GB in total) - they were web pages downloaded in some format (WARC? I don't remember what it was called) and I needed to change the formatting slightly (to feed them to Nutch) - Mac's default sed was literally 50 times slower than gsed (on the same machine). If I remember correctly, gsed finished the task in under two hours.

xtrahotsauce 14y ago

Does "git grep" use a system grep or does it implement grep on its own?

meaty 14y ago
It uses its own. See https://github.com/git/git/blob/master/builtin/grep.c https://github.com/git/git/blob/master/builtin/grep.c
- unwind 14y ago
  That seems to be the "command infrastructure" for the grep builtin. The actual grep engine is in https://github.com/git/git/blob/master/grep.c https://github.com/git/git/blob/master/grep.c.
drothlis 14y ago
The article has an answer to that. I'm not sure if you're challenging the article's answer or if you just missed it...
- xtrahotsauce 14y ago
  Oops, missed that part of the article, thanks!

pooriaazimi 14y ago

I'm not trying to start a theological war about grep/ack here, I'm just mentioning it in case someone hasn't heard about 'ack' before and they (like me) might find it extremely useful: http://betterthangrep.com http://betterthangrep.com It's grep, just better. It highlights the selected text, it shows which files, and in what line the text was found (and uses vivid colors so you can distinguish them easily), ignores .git and .hg directories (among others, that shouldn't be searched) by default, you can tell it to search, for example for only `--cpp` or `--objc` or `--ruby` or `--text` files (with a flag, not a filename pattern), and many many other neat features that I'm sure grep has, but you have to remember and memorize them. ack has sensible defaults. Why ack? http://betterthangrep.com/why-ack/ http://betterthangrep.com/why-ack/ manpage: http://betterthangrep.com/documentation/ http://betterthangrep.com/documentation/ Oh, and ack is written in perl and doesn't require admin privileges to install.

Mordor 14y ago
Not trying to start a war here either, but is it faster?
- pooriaazimi 14y ago
  It's faster than BSD grep, but (in my experience) slightly slower than GNU grep. The productivity boost though, is enormous.
ComputerGuru 14y ago
Do you know of any C ports of ack? Ack is beautiful and productive, but nowhere near as fast as grep (orders of magnitude slower, in fact). gfind . -type f -exec grep -i mbr {} \; >| /dev/null 1.10s user 0.81s system 90% cpu 2.113 total gfind . -type f -exec ack -i mbr {} \; >| /dev/null 24.34s user 4.17s system 96% cpu 29.678 total (Yes, I know about the flag to search recursively. This is the most fair comparison.)
- pooriaazimi 14y ago
  I'm not on a machine that I can use freely to test, but maybe you shouldn't use -exec? use xargs instead. I don't remember it being slower than grep that much...

eik3_de 14y ago

You should tack a "LC_CTYPE=C" in front of grep to get comparable results. A multibyte CTYPE can slow down grep up to factor 30.

pixelbeat 14y ago

I notice these Mac tools becoming a bit stale. sort is derived GNU sort, but from some ancient version. I guess this might be due in part to these tools now being GPLv3 ?

saurik 14y ago
https://news.ycombinator.com/item?id=3559990 https://news.ycombinator.com/item?id=3559990
paxswill 14y ago
Almost certainly. Apple stopped updating their tools past the GPLv2 versions, with the most noticeable example being gcc, which was frozen at 4.2 until they removed it.

wildranter 14y ago

Or... brew install ack

emidln 14y ago

Is speed really that much of a concern with grep? I typically use :vimgrep inside of vim, not because it's faster (it's orders of magnitude slower due to being interpreted vimscript), but because I hate remembering the differences between pcre/vim/gnu/posix regex syntax.

jlebar 14y ago
I regularly search my whole Firefox clone for keywords. If this takes 2s, that's plenty fast; if it takes 20s, I'd have to come up with some other way of doing it.
- Evbn 14y ago
  Ctags?
  - jlebar 14y ago
    Firefox is quite complicated; we have code written in C, C++, JS, Python, Make, m4, plus at least three custom IDL formats. grep handles these with ease.
_delirium 14y ago
I use grep in some pipelines to bulk-process data, because if you have a fast grep, using it to pre-filter input files to remove definitely-not-matching lines is one of the quickest ways to speed up some kinds of scripts without rewriting the whole thing. And in that case, sometimes processing gigabytes+ of data, it's nice if it's fast. One common case: I have a Perl script processing a giant file, but it only processes certain lines that match a test. You can move that test to grep, to remove nonmatching lines before Perl even hits them, which will typically be much faster than making Perl loop through them. Say your script.pl is doing something like: next unless /relevant/; You can replace that with: grep "relevant" filename | perl ./script.pl
- niggler 14y ago
  At the scale you are talking about (10Gb+ files), it's far more efficient to put primitive filtering in the application generating the lines in the first place. you pay two penalties for using grep: having another process touch the data and having to generate superfluous lines in the first place.