Zig: Performance of comptime

[squeek502]

While investigating https://github.com/ziglang/zig/issues/3863, I ran into an unexpected problem: the performance of certain things (in my case, std.hash.Wyhash and std.sort.sort) is hugely degraded during comptime.

Here's a test file that shows the problem using std.sort:

const std = @import("std");

const num_values: usize = 10000;
const expected_first_element: usize = num_values - 1;

fn sortSomething() usize {
    var buf = init: {
        var arr: [num_values]usize = undefined;
        for (arr) |*v, i| {
            v.* = i;
        }
        break :init arr;
    };
    std.sort.sort(usize, buf[0..], std.sort.desc(usize));
    return buf[0];
}

test "comptime" {
    @setEvalBranchQuota(100000);
    comptime std.testing.expectEqual(expected_first_element, sortSomething());
}

test "runtime" {
    std.testing.expectEqual(expected_first_element, sortSomething());
}

The runtime test on its own (--test-filter runtime) runs very quickly (as expected) with num_values = 10000. For comptime, however, here's what I get with various different num_values:

| num_values | time spent compiling | memory usage | status |
| --- | --- | --- | --- |
| 10 | 1s | ? | OK |
| 100 | 1s | ? | OK |
| 1000 | 3s | 500mb | OK |
| 10000 | 75s | 3gb | evaluation exceeded 100000 backwards branches |

(tested with zig 0.5.0+33d9dda55 on Windows)

I would assume most of this is due to things like gathering stack traces for potential compile errors and things like that, but maybe there needs to be a way to disable that for certain comptime blocks? Or maybe its something else that's causing the performance issues here?

[daurnimator]

Related to #4038 ?

[wangyi-fudan]

please upgrade to wyhash V3, it doubles speed

[andrewrk]

comptime code evaluation is barely beyond proof-of-concept in stage1. I'm expecting to achieve something close to cpython performance of comptime code execution in self-hosted.