[HN Gopher] Spotting and avoiding heap fragmentation in Rust app...
___________________________________________________________________
Spotting and avoiding heap fragmentation in Rust applications
Author : tasn
Score : 87 points
Date : 2023-04-06 15:25 UTC (7 hours ago)
(HTM) web link (www.svix.com)
(TXT) w3m dump (www.svix.com)
| jamboca wrote:
| "The specific cause for the fragmentation could be any number of
| things: JSON parsing with serde, something at the framework-level
| in axum, something deeper in tokio, or even just a quirk of the
| specific allocator implementation for the given system. Even
| without knowing the root cause (if there is such a thing) the
| behavior is observable in our environment and somewhat
| reproducible in a bare-bones app."
|
| So what is the ultimate cause of the fragmentation in this case?
| You can blame your allocator implementation, but how do you know
| it's not your use of the allocator? It feels like you are just
| slapping jemalloc on to solve this, which I suppose shows that
| the allocator you were using was causing problems before, but it
| doesn't really explain how? I suppose what I'm wondering is why
| specifically the allocator you were using before was causing this
| fragmentation... isn't that a bigger problem than you're making
| it sound?
|
| Also, what else can an allocator do other than coalescing free
| blocks to decrease fragmentation? Does it involve occasional
| checks to defragment the heap ie moving separated blocks so they
| are adjacent?
| tasn wrote:
| Our assumption, which turned out to be true, is that it's due
| to the JSON parsing code. Rust (serde) is very efficient with
| parsing JSON to a predefined structure, but when it comes to
| parsing to a "generic object", which we need for part of the
| payload, it's not as much. We are going to deploy a full fix
| for this issue too, but jemalloc already solved it as well.
|
| Though I disagree with saying it's "just slapping jemalloc on
| to solve this". The piece of code in question definitely made
| the fragmentation issue worse, as it was making a lot of
| allocations of varying sizes, but the underlying issue of
| memory fragmentation because of the allocator was still there,
| and it would have just triggered later by a different code
| path.
| astrange wrote:
| Heap fragmentation often comes from allocating objects with
| different lifetimes at the same time on the same pages.
| Parsing is a common case of this because you allocate the
| whole object tree then only keep some of it.
| tasn wrote:
| Not in the context of an HTTP server. As we just parse, use
| it in the request, and then return (freeing all the
| memory). I think the problem is because we have multiple
| requests being handled in tandem and Rust doesn't know it's
| probably better off allocating all of the data together and
| then freeing this big block.
|
| That's what's nice about jemalloc, it has a more generic
| algorithm for reusing allocated blocks.
| Tuna-Fish wrote:
| The gold standard for avoiding fragmentation is what jemalloc
| does, that is, only allocating objects of similar size from a
| chunk of memory. That is, instead of a single global heap there
| exists a pool for every valid size of object (and to keep the
| numbers low, object sizes are rounded up to some set of
| buckets).
|
| This means that there is more memory wasted for small programs,
| but as memory use grows the wastage caused by this remains
| constant and allocation and deallocation will always remain
| fast.
| astrange wrote:
| This isn't good enough because size of an allocation says
| nothing about what its lifetime is. If you know lifetimes or
| types then you can segregate those and it does help.
|
| (It does help in that if you have fixed size slabs, you can't
| waste space on that page, but you can still waste the entire
| page.)
| zackangelo wrote:
| If you're doing memory-intensive tasks that are clearly bounded
| (e.g., handling an http request), I wonder if it's worth looking
| at something like an arena allocator [0] that can free the entire
| task's memory at once.
|
| [0] https://docs.rs/bumpalo/latest/bumpalo/
| tayo42 wrote:
| was curious about
|
| > When services exit abruptly, this can lower availability...
| which is bad for business.
|
| interesting company
|
| > Do you offer SLAs? We offer uptime SLAs of 99.999% for our
| enterprise customers, 99.99% for our business tier customers, and
| 99.9% for our startup tier users.
|
| 99.999 is miserable to support. how do you even get the
| granularity to measure, freedom to try anything? i dont think
| cloud services even provide slas like that for their services.
|
| >Can you handle our scale? We process billions of webhooks a year
| for our customers,
|
| 1 billion a year would average out to 32 a second. if its 10
| billion? 320/second. surprising to see rust for this. gc
| languages should be able to handle it.
|
| would have been interesting to see how much fragmentation there
| is. reads like there was a debugging step missing.
| tasn wrote:
| > 99.999 is miserable to support. how do you even get the
| granularity to measure, freedom to try anything? i dont think
| cloud services even provide slas like that for their services.
|
| A lot of redundancies and testing.
|
| > 1 billion a year would average out to 32 a second. if its 10
| billion? 320/second. surprising to see rust for this. gc
| languages should be able to handle it.
|
| This assumes even distribution, though traffic is much much
| more spiky than this. We started with Python and switched to
| Rust. FWIW, Rust is great for many other reasons, not just the
| efficiency. For example, we absolutely love the type system.
|
| > would have been interesting to see how much fragmentation
| there is. reads like there was a debugging step missing.
|
| I'm not the engineer that did the investigation, so can't
| comment directly about what he checked. Maybe it's not written
| there, but he also measured allocator statistics and indeed saw
| that the memory used according to the US was much higher than
| what the allocator stats said.
| wongarsu wrote:
| > In the case of this old PC hard drive, files of varying sizes
| were written to disk then later moved or deleted, leaving a
| "hole" of available space between other used regions. As the disk
| starts to fill up, you might try to create a new file that
| doesn't quite fit in one of those smaller areas, and you'd be out
| of luck. You'd need to "defrag" in order to reclaim those open
| blocks which are too small to hold the new file when they are
| split up, but could be big enough when they are contiguous.
|
| While that is pretty much what heap fragmentation is about, the
| failure mode of disk fragmentation is less drastic. The file
| system will just split the file contents across multiple smaller
| free spots, making it possible to use the whole disk no matter
| your write pattern. The issue is that now the file is no longer
| contiguous, so reading the entire file takes longer. Much longer
| if we are talking about old HDDs.
| onelson wrote:
| Good point, thanks! Will update the article to clarify the
| difference.
| cryptonector wrote:
| The failure mode for filesystems is to get slow. Same as for
| heap allocation.
| dgacmu wrote:
| No - heap fragmentation actually leaves memory unusable by
| the workload. It may or may not slow down allocation
| depending on the design of the allocator.
|
| (The analogy to file system fragmentation for memory is that
| when physical pages are allocated in a discontinuous manner,
| it prevents some optimizations like coalescing them into
| hugepages, which for some workloads can help with TLB hit
| rate.)
| yakubin wrote:
| Filesystem may also run out of inodes, even though there is
| still plenty of space.
| cryptonector wrote:
| Or you should use ZFS and not worry about that.
| wongarsu wrote:
| I don't think either FAT32 or NTFS suffer this problem,
| they allow metadata to become fragmented instead.
| Certainly a different design philosophy to the unixy file
| systems.
| magicalhippo wrote:
| NTFS most definitely suffers from this[1]. We ran into it
| with a customer who had a particularly fragmented
| database file.
|
| IIRC it's due to a combination of relying on fixed-sized
| "pages" to hold fragment pointers and a limited number of
| page indirections. That is the root page can point to a
| sub-pages, which again can point to sub-pages, but those
| sub-sub-pages _have_ to point to the actual fragments. Or
| something along those lines.
|
| [1]: https://support.microsoft.com/en-au/topic/a-heavily-
| fragment...
| munificent wrote:
| In some ways Rust is in the worst possible position in terms of
| language design when it comes to fragmentation.
|
| In a completely manually managed language like C or C++, you can
| handle fragmentation problems yourself by writing your own
| allocators or doing object pools to reuse previously allocated
| memory. You have _control_ over fragmentation.
|
| In a garbage collected language like Java or C#, the runtime is
| able to move objects around in memory and update their pointers.
| So, as long as your language has a sufficiently advanced
| implementation, it may defragment on the fly for you.
|
| But Rust is sort of stuck in the middle. It's safe enough that
| it's hard to write your own allocators or easily reuse previously
| allocated memory. But it's low level enough that the runtime
| doesn't have the freedom to move things around in memory under
| the program.
|
| It's a hard problem.
| solomatov wrote:
| >In a completely manually managed language like C or C++, you
| can handle fragmentation problems yourself by writing your own
| allocators or doing object pools to reuse previously allocated
| memory. You have control over fragmentation.
|
| It's done constantly in Rust. Create a vector of items you want
| to allocate. Reference to them by their id, i.e. int
| representing them. There're libraries supporting this style of
| development, for example, slab: https://crates.io/crates/slab
| sgeisenh wrote:
| Doesn't the normal approach in C++ run into similar issues? The
| workarounds in C++ are more ergonomic than in Rust, but can
| still require a lot of refactoring.
|
| One of the performance bottlenecks that I ran into while
| reimplementing clox in C++ was using `new` and `delete` instead
| of `realloc` for arrays and hash tables. By the time that I
| figured out it was an issue, I was already using `operator new`
| to track heap allocations for the garbage collector.
| nikeee wrote:
| Shouldn't this also be a much larger problem when deploying rust
| on embedded systems or in the kernel? How is that solved in these
| cases? Or is this not a problem at all?
| tasn wrote:
| Both the kernel and embedded systems manage memory very
| differently to "normal" applications. The kernel has its own
| allocation functions, and embedded systems often don't
| "allocate" but rather just have fixed memory regions they use
| for things.
| nikeee wrote:
| I recall from playing with Arduino that using heap-allocated
| strings will cause heap fragmentation, which is why they
| should be avoided. This was C++, doesn't this count for rust
| as well?
|
| Do kmalloc/kzmalloc do magic to circumvent this problem,
| similar to jemalloc?
| Tuna-Fish wrote:
| Rust by default uses the platform allocator. Anything that's
| true of it's allocator performance is also true of C.
|
| Also, as the sibling comment said, when you are doing tight
| embedded, the solution is not to allocate things dynamically.
| steveklabnik wrote:
| The embedded code I write doesn't use an allocator at all, so
| it's not a problem there.
| lordnacho wrote:
| Any thoughts about snmalloc as an alternative? Can't quite recall
| the differences but seemed to look good on benchmarks.
| mcronce wrote:
| Not OP, but I've tried it in a handful of projects and haven't
| seen a measurable improvement to performance, memory
| utilization, or heap fragmentation. That said, it's easy to try
| out different allocators; I recommend giving it a shot for your
| specific workload, because IME they tend to perform very
| differently in different applications.
| MuffinFlavored wrote:
| This article would've been a bit cooler if the conclusion wasn't
| "switch from default allocator to jemalloc" but instead "use
| jemalloc to prove something is wrong in the default allocator and
| track down + find a fix for what's wrong in the default
| allocator"
|
| Unless I misunderstood that the default Rust allocator, with high
| request bodies and concurrency, is always going to suffer
| unfixable heap fragmentation like displayed in the article?
| Hooray_Darakian wrote:
| I'm not sure it's the case that there's something "wrong" with
| the default allocator, but rather that there are different
| tradeoffs at play. There's an old but good discussion of the
| issue here https://github.com/rust-
| lang/rfcs/blob/master/text/1183-swap...
| MuffinFlavored wrote:
| A sharp increase that never comes back down over time seems
| more "wrong" than right to me, no?
| Hooray_Darakian wrote:
| Without more context I think it's unclear. I know linux
| tends to avoid freeing memory until/unless the system is
| near capacity, so this test may be running on a system with
| low memory pressure.
| chc wrote:
| It's not good, but only looking at the bad half of a
| tradeoff will always look bad. Without diving into the
| glibc source code to understand what it's doing, it is hard
| to say if this is actually wrong.
| moomin wrote:
| I've recently been doing a lot of work that involves
| algorithmic design with non-technical people and this is
| the fun thing. It's very easy to identify expected
| scenarios, harder to identify how to achieve them and
| sometimes actually impossible on e you consider things
| like "the algorithm doesn't know what happens next".
| ht85 wrote:
| All allocators make different trade-offs in terms of memory
| usage, min / max / mean time to allocate and optimizations for
| certain allocation patterns (small, large, mixed, ...).
|
| There might not be anything wrong with the default allocator,
| it just isn't the best suited for that particular use.
| twic wrote:
| The default allocator is whatever is provided by the platform
| libc. In this case, i would guess that's the glibc allocator.
|
| It's possible that the glibc allocator contains some simple
| bug. It's more likely that it doesn't contain any simple bugs,
| but makes different tradeoffs to jemalloc, which make it less
| suitable to this particular slice of applications.
| mcronce wrote:
| I agree that there could have been a more satisfying
| conclusion, but it is worth noting that jemalloc isn't a
| panacea. I've seen issues similar to Svix in both Rust and C++
| applications that were heavy on ephemeral allocations, and have
| fixed it by doing all of the following, depending on the
| specific process: * Switching from libc malloc
| to jemalloc * Switching from libc malloc to tcmalloc
| (dating myself a little bit) * Switching from libc malloc
| to mimalloc * Switching from jemalloc to mimalloc *
| Switching from jemalloc to libc malloc * Switching from
| mimalloc to jemalloc
|
| Possibly others; I only want to list cases I'm 100% certain of.
|
| Heap fragmentation is just a reality of some allocation
| patterns without a GC runtime.
|
| One certainly can (and, in some cases, should) make their
| application more allocator-friendly, but - aside from some
| often-low-hanging fruit - this is a time-intensive process
| involving a bit of, for lack of a better word, arcane knowledge
| (I should inline all my fields and allocate on the stack as
| much as possible, right? Yes, well, except ...)
|
| If you already have a halfway decent benchmark suite or
| workload generator, which you'll want for other purposes
| anyway, it's often a lot quicker to just try a few other
| allocators and select the one that handles your workload best.
| scottlamb wrote:
| > * Switching from libc malloc to tcmalloc (dating myself a
| little bit)
|
| If you think of tcmalloc as an old crusty allocator, you've
| probably only seen the gperftools version of it.
|
| This is the version Google now uses internally:
| https://github.com/google/tcmalloc
|
| It's worth a fresh look. In particular, it supports per-CPU
| caches as an alternative to per-thread caches. Those are
| fantastic if you have a lot more threads than CPUs. I haven't
| checked if it's been adapted for the latest upstream kernel
| API, but there's also the idea of "vcpu"-based caches:
| basically rather than a physical cpu id, it's an (optionally
| per-numa-node-based) dense id assigned to active threads, so
| that it still works well if you have a small cpu allocation
| for this process on a many-core machine.
| adrianmonk wrote:
| > _Gaps that are too small and scattered throughout the heap can
| lead to new "fresh" blocks of memory being allocated to
| accommodate a new value that won't fit otherwise. Though
| unfortunately because of how memory management works a "defrag"
| is not possible._
|
| This is how memory management works now, but some older systems
| like classic Mac OS and Palm OS used a design that did make it
| possible to compact the heap.
|
| See
| https://en.wikipedia.org/wiki/Classic_Mac_OS_memory_manageme...
|
| When you allocated memory, instead of getting a pointer back,
| you'd get a handle. While the handle was unlocked, the operating
| system was free to move the memory around. If you wanted to
| access the memory, you'd lock the handle, giving a pointer with
| the actual address, then unlock the handle when done.
|
| To the extent that you kept handles unlocked, the system could
| fight fragmentation.
|
| It was tedious, and your code had lots of lock/unlock clutter in
| it. It also led to bugs where you'd accidentally use a pointer
| value after unlocking its handle, which makes the pointer value
| invalid because your data might have been moved somewhere else.
| Worse, usually your data was not moved, so these bugs were hard
| to detect, much like use-after-free bugs.
|
| But, when memory is very limited and you also don't have an MMU,
| life isn't easy.
| Narishma wrote:
| Early Windows version worked like that too.
| Asooka wrote:
| Rust's borrow checker should make it impossible to reference an
| unlocked pointer in safe code. I suspect it should be possible
| to have a compacting heap as a library.
___________________________________________________________________
(page generated 2023-04-06 23:01 UTC)