Could the kernel restrict the AVX use to memcpy to/from user buffers & to use a different API so that it was clear at the syscall boundary when that save/restore would be needed (+ you could potentially restrict the number of AVX registers used)? That way it wouldn't have the concerns of replacing all memcpy operations within the kernel & would just focus on I/O operations from userspace.
Or is the space for potentially stashing away the AVX registers for each thread also a major concern rather than just the cost of doing so?
Call me pedantic, but mmap is a syscall. The title would have been better as "Why memory mapped files are faster". The author does address this with "Mmap stands for memory-mapped files." It does? I thought mmap stands for memory map. To be clear I enjoyed the contents of the article.
But you call mmap only once per file: it gives you a pointer and then you just use the pointer normally. While for read() you have to call once per read() operation (minus some user space buffering).
mmap is more general than memory mapping files. It "establish[es] a mapping between an address space of a process and a memory object". In particular, many allocators (malloc and friends) use mmap to get a block of memory from the OS with mmap(0, size, PROT_READ|PROT_WRITE, MAP_ANONYMOUS, -1, 0); or similar.
You're misunderstanding. You call mmap once, which is a system call, and then instead of using system calls you just access memory which performs the operations as needed through loading on page faults, not through system calls. This compares to using system calls all the time.
I can't exactly answer that question because I'm not even sure if the premise is true, but I do know that "memory to memory" copying is often offloaded entirely off the CPU.
Here's a technical overview of some of the technologies from 2017
There are, kind of. For example x86 traditionally has `rep movsb`. However that doesn’t mean it will remain the fastest way to do things in the long term; AVX/SSE lets you copy more at once with the caveat that it is more complicated to use (due to alignment requirements and register usage.)
(I think certain ‘obvious’ patterns are optimized in microcode, but it’s probably hard to beat moving 32 bytes or 64 bytes at once with moving bytes/words at a time, no matter what the processor does.)
> For example x86 traditionally has `rep movsb`. However that doesn’t mean it will remain the fastest way to do things in the long term
Starting with Ice Lake, you can just use `rep movsb` all the time, and the processor will move memory in the fastest way it can.
The CPUID feature "ERMS", "Enhanced REP MOVSB", means you should use `rep movsb` for any memory copy that's at least 128 bytes. The CPUID feature "FSRM", "Fast Short REP MOVSB", implies ERMS and additionally means that you should use `rep movsb` for any memory copy, even if it's shorter than 128 bytes.
Maybe while resuming from interrupt you go slow for a while, although I suspect you eventually recover even if that happen. The interrupt will be slow as hell anyway, regardless of if you are doing rep movsb or not. Actually rep movsb with ERMS better has to work well in presence of exceptions (to support virtual memory well), so as what happens in the core in case of interrupt is very similar to what happens on exceptions, I think it's fine to use ERMS even on a system that is heavily interrupted.
Or maybe you ask what happens in an interrupt handler? Probably the same thing as everywhere else, I don't see why it would be different.
The state of the interrupted code has been flushed back to architectural at this point, so you can and do regular microarchitectural optims (it would even be difficult not too, there is not often a slow path and then optims on top of that, it's more the whole implementation that is made using optimisation tricks everywhere)
> Neat! Have any of the common libc’s picked this up yet?
glibc has, as has the Linux kernel.
> How does ERMS deal with interrupts? If I `rep movsb` while interrupted, do I also get the fast implementation?
Whether or not you have ERMS/FSRM available, interrupts are always defined to occur at an architecturally defined state. I don't know of any reason why, when it resumes, it would stop being optimized.
rep movsb has been quite optimized recently and I suspect it will continue to be. Today you can be faster with more complex solutions in some cases, and depending on your precise microarch alternate solution for small copies, etc., but I suspect eventually rep movsb will just be good enough for everything but the most demanding memcpy, which I'm not even sure has a good definition because in an ever increasing number of cases it will depend on what the other cores are doing...
Intel seems to be improving rep movsb from gen to gen, and on the AMD side it seems Zen3 is getting ERMS and FRMS. Given how useful it is when you can't do AVX or just because it is insanely compact, I think its usage will only increase in the near/medium future. Long term, who knows, but like anything.
There's actually dozens and dozens of such instructions on x86 and x86-64. So the question shouldn't really be if there is an instruction, it's whether the one you're using is the most performant for your given CPU. Old Linux kernels would actually calculate CPU speed, and whether 16-bit, 32-bit, FPU, MMX memory copies were fastest and pick one for the kernel to use.
I always wondered that myself, but 'rep movsb' sounds like a great solution. Back when I was still programming assembly, there were blitters (https://en.wikipedia.org/wiki/Blitter) to copy large chunks of memory.
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.
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.
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:
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.
@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.
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.
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.
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?
> When a user program requests to read a file, the page from the file is (usually) first put into the buffer cache. Then the data is copied from the buffer cache out to the user-supplied buffer during the return from the system call.
Doesn't linux do shared-read-only mapping of pages on read(2) and only copy if you modify? Though it can only do so on page-aligned buffers. Maybe results would be different if the buffers were aligned?
> So I changed my test to invoke mmap with MAP_POPULATE and learned that the experiment completes about 36% faster.
If your result spuriously change by 36%, you don't really have a robust statistic, and a model/understaing of objects measured. AFAIU, mmap with MAP_POPULATE should be equivalent to a read of whole file in a single call, on an aligned buffer - significant performance differences here would be interesting.
> Doesn't linux do shared-read-only mapping of pages on read(2) and only copy if you modify?
Eh? Do you have a reference for this? I'd be pretty interested to learn more.
This sounds like a very weird optimization to me, because, as you point out, it would only work if your buffer (and file offset) was page-aligned. That doesn't happen by accident, so "normal" programs that use read() would almost never get a benefit. To get guaranteed page alignment, you probably have to use mmap() to allocate the buffer in the first place, so... why wouldn't you just mmap the file, then?
In fact, you could arguably translate a page-aligned pread() into mmap() in userspace, using MAP_FIXED to force the mapping to be placed at your buffer address. No need for kernel help?
So why would a kernel implement this optimization? It seems like a lot of risk (of unexpected side effects) with little potential benefit.
You can get copy-on-write semantics by passing MAP_PRIVATE to mmap(). So, again, you could literally replace your pread() calls with mmap() calls with MAP_FIXED and MAP_PRIVATE and get the described optimization, without kernel help -- so long as your buffer is page-aligned. If your buffer isn't page aligned, then no such optimization is possible in either the kernel or userspace.
So the question is: Why would the kernel implement this optimization if (1) programs that aren't explicitly designed for it (by using page-aligned buffers) won't get the benefit, and (2) programs design for it could implement the same optimization in userspace anyway?
> Most modern implementations of malloc will call mmap in the background.
Well of course they do. But malloc() won't promise you a page-aligned address, regardless of how it's implemented. If you need a page-aligned address you have to call mmap() directly. (Or I suppose you could malloc() one more page than you need, and then find the page-aligned subset, but it's a lot easier to just call mmap()...)
1. It's not too hard to page align a buffer. If you malloc a big buffer, almost certainly page aligned anyway. So requires very little effort. 2. You can try the same with mmap, but large files won't fit in (32 bit) memory, and read() is cheaper than mapping and unmapping as you go.
> If you malloc a big buffer, almost certainly page aligned anyway.
Not necessarily. Remember that malloc() must produce a pointer which can later be passed to free() without any other details. free() needs some way to figure out, at the very least, how big the allocation is, to properly free it. Many allocators, such as glibc's, accomplish this by placing metadata in the bytes immediately before the allocated block -- which implies that a large allocation won't be page-aligned.
Some other allocators, such as tcmalloc, manage to place the metadata somewhere else, and in that case maybe they return page-aligned buffers, but it's hardly safe to assume.
(I just ran a quick test and verified -- a 4MB malloc() under glibc is typically 16 bytes off of the page boundary, but under tcmalloc it is aligned.)
> 2. You can try the same with mmap, but large files won't fit in (32 bit) memory, and read() is cheaper than mapping and unmapping as you go.
This thread is discussing the claim that the Linux kernel transparently "optimizes" large read() calls into mmap(), with me arguing that doesn't make a lot of sense as an optimization.
If you're saying that this "optimization" would actually be slower, then that supports my point.
You may be right. munmap() (or remapping with MAP_FIXED) triggers TLB shootdowns, which are rather expensive in multithreaded programs. This is another reason why "optimizing" read() to mmap() sounds awfully dubious to me.
That said, shootdowns would have a constant cost per read(), independent of the size. For a sufficiently gigantic read, the cost of the shootdown would be less than the cost of copying data into the target memory, so the "optimization" would possibly start to make sense at that point?
You are likely correct. I knew you could do zero-copy, but it seems special syscalls are necessary for the stated reasons. Calls like mmap, splice, vmsplice, tee, sendfile, io_uring, ..
It looks like the mmap call is not within the timed region in do_mmap_test. I'd call that a major flaw in the test methodology when combined with MAP_POPULATE and a cold cache. The read syscall version has to actually do IO in the timed region; the mmap(MAP_POPULATE) version just does TLB misses and memcpy.
edit: actually, sorry, I think the article points this out, mostly correctly:
> We will come back to __memmove_avx_unaligned_erms in a moment, but for the time being let’s try to figure out exactly how much time is spent mapping pages. I have a neat trick up my sleeve to do that. On Linux, the mmap system call can accept a MAP_POPULATE flag. What this flag does is it forces mmap to pre-populate all the page mappings during the actual system call, so none of the page-mapping work would be done when my test actually runs. So I changed my test to invoke mmap with MAP_POPULATE and learned that the experiment completes about 36% faster. (I only measure the timing of the main loop, and not that of the mmap system call). Therefore, I assume that in the above profile all those mapping functions take up about 36%.
They didn't point out that it doesn't actually do any IO in the main loop either then, but maybe they were only running the warm cache variant by here anyway. And it seems like they didn't use MAP_POPULATE when generating the comparison graphs earlier in the article.
Methodologically it makes sense to exclude work done in the mmap call. After all you would do that once to initialize the memory but you never need to call it to do the work. The point of the test wasn't to check performance of the mmap syscall versus the read syscall, but simply to check the performance of read() versus memory-mapped files.
To check the performance of read() versus memory-mapped files with a cold cache, you should absolutely be including the actual IO.
But on my closer read, they did that earlier in the article. Here they are examining the (userspace) memcpy in isolation. MAP_POPULATE is just a tool to help with that. They could get a similar effect by just looking at the second (on to Nth) call to do_mmap_test, not the first. Or just copying from heap memory to heap memory, without involving any kernel stuff at all...
> Doesn't linux do shared-read-only mapping of pages on read(2) and only copy if you modify?
No, I don't think that's how it works for the plain read() system call. (The kernel will have its own page cache / buffer cache entries that would be the same for both processes, but read() can't map those directly, it has to make a copy.) Though it should work the way you describe if multiple processes mmap the same file, in which case the page cache pages are exactly the same pages that are mapped by the processes.
However, if you use read() to copy data into a buffer and then fork() the process, I believe the child process should end up with a copy of the buffer that is backed by the same physical pages with copy-on-write semantics.
> Doesn't linux do shared-read-only mapping of pages on read(2) and only copy if you modify? Though it can only do so on page-aligned buffers. Maybe results would be different if the buffers were aligned?
Page table modifications slow down your program and many read(2) calls are short and frequent. I doubt that would be a helpful optimization unless the buffer sizes are big.
Source? I've never heard of this. What I have heard of is Linus ranting and insulting the intelligence of BSD kernel developers doing these kinds of virtual memory tricks.
It’s a bit surprising to me that modern processors don’t have their own special handling for recognising and speeding up these copies. But maybe that’s too hard to do.
I’m also surprised that Linux can’t use a vector based copy function (at least for any moderately large copy) as it seems saving a few avx registers would be much cheaper than the copy.
Modern processors speed up large copies with SIMD instructions like AVX.
The Linux kernel chooses not to use SIMD because the cost of copying & saving the relevant processor state (registers, in this case) would be borne by every syscall and consume precious CPU cache.
This would be true for any similar copying mechanism that spanned multiple cycles; the state—however represented—must be preserved.
That’s a statement about modern implementations of memcpy, whereas I was asking about what processors themselves do when they see a non-vector memcpy loop.
I bet if this article were written in 2020, they'd throw io_uring into the comparison. Does it allow directly returning the page cache memory without kernel copying also? I expect so (since it's a modern, performance-oriented interface) but don't know the details of how the buffer management works—seems like the kernel would have to supply the buffer then, it'd have to be at least page size, etc.
If so, it should have a similar benefit as what this article describes for mmap: either your program can completely avoid copying or it can do so in userspace with SIMD instructions.
Also, even when io_uring does copying in kernelspace, I wonder if it'd be more practical for it to use AVX instructions than from within a read syscall.
As I understand it, userspace<->kernel transitions are lighter-weight than full context switches between processes. As discussed here: not saving/restoring the SIMD registers. (I think a bunch of other ways, too, like not replacing all the memory mappings.)
There are also a bunch of pure-kernel processes (I don't know the terminology) shown on ps in square brackets, like [kthreadd], [rcu_gp], [rcu_par_gp], etc. I think a full context switch happens on entry/exit to one of these, just as between two different userspace processes. If the io_uring work always happens within one of these (does it?), the SIMD registers are already being saved/restored, and it'd be safe for it to use an avx_memcpy variant without paying any additional cost.
In short, that thing allows to setup these pointers in advance, and make the memory visible to both user-mode code and OS kernel at the same time. This way no need to copy the data.
Unfortunately, implementing that thing is way more complicated than calling read() or setting up memory mapping. For optimal performance you gonna need to zero-copy all the way up to whatever code is consuming the data read from these files.
The common pattern with any I/O, race conditions are avoided by writing in the documentation "please don't modify the memory after the I/O is initiated and before it's completed". Enforcing that would cause too much overhead.
Wouldn’t that violate the rule that userspace can’t crash the kernel?
On Windows this is solved by using the memory protection provided by the cpu and Structured Exception Handling; I am curious if Linux has something similar.
The kernel likely keeps it's own copies of necessary validated commands and pointers, but not of data buffers. If you read/write in an inappropriate time, you are likely to read/write garbage, get misinterpreted commands or segfaults, but that's your problem.
It shouldn't affect the kernel, aside from bugs present.
Yes. And in case of io_uring, the pointers to the buffers are provided well in advance, with IORING_REGISTER_BUFFERS opcode of io_uring_register API, to be reused across I/O system calls.
AFAIK, Windows only has an equivalent for sockets, called Registered Input/Output (RIO). However, RIO was introduced in Windows 8 (2012) while io_uring is much newer, introduced in Linux kernel 5.1 (2019).
> Wouldn’t that violate the rule that userspace can’t crash the kernel?
A program that accesses same memory location from different cores at the same time won’t crash, as long as the address is good. You’ll just get random garbage in your memory. Concurrent updates by CPU and DMA devices is equally fine, again garbage out is the only result you’ll get.
If you corrupt things like that due to a concurrency bug in your userspace code, you may get garbage in your memory, garbage in your files, but I don’t see why would it crash the kernel?
> On Windows this is solved by using the memory protection provided by the cpu and Structured Exception Handling
Switching memory protection is relatively expensive. Also memory protection doesn’t have byte granularity: you can allocate a 4kb buffer (a single page), view it as a circular buffer with four 1kb-long pieces, and use that circular buffer for streamed I/O.
It’s the same on Windows. Check the docs for WriteFileEx, it says “This buffer must remain valid for the duration of the write operation. The caller must not use this buffer until the write operation is completed.” but I don’t think you gonna get any SEH if you ignore what’s written there, and use the buffer in the meantime.
Did anyone else notice that read kept increasing substantially in speed with larger buffer sizes?
Like if the trend continues it would be about equal with mmap at 64kb buffer size. No way to know for sure without testing it, but that really jumped out at me.
Yes, the overhead is per-syscall. The number of read() syscalls shrinks as the per-call buffer grows.
With mmap() of course we only ever have one syscall to create the initial mapping. Everything else is a memory read.
We can get read() down to just one syscall too, with a 4G buffer ;) I can't recall if GB sized buffers are possible, but I have certainly used MB sized read buffers for exactly this reason.
On Linux, read() (and similar system calls) will transfer at most 0x7ffff000
(2,147,479,552) bytes, returning the number of bytes actually transferred.
(This is true on both 32-bit and 64-bit systems.)
Yes, of course. What I mean to say is that it's weird the author did not see that trend and test it. There wouldn't have been an article if the result was "mmap is faster than read using buffer size < 64kb". It seems kind of central to their whole thesis.
Here's the catch: Large buffer sizes only increase efficiency for sequential reads. mmap() is still much faster for random access within a file. Doubly so, because we need to not just read() but also lseek() for every read.
The inefficiencies of read() can be minimized in the sequential case only.
MUCH prefer to see system calls since strace becomes actually useful and readable.
IIRC this is why plan9 is nice to work with. You can actually understand what a program is doing. On a typical Linux system, mmaps galore and you have no idea what's happening. Pretty awful situation.
When you mmap, it gives you back a pointer that you can read from, but doesn’t necessarily populate your process’s page table with all of the data you can read. Instead, when you go to access it, there will be a page fault if the page you’re trying to read hasn’t been read from disk yet. The kernel catches the page fault, allocates a page, does the read from disk, and restarts your read as if nothing happened. The user process has no indication that any of this happened other than perhaps a bit of latency.
I'm curious now if electricfence could be configured to detect mmap faults, since it's described as using the virtual memory hardware for malloc debugging. I haven't used -lefence since well before I learned about Valgrind though.
And then again, for databases trying to rely on mmap might lead you to poorer results - for example trying to do in-place update, ignoring compression, dealing with concurrency, etc. Without mmap, and by using append-only data, no updates on exising ones (except metadata), and the ability to do compression might give you a big edge over just trying to work it out through mmap.
Check WiredTiger's articles/videos on how they've found previous mmap approach for mongodb to be much slower (I'm not saying mmap is slower than os calls reads, I'm saying it leads to architectural decisions that might limit you later.)
80 comments
[ 4.1 ms ] story [ 170 ms ] threadTLDR author suggests mmap's improved performance can be attributed to the use of AVX instructions during memory copy.
Could the kernel restrict the AVX use to memcpy to/from user buffers & to use a different API so that it was clear at the syscall boundary when that save/restore would be needed (+ you could potentially restrict the number of AVX registers used)? That way it wouldn't have the concerns of replacing all memcpy operations within the kernel & would just focus on I/O operations from userspace.
Or is the space for potentially stashing away the AVX registers for each thread also a major concern rather than just the cost of doing so?
D's std.experimental.allocator module is helpful for building allocators bit by bit even for eventual use in C++ or C.
Yes, some allocators still support using sbrk, though that's a bad idea for security reasons (ASLR).
Surely persnickety, no? If we're wordsmithing anyway.
You're misunderstanding. You call mmap once, which is a system call, and then instead of using system calls you just access memory which performs the operations as needed through loading on page faults, not through system calls. This compares to using system calls all the time.
Here's a technical overview of some of the technologies from 2017
https://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-...
(I think certain ‘obvious’ patterns are optimized in microcode, but it’s probably hard to beat moving 32 bytes or 64 bytes at once with moving bytes/words at a time, no matter what the processor does.)
Starting with Ice Lake, you can just use `rep movsb` all the time, and the processor will move memory in the fastest way it can.
The CPUID feature "ERMS", "Enhanced REP MOVSB", means you should use `rep movsb` for any memory copy that's at least 128 bytes. The CPUID feature "FSRM", "Fast Short REP MOVSB", implies ERMS and additionally means that you should use `rep movsb` for any memory copy, even if it's shorter than 128 bytes.
How does ERMS deal with interrupts? If I `rep movsb` while interrupted, do I also get the fast implementation?
Or maybe you ask what happens in an interrupt handler? Probably the same thing as everywhere else, I don't see why it would be different. The state of the interrupted code has been flushed back to architectural at this point, so you can and do regular microarchitectural optims (it would even be difficult not too, there is not often a slow path and then optims on top of that, it's more the whole implementation that is made using optimisation tricks everywhere)
glibc has, as has the Linux kernel.
> How does ERMS deal with interrupts? If I `rep movsb` while interrupted, do I also get the fast implementation?
Whether or not you have ERMS/FSRM available, interrupts are always defined to occur at an architecturally defined state. I don't know of any reason why, when it resumes, it would stop being optimized.
Intel seems to be improving rep movsb from gen to gen, and on the AMD side it seems Zen3 is getting ERMS and FRMS. Given how useful it is when you can't do AVX or just because it is insanely compact, I think its usage will only increase in the near/medium future. Long term, who knows, but like anything.
https://blog.burntsushi.net/ripgrep/
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.
For example, here's some ripgrep runs searching for "mmap" in the glibc source.
Performance counter stats for 'rg -j8 --mmap munmap':
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.
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?
Doesn't linux do shared-read-only mapping of pages on read(2) and only copy if you modify? Though it can only do so on page-aligned buffers. Maybe results would be different if the buffers were aligned?
> So I changed my test to invoke mmap with MAP_POPULATE and learned that the experiment completes about 36% faster.
If your result spuriously change by 36%, you don't really have a robust statistic, and a model/understaing of objects measured. AFAIU, mmap with MAP_POPULATE should be equivalent to a read of whole file in a single call, on an aligned buffer - significant performance differences here would be interesting.
Eh? Do you have a reference for this? I'd be pretty interested to learn more.
This sounds like a very weird optimization to me, because, as you point out, it would only work if your buffer (and file offset) was page-aligned. That doesn't happen by accident, so "normal" programs that use read() would almost never get a benefit. To get guaranteed page alignment, you probably have to use mmap() to allocate the buffer in the first place, so... why wouldn't you just mmap the file, then?
In fact, you could arguably translate a page-aligned pread() into mmap() in userspace, using MAP_FIXED to force the mapping to be placed at your buffer address. No need for kernel help?
So why would a kernel implement this optimization? It seems like a lot of risk (of unexpected side effects) with little potential benefit.
https://en.wikipedia.org/wiki/Copy-on-write
The only reason I remember is from first encountering this in code and wondering what the hell the "COW" flag was.
>To get guaranteed page alignment, you probably have to use mmap()
Most modern implementations of malloc will call mmap in the background.
You can get copy-on-write semantics by passing MAP_PRIVATE to mmap(). So, again, you could literally replace your pread() calls with mmap() calls with MAP_FIXED and MAP_PRIVATE and get the described optimization, without kernel help -- so long as your buffer is page-aligned. If your buffer isn't page aligned, then no such optimization is possible in either the kernel or userspace.
So the question is: Why would the kernel implement this optimization if (1) programs that aren't explicitly designed for it (by using page-aligned buffers) won't get the benefit, and (2) programs design for it could implement the same optimization in userspace anyway?
> Most modern implementations of malloc will call mmap in the background.
Well of course they do. But malloc() won't promise you a page-aligned address, regardless of how it's implemented. If you need a page-aligned address you have to call mmap() directly. (Or I suppose you could malloc() one more page than you need, and then find the page-aligned subset, but it's a lot easier to just call mmap()...)
Not necessarily. Remember that malloc() must produce a pointer which can later be passed to free() without any other details. free() needs some way to figure out, at the very least, how big the allocation is, to properly free it. Many allocators, such as glibc's, accomplish this by placing metadata in the bytes immediately before the allocated block -- which implies that a large allocation won't be page-aligned.
Some other allocators, such as tcmalloc, manage to place the metadata somewhere else, and in that case maybe they return page-aligned buffers, but it's hardly safe to assume.
(I just ran a quick test and verified -- a 4MB malloc() under glibc is typically 16 bytes off of the page boundary, but under tcmalloc it is aligned.)
> 2. You can try the same with mmap, but large files won't fit in (32 bit) memory, and read() is cheaper than mapping and unmapping as you go.
This thread is discussing the claim that the Linux kernel transparently "optimizes" large read() calls into mmap(), with me arguing that doesn't make a lot of sense as an optimization.
If you're saying that this "optimization" would actually be slower, then that supports my point.
You may be right. munmap() (or remapping with MAP_FIXED) triggers TLB shootdowns, which are rather expensive in multithreaded programs. This is another reason why "optimizing" read() to mmap() sounds awfully dubious to me.
That said, shootdowns would have a constant cost per read(), independent of the size. For a sufficiently gigantic read, the cost of the shootdown would be less than the cost of copying data into the target memory, so the "optimization" would possibly start to make sense at that point?
edit: actually, sorry, I think the article points this out, mostly correctly:
> We will come back to __memmove_avx_unaligned_erms in a moment, but for the time being let’s try to figure out exactly how much time is spent mapping pages. I have a neat trick up my sleeve to do that. On Linux, the mmap system call can accept a MAP_POPULATE flag. What this flag does is it forces mmap to pre-populate all the page mappings during the actual system call, so none of the page-mapping work would be done when my test actually runs. So I changed my test to invoke mmap with MAP_POPULATE and learned that the experiment completes about 36% faster. (I only measure the timing of the main loop, and not that of the mmap system call). Therefore, I assume that in the above profile all those mapping functions take up about 36%.
They didn't point out that it doesn't actually do any IO in the main loop either then, but maybe they were only running the warm cache variant by here anyway. And it seems like they didn't use MAP_POPULATE when generating the comparison graphs earlier in the article.
But on my closer read, they did that earlier in the article. Here they are examining the (userspace) memcpy in isolation. MAP_POPULATE is just a tool to help with that. They could get a similar effect by just looking at the second (on to Nth) call to do_mmap_test, not the first. Or just copying from heap memory to heap memory, without involving any kernel stuff at all...
No, I don't think that's how it works for the plain read() system call. (The kernel will have its own page cache / buffer cache entries that would be the same for both processes, but read() can't map those directly, it has to make a copy.) Though it should work the way you describe if multiple processes mmap the same file, in which case the page cache pages are exactly the same pages that are mapped by the processes.
However, if you use read() to copy data into a buffer and then fork() the process, I believe the child process should end up with a copy of the buffer that is backed by the same physical pages with copy-on-write semantics.
Page table modifications slow down your program and many read(2) calls are short and frequent. I doubt that would be a helpful optimization unless the buffer sizes are big.
I'm pretty sure Linux just does a memory copy.
I’m also surprised that Linux can’t use a vector based copy function (at least for any moderately large copy) as it seems saving a few avx registers would be much cheaper than the copy.
The Linux kernel chooses not to use SIMD because the cost of copying & saving the relevant processor state (registers, in this case) would be borne by every syscall and consume precious CPU cache.
This would be true for any similar copying mechanism that spanned multiple cycles; the state—however represented—must be preserved.
https://news.ycombinator.com/item?id=24843364
Hah, this conversation has already been linked in other comments.
If so, it should have a similar benefit as what this article describes for mmap: either your program can completely avoid copying or it can do so in userspace with SIMD instructions.
As I understand it, userspace<->kernel transitions are lighter-weight than full context switches between processes. As discussed here: not saving/restoring the SIMD registers. (I think a bunch of other ways, too, like not replacing all the memory mappings.)
There are also a bunch of pure-kernel processes (I don't know the terminology) shown on ps in square brackets, like [kthreadd], [rcu_gp], [rcu_par_gp], etc. I think a full context switch happens on entry/exit to one of these, just as between two different userspace processes. If the io_uring work always happens within one of these (does it?), the SIMD registers are already being saved/restored, and it'd be safe for it to use an avx_memcpy variant without paying any additional cost.
> the data referred to by these pointers must be copied into the kernel
Modern OS kernels avoid that when they can. The article is about Linux, modern ones have io_uring: https://unixism.net/loti/what_is_io_uring.html
In short, that thing allows to setup these pointers in advance, and make the memory visible to both user-mode code and OS kernel at the same time. This way no need to copy the data.
Unfortunately, implementing that thing is way more complicated than calling read() or setting up memory mapping. For optimal performance you gonna need to zero-copy all the way up to whatever code is consuming the data read from these files.
On Windows this is solved by using the memory protection provided by the cpu and Structured Exception Handling; I am curious if Linux has something similar.
It shouldn't affect the kernel, aside from bugs present.
AFAIK, Windows only has an equivalent for sockets, called Registered Input/Output (RIO). However, RIO was introduced in Windows 8 (2012) while io_uring is much newer, introduced in Linux kernel 5.1 (2019).
A program that accesses same memory location from different cores at the same time won’t crash, as long as the address is good. You’ll just get random garbage in your memory. Concurrent updates by CPU and DMA devices is equally fine, again garbage out is the only result you’ll get.
If you corrupt things like that due to a concurrency bug in your userspace code, you may get garbage in your memory, garbage in your files, but I don’t see why would it crash the kernel?
> On Windows this is solved by using the memory protection provided by the cpu and Structured Exception Handling
Switching memory protection is relatively expensive. Also memory protection doesn’t have byte granularity: you can allocate a 4kb buffer (a single page), view it as a circular buffer with four 1kb-long pieces, and use that circular buffer for streamed I/O.
It’s the same on Windows. Check the docs for WriteFileEx, it says “This buffer must remain valid for the duration of the write operation. The caller must not use this buffer until the write operation is completed.” but I don’t think you gonna get any SEH if you ignore what’s written there, and use the buffer in the meantime.
Like if the trend continues it would be about equal with mmap at 64kb buffer size. No way to know for sure without testing it, but that really jumped out at me.
With mmap() of course we only ever have one syscall to create the initial mapping. Everything else is a memory read.
We can get read() down to just one syscall too, with a 4G buffer ;) I can't recall if GB sized buffers are possible, but I have certainly used MB sized read buffers for exactly this reason.
Here's the catch: Large buffer sizes only increase efficiency for sequential reads. mmap() is still much faster for random access within a file. Doubly so, because we need to not just read() but also lseek() for every read.
The inefficiencies of read() can be minimized in the sequential case only.
IIRC this is why plan9 is nice to work with. You can actually understand what a program is doing. On a typical Linux system, mmaps galore and you have no idea what's happening. Pretty awful situation.
Check WiredTiger's articles/videos on how they've found previous mmap approach for mongodb to be much slower (I'm not saying mmap is slower than os calls reads, I'm saying it leads to architectural decisions that might limit you later.)
(edit)
This actually presents it better than above - https://15721.courses.cs.cmu.edu/spring2019/slides/01-inmemo...