4 ms·

And yet, grep and grep alternatives run much faster with the sequential file I/O tools than mmap. https://blog.burntsushi.net/ripgrep/ https://blog.burntsushi.

And yet, grep and grep alternatives run much faster with the sequential file I/O tools than mmap. https://blog.burntsushi.net/ripgrep/ https://blog.burntsushi.net/ripgrep/

deleted 6y ago
[deleted]
cb321 6y ago
Discussion of this exact issue over at https://lobste.rs/s/h5dfjo/why_mmap_is_faster_than_system_calls https://lobste.rs/s/h5dfjo/why_mmap_is_faster_than_system_ca...
burntsushi 6y ago
That's not quite true... My blog post there says mmap is slower in some cases (where you're searching a lot of files), but if you're just searching a single file, mmap does give a bit of a speed boost: $ time rg 'Sherlock Holmes' OpenSubtitles2018.raw.en -c --mmap 7673 real 1.754 user 1.235 sys 0.516 maxmem 12510 MB faults 0 $ time rg 'Sherlock Holmes' OpenSubtitles2018.raw.en -c --no-mmap 7673 real 2.663 user 1.130 sys 1.530 maxmem 6 MB faults 0 See the sibling comment for a link to a bit more discussion and some interesting observations! Namely, it looks like using mmap can be slower when searching a lot of files because of CPU cache effects.
- temac 6y ago
  and munmap can be quite costly too
- cb321 6y ago
  Playing with madvise MADV_SEQUENTIAL might also add some insight. The author of the original article here did mention different access patterns, but did not use madvise in any of her published code.
  - jart 6y ago
    madvise is more about good citizenship since kernels are usually tuned with a default strategy of salting the earth to get the best possible score on simple benchmarks: madvise(mapped_addr, mapped_size, MADV_WILLNEED | MADV_SEQUENTIAL); Please call that function before consuming a large file. If you ingest more data than is stored in RAM, then without madvise, you're going to make everything else on the system go really slow afterwards, since every other program that has hot pages in cache waiting to be re-used will become cold and have to hit disk again.
    - cb321 6y ago
      @burntsushi's usage context is a highly multi-threaded single process doing many mmap()/munmap()s in parallel. There "being a good citizen" may well mean "not being so hard on your own self", but where the definition of "self" is more complex. Hah. This is starting to sound more like pop psychology than systems programming. :-) :-) Anyway, there are quite a few ways a process can be too hard on itself, self-defeating its own max IO goals. Over in that lobste.rs thread, the idea also arose that, besides L3 cache sharing, the kernel may be locking the whole process to edit VM mappings during both mmap and munmap. A sibling(-ish) comment here mentions sharing another cache -- the TLB for Virtual->Physical translation. It's hard to say what the whole mix for `ripgrep` winds up being in various deployment scenarios without more investigation. Another "self"-competition example would definitely be waiting for disk head movement on Winchester drives, but `rg` is mostly a child of the SSD/Flash generation.
- brandmeyer 6y ago
  I don't actually think its the cache utilization, I think its TLB demand on the hardware, and address space management demand on the kernel. The multi-threaded use-once-only case is not well-suited to mmap. For example, here's some ripgrep runs searching for "mmap" in the glibc source. Performance counter stats for 'rg -j8 --mmap munmap': 783,429 dTLB-load-misses 20,903 faults 0.620738806 seconds time elapsed 0.309086000 seconds user 1.156984000 seconds sys Performance counter stats for 'rg -j4 --mmap munmap': 543,522 dTLB-load-misses 20,770 faults 0.210009979 seconds time elapsed 0.222609000 seconds user 0.390542000 seconds sys Performance counter stats for 'rg -j2 --mmap munmap': 318,628 dTLB-load-misses 20,736 faults 0.204980322 seconds time elapsed 0.162815000 seconds user 0.206498000 seconds sys Performance counter stats for 'rg -j8 --no-mmap munmap': 408,259 dTLB-load-misses 955 faults 0.064994749 seconds time elapsed 0.224760000 seconds user 0.185328000 seconds sys Note that even though the total work is the same, the number of TLB misses decreases with decreasing parallelism. There are far more "faults" recorded for all of the first-page-touches performed. Linux does have fault-around, but that only reduces the number of faults; it doesn't elide them entirely. Addendum: Additionally, the number of context switches grows super-linearly with increasing parallelism, but only with the `--mmap` flag. A followup on the linux kernel source showed 1600 switches at j2, 8400 at j4 and 52,000 at j8 for the same search on the same sources. With `--no-mmap` the number of context switches grows linearly from j2 through j8. When I first ran into that result, another fellow repiled that he reduced some of the gap in ripgrep by eliding ripgrep's munmap. Some of the TLB invalidation work can be saved by just holding onto the address space for longer.
  - burntsushi 6y ago
    Very interesting! Thanks so much for that analysis. Very helpful. So it sounds like we have: 1) work done by munmap (although perhaps this is connected to the TLB misses), 2) some kind of locking inside the kernel, 3) cache misses, 4) TLB misses and 5) context switches as possible causes/agitators here.

And yet, grep and grep alternatives run much faster with the sequential file I/O tools than mmap. https://blog.burntsushi.net/ripgrep/ https://blog.burntsushi.net/ripgrep/

deleted 6y ago

[deleted]

cb321 6y ago

Discussion of this exact issue over at https://lobste.rs/s/h5dfjo/why_mmap_is_faster_than_system_calls https://lobste.rs/s/h5dfjo/why_mmap_is_faster_than_system_ca...

burntsushi 6y ago

That's not quite true... My blog post there says mmap is slower in some cases (where you're searching a lot of files), but if you're just searching a single file, mmap does give a bit of a speed boost: $ time rg 'Sherlock Holmes' OpenSubtitles2018.raw.en -c --mmap 7673 real 1.754 user 1.235 sys 0.516 maxmem 12510 MB faults 0 $ time rg 'Sherlock Holmes' OpenSubtitles2018.raw.en -c --no-mmap 7673 real 2.663 user 1.130 sys 1.530 maxmem 6 MB faults 0 See the sibling comment for a link to a bit more discussion and some interesting observations! Namely, it looks like using mmap can be slower when searching a lot of files because of CPU cache effects.

temac 6y ago
and munmap can be quite costly too
cb321 6y ago
Playing with madvise MADV_SEQUENTIAL might also add some insight. The author of the original article here did mention different access patterns, but did not use madvise in any of her published code.
- jart 6y ago
  madvise is more about good citizenship since kernels are usually tuned with a default strategy of salting the earth to get the best possible score on simple benchmarks: madvise(mapped_addr, mapped_size, MADV_WILLNEED | MADV_SEQUENTIAL); Please call that function before consuming a large file. If you ingest more data than is stored in RAM, then without madvise, you're going to make everything else on the system go really slow afterwards, since every other program that has hot pages in cache waiting to be re-used will become cold and have to hit disk again.
  - cb321 6y ago
    @burntsushi's usage context is a highly multi-threaded single process doing many mmap()/munmap()s in parallel. There "being a good citizen" may well mean "not being so hard on your own self", but where the definition of "self" is more complex. Hah. This is starting to sound more like pop psychology than systems programming. :-) :-) Anyway, there are quite a few ways a process can be too hard on itself, self-defeating its own max IO goals. Over in that lobste.rs thread, the idea also arose that, besides L3 cache sharing, the kernel may be locking the whole process to edit VM mappings during both mmap and munmap. A sibling(-ish) comment here mentions sharing another cache -- the TLB for Virtual->Physical translation. It's hard to say what the whole mix for `ripgrep` winds up being in various deployment scenarios without more investigation. Another "self"-competition example would definitely be waiting for disk head movement on Winchester drives, but `rg` is mostly a child of the SSD/Flash generation.
brandmeyer 6y ago
I don't actually think its the cache utilization, I think its TLB demand on the hardware, and address space management demand on the kernel. The multi-threaded use-once-only case is not well-suited to mmap. For example, here's some ripgrep runs searching for "mmap" in the glibc source. Performance counter stats for 'rg -j8 --mmap munmap': 783,429 dTLB-load-misses 20,903 faults 0.620738806 seconds time elapsed 0.309086000 seconds user 1.156984000 seconds sys Performance counter stats for 'rg -j4 --mmap munmap': 543,522 dTLB-load-misses 20,770 faults 0.210009979 seconds time elapsed 0.222609000 seconds user 0.390542000 seconds sys Performance counter stats for 'rg -j2 --mmap munmap': 318,628 dTLB-load-misses 20,736 faults 0.204980322 seconds time elapsed 0.162815000 seconds user 0.206498000 seconds sys Performance counter stats for 'rg -j8 --no-mmap munmap': 408,259 dTLB-load-misses 955 faults 0.064994749 seconds time elapsed 0.224760000 seconds user 0.185328000 seconds sys Note that even though the total work is the same, the number of TLB misses decreases with decreasing parallelism. There are far more "faults" recorded for all of the first-page-touches performed. Linux does have fault-around, but that only reduces the number of faults; it doesn't elide them entirely. Addendum: Additionally, the number of context switches grows super-linearly with increasing parallelism, but only with the `--mmap` flag. A followup on the linux kernel source showed 1600 switches at j2, 8400 at j4 and 52,000 at j8 for the same search on the same sources. With `--no-mmap` the number of context switches grows linearly from j2 through j8. When I first ran into that result, another fellow repiled that he reduced some of the gap in ripgrep by eliding ripgrep's munmap. Some of the TLB invalidation work can be saved by just holding onto the address space for longer.
- burntsushi 6y ago
  Very interesting! Thanks so much for that analysis. Very helpful. So it sounds like we have: 1) work done by munmap (although perhaps this is connected to the TLB misses), 2) some kind of locking inside the kernel, 3) cache misses, 4) TLB misses and 5) context switches as possible causes/agitators here.