beautiful_skips.zig

skips.zig

const std = @import("std");

pub fn skips(
    T: type,
    allocator: std.mem.Allocator,
    items: []const T,
) std.mem.Allocator.Error!struct { [][]T, []T } {
    var total_elements: usize = 0;
    for (1..items.len + 1) |stride| {
        total_elements += std.math.divCeil(usize, items.len + 1 - stride, stride) catch unreachable;
    }

    const skips_ = try allocator.alloc([]T, items.len);
    errdefer allocator.free(skips_);
    const data: []T = try allocator.alloc(T, total_elements);

    var remaining = data;
    for (skips_, 1..) |*sk, stride| {
        const num_steps = std.math.divCeil(usize, items.len + 1 - stride, stride) catch unreachable;
        sk.*, remaining = .{ remaining[0..num_steps], remaining[num_steps..] };

        for (0..num_steps) |step| {
            sk.*[step] = items[stride - 1 + step * stride];
        }
    }
    return .{ skips_, data };
}

test skips {
    const actual_skips, const data = try skips(u32, std.testing.allocator, &.{ 1, 2, 3, 4, 5, 6 });
    defer std.testing.allocator.free(actual_skips);
    defer std.testing.allocator.free(data);

    const expected_skips: []const []const u32 = &.{
        &.{ 1, 2, 3, 4, 5, 6 },
        &.{ 2, 4, 6 },
        &.{ 3, 6 },
        &.{4},
        &.{5},
        &.{6},
    };

    for (expected_skips, actual_skips) |expected, actual| {
        try std.testing.expectEqualSlices(u32, expected, actual);
    }
}

/// Run on MBP, M3.
///
/// zig run -OReleaseSafe skips.zig
/// Took 35.042us for materializing 1000 splits over 1000 items, with 7069 total elements
/// Took 4.114ms for materializing 100000 splits over 100000 items, with 1166750 total elements
/// Took 8.286s for materializing 100000000 splits over 100000000 items, with 1857511568 total elements
///
/// zig run -OReleaseFast skips.zig
/// Took 9.917us for materializing 1000 splits over 1000 items, with 7069 total elements
/// Took 987.958us for materializing 100000 splits over 100000 items, with 1166750 total elements
/// Took 4.837s for materializing 100000000 splits over 100000000 items, with 1857511568 total elements
pub fn main() !void {
    const allocator = std.heap.smp_allocator;

    var timer: std.time.Timer = try .start();

    inline for (.{ 1000, 100_000, 100_000_000 }) |len| {
        const items = try allocator.alloc(u32, len);
        defer allocator.free(items);

        timer.reset();
        const actual_skips, const data = try skips(u32, allocator, items);
        defer allocator.free(actual_skips);
        defer allocator.free(data);

        const lap = timer.lap();
        std.debug.print("Took {D} for materializing {d} splits over {d} items, with {d} total elements \n", .{ lap, actual_skips.len, len, data.len });
    }
}