Placement of @setEvalBranchQuota

Help
,
1

Hi folks, I have some code that uses std.MultiArrayList for storage, which has started to hit the comptime branch quota as the underlying struct gains more fields.

The quota seems to be hit when generating code for the return type of some std.MultiArrayList functions, so I’m not sure where I should be placing @setEvalBranchQuota in my code to raise the limit in this case. Any tips/assistance would be much appreciated.

A repro case is the following:

const std = @import("std");

const Foo = struct {
    a01: u32,
    a02: u32,
    a03: u32,
    a04: u32,
    a05: u32,
    a06: u32,
    a07: u32,
    a08: u32,
    a09: u32,
    a10: u32,
    a11: u32,
    a12: u32,
    a13: u32,
    a14: u32,
    a15: u32,
    a16: u32,
    a17: u32,
};

pub fn main() !void {
    var gpa: std.heap.DebugAllocator(.{}) = .init;
    defer _ = gpa.deinit();

    const allocator = gpa.allocator();

    var list: std.MultiArrayList(Foo) = .empty;
    defer list.deinit(allocator);

    try list.resize(allocator, 1);
    list.slice().items(.a01)[0] = 42;
}

This produces the following error on godbolt:

/opt/compiler-explorer/zig-0.14.0/lib/std/math/log2.zig:24:13: error: evaluation exceeded 1000 backwards branches
            while (x_shifted >> (shift_amt << 1) != 0) shift_amt <<= 1;
            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/opt/compiler-explorer/zig-0.14.0/lib/std/math/log2.zig:24:13: note: use @setEvalBranchQuota() to raise the branch limit from 1000
/opt/compiler-explorer/zig-0.14.0/lib/std/math.zig:779:22: note: called from here
    const base = log2(largest_positive_integer);
                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/opt/compiler-explorer/zig-0.14.0/lib/std/meta.zig:546:49: note: called from here
            .tag_type = std.math.IntFittingRange(0, field_infos.len - 1),
                        ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/opt/compiler-explorer/zig-0.14.0/lib/std/meta.zig:386:61: note: called from here
pub fn fieldInfo(comptime T: type, comptime field: FieldEnum(T)) switch (@typeInfo(T)) {
                                                   ~~~~~~~~~^~~
/opt/compiler-explorer/zig-0.14.0/lib/std/multi_array_list.zig:568:34: note: called from here
            return meta.fieldInfo(Elem, field).type;
                   ~~~~~~~~~~~~~~^~~~~~~~~~~~~
/opt/compiler-explorer/zig-0.14.0/lib/std/multi_array_list.zig:83:73: note: called from here
            pub fn items(self: Slice, comptime field: Field) []FieldType(field) {
                                                               ~~~~~~~~~^~~~~~~
/opt/compiler-explorer/zig-0.14.0/lib/std/multi_array_list.zig:463:71: note: called from here
                    @memcpy(other_slice.items(field), self_slice.items(field));
                                                      ~~~~~~~~~~~~~~~~^~~~~~~
referenced by:
    ensureTotalCapacity: /opt/compiler-explorer/zig-0.14.0/lib/std/multi_array_list.zig:411:36
    resize: /opt/compiler-explorer/zig-0.14.0/lib/std/multi_array_list.zig:339:41
2

As an aside, it’s possible to work around this issue by replacing the implementation of std.MultiArrayList.FieldType to call the new @FieldType builtin, since this lowers the comptime branch usage a lot.

Regardless though, I’d be interested if there is a way to raise the quota for this case from client code, or does this need standard library changes to fix?

2 Likes
3

I can’t find any place where you can place the quota that fixes the error, so you should report this as a bug. AFAIK the goal is that most std data structures should work without the user needing to manually override the quota.

I don’t yet completely understand how the quota logic determines which scope the quota belongs to. Sometimes you can place @setEvalBranchQuota() as a regular statement in the function scope. Other times (often for types), you need to resolve the type in a block of its own, like

const FooDataStructure = comptime with_quota: {
    @setEvalBranchQuota(100_000);
    break :with_quota std.SomeComplexDataStructure(Foo);
};

Other times you might even need to “warm up” and resolve nested data structures used by the implementation of the main data structure in advance

comptime {
    @setEvalBranchQuota(100_000);
    _ = std.SomeComplexDataStructure(Foo).Indexer;
}

I tried a few variations of these but neither appear to work for your repro. Updating the implementations to @FieldType would probably be a good start, but someone should probably also audit the heavy use of std.meta which often incur enormous unnecessary overhead.

1 Like
4

Thanks for the comments, good to know I’ve not just missed some standard syntax for how to apply @setEvalBranchQuota to the list type.

Issue raised here: std.MultiArrayList field count limit · Issue #23352 · ziglang/zig · GitHub