4 ms·

Allocator underneath is keeping track of freed memory, so next allocation has high chance of being squeezed into memory region that has been used before. It's o

Allocator underneath is keeping track of freed memory, so next allocation has high chance of being squeezed into memory region that has been used before. It's obviously not as good as say GC that relocates after sweep, but at least it doesn't leave gaping holes.

haimez 7y ago
Indeed, but it also doesn’t maintain locality of access nearly as well for young objects (the most commonly manipulated ones) and even older ones that survive.
- jstrong 7y ago
  one related point: the article mentions utilizing rust's BTreeMap, which manages its heap allocations with cache efficiency in mind: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht.... The guts of BTreeMap's memory management code is here: https://github.com/rust-lang/rust/blob/master/src/liballoc/collections/btree/node.rs https://github.com/rust-lang/rust/blob/master/src/liballoc/c.... (warning: it is some of the most gnarly rust code I've ever come across, very dense, complex, and heavy on raw pointers. this is not a criticism at all, just in terms of readability). Anecdotally I've had very good results using BTreeMap in my own projects. In terms of how the "global" allocator impacts performance, I'd expect it to play a bigger role in terms of Strings (I mean, it's a chat program), and possibly in terms of how the async code "desugars" in storing futures and callbacks on the heap (just guessing, I'm not an expert on the rust async internals).
  - senderista 7y ago
    I was a bit surprised that BTreeMap turned out to be more memory-efficient than HashMap; can anyone shed some light on this? One of these days I’ll get around to turning my Rust set implementation[0] into a full-blown map (it’s already <50% the size of BTreeSet for ints)... [0] https://github.com/senderista/rotated-array-set https://github.com/senderista/rotated-array-set
- tsimionescu 7y ago
  In the current context, fragmentation refers more to the problem of consuming extra memory through fragmentation, which malloc implementations like the one Go (or Rust, or glibc) uses can often mitigate.

haimez 7y ago

Indeed, but it also doesn’t maintain locality of access nearly as well for young objects (the most commonly manipulated ones) and even older ones that survive.

jstrong 7y ago
one related point: the article mentions utilizing rust's BTreeMap, which manages its heap allocations with cache efficiency in mind: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht.... The guts of BTreeMap's memory management code is here: https://github.com/rust-lang/rust/blob/master/src/liballoc/collections/btree/node.rs https://github.com/rust-lang/rust/blob/master/src/liballoc/c.... (warning: it is some of the most gnarly rust code I've ever come across, very dense, complex, and heavy on raw pointers. this is not a criticism at all, just in terms of readability). Anecdotally I've had very good results using BTreeMap in my own projects. In terms of how the "global" allocator impacts performance, I'd expect it to play a bigger role in terms of Strings (I mean, it's a chat program), and possibly in terms of how the async code "desugars" in storing futures and callbacks on the heap (just guessing, I'm not an expert on the rust async internals).
- senderista 7y ago
  I was a bit surprised that BTreeMap turned out to be more memory-efficient than HashMap; can anyone shed some light on this? One of these days I’ll get around to turning my Rust set implementation[0] into a full-blown map (it’s already <50% the size of BTreeSet for ints)... [0] https://github.com/senderista/rotated-array-set https://github.com/senderista/rotated-array-set
tsimionescu 7y ago
In the current context, fragmentation refers more to the problem of consuming extra memory through fragmentation, which malloc implementations like the one Go (or Rust, or glibc) uses can often mitigate.