std.MultiArrayList field count limit

[sjb3d]

Zig Version

0.14.0

Steps to Reproduce and Observed Behavior

Hi, it seems that std.MultiArrayList hits the comptime branch quota once the underlying struct gets to 18 or so fields, but I am having some trouble finding the correct placement of @setEvalBranchQuota in client code that will raise the limit.

Here is a repro case that will fail to compile:

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;
}

Here is the output on godbolt for 0.14 (seemingly regardless of where I place @setEvalBranchQuota):

/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

As a local workaround, I have modified std.MultiArrayList.FieldType to use @FieldType(Elem, @tagName(field)) as its implemention (instead of stuff from std.meta), as this reduces the comptime branch usage a lot and allows this repro case to compile.

However, I am confused how client code could raise the quota for this case so would like to raise it as an issue. I also wonder if std.MultiArrayList or the std.meta functions it relies on are missing some internal @setBranchEvalQuota based on the number of fields of the struct so that it scales to any struct type? (See comments at https://ziggit.dev/t/placement-of-setevalbranchquota/9231/3)

Expected Behavior

It should be possible to use std.MultiArrayList with larger structs without modification to the standard library.

[alexrp]

As a local workaround, I have modified std.MultiArrayList.FieldType to use @FieldType(Elem, @tagName(field)) as its implemention (instead of stuff from std.meta), as this reduces the comptime branch usage a lot and allows this repro case to compile.

Separately from the quota question, this is clearly the right thing to do; a PR that replaces all uses of FieldType(T, name), TagPayloadType(T, name), TagPayloadByName(T, name) with @FieldType(T, name), as well as TagPayload(T, tag) with @FieldType(T, @tagName(tag)) would be welcome.

If no one else picks this up in the meantime, I'll do it before we tag 0.14.1.

[sjb3d]

Good news that my local workaround is a positive change, and it certainly allows for more fields before failure, but eventually more branch quota is needed (the next place is the comptime sort by size for std.MultiArrayList.sizes at around 45 fields).

For even larger structs, and for this case on 0.14, is there any syntax that will apply some @setEvalBranchQuota when creating the type with a large struct? Or does std.MultiArrayList need changes in various places to derive a quota from the number of struct fields to be able to support a struct of any size?

[alexrp]

cc @mlugg for the @setEvalBranchQuota questions

[mlugg]

If the issue is in the mem.sort call in the definition of sizes, then you need to put the @setEvalBranchQuota within that labeled block (the definition of sizes). Since std.mem.sort is O(n log n) worst-case, you'll want something like:

// The `mem.sort` call below is the most asymptotically expensive operation, at O(n log n).
@setEvalBranchQuota(3 * (fields.len * std.math.log2(fields.len)));

The 3 is an arbitrary constant factor; I don't know what it should be, because I've not analyzed the implementation of std.sort.block (the function underlying std.mem.sort). Just increase it until things seem happy.

[sjb3d]

OK thanks for the comment, sounds like std.MultiArrayList needs to carefully add quota in its implementation then, and there is no way for client code to add some quota when creating a specific type.

[alexrp]

I'm going to leave this open after #23353 because we also need the above @setEvalBranchQuota change to fully fix the issue.

[sjb3d]

Thanks, turns out after the @FieldType change only the sort needed quota (at least up to 200 fields) and that 3 was the minimum magic number. PR above adds the quota and test.