Support realloc without copying?

[hbgl]

When using realloc it will commonly fallback to alloc, copy, and free if growing the initial allocation is impossible (see mimalloc's realloc for an easy to read example). I think it would be useful to have a specialization of realloc that would leave the copying to the user code.

A good use case would be allocating a buffer for a Vec<Option<T>> where None represents a tombstone i.e. a slot that was previously occupied but is now empty (think of PHP array or Python dict). When growing the buffer it would sometimes make sense to only copy Ts and skip the tombstones. I would expect the usage of the new function to look something like this:

let allocation = realloc_manually_copy(ptr, layout, new_size)?;
if allocation.needs_copy() {
    let old_slice = slice::from_raw_parts(allocation.old_ptr, len);
    let vec = Vec::from_raw_parts(allocation.new_ptr, 0, new_size);
    vec.extend(slice.filter(|x| x.is_some());
    // ...
}
drop(allocation); // Will free the old memory

I do not know of an allocator interface which supports this special realloc operation but I thought it might be useful. The current implementations of the PHP array and Python dict do not bother with realloc and just use malloc instead.

[Lokathor]

I think the cost of all the checks and branching is going to overwhelm any savings from not copying a few bytes of None

[Amanieu]

If you really want this then you can do it with grow_in_place and manually copying to a new allocation if the call fails.

[hbgl]

@Lokathor
I agree that the branching will increase the cost of growing the buffer but it would be faster than copying unconditionally and then doing the branching later. It's a trade-off for sure.

@Amanieu
Does grow_in_place imply pointer stability? That would be a stronger guarantee than realloc has.

[Amanieu]

Yes, grow_in_place guarantees pointer stability if it succeeds.

[hbgl]

@Amanieu That means though that realloc_manually_copy allows the allocator to be more efficient than grow_in_place plus fallback because it is less constrained. I see that realloc_manually_copy might be troublesome to implement because the allocator would be in a weird state being interrupted by user code in the middle of a regular realloc.

It would be interesting to know if someone already pursued this idea and what the outcome was. I have not found much online and I have no perf data to justify an extra function. I guess this is more a question about whether it is worth checking out at all.

[Amanieu]

If the allocator has to move your data, it is already making a separate allocation and freeing the old one. This is exactly the same as what you should do if grow_in_place fails: just alloc, copy your data, then free the old allocation.

[the8472]

Is grow_in_place a hypothetical method or was it removed at some point?

[Amanieu]

It was removed because in practice no allocators supported it.

[the8472]

mimalloc has mi_expand which guarantees to either perform in-place expansion or returns null.

So it would be good to have a way to add future support, e.g. via flags as #58 proposed.

And it seems obvious to me that anything that uses mmap under the hood could support this at least in principle via MREMAP_FIXED on platforms that have that. So even if our most commonly used allocators today don't have it the API design should provide some forward-compatibility here.