What Is in a Rust Allocator?(blog.sulami.xyz) |
What Is in a Rust Allocator?(blog.sulami.xyz) |
Suppose I'm an allocator which only has power-of-2 sized spaces to hand out, and you're a growable array type and you want enough space for 20 of your 52 byte entries. So that's 20x52 = 1040 bytes, but my smallest suitable space is 2048 bytes. I can give you that space, but it seems like it'd be nice for me to say oh, here's 2048 bytes, and now the growable array type knows its new total capacity is not 20 but 39.
fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError>;
Yes I'm aware that I can ask how long a slice is.
It's even worse for types like HashMaps where reallocs can be much more expensive than just a big memcpy.
With this distinct hint, reserve(N) preserves the amortized growth. Say we have total capacity 30, currently there are 20 items in the Vec, and Vec::reserve(20). So the advise is that the Vec may soon have up to 40 items, we should grow it. But since we weren't promised that's as big as it'll get, we grow it by doubling - to total capacity 60 items. If this is a pattern, repeatedly reserving space for 20 items and then adding them, this grows 30 -> 60 -> 120 -> 240 and so on, amortized growth as advertised - and growth is avoided when we're only "reserving" capacity we already have anyway.
Several languages, including C++ only provide the Vec::reserve_exact(X) feature, but name it reserve. Any such "reservation" is also implicitly promising there won't be further growth, so for our example it grows 30 -> 40 -> 60 -> 80 -> 100 -> 120 -> 140 ... our amortized growth strategy was destroyed and our performance will be much worse than O(1). In such a language students get taught not to use the reservation API to signal what they know and so they lose out on performance optimisations better than O(1)
I first ran into this feature because I was wondering about the over-allocation problem, and I realised this is solving a different but also important problem.
That also gives the allocator the flexibility to use part of a block that it gave to you for someone else if that makes sense.
E.g. you request 200 bytes, a block of 256 bytes is actually allocated. Now you request with some other code 30 bytes. If the allocator had told you at allocation time "here are your 200 bytes, but just so you know, there's another 56" it could not hand the unused part of the 256 bytes to the next allocation.
If we don't know, we can't use anything except what we asked for. For some allocations that's not important, but e.g. Vec can just upgrade the capacity to match, buffering mechanisms often may just as well use the entire available buffer not just the part they specifically asked for.
> E.g. you request 200 bytes, a block of 256 bytes is actually allocated. Now you request with some other code 30 bytes. If the allocator had told you at allocation time "here are your 200 bytes, but just so you know, there's another 56" it could not hand the unused part of the 256 bytes to the next allocation.
You're assuming that the allocator is able to remember that these extra 56 bytes are available. That may or may not be practical, it's a shame if we have to otherwise throw the 56 bytes away.