8 ms·

Grep too slow? Use git-grep

58 points by mparramon 13y ago

iambot 13y ago
Why is this? Would anyone with a better understanding of the situation care to explain why it would be faster?
- bbrks 13y ago
  I'm not quite, sure. But here's why GNU grep is fast [1] 1. http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu...
  - dfc 13y ago
    See my comment[1], your intuition was correct. [1] https://news.ycombinator.com/item?id=6016352 https://news.ycombinator.com/item?id=6016352
- asianexpress 13y ago
  Not sure if this is the primary reason, but: "Look for specified patterns in the tracked files in the work tree" http://git-scm.com/docs/git-grep http://git-scm.com/docs/git-grep Presumably, this would exclude a lot of assets or libraries that aren't part of your branch/repo, don't know what the OP's setup was (are those 11K+ files all tracked?).
  - raylu 13y ago
    If you have a compiled project, files that aren't tracked include all of your intermediate .o files, for example. If you `grep -r` the wrong way, it may traverse the .git directory.
- reddit_clone 13y ago
  If I were to guess, I would think grep has to traverse the directory tree while git knows all the file names already.
  - abc_lisper 13y ago
    This I don't believe to be true. For many years, I have kept a file with all the filenames in it, and did a grep on the files in the list, and it is slower than git-grep.
- nilved 13y ago
  Doesn't git already have a compressed and optimized index of your files?
- cjp 13y ago
  In a packed repo, git grep can mmap the pack file once and search through it in one fell swoop. If the pack file isn't already in the filesystem buffer, mmap will get it there quickly. The number of system calls is O(1). The limitation, as others have said, is git grep won't match files that are not already checked in. In a regular directory tree, recursive grep has to open and read directories, stat files, and read (or mmap?) each individual file. The number of system calls is O(N) on the number of directory entries.
- vdm 13y ago
  After config/parsing, it runs the search at the end of cmd_grep in https://github.com/git/git/blob/master/builtin/grep.c?source=c https://github.com/git/git/blob/master/builtin/grep.c?source... I don't know the answer to your question, but the git source is simple and rewards reading.
gruseom 13y ago
I haven't been able to figure out how to match a one-sided word boundary using git-grep. For example, say a file includes the word "router". You can do this to match the exact word: git grep -w router But what if you want to match just the word boundary at the start ("rout") or at the end ("outer")?
- nephyrin 13y ago
  git grep -E '\brout|outer\b'
  - gruseom 13y ago
    Are you sure this works? I've tried it many times.
- moonboots 13y ago
  The "--perl-regexp" flag to git grep enables perl flavored regexes, which contain explicit word boundary matching. To match only word starts, you could use the following: git grep --perl-regexp "\brout" and for just word endings git grep --perl-regexp "outer\b"
  - gruseom 13y ago
    This doesn't work for me, nor do the other two users' suggestions. I even just rebuilt git in case my version was out of date.
    - dfc 13y ago
      Are you using homebrew? $ brew info git git: stable 1.8.3.2, HEAD http://git-scm.com /usr/local/Cellar/git/HEAD (1324 files, 29M) * Built from source with: --with-blk-sha1 --with-pcre From: https://github.com/mxcl/homebrew/commits/master/Library/Formula/git.rb ==> Dependencies Optional: pcre, gettext ==> Options --with-blk-sha1 Compile with the block-optimized SHA1 implementation --with-gettext Build with gettext support --with-pcre Build with pcre support --without-completions Disable bash/zsh completions from "contrib" directory What does "built from source with" say?
eliben 13y ago
Even better: use pss (https://github.com/eliben/pss https://github.com/eliben/pss) It's not git-exclusive and has a ton of additional capabilities and features. Besides, being a pure Python program it's very easy to tweak if there's something you want done differently. [Disclaimer: shameless plug]
- JulianWasTaken 13y ago
  I use ag, but it's good to know this exists, I hadn't seen it before; good to have if I ever needed grep-as-library-code.
abimaelmartell 13y ago
"Grep too slow?" no...
- jasonlotito 13y ago
  On large enough code bases, git grep is much faster than grep. Couple that with repo for git and repo grep, and searching is painless. grep is fast, but the nature of git grep only makes it faster.
MatthewPhillips 13y ago
The Silver Searcher is where it's at: https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher
- duaneb 13y ago
  Yea I have a lot of respect for little ag, used as much as my editor is.
  - brcrth 13y ago
    And if your editor is Emacs, you can use this: https://github.com/Wilfred/ag.el https://github.com/Wilfred/ag.el
    - lepht 13y ago
      Obligatory vim equivalent: https://github.com/rking/ag.vim https://github.com/rking/ag.vim
      - unwind 13y ago
        As long as we're plugging: I realize nobody here would ever use Geany, but my Gitbrowser plug-in for that teeny-tiny editor/IDE has a keyboard shortcut to do git grep, and make the results clickable. See https://github.com/unwind/gitbrowser#greping-a-repository https://github.com/unwind/gitbrowser#greping-a-repository.
- michaelmior 13y ago
  Thanks for the pointer! Had seen this before and never really checked it out. It's crazy fast. Some very unscientific testing showed searching for a word in a project I'm working on took 0.07s with ag and 21.7s with ack and 16.3s with grep. Not at all definitive, but I'm definitely going to keep trying ag.
- ggreer 13y ago
  I'm glad you (and many others) like it. I've neglected Ag lately, but I'll definitely come back to it once I'm less busy (probably in the fall). There are some features users still want, but it's tricky to implement them without performance regressions.
dfc 13y ago
I would like to know what version of grep is being used? GNU or BSD grep? My money is that it is a OSX box with BSD grep.[1] Using a clone of linus' kernel on a six year old amd64 box running debian/sid: (master):dfc@fob-xray:~/lk$ time git grep "leap second" > /dev/null real 0m0.739s user 0m0.540s sys 0m0.650s (master):dfc@fob-xray:~/lk$ time grep -r --exclude-dir=.git "leap second" . > /dev/null real 0m0.833s user 0m0.400s sys 0m0.430s (master):dfc@fob-xray:~/lk$ du -sh . 1.4G . [1] http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu... ADDENDUM: After running a test on a Mac mini with 10.8.4 and a clone of the same repository I am overly confident that the title should be "BSD grep too slow? Use git-grep or GNU grep": jumbo:lk dfc$ purge ; time grep -r --exclude-dir=.git "leap second" . > /dev/null real 1m8.479s user 0m32.229s sys 0m2.348s jumbo:lk dfc$ purge ; time ggrep -r --exclude-dir=.git "leap second" . > /dev/null real 0m41.844s user 0m1.682s sys 0m6.035s jumbo:lk dfc$ purge ; time git grep "leap second" > /dev/null real 0m37.325s user 0m1.423s sys 0m4.213s jumbo:lk dfc$ gdu -sh . 1.3G . You can read `ggrep` as either GNU grep or good grep.
- calinet6 13y ago
  Well shoot. `brew install grep` is is then. And there's also ack, and ag... no shortage of options that are better than BSD grep, apparently. It's not "WOW GNU grep is fast!" it's, "wow, BSD grep is slow."
- deleted 13y ago
  [deleted]
  - dfc 13y ago
    Which is why that reference has been included in my comment from the beginning.
kbuck 13y ago
There's another interesting method for speeding up regex searches as well - a trigram index[1]. This is what Google's code search used to do. A simple command-line version written in Go[2] was released for local use. There's even an ack replacement based upon it[3]. [1] http://swtch.com/~rsc/regexp/regexp4.html http://swtch.com/~rsc/regexp/regexp4.html [2] http://code.google.com/p/codesearch/ http://code.google.com/p/codesearch/ [3] https://github.com/rliebling/fastrAck https://github.com/rliebling/fastrAck
derekp7 13y ago
Another way of speeding up grep is to turn off Unicode. Check your LANG environment variable -- if it is set to en_US.UTF-8 (or simething similar), set it to C then run grep. Also speeds up wc, and makes sort behave better. Note, you can also export environment variables for a specific command, if you don't want to change it for your whole shell, by specifying "variable=value" before the command: LANG=C grep ...
- dfc 13y ago
  Are you sure this is still true? I thought that bug was fixed a little while ago? ADDENDUM: I remembered discussing this a while back and I just found my old comment. Someone said "fun fact, gnu grep is slow with UTF8"[1] and I said "funner fact gnu grep was slow with UTF8"[2]. I reran the same grep that I used elsewhere in this discussion with C and with UTF8: root@fob-xray:lk# sync ; echo 3 > /proc/sys/vm/drop_caches root@fob-xray:lk# declare -x LANG=C ; /usr/bin/time grep --exclude-dir=.git -r "leap second" . > /dev/null 0.51user 3.04system 1:28.40elapsed 4%CPU (0avgtext+0avgdata 992maxresident)k 0inputs+0outputs (3major+340minor)pagefaults 0swaps root@fob-xray:lk# sync ; echo 3 > /proc/sys/vm/drop_caches root@fob-xray:lk# declare -x LANG=en_US.UTF-8 ; /usr/bin/time grep --exclude-dir=.git -r "leap second" . > /dev/null 0.41user 3.44system 1:27.01elapsed 4%CPU (0avgtext+0avgdata 1100maxresident)k 0inputs+0outputs (2major+367minor)pagefaults 0swaps I think you must have a version of GNU grep before 2.7.3 or 2.7.1. The UTF problem seems to have disappeared. There is a decent amount of information in the debian bug report[3]. [1] https://news.ycombinator.com/item?id=2860932 https://news.ycombinator.com/item?id=2860932 [2] https://news.ycombinator.com/item?id=2862543 https://news.ycombinator.com/item?id=2862543 [3] http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=604408 http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=604408
  - derekp7 13y ago
    Your right -- I've been stuck with older RHEL 4 systems at work, and they run grep 2.5.something (although I'm not able to reproduce the problem at home now, maybe I'm not on an old enough RHEL 4 system -- will check when I get back to work). Problem disappears with the grep in RHEL 6. However there are still glitches in the sort command. For example: ls -lh |sort +4 -5 -h doesn't work (at least on my RHEL 6.4 box), yet: ls -lh |LANG=C sort +4 -5 -h does work.
7histle 13y ago
https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher
otikik 13y ago
I use the silver searcher: https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher

58 points by mparramon 13y ago

iambot 13y ago

Why is this? Would anyone with a better understanding of the situation care to explain why it would be faster?

bbrks 13y ago
I'm not quite, sure. But here's why GNU grep is fast [1] 1. http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu...
- dfc 13y ago
  See my comment[1], your intuition was correct. [1] https://news.ycombinator.com/item?id=6016352 https://news.ycombinator.com/item?id=6016352
asianexpress 13y ago
Not sure if this is the primary reason, but: "Look for specified patterns in the tracked files in the work tree" http://git-scm.com/docs/git-grep http://git-scm.com/docs/git-grep Presumably, this would exclude a lot of assets or libraries that aren't part of your branch/repo, don't know what the OP's setup was (are those 11K+ files all tracked?).
- raylu 13y ago
  If you have a compiled project, files that aren't tracked include all of your intermediate .o files, for example. If you `grep -r` the wrong way, it may traverse the .git directory.
reddit_clone 13y ago
If I were to guess, I would think grep has to traverse the directory tree while git knows all the file names already.
- abc_lisper 13y ago
  This I don't believe to be true. For many years, I have kept a file with all the filenames in it, and did a grep on the files in the list, and it is slower than git-grep.
nilved 13y ago
Doesn't git already have a compressed and optimized index of your files?
cjp 13y ago
In a packed repo, git grep can mmap the pack file once and search through it in one fell swoop. If the pack file isn't already in the filesystem buffer, mmap will get it there quickly. The number of system calls is O(1). The limitation, as others have said, is git grep won't match files that are not already checked in. In a regular directory tree, recursive grep has to open and read directories, stat files, and read (or mmap?) each individual file. The number of system calls is O(N) on the number of directory entries.
vdm 13y ago
After config/parsing, it runs the search at the end of cmd_grep in https://github.com/git/git/blob/master/builtin/grep.c?source=c https://github.com/git/git/blob/master/builtin/grep.c?source... I don't know the answer to your question, but the git source is simple and rewards reading.

gruseom 13y ago

I haven't been able to figure out how to match a one-sided word boundary using git-grep. For example, say a file includes the word "router". You can do this to match the exact word: git grep -w router But what if you want to match just the word boundary at the start ("rout") or at the end ("outer")?

nephyrin 13y ago
git grep -E '\brout|outer\b'
- gruseom 13y ago
  Are you sure this works? I've tried it many times.
moonboots 13y ago
The "--perl-regexp" flag to git grep enables perl flavored regexes, which contain explicit word boundary matching. To match only word starts, you could use the following: git grep --perl-regexp "\brout" and for just word endings git grep --perl-regexp "outer\b"
- gruseom 13y ago
  This doesn't work for me, nor do the other two users' suggestions. I even just rebuilt git in case my version was out of date.
  - dfc 13y ago
    Are you using homebrew? $ brew info git git: stable 1.8.3.2, HEAD http://git-scm.com /usr/local/Cellar/git/HEAD (1324 files, 29M) * Built from source with: --with-blk-sha1 --with-pcre From: https://github.com/mxcl/homebrew/commits/master/Library/Formula/git.rb ==> Dependencies Optional: pcre, gettext ==> Options --with-blk-sha1 Compile with the block-optimized SHA1 implementation --with-gettext Build with gettext support --with-pcre Build with pcre support --without-completions Disable bash/zsh completions from "contrib" directory What does "built from source with" say?

eliben 13y ago

Even better: use pss (https://github.com/eliben/pss https://github.com/eliben/pss) It's not git-exclusive and has a ton of additional capabilities and features. Besides, being a pure Python program it's very easy to tweak if there's something you want done differently. [Disclaimer: shameless plug]

JulianWasTaken 13y ago
I use ag, but it's good to know this exists, I hadn't seen it before; good to have if I ever needed grep-as-library-code.

abimaelmartell 13y ago

"Grep too slow?" no...

jasonlotito 13y ago
On large enough code bases, git grep is much faster than grep. Couple that with repo for git and repo grep, and searching is painless. grep is fast, but the nature of git grep only makes it faster.

MatthewPhillips 13y ago

The Silver Searcher is where it's at: https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher

duaneb 13y ago
Yea I have a lot of respect for little ag, used as much as my editor is.
- brcrth 13y ago
  And if your editor is Emacs, you can use this: https://github.com/Wilfred/ag.el https://github.com/Wilfred/ag.el
  - lepht 13y ago
    Obligatory vim equivalent: https://github.com/rking/ag.vim https://github.com/rking/ag.vim
    - unwind 13y ago
      As long as we're plugging: I realize nobody here would ever use Geany, but my Gitbrowser plug-in for that teeny-tiny editor/IDE has a keyboard shortcut to do git grep, and make the results clickable. See https://github.com/unwind/gitbrowser#greping-a-repository https://github.com/unwind/gitbrowser#greping-a-repository.
michaelmior 13y ago
Thanks for the pointer! Had seen this before and never really checked it out. It's crazy fast. Some very unscientific testing showed searching for a word in a project I'm working on took 0.07s with ag and 21.7s with ack and 16.3s with grep. Not at all definitive, but I'm definitely going to keep trying ag.
ggreer 13y ago
I'm glad you (and many others) like it. I've neglected Ag lately, but I'll definitely come back to it once I'm less busy (probably in the fall). There are some features users still want, but it's tricky to implement them without performance regressions.

dfc 13y ago

I would like to know what version of grep is being used? GNU or BSD grep? My money is that it is a OSX box with BSD grep.[1] Using a clone of linus' kernel on a six year old amd64 box running debian/sid: (master):dfc@fob-xray:~/lk$ time git grep "leap second" > /dev/null real 0m0.739s user 0m0.540s sys 0m0.650s (master):dfc@fob-xray:~/lk$ time grep -r --exclude-dir=.git "leap second" . > /dev/null real 0m0.833s user 0m0.400s sys 0m0.430s (master):dfc@fob-xray:~/lk$ du -sh . 1.4G . [1] http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu... ADDENDUM: After running a test on a Mac mini with 10.8.4 and a clone of the same repository I am overly confident that the title should be "BSD grep too slow? Use git-grep or GNU grep": jumbo:lk dfc$ purge ; time grep -r --exclude-dir=.git "leap second" . > /dev/null real 1m8.479s user 0m32.229s sys 0m2.348s jumbo:lk dfc$ purge ; time ggrep -r --exclude-dir=.git "leap second" . > /dev/null real 0m41.844s user 0m1.682s sys 0m6.035s jumbo:lk dfc$ purge ; time git grep "leap second" > /dev/null real 0m37.325s user 0m1.423s sys 0m4.213s jumbo:lk dfc$ gdu -sh . 1.3G . You can read `ggrep` as either GNU grep or good grep.

calinet6 13y ago
Well shoot. `brew install grep` is is then. And there's also ack, and ag... no shortage of options that are better than BSD grep, apparently. It's not "WOW GNU grep is fast!" it's, "wow, BSD grep is slow."
deleted 13y ago
[deleted]
- dfc 13y ago
  Which is why that reference has been included in my comment from the beginning.

kbuck 13y ago

There's another interesting method for speeding up regex searches as well - a trigram index[1]. This is what Google's code search used to do. A simple command-line version written in Go[2] was released for local use. There's even an ack replacement based upon it[3]. [1] http://swtch.com/~rsc/regexp/regexp4.html http://swtch.com/~rsc/regexp/regexp4.html [2] http://code.google.com/p/codesearch/ http://code.google.com/p/codesearch/ [3] https://github.com/rliebling/fastrAck https://github.com/rliebling/fastrAck

derekp7 13y ago

Another way of speeding up grep is to turn off Unicode. Check your LANG environment variable -- if it is set to en_US.UTF-8 (or simething similar), set it to C then run grep. Also speeds up wc, and makes sort behave better. Note, you can also export environment variables for a specific command, if you don't want to change it for your whole shell, by specifying "variable=value" before the command: LANG=C grep ...

dfc 13y ago
Are you sure this is still true? I thought that bug was fixed a little while ago? ADDENDUM: I remembered discussing this a while back and I just found my old comment. Someone said "fun fact, gnu grep is slow with UTF8"[1] and I said "funner fact gnu grep was slow with UTF8"[2]. I reran the same grep that I used elsewhere in this discussion with C and with UTF8: root@fob-xray:lk# sync ; echo 3 > /proc/sys/vm/drop_caches root@fob-xray:lk# declare -x LANG=C ; /usr/bin/time grep --exclude-dir=.git -r "leap second" . > /dev/null 0.51user 3.04system 1:28.40elapsed 4%CPU (0avgtext+0avgdata 992maxresident)k 0inputs+0outputs (3major+340minor)pagefaults 0swaps root@fob-xray:lk# sync ; echo 3 > /proc/sys/vm/drop_caches root@fob-xray:lk# declare -x LANG=en_US.UTF-8 ; /usr/bin/time grep --exclude-dir=.git -r "leap second" . > /dev/null 0.41user 3.44system 1:27.01elapsed 4%CPU (0avgtext+0avgdata 1100maxresident)k 0inputs+0outputs (2major+367minor)pagefaults 0swaps I think you must have a version of GNU grep before 2.7.3 or 2.7.1. The UTF problem seems to have disappeared. There is a decent amount of information in the debian bug report[3]. [1] https://news.ycombinator.com/item?id=2860932 https://news.ycombinator.com/item?id=2860932 [2] https://news.ycombinator.com/item?id=2862543 https://news.ycombinator.com/item?id=2862543 [3] http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=604408 http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=604408
- derekp7 13y ago
  Your right -- I've been stuck with older RHEL 4 systems at work, and they run grep 2.5.something (although I'm not able to reproduce the problem at home now, maybe I'm not on an old enough RHEL 4 system -- will check when I get back to work). Problem disappears with the grep in RHEL 6. However there are still glitches in the sort command. For example: ls -lh |sort +4 -5 -h doesn't work (at least on my RHEL 6.4 box), yet: ls -lh |LANG=C sort +4 -5 -h does work.

7histle 13y ago

https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher

otikik 13y ago

I use the silver searcher: https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher