5 ms·

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 m

by 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.

burntsushi 10y ago
> The main reason is that ag prints line numbers when showing matches. 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!
- ggreer 10y ago
  Ag doesn't search line-by-line. It's only if a match is found that it goes back and looks for newlines. This optimizes the typical case (most files have no matches) at the expense of the rare case (file contains a match). Also, ag only uses PCRE if the query looks like a regex. Otherwise, it uses Boyer-Moore strstr.
  - burntsushi 10y ago
    > Ag doesn't search line-by-line. Really? Am I misunderstanding this code that very much appears to search line by line? https://github.com/ggreer/the_silver_searcher/blob/master/src/search.c#L113-L121 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.
    - ggreer 10y ago
      You didn't check to see what value opts.multiline has. It's initialized to TRUE in src/options.c. It's only set to FALSE if a user passes the undocumented --nomultiline option to ag. Default behavior with a regex query is https://github.com/ggreer/the_silver_searcher/blob/master/src/search.c#L92-L111 https://github.com/ggreer/the_silver_searcher/blob/master/sr...
      - burntsushi 10y ago
        Ah excellent, thank you for fixing my understanding. :-)
xorcist 10y ago
> Ag has a multi-threaded architecture that can search multiple files 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).
- ggreer 10y ago
  I've documented most of ag's tricks in various blog posts.[1] You're right that sequential reads are faster than random reads, but searching a bunch of source code is going to be a bunch of short reads no matter what. Each file is on the order of 50kB, or about 0.5ms if read at 100MB/sec. That's far less than the seek time of a hard drive. I've experimented a lot, and found it best to read ASAP, then let the OS & device figure out the best order to service the requests. 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 http://geoff.greer.fm/ag#related-posts 2. http://geoff.greer.fm/2012/09/07/the-silver-searcher-adding-pthreads/#comment-644691480 http://geoff.greer.fm/2012/09/07/the-silver-searcher-adding-... 3. https://github.com/ggreer/the_silver_searcher/blob/7d52078cb6460db0c4725a34da45cec4d6d349e8/src/util.c#L288 https://github.com/ggreer/the_silver_searcher/blob/7d52078cb...
shandor 10y ago
Thanks for the really detailed reply. 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 :)

by ggreer 10y ago

burntsushi 10y ago

> The main reason is that ag prints line numbers when showing matches. 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!

ggreer 10y ago
Ag doesn't search line-by-line. It's only if a match is found that it goes back and looks for newlines. This optimizes the typical case (most files have no matches) at the expense of the rare case (file contains a match). Also, ag only uses PCRE if the query looks like a regex. Otherwise, it uses Boyer-Moore strstr.
- burntsushi 10y ago
  > Ag doesn't search line-by-line. Really? Am I misunderstanding this code that very much appears to search line by line? https://github.com/ggreer/the_silver_searcher/blob/master/src/search.c#L113-L121 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.
  - ggreer 10y ago
    You didn't check to see what value opts.multiline has. It's initialized to TRUE in src/options.c. It's only set to FALSE if a user passes the undocumented --nomultiline option to ag. Default behavior with a regex query is https://github.com/ggreer/the_silver_searcher/blob/master/src/search.c#L92-L111 https://github.com/ggreer/the_silver_searcher/blob/master/sr...
    - burntsushi 10y ago
      Ah excellent, thank you for fixing my understanding. :-)

xorcist 10y ago

> Ag has a multi-threaded architecture that can search multiple files 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).

ggreer 10y ago
I've documented most of ag's tricks in various blog posts.[1] You're right that sequential reads are faster than random reads, but searching a bunch of source code is going to be a bunch of short reads no matter what. Each file is on the order of 50kB, or about 0.5ms if read at 100MB/sec. That's far less than the seek time of a hard drive. I've experimented a lot, and found it best to read ASAP, then let the OS & device figure out the best order to service the requests. 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 http://geoff.greer.fm/ag#related-posts 2. http://geoff.greer.fm/2012/09/07/the-silver-searcher-adding-pthreads/#comment-644691480 http://geoff.greer.fm/2012/09/07/the-silver-searcher-adding-... 3. https://github.com/ggreer/the_silver_searcher/blob/7d52078cb6460db0c4725a34da45cec4d6d349e8/src/util.c#L288 https://github.com/ggreer/the_silver_searcher/blob/7d52078cb...

shandor 10y ago

Thanks for the really detailed reply. 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 :)