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 https://github.com/ziglang/zig/issues/1306#issuecomment-468719742

[andrewrk]

Have a look at the new Allocator interface API:

https://github.com/ziglang/zig/blob/9c13e9b7ed9806d0f9774433d5e24359aff1b238/std/mem.zig#L11-L71

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:

https://github.com/ziglang/zig/blob/9c13e9b7ed9806d0f9774433d5e24359aff1b238/std/array_list.zig#L144-L150

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