std.mem.Allocator.reallocFn guarantees seem too strong

[mdsteele]

The doc comment for std.mem.Allocator.reallocFn says that "if new_byte_count <= old_mem.len, this function must return successfully". This feels like too strong a guarantee to me; for allocator implementations that store blocks of different sizes in different ways/places, it might have to first allocate a new smaller block and transfer data over before freeing the larger block, and that allocation could fail. (Note for comparison that C's realloc() does not appear to make this promise.)

[andrewrk]

For std.heap.c_allocator we wrap realloc like this:

fn cRealloc(self: *Allocator, old_mem: []u8, new_size: usize, alignment: u29) ![]u8 {
    const old_ptr = @ptrCast(*c_void, old_mem.ptr);
    if (c.realloc(old_ptr, new_size)) |buf| {
        return @ptrCast([*]u8, buf)[0..new_size];
    } else if (new_size <= old_mem.len) {
        return old_mem[0..new_size];
    } else {
        return error.OutOfMemory;
    }
}

I think a similar strategy should work for any general purpose allocator, no?

This guarantee is important for the semantics of error handling and resource ownership - it's a guarantee that if you're only telling the allocator, "hey, if you can use less space, do it" then that cannot fail.

It is not required that the call actually results in less memory usage. So I think at least you can just return the same memory back to the caller, in the case that the new smaller block allocation fails.

[PavelVozenilek]

When I implemented my own allocator, I avoided this function. It provides empty promise of better performance. In practice, with a program doing lot of allocations, it almost never gets chance to expand allocated block. (I hijacked the function, and it had < 0.1% success.) If one uses fast arena (aka region) allocator, it could never expand any block.

Presence of this function is mistake of C design. Makes learning things hard, for no advantage.

[andrewrk]

In Zig realloc is currently semantically necessary because it is the API consumer's responsibility to keep track of the number of bytes allocated, and provide that number back to the allocator. (Probably the allocator will also keep track in debug modes, to find bugs.) So if the API consumer wishes to shrink the number of bytes in an allocation, they must use realloc to update the allocator on the agreed upon number of bytes in the allocation.

[PavelVozenilek]

@andrewrk: the need to shrink a block of bytes is rare, and when it happens, like contracting memory for a dynamic array, it doesn't work well with internals of block based allocators like dlmalloc - they take the smaller memory from another bucket.

I didn't measure this, but would expect it even more insignificant than expanding.

[mdsteele]

It is not required that the call actually results in less memory usage. So I think at least you can just return the same memory back to the caller, in the case that the new smaller block allocation fails.

Sure. The problem is that then the allocator's freeFn can't take advantage of old_mem.len e.g. to know which bucket the allocation came from. That happens to work fine for c_allocator because C's free() doesn't need to know the size.

(I mean, maybe that's just the way things are and allocator implementations have to deal with it; I'm willing to accept that answer. (-: But the fact that Zig's type system makes it possible for allocators to know the size of the memory being freed seems like a significant advantage over C's allocation API, and it would be a shame if allocator implementations couldn't make use of that in practice.)

So if the API consumer wishes to shrink the number of bytes in an allocation, they must use realloc to update the allocator on the agreed upon number of bytes in the allocation.

Agreed, but I don't see why that shrinking operation must be guaranteed to succeed. Yes, the API consumer itself isn't asking for more memory, but it is asking the allocator to change its internal mental model of the allocated block. Updating those internal data structures might require performing an allocation (e.g. from a child allocator), and that allocation might fail.

[andrewrk]

then the allocator's freeFn can't take advantage of old_mem.len e.g. to know which bucket the allocation came from.

hmm that's a good point. That is the main reason that allocators get access to old_mem.len.

Let me have a look at the API uses of realloc and report back and then let's come up with a plan.

[BarabasGitHub]

While we're on this issue let me state that I also don't really like that reallocFn will automagically copy my data if it allocates a new block of memory. I'd prefer to handle that myself if it can't extend the existing block. There's many reasons. I might want to move the contents anyway (ie insert) or I might not care about what's in it (uninitialized or old/unused objects). Or maybe I only care about the first few items and I know that I will need room for way more than I have so copying everything, even the uninitialized part is a waste. I know this is not what realloc in C does, but that doesn't mean they made the right decision. ;)

[andrewrk]

I think these are same good points about the API of realloc being problematic.

Here are some of the ideas that are on the table:

• Remove the realloc function from the Allocator interface.
• Remove the guarantee that realloc must succeed if new byte count <= old byte count.
• Modify the API of realloc. Change the name and prototype to fn resize(old_mem: []u8, old_alignment: u29, new_size: usize) (error{OutOfMemory}!void). If it succeeded then old_mem.ptr[0..new_size] is now available, with the previous bytes unmodified, and new bytes undefined. This still leaves the question of whether resize must succeed if new_size <= old_mem.len. Many allocators would implement this function with a simple return error.OutOfMemory.

Here's an example use case we should consider when thinking about these things:

pub fn selfExePath(allocator: *mem.Allocator) ![]u8 {
    var out_path = try Buffer.initSize(allocator, 0xff);
    errdefer out_path.deinit();
    while (true) {
        const dword_len = try math.cast(windows.DWORD, out_path.len());
        const copied_amt = windows.GetModuleFileNameA(null, out_path.ptr(), dword_len);
        if (copied_amt <= 0) {
            const err = windows.GetLastError();
            return switch (err) {
                else => unexpectedErrorWindows(err),
            };
        }
        if (copied_amt < out_path.len()) {
            out_path.shrink(copied_amt);
            return out_path.toOwnedSlice();
        }
        const new_len = (out_path.len() << 1) | 0b1;
        try out_path.resize(new_len);
    }
}

Here, toOwnedSlice is implemented like this:

    /// The caller owns the returned memory. The Buffer becomes null and
    /// is safe to `deinit`.
    pub fn toOwnedSlice(self: *Buffer) []u8 {
        const allocator = self.list.allocator;
        const result = allocator.shrink(u8, self.list.items, self.len());
        self.* = initNull(allocator);
        return result;
    }

Without realloc, selfExePath could potentially have the result, and some extra bytes, and then still have to return an error because it could not allocate a new slice with the smaller length. What a shame. Same problem if the realloc guarantee is gone.

[mdsteele]

Gotcha. Now that I am seeing the various existing APIs that rely on realloc-to-smaller always succeeding, I can see the reasoning behind it. (Also, for what it's worth, I think I found a way to get the allocator I'm working on to meet the guarantee.)

One thing I'm realizing is that bucket-based (e.g. Hoard-style) allocators, like the one I'm working on, that want to support arbitrary alignments will probably have to deal with this problem anyway, since if the user asks for an 8-byte block with a 256-byte alignment, the allocator may have no recourse but to allocate a 256-byte block, depending on the design. (Unless we want to add a precondition that alignment <= size?)

So if we want to keep the guarantee, I'll throw another (possibly bad) idea out there, which is to split reallocFn into growFn (which returns ![]u8) and shrinkFn (which returns []u8). We would still have std.mem.Allocator.realloc, which would choose between them as appropriate, but this would let us get rid of the catch unreachable in std.mem.Allocator.alignedShrink, and it would force Allocator authors to meet the guarantee.

[BarabasGitHub]

One thing I'm realizing is that bucket-based (e.g. Hoard-style) allocators, like the one I'm working on, that want to support arbitrary alignments will probably have to deal with this problem anyway, since if the user asks for an 8-byte block with a 256-byte alignment, the allocator may have no recourse but to allocate a 256-byte block, depending on the design. (Unless we want to add a precondition that alignment <= size?)

In C++ (and I guess C) if you explicitly align a type beyond the size of it, you also increase the size of the type up to the alignment. Just so you know.

[to-miz]

Some of the issues here seem to be because realloc conceptually does 2 different things. One is resizing an allocation and the other is allocating optimistically.
Many allocators for this reason have two different realloc flavors. There is plain old realloc (same as the on the C runtime) but then there is realloc_in_place (dlmalloc and windows heaps have this).
It is a way to say "can you resize this allocation in place without copying/doing too much work?". This would be the function to call when trying to give back memory to the allocator without incurring too much overhead.
Another use case is when there is a need to get more memory, but the memcpy behavior of realloc isn't needed. In that case the user could call realloc_in_place, see if it succeeds, if not call free on old_mem and then allocate a new block of memory. Then the user would have resized a region without copying. This pattern is something that isn't available to even C with its CRT. I think some of the problems could be solved by introducing a realloc_in_place to the allocator interface.

[andrewrk]

After doing some work on my own general purpose allocator, I've made a decision on this, and it solves #2009 as well. In summary:

• Add old_alignment: u29 parameter to freeFn function in the Allocator interface. (Users of the Allocator interface have the same API; the alignment is extracted from the type)
• Introduce a new function shrinkFn for the Allocator interface which cannot fail. It does, however, allow the allocator to move the memory. The application gives the allocator the choice. So the strong guarantee pointed out in the original issue remains. In practice, allocators will likely have to treat the old_mem.len and old_alignment parameters to free as hints.
• Change reallocFn to be always allowed to fail. Calls to reallocFn are preferred over shrinkFn. Data structures such as ArrayList will use this to negotiate their capacity with allocators.

/// Prefer calling realloc to shrink if you can tolerate failure.
/// This function is when the client requires the shrink to
/// succeed in order to be correct. For example, if it is only
/// keeping track of a slice to pass to free.
/// Shrink always succeeds, and new_n must be <= old_mem.len;
/// Returned slice has same alignment as old_mem.
fn shrink(comptime T: type, old_mem: var, new_n: usize) []align(old_mem.alignment)T;
/// This function allows the client to track a smaller alignment.
/// new_alignment must be <= old_mem.alignment
fn alignedShrink(comptime T: type, old_mem: var,
    new_n: usize, comptime new_alignment: u29) []align(new_alignment)T;
fn shrinkFn(old_mem: []u8, old_alignment: u29) []u8;


/// This function is used when the client is tracking a "capacity",
/// and therefore can handle failure, even when new_n <= old_mem.len.
/// Realloc is allowed to fail, and in fact for best performance
/// should fail when the realloc is not cheap.
/// For example ArrayList calls realloc for both growing and shrinking.
/// When a shrink returns OutOfMemory, the ArrayList will keep its capacity
/// and merely shrink its length.
/// In this way data structures and allocators can "negotiate" when
/// shrinking. The data structure gives the allocator the opportunity to
/// shrink if it is efficient; otherwise the data structure keeps its capacity.
fn realloc(comptime T: type, old_mem: var, old_alignment: u29,
    new_n: usize, new_alignment: u29) error{OutOfMemory}![]T;
fn reallocFn(old_mem: []u8, old_alignment: u29,
    new_n: usize, new_alignment: u29) error{OutOfMemory}![]T;

/// The alignment in the type of old_mem must be the same as the alignment
/// requested in alloc (or alignedShrink). The length of old_mem must be the same
/// as the length requested in alloc (or shrink).
fn free(old_mem: var) void;
fn freeFn(old_mem: []u8, old_alignment: u29) void;

[andrewrk]

Here's the new interface API. allocFn and freeFn are both gone, reallocFn has modified semantics, and shrinkFn is added.

zig/std/mem.zig

Lines 11 to 71 in 9c13e9b

	pub const Allocator = struct {
	pub const Error = error{OutOfMemory};
	/// Realloc is used to modify the size or alignment of an existing allocation,
	/// as well as to provide the allocator with an opportunity to move an allocation
	/// to a better location.
	/// When the size/alignment is greater than the previous allocation, this function
	/// returns `error.OutOfMemory` when the requested new allocation could not be granted.
	/// When the size/alignment is less than or equal to the previous allocation,
	/// this function returns `error.OutOfMemory` when the allocator decides the client
	/// would be better off keeping the extra alignment/size. Clients will call
	/// `shrinkFn` when they require the allocator to track a new alignment/size,
	/// and so this function should only return success when the allocator considers
	/// the reallocation desirable from the allocator's perspective.
	/// As an example, `std.ArrayList` tracks a "capacity", and therefore can handle
	/// reallocation failure, even when `new_n` <= `old_mem.len`. A `FixedBufferAllocator`
	/// would always return `error.OutOfMemory` for `reallocFn` when the size/alignment
	/// is less than or equal to the old allocation, because it cannot reclaim the memory,
	/// and thus the `std.ArrayList` would be better off retaining its capacity.
	/// When `reallocFn` returns,
	/// `return_value[0..min(old_mem.len, new_byte_count)]` must be the same
	/// as `old_mem` was when `reallocFn` is called. The bytes of
	/// `return_value[old_mem.len..]` have undefined values.
	/// The returned slice must have its pointer aligned at least to `new_alignment` bytes.
	reallocFn: fn (
	self: *Allocator,
	// Guaranteed to be the same as what was returned from most recent call to
	// `reallocFn` or `shrinkFn`.
	// If `old_mem.len == 0` then this is a new allocation and `new_byte_count`
	// is guaranteed to be >= 1.
	old_mem: []u8,
	// If `old_mem.len == 0` then this is `undefined`, otherwise:
	// Guaranteed to be the same as what was returned from most recent call to
	// `reallocFn` or `shrinkFn`.
	// Guaranteed to be >= 1.
	// Guaranteed to be a power of 2.
	old_alignment: u29,
	// If `new_byte_count` is 0 then this is a free and it is guaranteed that
	// `old_mem.len != 0`.
	new_byte_count: usize,
	// Guaranteed to be >= 1.
	// Guaranteed to be a power of 2.
	// Returned slice's pointer must have this alignment.
	new_alignment: u29,
	) Error![]u8,
	/// This function deallocates memory. It must succeed.
	shrinkFn: fn (
	self: *Allocator,
	// Guaranteed to be the same as what was returned from most recent call to
	// `reallocFn` or `shrinkFn`.
	old_mem: []u8,
	// Guaranteed to be the same as what was returned from most recent call to
	// `reallocFn` or `shrinkFn`.
	old_alignment: u29,
	// Guaranteed to be less than or equal to `old_mem.len`.
	new_byte_count: usize,
	// If `new_byte_count == 0` then this is `undefined`, otherwise:
	// Guaranteed to be less than or equal to `old_alignment`.
	new_alignment: u29,
	) []u8,