7 ms·

It's also worth checking out The Silver Searcher: https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher

by pie 12y ago

sillysaurus3 12y ago
How is it so fast? Files are mmap()ed instead of read into a buffer. It's hard to believe this would give a significant performance boost. Is there evidence of this?
- deleted 12y ago
  [deleted]
  - sillysaurus3 12y ago
    If anything, that post is evidence of how tricky optimization is, and how easy it is to fool yourself about what matters. It's probably best to be skeptical about mmap() as a performance optimization over reading into a buffer unless evidence demonstrates otherwise. Most OS's do a pretty good job of caching at the filesystem level, and under the hood paging is essentially reading into a buffer anyway. mmap() might make the code simpler, but it's hard to imagine it makes it faster. If it does, I'd like to understand why. EDIT: The post was http://geoff.greer.fm/2012/08/25/the-silver-searcher-benchmarking-revisions/ http://geoff.greer.fm/2012/08/25/the-silver-searcher-benchma...
- duaneb 12y ago
  > It's hard to believe this would give a significant performance boost. Why is that so hard to believe? It's a standard optimization—the kernel can almost certainly coordinate reading better than your userspace C can.
  - sillysaurus3 12y ago
    So are we talking about constant-time optimization, then? I.e. it shaves off a few milliseconds regardless of how complex the search is, or how many files it's reading, or how large each file is. I'll happily concede that mmap() might do that. But a performance boost linear w.r.t. search complexity/number of files/filesize? Hard to believe, and I should go measure it myself to prove the point or learn why I'm mistaken.
    - Crito 12y ago
      Likely a constant time improvement... for each file being searched. I don't think that anybody is claiming that mmapping actually changes the algorithmic complexity of the actual search operations.
    - duaneb 12y ago
      Constant-time improvements are still improvements, especially if they're in an inner loop. Otherwise we would all be using Python and just writing great algorithms.
- tobinfricke 12y ago
  There is a nice (and often posted) mailing list post explaining some of the reasons GNU Grep is so fast: http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu... He mentions: "So even nowadays, using --mmap can be worth a >20% speedup."
  - sillysaurus3 12y ago
    Now I'm burning with curiosity. I have to know why! My plan: - replicate the experiment, confirm --mmap shaves off a non-negligible amount of time. It could be that his computer happened to be running something in the background that was using his harddrive, for example, which would skew the results. - look at the code, figure out the exact difference between what --mmap is doing and what it does by default. Confirm that the problem isn't in grep itself (it's probably not, but it's important to check). - dig into the kernel source to figure out the difference under the hood and why it might be faster.
    - makmanalp 12y ago
      I wonder if it has to do with not having to copy data back and forth between kernel and userspace. My mildly uneducated thought is that you could do this with splice() or whatever, but mmap is an easy drop-in replacement. edit: I've been reading your posts for a while and I like them, but I keep wondering, why do you have sillysaurus1-2-3?
      - sillysaurus3 12y ago
        That's what has me so curious, because it doesn't seem like copying between kernel/userspace should account for a 20% speed drop. Once data is in the L3 CPU cache, it should be inexpensive to move it around. Regarding my ancestry, I'm sillysaurus3 because I've (rightfully) been in trouble twice with the mods for getting too personal on HN. I apologized and changed my behavior accordingly, and additionally created a new account both times to serve as a constant reminder to be objective and emotionless. There's rarely a reason to argue with a person rather than with an idea. Debating ideas, not people, has a bunch of nice benefits: it's easier to learn from your mistakes, it makes for better reading, etc. It's pretty important, because forgetting that principle leads to exchanges like https://news.ycombinator.com/item?id=7700145 https://news.ycombinator.com/item?id=7700145 Another nice benefit of creating a new account is that you lose your downvoting privilege for a time, which made me more thoughtful about whether a downvote is actually justified.
- bcoates 12y ago
  The last time I had to do fast, large sequential disk reads on Linux it was surprisingly complex to get all the buffering/caching/locking to not do the wrong thing and slow me down a lot. I wouldn't be surprised if non-optimized mmap() is a whole lot faster than non-optimized use of high level file i/o libraries.
- ggreer 12y ago
  In my benchmarking, mmap() was about 20% faster than read() on OS X, but the same speed on Ubuntu. Pretty much everything else in the list (pthreads, JIT regex compiler, Boyer-Moore-Horspool strstr(), etc) improves performance more than mmap(). Also, mmap() has the disadvantage that it can segfault your process if something else makes the underlying file smaller. In fact, there have been kernel bugs related to separate processes mmapping and truncating the same file.[1] I mostly use mmap() because my primary computer is a mac. A side note: Parts of OS X's kernel seem... not very optimized to say the least. See the bar graph at http://geoff.greer.fm/2012/09/07/the-silver-searcher-adding-pthreads/ http://geoff.greer.fm/2012/09/07/the-silver-searcher-adding-... for an example. 1. http://lwn.net/Articles/357767/ http://lwn.net/Articles/357767/
pmelendez 12y ago
1000 times this... it is exactly like ack-grep but faster :)
- 5h 12y ago
  I normally tell people to use ack because it's like grep but faster (owing to it's sensible defaults) ... if I use this I'm worried I might go too fast and travel backwards in time or something.
  - csgavino1 12y ago
    Give ag a shot, you'll be able to relive the emotions you felt when you switched to ack from grep, but this time you're switching to ag from ack.
- djeikyb 12y ago
  One thing I miss a little is that ack has the super convenient: ack --java "foo" while with ag you write: ag -G"\.java$" "foo" But yes, ack and ag feel pretty identical except for the speed. Most of the time the speed improvement is irrelevant to me, except sometimes now I'll use ag in my home folder, and it's still fairly snappy.
  - coffeeaddicted 12y ago
    That was too much typing anyway. When you mostly work with one language something like this is nice (in my case c/c++): alias ack-cpp='ack-grep --type=cpp --type=cc'
    - llimllib 12y ago
      I have that aliased to 'cack'. Then ruby is 'rack', python is 'pack', go is 'gack', etc. (I've never needed to use the rackup "rack" command directly, fortunately, if you do you ought to use a different alias)
      - 12y ago
tveita 12y ago
I switched to this after Ack 2 removed all options to search through binary files. ag is less picky, and the increased speed is a nice bonus.
- pudquick 12y ago
  Binary file search was my primary motivator as well. I really do love the functionality of the tool.
ihodes 12y ago
Big problem with ag is that it appears to be broken on even moderately larger files where ack works just fine: https://github.com/ggreer/the_silver_searcher/issues/384 https://github.com/ggreer/the_silver_searcher/issues/384
- ggreer 12y ago
  pcre_exec()'s length and offset parameters are ints, so there's not much I can do about files over 2GB. I really don't want to split the file into chunks and deal with matches across boundaries. That's just asking for bugs. I guess I could make literal string searches work, at least on 64 bit platforms. Honestly though, I don't think ag is the right tool for that job. For a single huge file, grep is going to be the same speed. Possibly faster, since grep's strstr() has been optimized for longer than I've been alive.
  - tveita 12y ago
    If ag knows it can't search the whole file, it should at least give a warning. Or why not use search_stream? Silently skipping parts of it seems like the worst thing to do.
    - ggreer 12y ago
      Good point about the warning. I'll add that. With regards to search_stream() in search.c... all I can say is that I'm sorry: https://github.com/ggreer/the_silver_searcher/blob/master/src/search.c#L163 https://github.com/ggreer/the_silver_searcher/blob/master/sr... I built ag for myself; both as a tool and to improve my skills profiling, benchmarking, and optimizing. Had I known how popular it would become, I would have definitely held myself to a higher standard, or any standard. Most importantly, I'd have written tests. These days, I'm busy with a startup so progress on those fronts has been slow.
      - x0x0 12y ago
        it's an awesome tool I use dozens of times a day, so thank you
i_s 12y ago
The silver searcher is pretty good. but it has a couple of big problems. It does not parse the .gitignore correctly [0], so it frequently searches files that are not committed to your repo. This, combined with the decision to print 10000 character long lines mean a lot of search results are useless. [0] https://github.com/ggreer/the_silver_searcher/issues/367 https://github.com/ggreer/the_silver_searcher/issues/367 for example
- davidgerard 12y ago
  The author notes that git grep is faster than ag when you're lucky enough to be searching a repo.
- michaelmior 12y ago
  I noticed the issue you mentioned, but as the last comment mentions, I believe this has already been fixed. My specific case at least was resolved by updating from master.

It's also worth checking out The Silver Searcher: https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher

by pie 12y ago

It's also worth checking out The Silver Searcher: https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher

sillysaurus3 12y ago

How is it so fast? Files are mmap()ed instead of read into a buffer. It's hard to believe this would give a significant performance boost. Is there evidence of this?

deleted 12y ago
[deleted]
- sillysaurus3 12y ago
  If anything, that post is evidence of how tricky optimization is, and how easy it is to fool yourself about what matters. It's probably best to be skeptical about mmap() as a performance optimization over reading into a buffer unless evidence demonstrates otherwise. Most OS's do a pretty good job of caching at the filesystem level, and under the hood paging is essentially reading into a buffer anyway. mmap() might make the code simpler, but it's hard to imagine it makes it faster. If it does, I'd like to understand why. EDIT: The post was http://geoff.greer.fm/2012/08/25/the-silver-searcher-benchmarking-revisions/ http://geoff.greer.fm/2012/08/25/the-silver-searcher-benchma...
duaneb 12y ago
> It's hard to believe this would give a significant performance boost. Why is that so hard to believe? It's a standard optimization—the kernel can almost certainly coordinate reading better than your userspace C can.
- sillysaurus3 12y ago
  So are we talking about constant-time optimization, then? I.e. it shaves off a few milliseconds regardless of how complex the search is, or how many files it's reading, or how large each file is. I'll happily concede that mmap() might do that. But a performance boost linear w.r.t. search complexity/number of files/filesize? Hard to believe, and I should go measure it myself to prove the point or learn why I'm mistaken.
  - Crito 12y ago
    Likely a constant time improvement... for each file being searched. I don't think that anybody is claiming that mmapping actually changes the algorithmic complexity of the actual search operations.
  - duaneb 12y ago
    Constant-time improvements are still improvements, especially if they're in an inner loop. Otherwise we would all be using Python and just writing great algorithms.
tobinfricke 12y ago
There is a nice (and often posted) mailing list post explaining some of the reasons GNU Grep is so fast: http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu... He mentions: "So even nowadays, using --mmap can be worth a >20% speedup."
- sillysaurus3 12y ago
  Now I'm burning with curiosity. I have to know why! My plan: - replicate the experiment, confirm --mmap shaves off a non-negligible amount of time. It could be that his computer happened to be running something in the background that was using his harddrive, for example, which would skew the results. - look at the code, figure out the exact difference between what --mmap is doing and what it does by default. Confirm that the problem isn't in grep itself (it's probably not, but it's important to check). - dig into the kernel source to figure out the difference under the hood and why it might be faster.
  - makmanalp 12y ago
    I wonder if it has to do with not having to copy data back and forth between kernel and userspace. My mildly uneducated thought is that you could do this with splice() or whatever, but mmap is an easy drop-in replacement. edit: I've been reading your posts for a while and I like them, but I keep wondering, why do you have sillysaurus1-2-3?
    - sillysaurus3 12y ago
      That's what has me so curious, because it doesn't seem like copying between kernel/userspace should account for a 20% speed drop. Once data is in the L3 CPU cache, it should be inexpensive to move it around. Regarding my ancestry, I'm sillysaurus3 because I've (rightfully) been in trouble twice with the mods for getting too personal on HN. I apologized and changed my behavior accordingly, and additionally created a new account both times to serve as a constant reminder to be objective and emotionless. There's rarely a reason to argue with a person rather than with an idea. Debating ideas, not people, has a bunch of nice benefits: it's easier to learn from your mistakes, it makes for better reading, etc. It's pretty important, because forgetting that principle leads to exchanges like https://news.ycombinator.com/item?id=7700145 https://news.ycombinator.com/item?id=7700145 Another nice benefit of creating a new account is that you lose your downvoting privilege for a time, which made me more thoughtful about whether a downvote is actually justified.
bcoates 12y ago
The last time I had to do fast, large sequential disk reads on Linux it was surprisingly complex to get all the buffering/caching/locking to not do the wrong thing and slow me down a lot. I wouldn't be surprised if non-optimized mmap() is a whole lot faster than non-optimized use of high level file i/o libraries.
ggreer 12y ago
In my benchmarking, mmap() was about 20% faster than read() on OS X, but the same speed on Ubuntu. Pretty much everything else in the list (pthreads, JIT regex compiler, Boyer-Moore-Horspool strstr(), etc) improves performance more than mmap(). Also, mmap() has the disadvantage that it can segfault your process if something else makes the underlying file smaller. In fact, there have been kernel bugs related to separate processes mmapping and truncating the same file.[1] I mostly use mmap() because my primary computer is a mac. A side note: Parts of OS X's kernel seem... not very optimized to say the least. See the bar graph at http://geoff.greer.fm/2012/09/07/the-silver-searcher-adding-pthreads/ http://geoff.greer.fm/2012/09/07/the-silver-searcher-adding-... for an example. 1. http://lwn.net/Articles/357767/ http://lwn.net/Articles/357767/

pmelendez 12y ago

1000 times this... it is exactly like ack-grep but faster :)

5h 12y ago
I normally tell people to use ack because it's like grep but faster (owing to it's sensible defaults) ... if I use this I'm worried I might go too fast and travel backwards in time or something.
- csgavino1 12y ago
  Give ag a shot, you'll be able to relive the emotions you felt when you switched to ack from grep, but this time you're switching to ag from ack.
djeikyb 12y ago
One thing I miss a little is that ack has the super convenient: ack --java "foo" while with ag you write: ag -G"\.java$" "foo" But yes, ack and ag feel pretty identical except for the speed. Most of the time the speed improvement is irrelevant to me, except sometimes now I'll use ag in my home folder, and it's still fairly snappy.
- coffeeaddicted 12y ago
  That was too much typing anyway. When you mostly work with one language something like this is nice (in my case c/c++): alias ack-cpp='ack-grep --type=cpp --type=cc'
  - llimllib 12y ago
    I have that aliased to 'cack'. Then ruby is 'rack', python is 'pack', go is 'gack', etc. (I've never needed to use the rackup "rack" command directly, fortunately, if you do you ought to use a different alias)
    - 12y ago

tveita 12y ago

I switched to this after Ack 2 removed all options to search through binary files. ag is less picky, and the increased speed is a nice bonus.

pudquick 12y ago
Binary file search was my primary motivator as well. I really do love the functionality of the tool.

ihodes 12y ago

Big problem with ag is that it appears to be broken on even moderately larger files where ack works just fine: https://github.com/ggreer/the_silver_searcher/issues/384 https://github.com/ggreer/the_silver_searcher/issues/384

ggreer 12y ago
pcre_exec()'s length and offset parameters are ints, so there's not much I can do about files over 2GB. I really don't want to split the file into chunks and deal with matches across boundaries. That's just asking for bugs. I guess I could make literal string searches work, at least on 64 bit platforms. Honestly though, I don't think ag is the right tool for that job. For a single huge file, grep is going to be the same speed. Possibly faster, since grep's strstr() has been optimized for longer than I've been alive.
- tveita 12y ago
  If ag knows it can't search the whole file, it should at least give a warning. Or why not use search_stream? Silently skipping parts of it seems like the worst thing to do.
  - ggreer 12y ago
    Good point about the warning. I'll add that. With regards to search_stream() in search.c... all I can say is that I'm sorry: https://github.com/ggreer/the_silver_searcher/blob/master/src/search.c#L163 https://github.com/ggreer/the_silver_searcher/blob/master/sr... I built ag for myself; both as a tool and to improve my skills profiling, benchmarking, and optimizing. Had I known how popular it would become, I would have definitely held myself to a higher standard, or any standard. Most importantly, I'd have written tests. These days, I'm busy with a startup so progress on those fronts has been slow.
    - x0x0 12y ago
      it's an awesome tool I use dozens of times a day, so thank you

i_s 12y ago

The silver searcher is pretty good. but it has a couple of big problems. It does not parse the .gitignore correctly [0], so it frequently searches files that are not committed to your repo. This, combined with the decision to print 10000 character long lines mean a lot of search results are useless. [0] https://github.com/ggreer/the_silver_searcher/issues/367 https://github.com/ggreer/the_silver_searcher/issues/367 for example

davidgerard 12y ago
The author notes that git grep is faster than ag when you're lucky enough to be searching a repo.
michaelmior 12y ago
I noticed the issue you mentioned, but as the last comment mentions, I believe this has already been fixed. My specific case at least was resolved by updating from master.