Vec's reallocation strategy needs settling

[Gankra]

Background

Currently, Vec's documentation frequently contains the caveat that "more space may be reserved than requested". This is primarily in response to the fact that jemalloc (or any other allocator) can actually reserve more space than you requested because it relies on fixed size-classes to more effeciently dole out memory. (see the table here)

Jemalloc itself exposes a malloc_usable_size function which can be used to determine how much capacity was actually allocated for a pointer, as well as nallocx which can be used to determine how much capacity will be allocated for a given size and alignment. Vec can in principle query one of these methods and update its capacity field with the result.

The question at hand is: is this ever worth it to check usable_capacity, and is it ever undesirable?

This issue was kicked off by Firefox devs who have experience doing exactly this optimization, and claim it being profitable. Facebook has also claimed excellent dividends in making its allocation strategy more jemalloc friendly, but to my knowledge do not actually query usable_capacity.

Currently our alloction strategy is almost completely naive. One can see the source here, which boils down to:

let new_cap = if self.cap == 0 { 
    4
} else { 
    2 * self.cap 
}

To the best of my knowledge, this is all the capacity logic for FBVector, which boils down to:

let new cap = if self.cap == 0 {
    max(64 / size_of_elem, 1)   // empty
} else if self.cap < 4096 / size_of_elem) {
    self.cap * 2                // small
} else if self.cap > 4096 * 32 / size_of_elem) {
    self.cap * 2                // huge
} else {
    (self.cap * 3 + 1) / 2      // moderate
}

The only major deviation from Rust today being a 1.5 growth factor for "moderate" sized allocations. Note that there is a path in their small_vector type that queries malloc_usable_size.

Unfortunately I've been unable to find good information on what Firefox does here. The best I could find is this discussion which demonstrates big wins -- 6.5% less calls to malloc and 11% less memory usage. However the effort seems to peter out when it is asserted that this is obsoleted by Gecko just using power-of-two capacities. mxr and dxr seem to suggest it's only used for statistics.

Hopefully Firefox and Facebook devs can chime in on any experiences.

Going Forward

I have several outstanding concerns before we push further on this matter.

Rust is not C++, so I am partially suspicious of any benchmarks that demonstrate value in C++. In particular, the proliferation of size_hint and extend could completely blast away any need to be clever with capacities for most programs. I would also expect a large Rust application to frob the allocator less in general just because we default to move semantics, and don't have implicit assignment/copy constructors. Also, Rust programs are much more "reckless" with just passing around pointers into buffers because the borrow checker will always catch misuse. Slices in particular make this incredibly ergonomic. We need Rust-specific benchmarks. I'm sure the Hyper, Servo, Glium, Serde, and Rust devs all have some interesting workloads to look at.

Rust's Vec is basically the community's malloc/calloc, because actual malloc is unstable and unsafe. We explicitly support extracting the Vec's pointer and taking control of the allocation. In that regard I believe it is desirable for it to be maximally well-behaved and performant for "good" cases (knowing exactly the capacity you want, having no use for extra capacity). There's a certain value in requesting a certain capacity, and getting the capacity. Both nallocx and malloc_usable_size are virtual function calls with non-trivial logic, and may have unacceptable overhead for responsible users of Vec.

Note that anything we do must enable Vec and Box<[T]> to reliably roundtrip through each other without reallocating in certain cases. If I invoke shrink_to_fit or with_capacity, it ought to not reallocate when I try to convert to a Box<[T]>. As far as I can tell, this should be possible to uphold even when using malloc_usable_size because jemalloc is "fuzzy" and only requires that the given size is somewhere between the requested one and the usable one.

Anything we do must also work with allocators that aren't jemalloc. This may be as simple as setting usable_size = requested_size for every allocator that isn't jemalloc.

CC @pnkfelix @erickt @reem @seanmonstar @tomaka @SimonSapin @larsberg @pcwalton @Swatinem @nnethercote

CC #29848 #29847 #27627

CC @rust-lang/libs

EDIT(workingjubilee, 2023-05-06): Originally one of the links touched on the master branch of folly instead of a permalink to a specific commit. Linkrot claimed the one to jemalloc's docs. These have been updated with a permalink and a Wayback Machine link, respectively.

[aturon]

cc @briansmith

[jdm]

cc me

[briansmith]

The question at hand is: is this ever worth it to check usable_capacity, and is it ever undesirable?

I guess you mean s/usable_capacity/malloc_usable_size/.

If I invoke shrink_to_fit or with_capacity, it ought to not reallocate when I try to convert to a Box<[T]>

I think that's a "nice to have" but not very important. Is real-world code doing shrink_to_fit and then into_boxed_slice? I searched the uses of into_boxed_slice and into_boxed_str in the Rust and Servo repos and it looks like they are rarely used in those repos. I think using those functions is a code smell, actually.

Rust's Vec is basically the community's malloc/calloc,

I disagree with this. Vec is the data structure you use by default, and it should have good performance by default. For example, its the thing I collect iterators into by default. Some people might be using Vec to simulate malloc, but I think that's much more rare. I use with_capacity(N) because I know I'm going to be pushing at least N elements into the vector and I don't want to be wasteful; I'm noever using it because I want to create a boxed slice with N elements in it. It makes sense to have a separate interface for people that want a "safe" malloc; perhaps that separate interface would just be additional stuff added to Vec. But I think the behavior of the common (existing) interface should be geared towards more naive uses.

[SimonSapin]

Rust's Vec is basically the community's malloc/calloc

That’s a hack to work around the lack of proper stable API, not how it should be.

[bluss]

Regardless of what we want to do now, we need to remove the "guarantee" in the nightly docs about capacity, which locks us in. We have no reason to promise all kinds of things about Vec internals.

[Ms2ger]

CC @glandium

[Swatinem]

Maybe instead of actually using usable_size (which has a non-zero cost as you mentioned), the better thing to do would be to just round up to the nearest power-of-two (in bytes) for small allocations and to the nearest MiB for large ones, like mozillas nsTArray does.

I have also looked a bit at the code, and at least VecDeque rounds up to the nearest pot (in elements), probably because it does a + 1 which is like the most wasteful thing to do related to this issue.
The docs for VecDeque btw say it reserves space for "at least" that many elements, not exactly.

Btw, just grepping through the rustc code for with_capacity reveals a few cases where it does a + 1 as well.

[Gankra]

VecDeque needs to maintain its power of two capacity in order to support efficient modular arithmetic (just a bit mask). HashMap does the same.

[huonw]

FWIW, one can use constant-division tricks to do (relatively) efficient modular arithmetic, if the bit pattern is fixed (e.g. if the capacities are guaranteed to be either 1 << n or 3 << n). Of course, branching and then doing the multiplications/shifts for the latter case definitely isn't free.

(I believe x % (3 << n) can be computed via something like:

x - ((x * C) >> (n + 1)) * (3 << n)

for some constant C.)

[Gankra]

Oh and they both keep some slack capacity for similar perf reasons. Hashmap will only use 91% of its cap because it keeps access times down. VecDeque keeps an empty slot so that the "two indices" representation can differentiate between the empty and full state without us maintaining some flag that constantly needs to be checked/maintained.

I would also like to slightly dissent on the point of Vec being a good malloc. It's an excellent memory-safe and exception-safe interface for acquiring, initializing, deinitializing, and releasing an allocation. It's a bad choice for lower-level uses (all the other collections), of course.

[arthurprs]

It's important to note that jemalloc isn't the only allocation that exhibits this behavior (having some slack), actually many do.

I assumed we had the trio: reserve, reserve_exact and shrink_to_fit; exactly in order to allow reserve to be highly optimized and do smart reallocation, like in this case.

[larsberg]

I think you've got the wrong larsberg. I believe you want @larsbergstrom