3 ms·

Understanding Mesh Allocator

70 points by signa11 3y ago

anonymoushn 3y ago
This is a cool technique, but it will cost you more TLB misses, which are pretty expensive. For most software, you can get it to run 10-20% faster just by reducing TLB misses by 99% using 2MB pages. I speculate that the reason this is not often done is that the feature is basically unusable on Windows.
- CyberDildonics 3y ago
  Can you go in to more detail about that? Are any larger pages usable on windows?
  - anonymoushn 3y ago
    Using 2MB or 1GB pages on Windows involves changing security settings, rebooting the machine, and immediately launching the app you care about as administrator. If you ever close it, you'll need to reboot again, because Windows will not try to rearrange 4KB pages to create new contiguous aligned physical 2MB or 1GB regions to back future requests for huge pages.
    - lostmsu 3y ago
      From skimming MSDN this seems wrong. Windows will try to defragment memory to give you a large page. Of course that takes time though. Slightly more concerning is that docs claim large pages don not support paging (to disk).
      - anonymoushn 3y ago
        I haven't kept up with this in the last year or so, but as of about a year ago memory defragmentation was essentially absent, having been mostly disabled after users complained that it took way too long in win8.
- emeryberger 3y ago
  Hi, Mesh co-author here. Mesh should not introduce any additional TLB pressure - the number of virtual pages remains the same, so the number of TLB entries does not change. It remaps existing virtual pages to the same physical page once they have been meshed. Using huge pages is an entirely different question, and one that would require novel techniques to adapt meshing to that setting.
  - anonymoushn 3y ago
    If for example you have some pages that are used for 64b objects, and you merge them to be backed by the same physical page, and then the user allocates more 64b objects such that a 2nd physical page of 64b objects must be allocated, they're now using 3 virtual pages for their 2 physical pages worth of 64b objects. With an allocator that does not point multiple virtual pages at the same physical page, they could only be using 2 virtual pages for their 64b objects. So more TLB entries are not required immediately when pages are merged, they are required later when more objects are allocated. It's certainly possible that I've misunderstood and the pages are actually un-merged by Mesh at this point so that new allocations can be served from the existing 2 half-full virtual pages (which are now backed by 2 separate half-full physical pages).
    - emeryberger 3y ago
      In the steady state, I would not expect this to happen. Mesh prefers to allocate from nearly full virtual pages (see Section 3.1). This gives emptier pages time to get emptier; once they become completely empty, their virtual addresses can be reclaimed. In short, Mesh maintains roughly the same TLB footprint (note: we should otherwise have observed a performance decrease, which we did not), while significantly reducing physical memory consumption. It's also worth noting that meshing is only triggered when memory is fragmented and the heap is sparsely occupied, so it really lowers the peaks of physical memory consumption exactly at the moment when meshing helps the most, and at the same time, has no impact on the TLB (except of course updating entries).
- crotchfire 3y ago
  Cannot upvote enough. Software people think the MMUs are zero-cost, memory mappings are free, and TLBs are infinite. None of these are true.
nu11ptr 3y ago
Interesting, but if it decreases performance...why do it? I would have hoped cache locality would have beat out the increase due to copying, but per the article it doesn't sound like the case.
- deleted 3y ago
  [deleted]
- emeryberger 3y ago
  Hi, Mesh co-author here. The point of the work was to save memory by “virtual compaction”; we hoped to be able to do this while not degrading performance too much, since compaction typically is quite costly. Our empirical results found that Mesh saves memory by between 16% to 39%, while imposing very modest slowdowns, e.g. 1% for Firefox (see Section 6 of the paper - https://people.cs.umass.edu/~mcgregor/papers/19-pldi.pdf https://people.cs.umass.edu/~mcgregor/papers/19-pldi.pdf).
  - nu11ptr 3y ago
    Thanks for the follow up. 1% slowdown easily worth that level of memory savings IMO. I guess the goal was simply different than I expected.
  - nahuel0x 3y ago
    Besides memory saving, there are workloads that can still fragment the memory even using Mesh to a point that you can't compact / allocate no more? I'm thinking about Embedded systems were maybe you can have a max number of dynamic allocations but whose number oscillates a lot over time with different patterns. What are the limits of Mesh?
    - emeryberger 3y ago
      Mesh's fragmentation protection is probabilistic (but highly effective) and as fragmentation grows, the likelihood of it being able to perform compaction also grows. Intuitively, if you have lots of sparsely allocated pages, Mesh is almost certainly going to be able to find many pairs of pages that it can "mesh" together into a single physical page. If the pages are too dense, then Mesh becomes ineffective, but that's exactly the point where there's little opportunity to squeeze out memory savings and the pages aren't really fragmented.
diimdeep 3y ago
Any software in the wild using this allocator since invention more than 6 year ago? https://github.com/bpowers/redis/tree/mesh https://github.com/bpowers/redis/tree/mesh
- imglorp 3y ago
  The linked talk video mentioned they're playing with it in jemalloc and tcmalloc. I found this https://github.com/jemalloc/jemalloc/issues/1440 https://github.com/jemalloc/jemalloc/issues/1440 but couldn't find tcmalloc doing similar. These guys are aware of mesh and compare against it: https://abelay.github.io/6828seminar/papers/maas:llama.pdf https://abelay.github.io/6828seminar/papers/maas:llama.pdf
tlb 3y ago
Back in the 90s I tried to do something clever with page tables. But at the time, some architectures like PA-RISC used virtually tagged caches and it was very hard to make it work on such systems. Can we assume that we’ll never see such a memory architecture again?

70 points by signa11 3y ago

This is a cool technique, but it will cost you more TLB misses, which are pretty expensive. For most software, you can get it to run 10-20% faster just by reducing TLB misses by 99% using 2MB pages. I speculate that the reason this is not often done is that the feature is basically unusable on Windows.

CyberDildonics 3y ago
Can you go in to more detail about that? Are any larger pages usable on windows?
- anonymoushn 3y ago
  Using 2MB or 1GB pages on Windows involves changing security settings, rebooting the machine, and immediately launching the app you care about as administrator. If you ever close it, you'll need to reboot again, because Windows will not try to rearrange 4KB pages to create new contiguous aligned physical 2MB or 1GB regions to back future requests for huge pages.
  - lostmsu 3y ago
    From skimming MSDN this seems wrong. Windows will try to defragment memory to give you a large page. Of course that takes time though. Slightly more concerning is that docs claim large pages don not support paging (to disk).
    - anonymoushn 3y ago
      I haven't kept up with this in the last year or so, but as of about a year ago memory defragmentation was essentially absent, having been mostly disabled after users complained that it took way too long in win8.
emeryberger 3y ago
Hi, Mesh co-author here. Mesh should not introduce any additional TLB pressure - the number of virtual pages remains the same, so the number of TLB entries does not change. It remaps existing virtual pages to the same physical page once they have been meshed. Using huge pages is an entirely different question, and one that would require novel techniques to adapt meshing to that setting.
- anonymoushn 3y ago
  If for example you have some pages that are used for 64b objects, and you merge them to be backed by the same physical page, and then the user allocates more 64b objects such that a 2nd physical page of 64b objects must be allocated, they're now using 3 virtual pages for their 2 physical pages worth of 64b objects. With an allocator that does not point multiple virtual pages at the same physical page, they could only be using 2 virtual pages for their 64b objects. So more TLB entries are not required immediately when pages are merged, they are required later when more objects are allocated. It's certainly possible that I've misunderstood and the pages are actually un-merged by Mesh at this point so that new allocations can be served from the existing 2 half-full virtual pages (which are now backed by 2 separate half-full physical pages).
  - emeryberger 3y ago
    In the steady state, I would not expect this to happen. Mesh prefers to allocate from nearly full virtual pages (see Section 3.1). This gives emptier pages time to get emptier; once they become completely empty, their virtual addresses can be reclaimed. In short, Mesh maintains roughly the same TLB footprint (note: we should otherwise have observed a performance decrease, which we did not), while significantly reducing physical memory consumption. It's also worth noting that meshing is only triggered when memory is fragmented and the heap is sparsely occupied, so it really lowers the peaks of physical memory consumption exactly at the moment when meshing helps the most, and at the same time, has no impact on the TLB (except of course updating entries).
crotchfire 3y ago
Cannot upvote enough. Software people think the MMUs are zero-cost, memory mappings are free, and TLBs are infinite. None of these are true.

nu11ptr 3y ago

Interesting, but if it decreases performance...why do it? I would have hoped cache locality would have beat out the increase due to copying, but per the article it doesn't sound like the case.

deleted 3y ago
[deleted]
emeryberger 3y ago
Hi, Mesh co-author here. The point of the work was to save memory by “virtual compaction”; we hoped to be able to do this while not degrading performance too much, since compaction typically is quite costly. Our empirical results found that Mesh saves memory by between 16% to 39%, while imposing very modest slowdowns, e.g. 1% for Firefox (see Section 6 of the paper - https://people.cs.umass.edu/~mcgregor/papers/19-pldi.pdf https://people.cs.umass.edu/~mcgregor/papers/19-pldi.pdf).
- nu11ptr 3y ago
  Thanks for the follow up. 1% slowdown easily worth that level of memory savings IMO. I guess the goal was simply different than I expected.
- nahuel0x 3y ago
  Besides memory saving, there are workloads that can still fragment the memory even using Mesh to a point that you can't compact / allocate no more? I'm thinking about Embedded systems were maybe you can have a max number of dynamic allocations but whose number oscillates a lot over time with different patterns. What are the limits of Mesh?
  - emeryberger 3y ago
    Mesh's fragmentation protection is probabilistic (but highly effective) and as fragmentation grows, the likelihood of it being able to perform compaction also grows. Intuitively, if you have lots of sparsely allocated pages, Mesh is almost certainly going to be able to find many pairs of pages that it can "mesh" together into a single physical page. If the pages are too dense, then Mesh becomes ineffective, but that's exactly the point where there's little opportunity to squeeze out memory savings and the pages aren't really fragmented.

diimdeep 3y ago

Any software in the wild using this allocator since invention more than 6 year ago? https://github.com/bpowers/redis/tree/mesh https://github.com/bpowers/redis/tree/mesh

imglorp 3y ago
The linked talk video mentioned they're playing with it in jemalloc and tcmalloc. I found this https://github.com/jemalloc/jemalloc/issues/1440 https://github.com/jemalloc/jemalloc/issues/1440 but couldn't find tcmalloc doing similar. These guys are aware of mesh and compare against it: https://abelay.github.io/6828seminar/papers/maas:llama.pdf https://abelay.github.io/6828seminar/papers/maas:llama.pdf

tlb 3y ago

Back in the 90s I tried to do something clever with page tables. But at the time, some architectures like PA-RISC used virtually tagged caches and it was very hard to make it work on such systems. Can we assume that we’ll never see such a memory architecture again?