While testing my allocator, I was quite surprised that this failed:
#[test]
fn test_vec_capacity() {
// Only ever allocates a single block of 1024 bytes
let alloc = Stalloc::<1, 1024>::new();
let v: Vec<u8, _> = Vec::with_capacity_in(1, &alloc);
assert!(v.capacity() == 1024);
}
I went digging through the standard library to figure out how Vec allocates, and I found this:
// Allocators currently return a `NonNull<[u8]>` whose length
// matches the size requested. If that ever changes, the capacity
// here should change to `ptr.len() / mem::size_of::<T>()`.
Ok(Self { ptr: Unique::from(ptr.cast()), cap: unsafe { Cap(capacity) }, alloc })
In this code, capacity is the capacity chosen by the user, not the capacity actually returned by the allocator. This seems quite inefficient, and actually causes an OOM here:
// Only ever allocates a single block of 1024 bytes
let alloc = Stalloc::<1, 1024>::new();
let mut v: Vec<u8, _> = Vec::with_capacity_in(9, &alloc);
for _ in 0..1024 {
v.push(7);
}
Because the Vec doubles its capacity each time, it eventually tries to allocate 1152 bytes, exceeding the capacity of the allocator. This wouldn't have happened if the Vec had realized that its capacity was exactly 1024 bytes all along. But what I'm really curious about is the comment, which references the behaviour of certain unnamed "allocators" but suggests that their behaviour might change at some point. To my knowledge, Rust doesn't have any official allocators and simply uses whatever allocator the system or the user provides.
This comment is also hard to square with the documentation for Allocator::allocate, which specifically states: "The returned block may have a larger size than specified by layout.size()". That seems to suggest that over-allocation is a supported use case.
The comment seems to also be contradicted by the documentation for Vec::reserve_exact: "Note that the allocator may give the collection more space than it requests. Therefore, capacity can not be relied upon to be precisely minimal." The documentation neglects to mention that extra capacity offered by the allocator is entirely ignored.
I would recommend that Vec be changed to use the capacity returned by the allocator rather than the user-provided capacity. This would apply to both the growing and shrinking methods. I don't think this would have any significant performance impact for typical applications, but this would enable improved performance and memory efficiency when using a custom allocator that supports over-allocation.