improve comptime performance to roughly, generally the same as CPython execution speed of equivalent Python code

[squeek502]

While investigating #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.

[matu3ba]

Reminder for related question:
What performance difference does make computing things with floats and in ints in comptime?
Here is python performance from 7 years ago.

SpexGuy:
"That's just conversion from string to values though, and depends a lot on CPython internals. If you look at the only real answer to that question (https://stackoverflow.com/a/49410878), it shows that the int parse is doing a whole bunch of extra string operations for unknown reasons, in addition to allocations and tuple packing that doesn't exist in the other profiles.
Probably due to having to be able to interpret multiple bases. Since Zig has a tokenizer instead, this shouldn't affect compile speed for us much."