Section 3.2 of this paper has more details: https://db.cs.cmu.edu/papers/2022/cidr2022-p13-crotty.pdf
Memory operations are always synchronous because they’re performed directly as a consequence of CPU instructions. Reading memory that’s been paged out results in the CPU itself detecting that the virtual address isn’t in RAM, and performing a hardware level interrupt. Literally abandoning a CPU instruction mid execution to start executing an entirely separate set of instructions which will hopefully sort out the page fault that just occurred, then kindly ask the CPU to go back and repeat the operation that caused the page fault.
OS is only involved only because it’s the thing that provided the handling instructions for the CPU to execute in the event of a page fault. But it’s not in anyway actually capable of changing how the CPU initially handles the page fault.
Also the current model does allow other threads to continue executing other work while the page fault is handled. The fault is completely localised to individual thread that triggered the fault. The CPU has no concept of the idea that multiple threads running on different physical core are in anyway related to each other. It also wouldn’t make sense to allow the interrupted thread to someone kick off a separate asynchronous operation, because where is it going to execute? The CPU core where the page fault happened is needed to handle the actual page fault, and copy in the needed memory. So even if you could kick off an async operation, there wouldn’t be any available CPU cycles to carry out the operation.
Fundamentally there aren’t any sensible ways to improve on this problem, because the problem only exists due to us pretending that our machines have vastly more memory than they actually do. Which comes with tradeoffs, such as having to pause the CPU and steal CPU time to maintain the illusion.
If people don’t like those tradeoffs, there’s a very simple solution. Put enough memory in your machine to keep your entire working set in memory all the time. Then page faults can never happen.
So far so good, but then the question is to ensure that the CPU core has something more productive to do then just check "did the data arrive yet?" over and over and coordinating that is where good apis come in.
There is nothing in the sense of Python async or JS async that the OS thread or OS process in question could usefully do on the CPU until the memory is paged into physical RAM. DMA or no DMA.
The OS process scheduler can run another process or thread. But your program instance will have to wait. That’s the point. It doesn’t matter whether waiting is handled by a busy loop a.k.a. polling or by a second interrupt that wakes the OS thread up again.
That is why Linux calls it uninterruptible sleep.
EDIT: io_uring would of course change your thread from blocking syscalls to non-blocking syscalls. Page faults are not a syscall, as GP pointed out. They are, however, a context-switch to an OS interrupt handler. That is why you have an OS. It provides the software drivers for your CPU, MMU, and disks/storage. Here this is the interrupt handler for a page fault.
Not only is there a sensible OS API that could support this, Linux already implements it; it's the SIGSEGV signal. The default way to respond to a SIGSEGV is by exiting the process with an error, but Linux provides the signal handler with enough information to do something sensible with it. For example, it could map a page into the page frame that was requested, enqueue an asynchronous I/O to fill it, put the current green thread to sleep until the I/O completes, and context-switch to a different green thread.
Invoking a signal handler only has about the same inherent overhead as a system call. But then the signal handler needs another couple of system calls. So on Linux this is over a microsecond in all. That's probably acceptable, but it's slower than just calling pread() and having the kernel switch threads.
Some garbage-collected runtimes do use SIGSEGV handlers on Linux, but I don't know of anything using this technique for user-level virtual memory. It's not a very popular technique in part because, like inotify and epoll, it's nonportable; POSIX doesn't specify that the signal handler gets the arguments it would need, so running on other operating systems requires extra work.
im3w1l also mentions userfaultfd, which is a different nonportable Linux-only interface that can solve the same thing but is, I think, more efficient.
If you have enough free memory, the file will be cached in memory anyway instead of residing on disk. Therefore both will be reading from memory, albeit through different API.
Looking for recent benchmark or view from OS developers.
additionally, mmap is heavily optimized for random access, so if that’s what you’re doing, then you’ll have a much better time with it than fread.
(I hope a plug is not frowned upon here: if you like this kind of stuff, we’re a fully remote company and hiring C++ devs: https://apply.workable.com/quasar/j/436B0BEE43/ )
(Not that you can afford me.)
Also, your company is breaking the law by false advertising. It suggests your current leadership is fucking stupid. Why do you work for a criminal enterprise?
I assume they’re referring to the no-salary aspect and (based on their speech style) are in the US. But, even in that case, it would only matter if the posting were targeted to one of the states that require salary information and the company operated or had a presence in said state. Since it’s an EU company, that’s almost definitely not the case.
I assume both cases have the file cached in RAM already fully, with a tiny size of 100MB. But the file read based version actually copies the data into a given buffer, which involves cache misses to get data from RAM to L1 for copying. The mmap version just returns the slice and it's discarded immediately, the actual data is not touched at all. Each record is 2 cache lines and with random indices is not prefetched. For the CPU AMD Ryzen 7 9800X3D mentioned in the repo, just reading 100 bytes from RAM to L1 should take ~100 nanos.
The benchmark compares actually getting data vs getting data location. Single digit nanos is the scale of good hash tables lookups with data in CPU caches, not actual IO. For fairness, both should use/touch the data, eg copy it.
I think this is the wrong order of magnitude. One core of my Ryzen 5 3500U seems to be able to run memcpy() at 10 gigabytes per second (0.1 nanoseconds per byte) and memset() at 31 gigabytes per second (0.03 nanoseconds per byte). I'd expect a sequential read of 100 bytes to take about 3 nanoseconds, not 100 nanoseconds.
However, I think random accesses do take close to 100 nanoseconds to transmit the starting row and column address and open the row. I haven't measured this on this hardware because I don't have a test I'm confident in.
moreover, mmap by default will load lazy, where mmap with MAP_POPULATE will prefetch. in the former case, reporting average operation times is not valid because the access time distributions are not gaussian (they have a one time big hit at first touch). with MAP_POPULATE (linux only), there is long loading delay when mmap is first called, but then the average access times will be very low. when pages are released will be determined by the operating system page cache eviction policy.
the data structure on top is best chosen based on desired runtime characteristics. if it's all going in ram, go ahead and use a standard randomized hash table. if it's too big to fit in ram, designing a structure that is aware of lru style page eviction semantics may make sense (ie, a hash table or other layout that preserves locality for things that are expected to be accessed in a temporally local fashion.)
In my case, it seems that Mac's ExFAT driver is incompatible with sqlite's WAL mode because the driver returned a memory address that is misaligned on ARM64. Most bizarre error I've encountered in years.
So, uh, mind your file systems, kids!
The reason I’m skeptical is three fold. The first is that it’s generally impossible for a filesystem to mmap return a pointer that’s not page boundary aligned. The second is that unaligned accesses are still fine on modern ARM is not a SIGBUS. The third is that Claude’s reasoning that the pointer must be 8-byte aligned and that indicates a misaligned read is flawed - how do you know that SQLite isn’t doing a 2-byte read at that address?
If you really think it’s a bad alignment it should be trivial to reproduce - mmap the file explicitly and print the address or modify the SQLite source to print the mmap location it gets.
I honestly don't know anything about this. There's no search results for my error. ChatGPT and Claude and Grok all agreed one way or another, with various prompts.
Would be happy to have some help verifying any of this. I just know that disabling WAL mode, and not using Mac's ExFAT driver, both fixed the error reliably.
It also means the latency due to pagefaults is shifted from inside mmapReader.ReadRecord() (where it would be expected) to wherever in the application the bytes are first accessed, leading to spooky unpreditactable latency spikes in what are otherwise pure functions. That inevitably leads to wild arguments about how bad GC stalls are :-)
An apples to apples comparison should be copying the bytes from the mmap buffer and returning the resulting slice.
Good point.
Obviously if you have kernel-backed async IO APIs (io_uring) and willing to dig into the deeper end (for better managed cache), you can get better performance than mmap. But in many cases, mmap is "good-enough".
I was suspicious of the 25× speedup claim, but it's a lot more plausible than I thought.
On this Ryzen 5 3500U running mostly at 3.667GHz (poorly controlled), reading data from an already-memory-mapped page is as fast as memcpy (about 10 gigabytes per second when not cached on one core of my laptop, which works out to 0.1 nanoseconds per byte, plus about 20 nanoseconds of overhead) while lseek+read is two system calls (590ns each) plus copying bytes into userspace (26–30ps per byte for small calls, 120ps per byte for a few megabytes). Small memcpy (from, as it happens, an mmapped page) also costs about 25ps per byte, plus about 2800ps per loop iteration, probably much of which is incrementing the loop counter and passing arguments to the memcpy function (GCC is emitting an actual call to memcpy, via the PLT).
So mmap will always be faster than lseek+read on this machine, at least if it doesn't have a page fault, but the point at which memcpy from mmap would be 25× faster than lseek+read would be where 2×590 + .028n = 25×(2.8 + .025n) = 70 + .625n. Which is to say 1110 = .597n ∴ n = 1110/.597 = 1859 bytes. At that point, memcpy from mmap should be 49ns and lseek+read should be 1232ns, which is 25× as big. You can cut that size more than in half if you use pread() instead of lseek+read, and presumably io_uring would cut it even more. If we assume that we're also taking cache misses to bring in the data from main memory in both cases, we have 2×590 + .1n = 25×(2.8 + .1n) = 70 + 2.5n, so 1110 = 2.4n ∴ n = 1110/2.4 = 462 bytes.
On the other hand, mmap will be slow if it's hitting a page fault, which sort of corresponds to the case where you could have cached the result of lseek+read in private RAM, which you could do on a smaller-than-pagesize granularity, which potentially means you could hit the slow path much less often for a given working set. And lseek+read has several possible ways to do make the I/O asynchronous, while the only way to make mmap page faults asynchronous is to hit the page faults in different threads, which is a pretty heavyweight mechanism.
On the other hand, lseek+read with a software cache is sort of using twice as much memory (one copy is in the kernel's buffer cache and another copy is in the application's software cache) so mmap could still win. And, if there are other processes writing to the data being queried, you need some way to invalidate the software cache, which can be expensive.
(On the gripping hand, if you're reading from shared memory while other processes are updating it, you're probably going to need some kind of locking or lock-free synchronization with those other processes.)
So I think a reasonably architected lseek+read (or pread) approach to the problem might be a little faster or a little slower than the mmap approach, but the gap definitely won't be 25×. But very simple applications or libraries, or libraries where many processes might be simultaneously accessing the same data, could indeed get 25× or even 256× performance improvements by letting the kernel manage the cache instead of trying to do it themselves.
Someone at a large user of Varnish told me they've mostly removed mmap from their Varnish fork for performance.
nawgz•2h ago
trenchpilgrim•2h ago
2. As the article points out mmap is very fast for reading huge amounts of data but is a lot slower at other file operations. For reading smallish files, which is the majority of calls most software will make to the filesystem, the regular file syscalls are better.
3. If you're on a modern Linux you might be better off with io_uring than mmap.
scottlamb•1h ago
In theory I suppose you could have a libc that mostly emulates read() and write() calls on files [1] with memcpy() on mmap()ed regions. But I don't think it'd be quite right. For one thing, that read() behavior after shrink would be a source of error.
Higher-level APIs might be more free to do things with either mmap or read/write.
[1] just on files; so it'd have to track which file descriptors are files as opposed to sockets/pipes/etc, maintaining the cached lengths and mmap()ed regions and such. libc doesn't normally do that, and it'd go badly if you bypass it with direct system calls.