[wongarsu]

Like most implementations, if you add items to a rust `Vec` one item at a time it doubles in size each time it hits its capacity (to make sure insert is amortized to O(1) even though each realloc potentially requires an O(n) memcpy). With the described allocator that would never lead to a cheap realloc.

It's even worse for types like HashMaps where reallocs can be much more expensive than just a big memcpy.

[tialaramex]

Also, Rust's Vec has the correct size hinting API, so we can say Vec::reserve(N) meaning that we expect to put as many as N more things into this Vec soon, or Vec::reserve_exact(X) meaning that we expect to put no more than X more things into this Vec, ever

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.

[filmor]

I have no idea what you are getting at. I just stated that you alloc/realloc what you require for your type. If you want to over-allocate, do it. But I don't see the need to know the size of the memory block that fulfilled your request.

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.

[tialaramex]

> But I don't see the need to know the size of the memory block that fulfilled your request.

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.