4 ms·

A queue of page faults (2014)

59 points by vmorgulis 10y ago

MichaelGG 10y ago
On page zeroing, why does the kernel and CPU need to do this like any regular write? Shouldn't there be some fast-path instruction+RAM support to "zero this range"? The kernel can guarantee the page/lines are not in use elsewhere, right? So such an instruction can just wipe everything out. Or is just writing 0s detected and optimized already? Same question for memcpy and stuff like that: shouldn't that be a CPU instruction instead of special code trying to detect which CPU and emit optimized instructions? Is my model of these costs that far off?
- david-given 10y ago
  ia32 architectures do actually have an instruction which lets you do cheap memcpys and memsets --- REP (and friends). All it does it to repeat the next instruction rapidly, so if the next instruction is a set-and-increment-pointer than you get a memset. etc. (Don't know about ia64.) Trouble is, it's still just a simple loop, and it's not that much faster than doing it the long way... and on some architectures it's actually slower. It all depends on how optimised the microcode it decodes into is. After all, it still has to set the address bus and issue a write for every location in the RAM. There are no shortcuts there. Some architectures will let you do memcpys and memsets via the DMA engine, which can give a small performance boost, but these are usually embedded architectures. (I've used one on the MSP430.)
  - MichaelGG 10y ago
    Is it though? The memcpy implementations I remember reading about do all sorts of exotic things depending on the size, which processor, etc. As you mention, sometimes it's still slower and depends on microcode. A dedicated memcpy instruction shouldn't have that issue right?
- amluto 10y ago
  Unless you have a system some kind of per-page tag in memory that indicates "should be zero", the CPU still has to write all the zero to RAM. This is limited by memory bandwidth. On newer Intel CPUs, REP STOSB is highly optimized, but you still have to do the writes.
  - Someone 10y ago
    Because DRAM is (relatively) so slow, avoiding the _reads_ is a big gain. If you zero a large range of memory the naive way, the first write to each cache line _reads_ a cache line of data that likely will be overwritten by zeroes. Problem is: how does the CPU know it doesn't have to do that read? REP STOSB may, but it isn't trivial to implement, as neither start nor end of the range to be processed need to lie on a cache line boundary. PowerPC has the dcbz and dcbzl instructions which zero a cache line without reading the to-be-zeroed data (dcbzl was invented because real-world code assumed dcbz always zeroed 32 bytes. See http://lists.apple.com/archives/darwin-drivers/2005/Apr/msg00142.html http://lists.apple.com/archives/darwin-drivers/2005/Apr/msg0...)
    - neopallium 10y ago
      The processor will try to do write-combining to fill entire cache lines, so it doesn't need to do a memory read. GCC already has a number of intrinsics to help with streaming data directly to RAM (helps to keep from evicting more important data from the cache). The cache can be bypassed when doing a lot of writes. See section "Bypassing the cache" of [0]. That article says that memset() already uses cache bypassing instructions for large blocks. 0. https://lwn.net/Articles/255364/ https://lwn.net/Articles/255364/
- MarkSweep 10y ago
  Zeroing the pages is not nessisarily the bottleneck here, as Windows has a background thread that will zero memory as it is freed. The problem is the initial allocation just sets up the virtual address space without backing those virtual pages with physical pages. Upon accessing the pages for the first time a page fault has to find a physical page to use. According to MSDN, even when you use MEM_COMMIT: "The function also guarantees that when the caller later initially accesses the memory, the contents will be zero. Actual physical pages are not allocated unless/until the virtual addresses are actually accessed." https://msdn.microsoft.com/en-us/library/windows/desktop/aa366887(v=vs.85).aspx https://msdn.microsoft.com/en-us/library/windows/desktop/aa3...
- repiret 10y ago
  Most CPU architectures have instructions to zero memory, but whether its a single instructions or a few in a loop doesn't make much of a difference [1], since the problem is that the underlying memory is dog slow in comparison. If you want better hardware support, you need to keep the memory hierarchy in mind, and recall that there are multiple coherent masters in any modern system. If we teach DRAM to zero a block on command, the CPU can't just ask DRAM to do that - the L1, L2 and L3 caches need to be kept coherent, and the other CPUs have their own L1 caches too. We could teach DDR to accept "write zeros" commands from L3, and L3 to accept them from L2, and L2 to accept them from L1. L1 is already accepting them from the CPUs that have memory-zeroing instructions. In fact I'm aware of one CPU design where that already exists in the L1<->L2 interface [2]. One could also take a different approach - if you assume the kernel wants to keep the memory on the free-list zero'd, then you could have another coherent master in the memory system to do that work for the kernel. When a page is de-allocated, the kernel hands it to the memory zero-er, when the zero-er is done, it fires an interrupt and the kernel accepts the page onto the free list. I'll bet there are a lot of DMA controllers that could be made to do this already, although I don't know if any of them could do it fast enough to be a net win given the extra interrupt activity. [1]: Except on some embedded CPUs, which can manage caches more efficiently when using memory-zeroing instructions. [2]: http://infocenter.arm.com/help/topic/com.arm.doc.100511_0401_10_en/ric1447333697057.html http://infocenter.arm.com/help/topic/com.arm.doc.100511_0401...
twoodfin 10y ago
I'm surprised this article doesn't mention one typical solution to the problem of massive numbers of expensive page faults for large allocations: Pages bigger than 4K, which are supported on most modern operating systems. On Linux they go by the name "huge pages": https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt

59 points by vmorgulis 10y ago

On page zeroing, why does the kernel and CPU need to do this like any regular write? Shouldn't there be some fast-path instruction+RAM support to "zero this range"? The kernel can guarantee the page/lines are not in use elsewhere, right? So such an instruction can just wipe everything out. Or is just writing 0s detected and optimized already? Same question for memcpy and stuff like that: shouldn't that be a CPU instruction instead of special code trying to detect which CPU and emit optimized instructions? Is my model of these costs that far off?

david-given 10y ago
ia32 architectures do actually have an instruction which lets you do cheap memcpys and memsets --- REP (and friends). All it does it to repeat the next instruction rapidly, so if the next instruction is a set-and-increment-pointer than you get a memset. etc. (Don't know about ia64.) Trouble is, it's still just a simple loop, and it's not that much faster than doing it the long way... and on some architectures it's actually slower. It all depends on how optimised the microcode it decodes into is. After all, it still has to set the address bus and issue a write for every location in the RAM. There are no shortcuts there. Some architectures will let you do memcpys and memsets via the DMA engine, which can give a small performance boost, but these are usually embedded architectures. (I've used one on the MSP430.)
- MichaelGG 10y ago
  Is it though? The memcpy implementations I remember reading about do all sorts of exotic things depending on the size, which processor, etc. As you mention, sometimes it's still slower and depends on microcode. A dedicated memcpy instruction shouldn't have that issue right?
amluto 10y ago
Unless you have a system some kind of per-page tag in memory that indicates "should be zero", the CPU still has to write all the zero to RAM. This is limited by memory bandwidth. On newer Intel CPUs, REP STOSB is highly optimized, but you still have to do the writes.
- Someone 10y ago
  Because DRAM is (relatively) so slow, avoiding the _reads_ is a big gain. If you zero a large range of memory the naive way, the first write to each cache line _reads_ a cache line of data that likely will be overwritten by zeroes. Problem is: how does the CPU know it doesn't have to do that read? REP STOSB may, but it isn't trivial to implement, as neither start nor end of the range to be processed need to lie on a cache line boundary. PowerPC has the dcbz and dcbzl instructions which zero a cache line without reading the to-be-zeroed data (dcbzl was invented because real-world code assumed dcbz always zeroed 32 bytes. See http://lists.apple.com/archives/darwin-drivers/2005/Apr/msg00142.html http://lists.apple.com/archives/darwin-drivers/2005/Apr/msg0...)
  - neopallium 10y ago
    The processor will try to do write-combining to fill entire cache lines, so it doesn't need to do a memory read. GCC already has a number of intrinsics to help with streaming data directly to RAM (helps to keep from evicting more important data from the cache). The cache can be bypassed when doing a lot of writes. See section "Bypassing the cache" of [0]. That article says that memset() already uses cache bypassing instructions for large blocks. 0. https://lwn.net/Articles/255364/ https://lwn.net/Articles/255364/
MarkSweep 10y ago
Zeroing the pages is not nessisarily the bottleneck here, as Windows has a background thread that will zero memory as it is freed. The problem is the initial allocation just sets up the virtual address space without backing those virtual pages with physical pages. Upon accessing the pages for the first time a page fault has to find a physical page to use. According to MSDN, even when you use MEM_COMMIT: "The function also guarantees that when the caller later initially accesses the memory, the contents will be zero. Actual physical pages are not allocated unless/until the virtual addresses are actually accessed." https://msdn.microsoft.com/en-us/library/windows/desktop/aa366887(v=vs.85).aspx https://msdn.microsoft.com/en-us/library/windows/desktop/aa3...
repiret 10y ago
Most CPU architectures have instructions to zero memory, but whether its a single instructions or a few in a loop doesn't make much of a difference [1], since the problem is that the underlying memory is dog slow in comparison. If you want better hardware support, you need to keep the memory hierarchy in mind, and recall that there are multiple coherent masters in any modern system. If we teach DRAM to zero a block on command, the CPU can't just ask DRAM to do that - the L1, L2 and L3 caches need to be kept coherent, and the other CPUs have their own L1 caches too. We could teach DDR to accept "write zeros" commands from L3, and L3 to accept them from L2, and L2 to accept them from L1. L1 is already accepting them from the CPUs that have memory-zeroing instructions. In fact I'm aware of one CPU design where that already exists in the L1<->L2 interface [2]. One could also take a different approach - if you assume the kernel wants to keep the memory on the free-list zero'd, then you could have another coherent master in the memory system to do that work for the kernel. When a page is de-allocated, the kernel hands it to the memory zero-er, when the zero-er is done, it fires an interrupt and the kernel accepts the page onto the free list. I'll bet there are a lot of DMA controllers that could be made to do this already, although I don't know if any of them could do it fast enough to be a net win given the extra interrupt activity. [1]: Except on some embedded CPUs, which can manage caches more efficiently when using memory-zeroing instructions. [2]: http://infocenter.arm.com/help/topic/com.arm.doc.100511_0401_10_en/ric1447333697057.html http://infocenter.arm.com/help/topic/com.arm.doc.100511_0401...

twoodfin 10y ago

I'm surprised this article doesn't mention one typical solution to the problem of massive numbers of expensive page faults for large allocations: Pages bigger than 4K, which are supported on most modern operating systems. On Linux they go by the name "huge pages": https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt