3 ms·

What we need is a page-based Vec that mmaps (anon) for the storage but leaves the unused portions zero-bytes and therefore not part of RSS until actually requir

What we need is a page-based Vec that mmaps (anon) for the storage but leaves the unused portions zero-bytes and therefore not part of RSS until actually required. (And when clearing/shrinking sections, madvise DONTNEED the pages). That is, the vec could expand to areas much larger than the actual used size, but this would have no effect on process RSS until those pages get dirtied with actual data.

cnity 3y ago
Couldn't this obfuscate OOM type problems by not triggering actual memory issues until much later than the allocation?
- cmrdporcupine 3y ago
  Maybe? Depends on how you monitor and what your expectations are. But for workloads that use a lot of memory, and want to avoid wasteful empty allocations, or have sparse data, etc. it's a reasonable strategy.
vlovich123 3y ago
That can be not a great idea for subtle reasons even though it does seem like a better design at first. When you do the madvise, based on the contact of the API, the kernel has to do a TLB shoot down which is really expensive. And not just “expensive for my process” but expensive in terms of a significant slowdown for entire machine. Honestly you could probably DDOS a machine if you could reliably trigger that shootdown. As such you want to be very very careful where you place that data structure. For what it’s worth your memory allocator (or at least a good one like mimalloc or the non-gperftools newer tcmalloc) will do exactly as you mentioned where it will free memory back to the OS using advanced heuristics tested out at scale. As for why a shoot down is needed, it’s so that a racing allocation call in another process doesn’t get that virtual address but be running on a core where the TLB points elsewhere (the core that did the allocation may not even be the one where it’s used).
- cmrdporcupine 3y ago
  Yes, well, I think you're right it's a lot about the contract of the API and the expectation of the user. I'd certainly want intelligence (either by the user or by the framework) in how frequently you release pages back to the OS. But the DONTNEED is really not the core of the value. It's being able to create vectors that don't fragment as badly. And yes, you're right a decent allocator could help with this, and what I'm describing is really just a kind of specialized allocator.
  - vlovich123 3y ago
    I don’t follow. Fragmentation wasn’t the problem here - it’s that an optimization to trying to reuse the underlying allocation resulted in a severe over-allocation in a specific path. That would happen even with your idea unless you use DONTNEED to release all the unused pages. I think fragmentation is an over focused on problem when in practice it’s rarely the problem. It’s also a problem that can be solved by an application reset and making sure to periodically reset your running application in a way that doesn’t result in severe disruption is a better practice that works around many more issues than just fragmentation.
- LegionMammal978 3y ago
  Is MADV_FREE on Linux any better in this regard? It's what the libc allocators tend to use, if I recall correctly.
  - vlovich123 3y ago
    It would have to be the same problem because there’s no way to free memory without a shootdown AFAIK. As I describe elsewhere, I don’t think there’s any way to free memory to the OS without one as otherwise you can run into race conditions where another process allocating memory gets access to the memory being freed in another process through a stale TLB entry. Here’s a discussion [1] of a hypothetical lazy_munmap option that would initiate the unmap without an immediate shoot down (i.e. the CPUs would lazily evict from the TLB when they notice the request) but no such option exists. It’s also not immediately clear such a hypothetical API could exist on current CPU architectures or if it would require new HW support as I don’t have enough hands-on expertise at that level. Anyway, [1] is an interesting discussion of this idea and the note about huge pages making these even less valuable is interesting to keep in mind. [1] https://news.ycombinator.com/item?id=23216590 https://news.ycombinator.com/item?id=23216590
loeg 3y ago
Is this not going to be more or less what the memory allocator backing Vec does under the hood anyway?
glandium 3y ago
That's already what it does (except when shrinking)

cnity 3y ago

Couldn't this obfuscate OOM type problems by not triggering actual memory issues until much later than the allocation?

cmrdporcupine 3y ago
Maybe? Depends on how you monitor and what your expectations are. But for workloads that use a lot of memory, and want to avoid wasteful empty allocations, or have sparse data, etc. it's a reasonable strategy.

vlovich123 3y ago

That can be not a great idea for subtle reasons even though it does seem like a better design at first. When you do the madvise, based on the contact of the API, the kernel has to do a TLB shoot down which is really expensive. And not just “expensive for my process” but expensive in terms of a significant slowdown for entire machine. Honestly you could probably DDOS a machine if you could reliably trigger that shootdown. As such you want to be very very careful where you place that data structure. For what it’s worth your memory allocator (or at least a good one like mimalloc or the non-gperftools newer tcmalloc) will do exactly as you mentioned where it will free memory back to the OS using advanced heuristics tested out at scale. As for why a shoot down is needed, it’s so that a racing allocation call in another process doesn’t get that virtual address but be running on a core where the TLB points elsewhere (the core that did the allocation may not even be the one where it’s used).

cmrdporcupine 3y ago
Yes, well, I think you're right it's a lot about the contract of the API and the expectation of the user. I'd certainly want intelligence (either by the user or by the framework) in how frequently you release pages back to the OS. But the DONTNEED is really not the core of the value. It's being able to create vectors that don't fragment as badly. And yes, you're right a decent allocator could help with this, and what I'm describing is really just a kind of specialized allocator.
- vlovich123 3y ago
  I don’t follow. Fragmentation wasn’t the problem here - it’s that an optimization to trying to reuse the underlying allocation resulted in a severe over-allocation in a specific path. That would happen even with your idea unless you use DONTNEED to release all the unused pages. I think fragmentation is an over focused on problem when in practice it’s rarely the problem. It’s also a problem that can be solved by an application reset and making sure to periodically reset your running application in a way that doesn’t result in severe disruption is a better practice that works around many more issues than just fragmentation.
LegionMammal978 3y ago
Is MADV_FREE on Linux any better in this regard? It's what the libc allocators tend to use, if I recall correctly.
- vlovich123 3y ago
  It would have to be the same problem because there’s no way to free memory without a shootdown AFAIK. As I describe elsewhere, I don’t think there’s any way to free memory to the OS without one as otherwise you can run into race conditions where another process allocating memory gets access to the memory being freed in another process through a stale TLB entry. Here’s a discussion [1] of a hypothetical lazy_munmap option that would initiate the unmap without an immediate shoot down (i.e. the CPUs would lazily evict from the TLB when they notice the request) but no such option exists. It’s also not immediately clear such a hypothetical API could exist on current CPU architectures or if it would require new HW support as I don’t have enough hands-on expertise at that level. Anyway, [1] is an interesting discussion of this idea and the note about huge pages making these even less valuable is interesting to keep in mind. [1] https://news.ycombinator.com/item?id=23216590 https://news.ycombinator.com/item?id=23216590

loeg 3y ago

Is this not going to be more or less what the memory allocator backing Vec does under the hood anyway?

glandium 3y ago

That's already what it does (except when shrinking)