std.mem.Allocator interface doen't allow for zero-copy resizing using mremap

xbx · September 13, 2024, 6:18am

in C, when using realloc() it is sometimes possible to grow the allocation and avoid the memcopy by only changing the virtual addresses and keeping the data in physical memory in place.

see: zig/lib/libc/musl/src/malloc/mallocng/realloc.c at b56a667ecdb9f34dbd60d247d4237bc008755979 · ziglang/zig · GitHub

The current allocator interface doesn’t seem to allow for this case and I wasn’t able to find an issue documenting the rationale for this choice?

Maybe one reason could be that it is not so useful in practice:
I did a cursory check by adding some logs to MultiArrayList.setCapacity() and ArrayList.ensureTotalCapacityPrecise()

and while something like for (0..123456789) |v| try array.append(v); would benefit a lot,

running zig itself doesn’t triggers the case that much.

squeek502 · September 13, 2024, 10:03am

EDIT: I missed the “only changing the virtual addresses and keeping the data in physical memory in place” part (Zig’s Allocator.resize stipulates that the memory address must stay the same). Expand below for a probably-irrelevant response.

Unless I’m missing something, the Allocator interface does support this use-case:

github.com

ziglang/zig/blob/b56a667ecdb9f34dbd60d247d4237bc008755979/lib/std/mem/Allocator.zig#L25-L40


      
          /// Attempt to expand or shrink memory in place. `buf.len` must equal the
          /// length requested from the most recent successful call to `alloc` or
          /// `resize`. `buf_align` must equal the same value that was passed as the
          /// `ptr_align` parameter to the original `alloc` call.
          ///
          /// A result of `true` indicates the resize was successful and the
          /// allocation now has the same address but a size of `new_len`. `false`
          /// indicates the resize could not be completed without moving the
          /// allocation to a different address.
          ///
          /// `new_len` must be greater than zero.
          ///
          /// `ret_addr` is optionally provided as the first return address of the
          /// allocation call stack. If the value is `0` it means no return address
          /// has been provided.
          resize: *const fn (ctx: *anyopaque, buf: []u8, buf_align: u8, new_len: usize, ret_addr: usize) bool,

PageAllocator (which is commonly used as a backing allocator for other allocator implementations) has a resize implementation with a // TODO: call mremap, but note that since it always allocates at least a full page for any requested size, resize is guaranteed to succeed when growing an allocation from < page size to <= page size.

Here’s an example of using std.heap.page_allocator as the backing allocator for an arena, which shows that resize-in-place does indeed occur.

Also see the ArrayList implementation, which takes advantage of resize:

github.com

ziglang/zig/blob/b56a667ecdb9f34dbd60d247d4237bc008755979/lib/std/array_list.zig#L466-L480


      
          // Here we avoid copying allocated but unused bytes by
          // attempting a resize in place, and falling back to allocating
          // a new buffer and doing our own copy. With a realloc() call,
          // the allocator implementation would pointlessly copy our
          // extra capacity.
          const old_memory = self.allocatedSlice();
          if (self.allocator.resize(old_memory, new_capacity)) {
              self.capacity = new_capacity;
          } else {
              const new_memory = try self.allocator.alignedAlloc(T, alignment, new_capacity);
              @memcpy(new_memory[0..self.items.len], self.items);
              self.allocator.free(old_memory);
              self.items.ptr = new_memory.ptr;
              self.capacity = new_memory.len;
          }

For your actual question, the most relevant issue is probably Improve Allocator interface so client can avoid needless copying · Issue #4431 · ziglang/zig · GitHub. This is the only MREMAP_MAYMOVE mention, though:

From an allocator implementation standpoint, the only case I’ve heard of for implementing realloc as anything more than reallocInPlace + memcpy on failure is to be able to use MREMAP_MAYMOVE on large allocations. Some allocators (e.g. jemalloc) try to avoid MREMAP_MAYMOVE anyway for fragmentation reasons.