make it possible to have the Allocator interface give a comptime-known alignment to Allocator implementations

[andrewrk]

Alignment is almost always compile-time known when allocating memory, but then gets turned into a runtime value for implementations.

Here @LemonBoy and I discuss some of the trade-offs of trying to get the behavior and safety that we want with the C allocator: https://github.com/ziglang/zig/issues/6674#issuecomment-730186072

This proposal is a way for everybody to get what they want:

• Only 1 std.heap.c_allocator, no std.heap.raw_c_allocator
• It supports any alignment, no assert footguns
• When the allocation's alignment is within the malloc supported amount, it will do the efficient choice of calling malloc directly instead of inserting additional metadata or calling the more expensive posix_memalign.

The idea of the proposal is to add some more function pointers to the interface, which encode a comptime-known alignment in the name:

--- a/lib/std/mem/Allocator.zig
+++ b/lib/std/mem/Allocator.zig
@@ -24,6 +24,21 @@ pub const Error = error{OutOfMemory};
 /// If the value is `0` it means no return address has been provided.
 allocFn: fn (self: *Allocator, len: usize, ptr_align: u29, len_align: u29, ret_addr: usize) Error![]u8,

+/// Same as `allocFn` but alignment is 1 byte.
+alloc1: fn (self: *Allocator, len: usize, ret_addr: usize) Error![]u8 = defaultAlloc(1),
+
+/// Same as `allocFn` but alignment is 2 bytes.
+alloc2: fn (self: *Allocator, len: usize, ret_addr: usize) Error![]u8 = defaultAlloc(2),
+
+/// Same as `allocFn` but alignment is 4 bytes.
+alloc4: fn (self: *Allocator, len: usize, ret_addr: usize) Error![]u8 = defaultAlloc(4),
+
+/// Same as `allocFn` but alignment is 8 bytes.
+alloc8: fn (self: *Allocator, len: usize, ret_addr: usize) Error![]u8 = defaultAlloc(8),
+
+/// Same as `allocFn` but alignment is 16 bytes.
+alloc16: fn (self: *Allocator, len: usize, ret_addr: usize) Error![]u8 = defaultAlloc(16),
+
 /// Attempt to expand or shrink memory in place. `buf.len` must equal the most recent
 /// length returned by `allocFn` or `resizeFn`. `buf_align` must equal the same value
 /// that was passed as the `ptr_align` parameter to the original `allocFn` call.
@@ -46,6 +61,12 @@ allocFn: fn (self: *Allocator, len: usize, ptr_align: u29, len_align: u29, ret_a
 /// If the value is `0` it means no return address has been provided.
 resizeFn: fn (self: *Allocator, buf: []u8, buf_align: u29, new_len: usize, len_align: u29, ret_addr: usize) Error!usize,

+fn defaultAlloc(comptime alignment: u29) fn (*Allocator, usize, usize) Error![]u8 {
+    return fn (self: *Allocator, len: usize, ret_addr: usize) Error![]u8 {
+        return self.allocFn(len, alignment, 0, ret_addr);
+    }
+}
+
 /// Set to resizeFn if in-place resize is not supported.
 pub fn noResize(
     self: *Allocator,

This is backwards compatible with existing Allocator implementations and provides the ability for the Allocator interface to call the respective function for lower alignments, and it provides the Allocator implementation the ability to optimize some of the calls to the lower alignments. For example, for std.heap.c_allocator, it would avoid additional overhead if it knew that malloc is guaranteed to be aligned appropriately.

[LemonBoy]

Nice idea. I think we can simplify it even further by having the allocator interface specify the maximum alignment it supports (comptime field of type ?u29 with a default value of null) and an extra function allocAlignedFn: fn (self: *Allocator, len: usize, len_align: u29, ret_addr: usize) Error![]u8 that assumes the allocator's default alignment is ok.

[andrewrk]

I'm not sure I understand the comptime field thing - wouldn't that require an allocator parameter to change from foo: *Allocator to foo: anytype ?

[LemonBoy]

Uh I accidentally a word. I meant comptime-known field, so that one can choose between allocAlignedFn and allocFn when the type alignment is statically known.

[andrewrk]

Ah I think I understand now and that makes sense to me

[LemonBoy]

The other alternative is to make c_allocator use a plain call to malloc when the alignment is small enough (branching on ptr_align, cannot be done at runtime). resizeFn needs to take this extra case into account and examine the slice pointer alignment by counting the number of trailing zeros...

Speaking of alignment, resizeFn accepts a buf_align parameter hoping that its value matches the original alignment value. I don't really get why? The allocator will break if you under-align a slice (going from N to 1, that's totally legal and safe) and accidentally pass it to an allocator that cares about buf_align, having the allocator "extract" the pointer alignment is better as it avoids this pitfall and cleans up a bit the allocator API.

As usual, there's no allocator that's actively using buf_align so you won't notice any problem/change.

cc @marler8997, you were the mind behind the allocator API redesign, no?

[marler8997]

@LemonBoy resizeFn didn't originally have buf_align so I can't speak to why it was added.

I think the 3 bullet points Andrew listed are reasonable. However, I'm not seeing why we need to add more function pointers to implement it. Couldn't we implement that strategy with this?

// from std.heap.CAllocator
fn alloc(...) {
    if (alignment <= simple_alloc_threshold) {
        // use simple allocation
    } else {
        // use posix_memalign
    }
}

I've discovered that allocation in general is a surprisingly complex topic. There are other problems that could be addressed by adding more function pointers to the allocator interface, which makes me think that adding a slew of new ones for small alignments won't be a scalable solution. I think we'll need to step in to "generic allocator land" if we want to start giving our allocators that level of control (https://github.com/marler8997/zigalloc/blob/master/alloc.zig). As for our current interface, I don't see why the C allocator couldn't implement the proposed semantics with the current 2 function pointer interface.

[LemonBoy]

However, I'm not seeing why we need to add more function pointers to implement it. Couldn't we implement that strategy with this?

That's what I proposed in the post you replied to, the only downside is that resizeFn now has to be smarter and use the correct set of functions to operate on the given slice, hence the question about buf_align.

If that wasn't part of the original interface specification I wonder where it popped out from.