3 ms·
As an anonymous `mmap()` returns zeroed pages it's likely the fastest mechanism for large arrays.
by gumby 7y ago
As an anonymous `mmap()` returns zeroed pages it's likely the fastest mechanism for large arrays.
- quotemstr 7y agoWhere do you think those zeros come from? The kernel demand faults that mmap, and on each fault, has to find a page containing zero. Sometimes it has to make one.
- gumby 7y agoYes but the large array needs to allocate that memory already.
- quotemstr 7y agoSure. I'm just saying that the kernel doesn't have some kind of magic capability that lets it zero memory faster than userspace can. It does have a small free-list of already-zero pages, granted, but a really big allocation will deplete that list, and that list needs to be replenished somehow. For Linux, I want to grant MAP_UNINITIALIZED access to unprivileged users (keep reading) but actually zero pages it gives to these unprivileged MAP_UNINITIALIZED --- users unless it knows that a page doesn't contain privileged information. For example, if a process munmap()s a particular region and then immediately mmap()s a different one, and no other process has ever mapped that page, there's no harm in allowing the process to see its own previous page content.
- BeeOnRope 7y agoHeh, I've had similar thoughts about "safe MAP_UNINITIALIZED", although the demand for this feature is probably pretty low since you can do much the same thing in userspace (just don't return that memory in the first place). Of course, the kernel way has some advantages: - You are making the memory available to the rest of the system if needed. - It could give you other types of pages w/o privileged info, e.g., page cache pages from files you have permission to read, or something like that.
- BeeOnRope 7y agoYes, if you know you want zeroed memory, calloc() is best: because a smart userspace allocator will have two paths: if it is able to re-use memory already allocated and freed from userspace, it will explicitly zero it (probably with a memset) since it it is not (guaranteed to be) zero. OTOH, if it is asking the OS for fresh memory to satisfy the request, or is satisfying the request from an earlier allocation returned by the OS (which hasn't yet been fully used), it knows the memory is zero and can just return it directly. In that scenario calloc() is as fast as malloc(), yet it provides the additional guarantee of zeroed memory. Unfortunately, calloc() and C++ don't really place nice together, and C++ has no equivalent concept to calloc() in its allocator model (the same complaint applies to realloc() which would otherwise be very useful).
- jbapple 7y agoWhen I benchmarked that a few years ago, I found the overhead of a syscall made mmap much slower (assuming the C or C++ memory allocator had already received some memory from the OS it could dole out).
- gumby 7y agoMy point is that nobody cares about the time to zero out small blocks of memory, but when allocating large blocks you'll typically have to request the memory anyway...in which case don't re-zero it.
- BeeOnRope 7y agoThe kernel doesn't really have any tricks that userspace doesn't have to zero arrays quickly. In fact, it is somewhat hamstrung when zeroing since use of SIMD instructions in the kernel is discouraged and generally avoided. It usually ends up using `rep stosb` which is nice and fast on modern Intel (up to 32 bytes/cycle for AVX-supporting boxes), so that's not currently a problem, but it was slower in the past. Furthermore, this doesn't help you for repeatedly zeroing existing memory, which is probably the most important: are you going to mmap fresh pages every time you want zeros in there rather than just zeroing in userspace the memory you have?
- toast0 7y ago> The kernel doesn't really have any tricks that userspace doesn't have to zero arrays quickly. The kernel does have some tricks available --- it can't clean pages any faster than userspace, but it can keep a cache of clean pages, and keep the cache filled by cleaning free pages during idle, including before your program was launched. I'm sure that the kernel was able to do the work before your program was launched will look great in microbenchmarks, if used right, but if you need to do it repeatedly, mmunap/mmap syscall processing time is going to be a lot bigger than rep stosb, unless you have a giant block to zero out and the block is nicely aligned. Another comment in this general thread suggests that Linux doesn't do idle zeroing, but it's not the only kernel; FreeBSD has idle zeroing [1]. [1] https://www.freebsd.org/doc/en/articles/vm-design/prefault-optimizations.html https://www.freebsd.org/doc/en/articles/vm-design/prefault-o...
- nwallin 7y agoThis isn't actually true. The kernel has two giant tricks up its sleeve when it comes to serving zero pages: the kernel gets to decide what happens when a page fault happens, and it gets to decide what to tell the mmu. At boot, the kernel allocates a physical page of RAM, zeroes it, and marks it read only. Some time later, a user process requests a zeroed page. The kernel finds a new address in virtual memory, and tells the mmu to point that address to the zeroed page. The user process reads from the page, and gets zeroes back, because that's what's in the zero page. And there's nothing wrong with reading a read only page. Then the user tries to write into the zero page, and a page fault happens, because the page is read only. The kernel allocates new physical RAM, zeroes it, and updates the mmu mapping. This doesn't appear to do any less work, but gigabytes of virtual memory can in 4kB of cache, because it's all the same page. So it's way faster. One of my favorite benchmarks of all time is creating an identity matrix by using malloc, memset(0) it, then assign ones to the diagonal, vs using calloc, (which as per its specification zeroes it) and assigning ones to the diagonal. Then comparing the run time of multiplying the two identity matrices by some other matrix. The calloc identity matrix is multiple orders of magnitude faster.