Grep too slow? Use git-grep(developingandstuff.blogspot.de)
developingandstuff.blogspot.de
Grep too slow? Use git-grep
http://developingandstuff.blogspot.de/2013/07/grep-too-slow-tired-of-waiting-for-it.html
10 comments
The Silver Searcher is where it's at:
https://github.com/ggreer/the_silver_searcher
https://github.com/ggreer/the_silver_searcher
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.
It amazes me every time that I use it. You did a fantastic job. Thank you
Or at least ack, which came before it and still kicks grep's ass.
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.
Yea I have a lot of respect for little ag, used as much as my editor is.
And if your editor is Emacs, you can use this: https://github.com/Wilfred/ag.el
Obligatory vim equivalent: https://github.com/rking/ag.vim
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.
I remember these scripts coming up a while ago here, along with some scathing criticism.
How does it compare to ack? How did you go retraining the muscle memory used to type grep -E?
How does it compare to ack? How did you go retraining the muscle memory used to type grep -E?
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 [2] http://code.google.com/p/codesearch/ [3] https://github.com/rliebling/fastrAck
[1] http://swtch.com/~rsc/regexp/regexp4.html [2] http://code.google.com/p/codesearch/ [3] https://github.com/rliebling/fastrAck
Why is this? Would anyone with a better understanding of the situation care to explain why it would be faster?
I'm not quite, sure. But here's why GNU grep is fast [1]
1. http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu...
1. http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu...
See my comment[1], your intuition was correct.
[1] https://news.ycombinator.com/item?id=6016352
[1] https://news.ycombinator.com/item?id=6016352
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.
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.
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
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?).
"Look for specified patterns in the tracked files in the work tree"
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?).
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.
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...
I don't know the answer to your question, but the git source is simple and rewards reading.
I don't know the answer to your question, but the git source is simple and rewards reading.
If I were to guess, I would think grep has to traverse the directory tree while git knows all the file names already.
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.
Doesn't git already have a compressed and optimized index of your files?
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
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"
git grep --perl-regexp "outer\b"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.
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
I don't use homebrew, but your comment made me realize what I needed to do to successfully compile git with pcre. As a result, this now works:
This is an important feature for me, because I organize my code lexically (primarily by being disciplined about using unique names for things) and rely on grep to quickly find what I want. Occasionally one unique name overlaps with another, and then I really want to match the word boundary.
git grep -P "outer\b"
This is an important feature for me, because I organize my code lexically (primarily by being disciplined about using unique names for things) and rely on grep to quickly find what I want. Occasionally one unique name overlaps with another, and then I really want to match the word boundary.
The standard grep symbols for beginning and end of word are \< and \>
So try those. (I don't have a git repo handy to test)
(edit: I tested and it works)
So try those. (I don't have a git repo handy to test)
(edit: I tested and it works)
git grep '\<rout'
This is the syntax I use in Emacs, so I would love it if git-grep would do the same. But it doesn't, for me. Are you sure that it does for you?
Works for me (git 1.7.7.6)
https://news.ycombinator.com/item?id=6017401
https://news.ycombinator.com/item?id=6017401
Huh. How annoying that it doesn't just work everywhere. Annoying in two ways, actually: one, I want it to work; two, it bugs me not to understand what's going on.
"Grep too slow?" no...
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.
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:
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 ...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:
[1] https://news.ycombinator.com/item?id=2860932
[2] https://news.ycombinator.com/item?id=2862543
[3] http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=604408
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
[1] https://news.ycombinator.com/item?id=2860932
[2] https://news.ycombinator.com/item?id=2862543
[3] http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=604408
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
ls -lh |LANG=C sort +4 -5 -h
Wow sort is misbehaving, but I cannot verbalize the problem. I ran your two ls invocations on the kernel source directory and diffed the output.
There seems to be a bug regarding utf and sort in debian[1] but I am not sure if it is the same problem. Do you know if there is a bug in redhat's bugzilla for the issue? Up until this thread I did not realize sort behaved differently depending on the locale.[2] Are you sure its not a difference in locale expectations on how strings are sorted?
[1] http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=695489
[2] http://stackoverflow.com/questions/5909404/sort-not-sorting-...
--- /tmp/withutf 2013-07-09 21:03:23.060064079 -0400
+++ /tmp/withC 2013-07-09 21:03:30.069578205 -0400
@@ -1,26 +1,26 @@
total 544K
-rw-r--r-- 1 dfc dfc 252 Jul 9 19:27 Kconfig
-rw-r--r-- 1 dfc dfc 2.5K Jul 9 19:27 Kbuild
-drwxr-xr-x 113 dfc dfc 4.0K Jul 9 19:27 drivers
+drwxr-xr-x 2 dfc dfc 4.0K Jul 9 19:27 init
+drwxr-xr-x 2 dfc dfc 4.0K Jul 9 19:27 ipc
+drwxr-xr-x 2 dfc dfc 4.0K Jul 9 19:27 mm
+drwxr-xr-x 2 dfc dfc 4.0K Jul 9 19:27 usr
+drwxr-xr-x 3 dfc dfc 4.0K Jul 9 19:27 block
+drwxr-xr-x 3 dfc dfc 4.0K Jul 9 19:27 virt
+drwxr-xr-x 4 dfc dfc 4.0K Jul 9 19:27 crypto
+drwxr-xr-x 9 dfc dfc 4.0K Jul 9 19:27 lib
+drwxr-xr-x 9 dfc dfc 4.0K Jul 9 19:27 security
drwxr-xr-x 11 dfc dfc 4.0K Jul 9 19:27 kernel
drwxr-xr-x 12 dfc dfc 4.0K Jul 9 19:27 samples
drwxr-xr-x 13 dfc dfc 4.0K Jul 9 19:27 scripts
drwxr-xr-x 17 dfc dfc 4.0K Jul 9 19:27 tools
drwxr-xr-x 22 dfc dfc 4.0K Jul 9 19:27 sound
drwxr-xr-x 26 dfc dfc 4.0K Jul 9 19:27 include
-drwxr-xr-x 2 dfc dfc 4.0K Jul 9 19:27 init
-drwxr-xr-x 2 dfc dfc 4.0K Jul 9 19:27 ipc
-drwxr-xr-x 2 dfc dfc 4.0K Jul 9 19:27 mm
-drwxr-xr-x 2 dfc dfc 4.0K Jul 9 19:27 usr
drwxr-xr-x 32 dfc dfc 4.0K Jul 9 19:27 arch
drwxr-xr-x 36 dfc dfc 4.0K Jul 9 19:27 firmware
-drwxr-xr-x 3 dfc dfc 4.0K Jul 9 19:27 block
-drwxr-xr-x 3 dfc dfc 4.0K Jul 9 19:27 virt
-drwxr-xr-x 4 dfc dfc 4.0K Jul 9 19:27 crypto
drwxr-xr-x 55 dfc dfc 4.0K Jul 9 19:27 net
drwxr-xr-x 73 dfc dfc 4.0K Jul 9 19:27 fs
-drwxr-xr-x 9 dfc dfc 4.0K Jul 9 19:27 lib
-drwxr-xr-x 9 dfc dfc 4.0K Jul 9 19:27 security
+drwxr-xr-x 113 dfc dfc 4.0K Jul 9 19:27 drivers
-rw-r--r-- 1 dfc dfc 7.4K Jul 9 19:27 REPORTING-BUGS
drwxr-xr-x 101 dfc dfc 12K Jul 9 19:27 Documentation
-rw-r--r-- 1 dfc dfc 19K Jul 9 19:27 COPYING
There seems to be a bug regarding utf and sort in debian[1] but I am not sure if it is the same problem. Do you know if there is a bug in redhat's bugzilla for the issue? Up until this thread I did not realize sort behaved differently depending on the locale.[2] Are you sure its not a difference in locale expectations on how strings are sorted?
[1] http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=695489
[2] http://stackoverflow.com/questions/5909404/sort-not-sorting-...
The -h option is supposed to sort numerically when the numbers are in "human readable" format (i.e., 42k instead of 42137), as in the matching -h option for ls (and other commands). And the "+4 -5 -h" will sort on the 5'th column. It works great if you aren't using -h (sort +4 -5 -n, with a regular "ls -l" command). Also, works if the number is in the first column (as in: du -h |sort -h).
One is sorting "intelligently" numerically, the other is just comparing ascii values, on the first numerical field.
Thank you for indulging our rather off topic curiosity. Just so I am clear are you saying the reason for the difference in sorting has to do with locale interpretations and is not a bug in sort?
Even better: use 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]
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]
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.
I use the silver searcher: https://github.com/ggreer/the_silver_searcher
Using a clone of linus' kernel on a six year old amd64 box running debian/sid:
[1] 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":
You can read `ggrep` as either GNU grep or good grep.