Zig Zig Zag, as Fast as You Can

const std = @import("std");
const print = std.debug.print;

pub fn main() !void {
    // You can ignore this - it's setting up an allocator, which is used for reserving and freeing memory
    // for Zig's objects. Systems Programming, ahoy! :P
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // "Create a Map<int, List<int>>"
    var map = std.AutoHashMap(u32, std.ArrayList(u32)).init(allocator);
    // This next line is a pattern of many Systems Programming languages - the necessity to
    // tell your system when to free up memory allocated to a variable.
    //
    // In support of Zig - not only does `defer` (which defers execution until the enclosing function returns)
    // make this easier to do, but the toolchain also identifies memory leaks for you.
    defer map.deinit();

    print("Is the key present _before_ getOrPut? {}\n", .{map.contains(1)});

    const response = try map.getOrPut(1);
    // At this point, there is still nothing "at" the value - that is, if the following line were uncommented,
    // it would cause an error
    // print("{}\n", .{response.value_ptr});
    //
    // But there is a key in the map:
    print("Is the key present? {}\n", .{map.contains(1)});

    // `response` tells us whether anything was found...
    if (!response.found_existing) {
        // ...so we can populate an (empty) list at that location...
        var list = std.ArrayList(u32).init(allocator);
        // This doesn't actually seem to work - see comment near the end of the function
        defer list.deinit();
        try map.put(1, list);
    }
    // And add a value to it
    try response.value_ptr.append(2);
    // For reasons I don't understand, `map.get(1).?.append(2)` doesn't work - the returned
    // pointer-to-ArrayList is immutable (`const`), thus preventing appending

    // Prove that it worked:
    print("The first value of the list is {}\n", .{map.get(1).?.items[0]});
    // I don't know why this is necessary, since I already called `defer list.deinit()` above -
    // but, without this, I get a memory leak reported
    map.get(1).?.deinit();
}

const std = @import("std");
const print = std.debug.print;

// Yes, these are low - see discussion below
const TIMES_TO_RUN_A_SINGLE_TEST = 5;
const NUMBER_OF_TESTS_TO_RUN = 5;

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Stolen from https://zig.guide/standard-library/random-numbers/
    var prng = std.Random.DefaultPrng.init(blk: {
        var seed: u64 = undefined;
        try std.posix.getrandom(std.mem.asBytes(&seed));
        break :blk seed;
    });
    const rand = prng.random();

    // I tried `= try allocator.alloc(u25, NUMBER_OF_TESTS_TO_RUN);`, and got `expected type '[5]u256', found '[]u256'`
    // :shrug:
    var pointer_based_times: [NUMBER_OF_TESTS_TO_RUN]u256 = undefined;
    for (0..NUMBER_OF_TESTS_TO_RUN - 1) |i| {
        pointer_based_times[i] = try timePointerBasedMethod(rand, allocator);
    }

    var non_pointer_based_times: [NUMBER_OF_TESTS_TO_RUN]u256 = undefined;
    for (0..NUMBER_OF_TESTS_TO_RUN - 1) |i| {
        non_pointer_based_times[i] = try timeNonPointerBasedMethod(rand, allocator);
    }

    print("Summary of pointer-based times: {}\n", .{summarizeTimes(pointer_based_times)});
    print("Summary of non-pointer-based times: {}\n", .{summarizeTimes(non_pointer_based_times)});
}

fn timePointerBasedMethod(rnd: std.Random, allocator: std.mem.Allocator) !u256 {
    var map = std.AutoHashMap(u32, std.ArrayList(u32)).init(allocator);
    defer map.deinit();
    const start_timestamp = std.time.nanoTimestamp();
    for (0..TIMES_TO_RUN_A_SINGLE_TEST - 1) |_| {
        const key = rnd.int(u32);
        const value = rnd.int(u32);
        const response = try map.getOrPut(key);
        if (!response.found_existing) {
            response.value_ptr.* = std.ArrayList(u32).init(allocator);
        }
        try response.value_ptr.append(value);
    }
    const time_elapsed = std.time.nanoTimestamp() - start_timestamp;
    var it = map.valueIterator();
    while (it.next()) |value| {
        value.deinit();
    }
    return try convertTou256(time_elapsed);
}

fn timeNonPointerBasedMethod(rnd: std.Random, allocator: std.mem.Allocator) !u256 {
    var map = std.AutoHashMap(u32, std.ArrayList(u32)).init(allocator);
    defer map.deinit();
    const start_timestamp = std.time.nanoTimestamp();
    for (0..TIMES_TO_RUN_A_SINGLE_TEST - 1) |_| {
        const key = rnd.int(u32);
        const value = rnd.int(u32);
        const response = try map.getOrPut(key);
        if (!response.found_existing) {
            try map.put(key, std.ArrayList(u32).init(allocator));
        }
        try response.value_ptr.append(value);
    }
    const time_elapsed = std.time.nanoTimestamp() - start_timestamp;
    var it = map.valueIterator();
    while (it.next()) |value| {
        value.deinit();
    }
    return try convertTou256(time_elapsed);
}

const ArithmeticError = error{NegativeTime};

fn convertTou256(n: i128) ArithmeticError!u256 {
    if (n < 0) {
        // This _should_ never happen!
        return ArithmeticError.NegativeTime;
    } else {
        return @intCast(n);
    }
}

// Plenty of other stats we could consider, like p90/p99, median, etc.
const Summary = struct {
    max: u256,
    mean: u256,
};

fn summarizeTimes(times: [NUMBER_OF_TESTS_TO_RUN]u256) Summary {
    var total_so_far: u256 = 0;
    var max_so_far: u256 = 0;
    // For some reason (probably to do with integer overflow :shrug:), I get the occasional time that is _wildly_ large -
    // like, 10^60 years big. I already spent an hour futzing with integer types trying to avoid this, to no avail - so
    // I'm just filtering out the nonsense instead to get usable data.
    var count_of_legal_times: usize = 0;
    for (times) |time| {
        if (time > 100000000) {
            continue;
        }
        total_so_far += time;
        if (time > max_so_far) {
            max_so_far = time;
        }
        count_of_legal_times += 1;
    }
    return Summary{ .max = max_so_far, .mean = @divFloor(total_so_far, count_of_legal_times) };
}