optimize behavior of shrink in standard library data structures

[andrewrk]

Related: #1306

As @schmee notes in #2008, ArrayList.shrink does not actually interact with the allocator.

I would like it to call shrink in the allocator. However the allocator currently has no way to communicate back, "hey I actually can't reclaim this memory, so if you just want to hang on to it, that would actually be better". So I want to look into this before deciding how shrink will work for array lists.

To resolve this issue, we need to enumerate the various use cases for the various data structures that can have the concept of shrink:

• HashMap
• ArrayList
• PriorityQueue
• (there are more)

And we need to consider the various allocators that may be used as a backing allocator for these data structures:

• ArenaAllocator / FixedBufferAllocator (can never reclaim space when reallocating)
• General Purpose Allocator (can sometimes reclaim space when reallocating)
• (there are more)

And then make sure that the most optimal thing is happening in every case, for every data structure. If this isn't the case, then the Allocator API and/or data structure APIs need to be modified.

[andrewrk]

Here's the plan to solve it #1306 (comment)

[andrewrk]

Have a look at the new Allocator interface API:

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,

In particular, realloc now returns error.OutOfMemory when the new size is smaller than the old size and the allocator decides it has nothing useful to do with the reclaimed bytes.

And here's std.ArrayList now which takes advantage of it:

zig/std/array_list.zig

Lines 144 to 150 in 9c13e9b

	pub fn shrink(self: *Self, new_len: usize) void {
	assert(new_len <= self.len);
	self.len = new_len;
	self.items = self.allocator.realloc(self.items, new_len) catch |e| switch (e) {
	error.OutOfMemory => return, // no problem, capacity is still correct then.
	};
	}

So what's left is to update the other data structures from the standard library to take advantage of this new interface.