3 ms·

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

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 13y ago
[deleted]
- sillysaurus3 13y 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 13y 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 13y 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 13y 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 13y 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 13y 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 13y 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 13y 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 13y 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 13y 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 13y 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/

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 13y ago

[deleted]

sillysaurus3 13y 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 13y 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 13y 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 13y 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 13y 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 13y 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 13y 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 13y 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 13y 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 13y 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 13y 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/