8 ms·

Spotting and avoiding heap fragmentation in Rust applications

138 points by tasn 4y ago

MuffinFlavored 4y ago
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 4y ago
  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-out-jemalloc.md https://github.com/rust-lang/rfcs/blob/master/text/1183-swap...
  - MuffinFlavored 4y ago
    A sharp increase that never comes back down over time seems more "wrong" than right to me, no?
    - Hooray_Darakian 4y ago
      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 4y ago
      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 4y ago
        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 4y ago
  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 4y ago
  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 4y ago
  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 4y ago
    > * 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 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.
    - jeffbee 4y ago
      I think we can safely say that jemalloc has much better marketing than tcmalloc. If you search on github there is only 1 real project with a bazel WORKSPACE that mentions tcmalloc ... the rest are either forks of tcmalloc itself or trivial toy programs that I personally put on github to share with someone. There are zillions of users of jemalloc and everyone has heard of it.
- glandium 4y ago
  Reading the article reminded me of https://sourceware.org/bugzilla/show_bug.cgi?id=23416 https://sourceware.org/bugzilla/show_bug.cgi?id=23416 and I wouldn't be surprised if it's the same underlying issue.
wongarsu 4y ago
> 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 4y ago
  Good point, thanks! Will update the article to clarify the difference.
- cryptonector 4y ago
  The failure mode for filesystems is to get slow. Same as for heap allocation.
  - dgacmu 4y ago
    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 4y ago
      Filesystem may also run out of inodes, even though there is still plenty of space.
zackangelo 4y ago
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/ https://docs.rs/bumpalo/latest/bumpalo/
nikeee 4y ago
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 4y ago
  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 4y ago
    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 4y ago
  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.
  - mr_00ff00 4y ago
    I’m curious when not allocating things dynamically, does that just get around all memory safety (other than temporal with array bounds checking). Essentially any language that does array bounds checking would be as safe as rust? Or am I missing anything? C does not technically do that, so rust is still safer. But zig would be the same in the embedded space as rust? Or is there anything I am missing?
    - pdimitar 4y ago
      Rust's compiler also makes sure you never modify a place in memory from more than one place.
jamboca 4y ago
"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?
- Tuna-Fish 4y ago
  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 4y ago
    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.)
- tasn 4y ago
  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.
lordnacho 4y ago
Any thoughts about snmalloc as an alternative? Can't quite recall the differences but seemed to look good on benchmarks.
- mcronce 4y ago
  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.
munificent 4y ago
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 4y ago
  >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 https://crates.io/crates/slab
  - mr_00ff00 4y ago
    I assume there might be performance issues using a vector that’s gonna reallocate when capacity is full? That being said vectors seem like a gift in rust. I feel like it’s the easiest way to get around some ownership rules when you need to work with many pointers. You can just use indices.
    - cozzyd 4y ago
      You can just allocate a large buffer and serialize/deserialize everything at various indices in that buffer
- sgeisenh 4y ago
adrianmonk 4y ago
> 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_management 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 4y ago
  Early Windows version worked like that too.
- Asooka 4y ago
  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.
  - vlovich123 4y ago
    Yeah. I wonder if something like this might be interesting for a pure Rust program / what computing would look like if Rust were available back then (we now have a path dependency on modern memory allocation patterns that are unlikely to change where we rely on the allocator to do really heavy lifting). I wonder how expensive the extra handle indirection would be (I imagine modern CPUs should be an able to speculate through it without much difficulty).
tayo42 4y ago
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 4y ago
  > 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.
  - tayo42 4y ago
    Oh maybe I missed but I didn't think that info was there. Would have been interesting to see thr extent of fragmentation or what the cause was. 5 9s of uptime means 800ms of down time a day. Is this not in a cloud, a load balancer health check can't react that fast. Vms will get randomly killed if something is wrong.
mindyhausler 4y ago
[flagged]

138 points by tasn 4y ago

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 4y ago
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-out-jemalloc.md https://github.com/rust-lang/rfcs/blob/master/text/1183-swap...
- MuffinFlavored 4y ago
  A sharp increase that never comes back down over time seems more "wrong" than right to me, no?
  - Hooray_Darakian 4y ago
    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 4y ago
    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 4y ago
      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 4y ago
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 4y ago
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 4y ago
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 4y ago
  > * 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 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.
  - jeffbee 4y ago
    I think we can safely say that jemalloc has much better marketing than tcmalloc. If you search on github there is only 1 real project with a bazel WORKSPACE that mentions tcmalloc ... the rest are either forks of tcmalloc itself or trivial toy programs that I personally put on github to share with someone. There are zillions of users of jemalloc and everyone has heard of it.
glandium 4y ago
Reading the article reminded me of https://sourceware.org/bugzilla/show_bug.cgi?id=23416 https://sourceware.org/bugzilla/show_bug.cgi?id=23416 and I wouldn't be surprised if it's the same underlying issue.

wongarsu 4y ago

> 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 4y ago
Good point, thanks! Will update the article to clarify the difference.
cryptonector 4y ago
The failure mode for filesystems is to get slow. Same as for heap allocation.
- dgacmu 4y ago
  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 4y ago
    Filesystem may also run out of inodes, even though there is still plenty of space.

zackangelo 4y ago

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/ https://docs.rs/bumpalo/latest/bumpalo/

nikeee 4y ago

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 4y ago
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 4y ago
  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 4y ago
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.
- mr_00ff00 4y ago
  I’m curious when not allocating things dynamically, does that just get around all memory safety (other than temporal with array bounds checking). Essentially any language that does array bounds checking would be as safe as rust? Or am I missing anything? C does not technically do that, so rust is still safer. But zig would be the same in the embedded space as rust? Or is there anything I am missing?
  - pdimitar 4y ago
    Rust's compiler also makes sure you never modify a place in memory from more than one place.

jamboca 4y ago

"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?

Tuna-Fish 4y ago
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 4y ago
  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.)
tasn 4y ago
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.

lordnacho 4y ago

Any thoughts about snmalloc as an alternative? Can't quite recall the differences but seemed to look good on benchmarks.

mcronce 4y ago
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.

munificent 4y ago

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 4y ago
>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 https://crates.io/crates/slab
- mr_00ff00 4y ago
  I assume there might be performance issues using a vector that’s gonna reallocate when capacity is full? That being said vectors seem like a gift in rust. I feel like it’s the easiest way to get around some ownership rules when you need to work with many pointers. You can just use indices.
  - cozzyd 4y ago
    You can just allocate a large buffer and serialize/deserialize everything at various indices in that buffer
sgeisenh 4y ago

adrianmonk 4y ago

> 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_management 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 4y ago
Early Windows version worked like that too.
Asooka 4y ago
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.
- vlovich123 4y ago
  Yeah. I wonder if something like this might be interesting for a pure Rust program / what computing would look like if Rust were available back then (we now have a path dependency on modern memory allocation patterns that are unlikely to change where we rely on the allocator to do really heavy lifting). I wonder how expensive the extra handle indirection would be (I imagine modern CPUs should be an able to speculate through it without much difficulty).

tayo42 4y ago

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 4y ago
> 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.
- tayo42 4y ago
  Oh maybe I missed but I didn't think that info was there. Would have been interesting to see thr extent of fragmentation or what the cause was. 5 9s of uptime means 800ms of down time a day. Is this not in a cloud, a load balancer health check can't react that fast. Vms will get randomly killed if something is wrong.

mindyhausler 4y ago

[flagged]