I've painted myself into a corner with comptime and I'm seeking advice

Help
, ,
1

I didn’t know it was possible to create a comptime program that was so large it would no longer compile. I kept raising @setEvalBranchQuota to fix it, but now, by passing maxInt(u32), the compiler just segfaults. I have to assume I’m either missing something obvious to work around this or I’ve been misusing comptime altogether. After investing several weeks into this tool already, I wanted to see if anyone had insight into how salvageable this project is.

I work in transportation and this is a cli/library for my job. There are a range of versions of raw/processed geodata this library has to pull from. My solution to this was to create a multi-step build system that embedded these files at comptime. When I originally wrote it I just parsed these json files and created the derived hashmaps I needed at runtime. I decided this wasn’t good enough, and I got greedy.

To get around not being able to parse json at comptime, I made a build module that turned the json into zon and handed it + a manifest off to the final program. By largely copying the StaticStringMap implementation, I made a generalized comptime map that would make these maps “instantly” available at runtime. (there’s a lot more to the system but hopefully you get the picture)

pub fn Map(
    comptime K: type, // has to be an int
    comptime V: type, // hopefully a struct, if it's an array we gotta do something else I think
) type {
    return struct {
        kvs: *const KVs = &empty_kvs,

        pub const KV = struct {
            key: K,
            value: V,
        };

        const KVs = struct {
            keys: [*]const K,
            values: [*]const V,
            len: u32,
        };

        const Self = @This();

        const empty_kvs = KVs{
            .keys = &empty_keys,
            .values = &empty_vals,
            .len = 0,
        };
        const empty_keys = [0]K{};
        const empty_vals = [0]V{};
        const empty_len_indexes = [0]u32{};

        // same deal as StaticStringMap
        // has to be a list of struct { K, V }
        pub inline fn init(comptime kvs_list: anytype) Self {
            comptime {
                var self = Self {};
                @setEvalBranchQuota(std.math.maxInt(u32));

                // this is a dogshit sort but it's comptime so you can't get mad at me
                var keys: [kvs_list.len]K = undefined;
                for(kvs_list, 0..kvs_list.len) |kv, i| {
                    const key, const val = kv;
                    _ = val;
                    keys[i] = key;
                }
                std.mem.sort(K, &keys, {}, std.sort.asc(K));
                
                var values: [kvs_list.len]V = undefined;
                for(keys, 0..keys.len) |sorted_key, i| {
                    const index = blk: {
                        for(kvs_list, 0..kvs_list.len) |kv, j| {
                            const key, const val = kv;
                            _ = val;
                            if(key == sorted_key) {
                                break :blk j;
                            }
                        }
                        unreachable;
                    };
                    const key, const val = kvs_list[index];
                    _ = key;

                    values[i] = val;
                }

                const final_keys = keys;
                const final_values = values;

                self.kvs = &.{
                    .keys = &final_keys,
                    .values = &final_values,
                    .len = @intCast(kvs_list.len),
                };

                return self;
            }
        }

        pub fn get(self: Self, key: K) ?V {
            // TODO: keys are sorted, do a binary search
            // but I just want to see if it compiles

            for(self.kvs.keys, 0..self.kvs.len) |map_key, i| {
                if(map_key == key) {
                    return self.kvs.values[i];
                }
            }

            return null;
        }
    };
}

This worked, but compile times ballooned to an insane degree. This should have been a warning, but I pressed on. I made it pretty far and the library is ok and functional, but now that I need to add a set of maps that was derived from 2 other maps, I’ve hit my head on the setEvalBranchQuota ceiling.

I’m sure I’m not the first person to obsessively pre-compute to this degree. Where did I go wrong

2

Keep an eye on this issue:

It hasn’t been a top priority issue for some time, but at some point it will become the focus.

In the meantime, remember that anything you can do at compile-time you can also do at build-time. And at build-time, run-time is compile-time! :zany_face:

Silliness aside, I do think that generating code or data as a build step is the best thing to do when you run into limitations like this. You might even be able to get something out of it as a consolation prize, for instance, making it easier to inspect and visualize those intermediate artifacts.

3

I do think that generating code or data as a build step is the best thing to do when you run into limitations like this

If I understand correctly, I believe that’s what I’m already doing? The json → zon conversion happens as its own build step with a separate executable. I could probably try splitting some of it into yet another step though

4

But then you’re processing that zon into something else at comptime right? you could do that at build-time as well.

Edit: also I’m sure you already checked this but make sure you’re not doing anything O(N^2)…

5

Sounds like a job for @embedFile().

You seem to use text format (json or zon) and parse it at comptime. You should convert text to binary format and just embed the binary file.

6

The trouble with embedFile() is I’m making a map that holds structs that have methods on them, not just raw text. To Andrew’s point though, I will try splitting zon → struct conversion into its own step. A bit shaky on the details but I’ll do some reading. My hope is I won’t have to turn the zon into structs, turn those struct into zon, then “de-anonymize” them in the final program. Either way thank you for the insight!

7

You can use std.mem.bytesAsSlice:

const StructWithMethod = struct {
    text: [7]u8,
    integer: u32,
    float: f32,

    fn method(self: *const StructWithMethod) f64 {
        return @as(f64, self.integer) + self.float;
    }
};

test "generate" {
    const io = std.testing.io;
    const file = try std.Io.Dir.cwd().createFile(io, "binary_data", .{});
    defer file.close(io);
    const slice: []const StructWithMethod = &.{
        .{ .text = @splat('a'), .integer = 2, .float = 3.0 },
        .{ .text = @splat('b'), .integer = 5, .float = 7.0 },
    };
    try file.writeStreamingAll(io, std.mem.sliceAsBytes(slice));
}

const raw_binary = @embedFile("binary_data");
const aligned_binary: [raw_binary.len]u8 align(@alignOf(StructWithMethod)) = raw_binary.*;

test "embed" {
    const slice: []const StructWithMethod = std.mem.bytesAsSlice(StructWithMethod, &aligned_binary);
    try std.testing.expectEqual(5, slice[0].method());
    try std.testing.expectEqual(12, slice[1].method());
}
8

oh shit that is exactly what I needed, thank you

9

Make sure to check that the compiler did not mess up the layout of the struct. Make the struct extern if it did.

Can you :check_box_with_check: my answer as solution instead of Andrew’s?