use case: comptime allocator

[andrewrk]

Here's an implementation of the Allocator interface at compile-time:

const std = @import("std");
const Allocator = std.mem.Allocator;
const Alignment = std.mem.Alignment;

pub const panic = std.debug.no_panic;

comptime {
    var map = std.AutoArrayHashMap(i32, i32).init(comptime_allocator);
    map.put(12, 34) catch unreachable;
}

pub const comptime_allocator: Allocator = .{
    .ptr = undefined,
    .vtable = &.{
        .alloc = comptimeAlloc,
        .resize = comptimeResize,
        .remap = comptimeRemap,
        .free = comptimeFree,
    },
};

fn comptimeAlloc(
    context: *anyopaque,
    len: usize,
    alignment: Alignment,
    return_address: usize,
) ?[*]u8 {
    _ = context;
    _ = return_address;
    if (!@inComptime()) unreachable;
    var bytes: [len]u8 align(alignment.toByteUnits()) = undefined;
    return &bytes;
}

fn comptimeResize(
    context: *anyopaque,
    memory: []u8,
    alignment: Alignment,
    new_len: usize,
    return_address: usize,
) bool {
    _ = memory;
    _ = context;
    _ = alignment;
    _ = return_address;
    _ = new_len;
    // Always returning false here ensures that callsites make new allocations that fit
    // better, avoiding wasted .cdata and .data memory.
    return false;
}

fn comptimeRemap(
    context: *anyopaque,
    memory: []u8,
    alignment: Alignment,
    new_len: usize,
    return_address: usize,
) ?[*]u8 {
    _ = context;
    _ = memory;
    _ = alignment;
    _ = new_len;
    _ = return_address;
    // Always returning false here ensures that callsites make new allocations that fit
    // better, avoiding wasted .cdata and .data memory.
    return null;
}

fn comptimeFree(
    context: *anyopaque,
    memory: []u8,
    alignment: Alignment,
    return_address: usize,
) void {
    _ = context;
    _ = memory;
    _ = alignment;
    _ = return_address;
    // Global variables are garbage-collected by the linker.
}

It works, with a caveat mentioned below by @mlugg.

This issue can be closed when:

• [ ] It is added to the std lib, with test coverage
• [ ] The caveat about auto-layout types is fixed

Related:

• #2414

[andrewrk]

Perhaps related to #130

[Hejsil]

We probably don't need @getNextGloballyIncrementingInteger() for uniqueness, as that is what we have @OpaqueType for. We could probably pass @OpaqueType to ComptimeAllocator.init to ensure that all calls are never cashed (index would now be of type type and would be reassigned to a new @OpaqueType in alloc)

[andrewrk]

I had a second pass at this, and it almost all worked, except for:

In std.mem.Allocator, setting the bytes to undefined didn't work at comptime.

Which is a legitimate problem. Because this is trying to, at comptime, do a @memset of a global variable (runtime memory) to undefined. Trying to use this memory at comptime wouldn't work either, again because it is runtime memory.

Related - I had a conversation with @cavedweller about this the other evening, and he pointed out an important use case: freeing the memory. With a pure userland solution to this, as you can see, there is no freeing memory. All comptime-allocated memory escapes, because @ptrToInt or similar could have been using. However if we introduce a compiler builtin which is capable of freeing memory, this allows the following use cases to work:

• comptime code wants to use structures that require heap allocation, but will leave no memory used after it is done. Nothing is actually emitted to the .data section when the build completes.
• comptime code wants to allocate memory, and keep it allocated, initialize some stuff, and then leave it initialized, using standard data structures that expect allocators.
• some mix of both.

My proposal for this builtin would be:

@comptimeRealloc(old_mem: []u8, new_size: usize, new_align: u29) []u8

Notably, comptime allocation doesn't fail - that would be a compile error! To allocate fresh memory, pass a zero-length slice for old_mem.

The returned byte slice would point to memory that is comptime-mutable within the current comptime scope. Outside that scope, the memory would be either runtime-mutable or runtime-const, depending on where the memory escaped to outside the comptime scope.

One problem to solve with this proposal would be the lingering reference to a comptime allocator. As an example:

const std = @import("std");

const foo = comptime blk: {
    var comptime_alloc_state = ComptimeAllocator.init();
    const allocator = &comptime_alloc_state.allocator;

    var list = std.ArrayList(i32).init(allocator);
    list.append(10) catch unreachable;
    list.append(20) catch unreachable;
    break :blk list;
};

pub fn main() void {
    std.debug.warn("list[0]={}\n", foo.at(0));
    std.debug.warn("list[1]={}\n", foo.at(1));
}

const Allocator = std.mem.Allocator;
const assert = std.debug.assert;

const ComptimeAllocator = struct {
    allocator: Allocator,

    fn init() ComptimeAllocator {
        return ComptimeAllocator{
            .allocator = Allocator{
                .reallocFn = realloc,
                .shrinkFn = shrink,
            },
        };
    }

    fn realloc(allocator: *Allocator, old_mem: []u8, old_align: u29, new_size: usize, new_align: u29) Allocator.Error![]u8 {
        return @comptimeRealloc(old_mem, new_size, new_align);
    }

    fn shrink(allocator: *Allocator, old_mem: []u8, old_align: u29, new_size: usize, new_align: u29) []u8 {
        return @comptimeRealloc(old_mem, new_size, new_align);
    }
};

Clearly the example wouldn't work if we made foo a var instead of const and then tried to append. But what about other methods that want to mutate state but don't mess with the comptime allocator reference? Theoretically that should work. I think trying to implement this would make the problems and potential solutions more clear.

[rohlem]

First off, the solution with the smallest-footprint change could look like this:

@comptimeRealloc(old_mem: []u8, new_size: usize, new_align: u29) ?[]u8 //returns null if evaluated at runtime

---

For a more thorough and "optimal" concept, maybe I'm just stating the obvious here, I'll try to keep it short; this is how my mind completes/solves the last comment's perspective:

• Supposing @comptimeRealloc, calling this function only seems sensible in a comptime context/block. In this way, it's in the same "comptime-only" category as ++, or handling instances of type type.
• If our main motivation is to "enable runtime concepts at comptime", we could automatically flag [expressions / blocks / code paths] as "comptime-only" if they unconditionally contain "comptime-only" operations. This would work similarly to the flagging of async functions if they contain suspend/await, but not necessarily bubbling up to function scope, because it doesn't affect calling convention.
• Entering a "comptime-only" block in a runtime context would be equivalent to unreachable - panic in safe builds, UB in unsafe builds.

If this design is accepted, the implementation of comptime variants can use the same interface as a runtime variant - in the case of allocators, the allocate function would unconditionally contain @comptimeRealloc, marking the surrounding block as "comptime-only". Therefore any runtime control flow that ends up there triggers (in safe build modes) a stack trace like f.e.:

comptime_allocator.zig:xx - Error: comptime-only block entered at runtime
comptime_allocator.zig:xy - Note: Block is marked comptime-only because of use of `@comptimeRealloc` here.
std/array_list.zig:zz - called from here ...

For the purpose of code-deduplication, maybe something like #868 could also help in usage:

if(@weAreInComptime())
  return comptime_allocator.allocate(T);
else
  return error.OnlySupportedAtComptime;

[rohlem]

EDIT2: Looks like I commented without doing proper research/testing again. Sorry for the noise. (After further testing, it appears that comptime-caching with @fieldParentPtr already does what I proposed before this edit, and some forms of fixed-buffer allocators already work during comptime (with certain limitations).) This discussion is therefore about the semantics behind transferring comptime-initialized memory to runtime-usable (global) memory. Seems I misinterpreted what the actual issue was before. EDIT3: After a couple more tries, I did get something up and running with status-quo language semantics (only requiring a couple workarounds in std/mem.zig to be more comptime-friendly): see my branch . ( maybe see also irc discussion, if something about my approach still seems unclear )

[ghost]

@rohlem: I don't think we want to draw a hard line between comptime and runtime code here. After all, a key feature of comptime is the ability to integrate with runtime program flow (see: comptime var). A much simpler restriction would be to require the arguments of these builtins to be comptime-known. I'll open a concrete proposal.

Also, #5675 could be helpful here in any case.

[ghost]

I've proposed a reworking of comptime semantics (#5895) to accommodate this use case.

[glyh]

I run into this when trying to port ctregex to zig 0.13, what is the status of this issue? Is this abandoned or implemented?

[andrewrk]

I updated the OP with a fresh writeup. In summary:

• This is definitely within the grasp of the Zig language.
• #4298 is an easy prerequisite
• Last remaining task is to make a proposal to allow inline functions to coerce to function pointers as long as the value is and remains comptime-known.

[mlugg]

Additionally, one of the biggest thing blocking any Allocator from being useful at comptime (e.g. FBA) is memory reinterpretation rules. Allocating something with a well-defined layout with a comptime FBA probably works today, but allocating something with ill-defined layout (e.g. an auto-layout struct) currently fails because we try to reinterpret the u8 buffer to this different type at comptime, which emits a compile error.

There is a plan for this, discussed in a compiler meeting a while back -- the comptime pointer access rules should be relaxed, so that instead of emitting an error, accessing this kind of reinterpreted pointer works fine, but always spits out undefined when switching from a well-defined to ill-defined layout or vice versa.

[mlugg]

@andrewrk, in the (newly added) implementation in the OP, you have written comments stating:

// Global variables are garbage-collected by the linker.

and

// Always returning false here ensures that callsites make new allocations that fit
// better, avoiding wasted .cdata and .data memory.

This implies a feature which does not currently exist: the ability to reference the allocated data at runtime though the compiler turning the comptime vars into global runtime data. Right now, trying to use comptime-allocated data at runtime will emit everyone's favourite compile error:

export fn foo() void {
    const ptr: *const u32 = comptime ptr: {
        const ptr = comptime_allocator.create(u32) catch unreachable;
        ptr.* = 12345;
        break :ptr ptr;
    };
    bar(ptr);
}
fn bar(ptr: *const u32) void {
    _ = ptr.*;
}

[mlugg@nebula ~]$ zig build-obj repro.zig
repro.zig:7:9: error: runtime value contains reference to comptime var
    bar(ptr);
        ^~~
repro.zig:7:9: note: comptime var pointers are not available at runtime
repro.zig:32:57: note: 'runtime_value' points to comptime var declared here
    var bytes: [len]u8 align(alignment.toByteUnits()) = undefined;
                                                        ^~~~~~~~~

Currently, the only way to access this data at runtime would be to copy the underlying data (the u32 in the above example) into a const after we're done and use a pointer to that. If we don't want to require that, and instead want the above to just magically work, we'll need to complicate the language rules surrounding comptime var. I'm open to that (I think I even recall us saying we were leaving the door open to changes when we decided the current semantics), but I just wanted to flag up that this functionality does not exist today. It's up to you whether you also consider that a blocker for closing this issue.

[l-kand]

There might be an alternative to figuring out how to write a dedicated comptime allocator (and particularly figuring out how to reinterpret raw bytes as ill-defined layout types at comptime as pointed out by @mlugg here).

We could move allocation at comptime to the allocator interface where we have the actual type information of the memory we want to allocate. E.g. the implementation of std.mem.Allocator.create(...) could be extended more or less like this:

pub fn create(a: Allocator, comptime T: type) Error!*T {
    if (@inComptime()) {
        var value: T = undefined;
        return &value;
    }

    // existing implementation
}

This way one could even pass undefined as std.mem.Allocator and – given that it is only ever used at comptime – it would still work.

---

Edit for context: I went more or less exactly the same path as @tristanpemble descibed here and ended writing my own list that was basically an 1:1 rewrite of std.ArrayList where I replaced usage of the gpa: std.mem.Allocator with the comptime-allocation shown above. While doing so I got the idea that this logic could simply be moved into the std.mem.Allocator-interface.