4 ms·

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

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.
- brandmeyer 6y ago
  mmap doesn't actually stitch the file into the caller's address space right away; its lazy because that's the right answer for the vast majority of programs. So when it returns with success, the caller doesn't actually have the memory in its address space. The kernel has merely promised that when a page fault happens in that range in the future that it won't deliver SIGSEGV all the way to you. You still take the faults on the access violations. And there will be many of them. Perhaps there is a set of flags to madvise that will eagerly map all of the file that is currently in the VM cache already. On the other hand, munmap must be eager. There are some page table maintenance operations which require some or all of the TLB to be flushed, because TLB's aren't cache coherent. So when the kernel replaces some page table entries with "invalid" mappings it has to nuke part of the TLB as well. Alas, in some cases the smallest unit of detonation is the entire TLB of the entire process on all cores. Until the cache warms up, every single time the process touches a new page will require a complete walk of the page tables. I only briefly peaked at the mmap crate. Looks like many of the knobs are hidden from you. Perhaps my rust-fu is weak, but I don't see any signs of support for madvise or posix_madvise except for a couple of random 0.x crates from 2017. Do I read that right - mmap is in some random 0.x crate from 2018 as well?

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.

brandmeyer 6y ago
mmap doesn't actually stitch the file into the caller's address space right away; its lazy because that's the right answer for the vast majority of programs. So when it returns with success, the caller doesn't actually have the memory in its address space. The kernel has merely promised that when a page fault happens in that range in the future that it won't deliver SIGSEGV all the way to you. You still take the faults on the access violations. And there will be many of them. Perhaps there is a set of flags to madvise that will eagerly map all of the file that is currently in the VM cache already. On the other hand, munmap must be eager. There are some page table maintenance operations which require some or all of the TLB to be flushed, because TLB's aren't cache coherent. So when the kernel replaces some page table entries with "invalid" mappings it has to nuke part of the TLB as well. Alas, in some cases the smallest unit of detonation is the entire TLB of the entire process on all cores. Until the cache warms up, every single time the process touches a new page will require a complete walk of the page tables. I only briefly peaked at the mmap crate. Looks like many of the knobs are hidden from you. Perhaps my rust-fu is weak, but I don't see any signs of support for madvise or posix_madvise except for a couple of random 0.x crates from 2017. Do I read that right - mmap is in some random 0.x crate from 2018 as well?