What's the desired effect of `shrink`?

[TimDiekmann]

There are a few pre and postconditions to shrink:

• it has to be called with a new_size < layout.size(),
• the passed pointer has to be returned by a previous call to the same allocator,
• every pointer returned from shrink can be passed to any other allocator method,
• ... other conditions, but this issue is not affected by them.

Recently I tried to optimize the Region allocator (basically a bump allocator using &mut [u8] as backend). Implementing alloc, dealloc and grow is straight forward but how is shrink supposed to be implemented? There are 3 possible cases, for which all pre-/post conditions still hold. I leave out ReallocPlacement and implementation details like bumping-up and bumping-down, similar cases applies to all of them.

1. new_size == layout.size(): just return the same pointer, just like the default implementation. This is the trivial case.
2. ptr is the latest allocated block: It is possible to reduce the used memory by moving the current-ptr to match the requested size (maybe introduces ptr::copy). It's also possible to simply return the same pointer as passed to shrink. Both cases are valid; the former is less memory hungry, the latter is faster.
3. else: As always, returning the same pointer is also valid, but how expected is this behavior?

What's the prefered way to implement shrink (performance vs memory)? Do we have to specify the behavior of shrink? Should shrink be overhauled in it's API in any way?

Notes:

• This also applies to realloc for new_size < layout.size(),
• we cannot make shrink a best-effort-method, as other methods like dealloc has to deal with the returned pointer.

[Amanieu]

The main users of shrink are Vec::shrink_to_fit and Vec::into_boxed_slice so let's consider when you would use those. Generally speaking it's only used if:

• You are no longer going to be adding elements to the vector.
• You want to save memory because you're going to be keeping this allocation around for a while.

As such I think it's fine for shrink to favor saving memory over performance.

[sollyucko]

FWIW, for the case of a bump allocator, wouldn't a realloc-ing shrink merely use more space, since the old space can't be used?

[TimDiekmann]

Not necessarily, if you shrink the latest allocated block, it's possible to actually shrink the used memory.

@Amanieu thank you for reminding me about this!