b54e77d9bd78 — Nathan Michaels 10 months ago
Something iterating
3 files changed, 427 insertions(+), 0 deletions(-)

A => build.zig
A => src/iterators.zig
A => src/rangespeed.zig
A => build.zig +22 -0
@@ 0,0 1,22 @@ 
+const Builder = @import("std").build.Builder;
+
+pub fn build(b: *Builder) void {
+    const mode = b.standardReleaseOptions();
+    const lib = b.addStaticLibrary("iterators", "src/iterators.zig");
+    lib.setBuildMode(mode);
+    lib.install();
+
+    const target = b.standardTargetOptions(.{});
+    const exe = b.addExecutable("rangespeed", "src/rangespeed.zig");
+    exe.setTarget(target);
+    exe.setBuildMode(mode);
+    exe.setOutputDir(".");
+    exe.single_threaded = true;
+    exe.install();
+
+    var tests = b.addTest("src/iterators.zig");
+    tests.setBuildMode(mode);
+
+    const test_step = b.step("test", "Run library tests");
+    test_step.dependOn(&tests.step);
+}

          
A => src/iterators.zig +331 -0
@@ 0,0 1,331 @@ 
+//! This module contains iterators for use in while loops. Some
+//! iterators accept other iterators. Any struct that exposes a "next"
+//! method can be used with most of those, though some also require
+//! "reset".
+//!
+//! To use any iterator in this module, follow this pattern:
+//! var specialized = IterType(args).init();
+//! var iter = &specialized.iterator;
+//! while (iter.next()) |v| {
+//!     // Do things with v.
+//! }
+//!
+//! Note that these iterators' next methods all change the state of the
+//! iterators themselves. They can't be const and they shouldn't be
+//! shared across threads.
+const std = @import("std");
+
+pub fn Iterator(comptime T: type) type {
+    return struct {
+        const Self = @This();
+        nextFn: fn (self: *Self) ?T,
+        resetFn: fn (self: *Self) void,
+        pub fn next(self: *Self) ?T {
+            return self.nextFn(self);
+        }
+        pub fn reset(self: *Self) void {
+            return self.resetFn(self);
+        }
+    };
+}
+
+/// Half-open range type. Call next() on it to get values out. Example
+/// usage:
+///
+/// var range = try Range(u32, 1).init(0, 10);
+/// var iter = &range.iterator;
+/// while (iter.next()) |n| {
+///     std.debug.warn("{}\n", .{n});
+/// }
+pub fn Range(comptime T: type, step: T) type {
+    // Some profiling results, as run on an i5-9600KF: This is
+    // consistently a good deal slower than
+    // u32 i = 0; while (i < limit) : (i += 1) {}
+    // debug: 2.27 times the run time
+    // release-fast, release-safe: 5 times the run time
+    // release-small: 6 times the run time
+    //
+    // This is mostly due to the iterator construct. When calling
+    // Range's next directly, the comparison becomes much more
+    // favorable with all release modes running slightly faster
+    // (around 0.1%) than the idiomatic while loop and Debug taking
+    // about 7/4 as long.
+    //
+    // Note: when this was written (June 2020), passing
+    // --single-threaded to a release-fast build slowed idiomatic
+    // loops down by about a factor of 2. These benchmarks should
+    // probably be re-run when the compiler is more stable.
+    return struct {
+        iterator: Iterator(T),
+        next_val: T,
+        start: T,
+        end: T,
+        const Self = @This();
+
+        /// Return the next element in the range, or null if the range
+        /// has been exhausted.
+        pub fn next(iterator: *Iterator(T)) ?T {
+            const self = @fieldParentPtr(Self, "iterator", iterator);
+            const rv = self.next_val;
+            if (step < 0) {
+                if (rv <= self.end) {
+                    return null;
+                }
+            } else {
+                if (rv >= self.end) {
+                    return null;
+                }
+            }
+
+            self.next_val += step;
+            return rv;
+        }
+
+        /// Reset the range back to its start.
+        pub fn reset(iterator: *Iterator(T)) void {
+            const self = @fieldParentPtr(Self, "iterator", iterator);
+            self.next_val = self.start;
+        }
+
+        /// Initialize. Returns error if step size is invalid.
+        pub fn init(start: T, end: T) !Self {
+            if (step == 0) {
+                return error.ZeroStepSize;
+            }
+            return Self{
+                .next_val = start,
+                .start = start,
+                .end = end,
+                .iterator = Iterator(T){
+                    .nextFn = next,
+                    .resetFn = reset,
+                },
+            };
+        }
+    };
+}
+
+/// Reverse a slice. Example usage:
+///
+/// const word: []const u8 = "Word";
+/// var drow = Reversed(u8).init(word);
+/// var iter = &drow.iterator;
+/// while (drow.next()) |c| {
+///     std.debug.warn("{}", .{c});
+/// std.debug.warn("\n", .{});
+pub fn Reversed(comptime T: type) type {
+    return struct {
+        const Self = @This();
+        idx: ?usize,
+        slice: []const T,
+
+        /// Initialize with slice to be reversed.
+        pub fn init(slice: []const T) Self {
+            return Self{ .idx = slice.len - 1, .slice = slice };
+        }
+
+        /// Reset the iterator state to what it was when initialized.
+        pub fn reset(self: *Self) void {
+            self.idx = self.slice.len - 1;
+        }
+
+        /// Return the previous element in the slice, or null if the whole
+        /// slice has been consumed.
+        pub fn next(self: *Self) ?T {
+            var rv: T = undefined;
+            if (self.idx) |i| {
+                if (i == 0) {
+                    defer self.idx = null;
+                } else {
+                    defer self.idx = self.idx.? - 1;
+                }
+                return self.slice[i];
+            } else {
+                return null;
+            }
+        }
+    };
+}
+
+/// Convert a slice of T to an iterator that can be used with the
+/// other iterators in this module.
+pub fn SliceIter(comptime T: type) type {
+    return struct {
+        const Self = @This();
+        idx = ?usize,
+        slice: []const T,
+
+        /// Initialize with a slice.
+        pub fn init(slice: []const T) Self {
+            return Self{ .idx = 0, .slice = slice };
+        }
+
+        /// Reset the iterator to the start.
+        pub fn reset(self: *Self) void {
+            self.idx = 0;
+        }
+
+        /// Return the next element in the slice, or null if the whole
+        /// slice has been consumed.
+        pub fn next(self: *Self) ?T {
+            if (idx) |i| {
+                if (i < self.slice.len) {
+                    defer self.idx += 1;
+                } else {
+                    defer self.idx = null;
+                }
+                return self.slice[i];
+            } else {
+                return null;
+            }
+        }
+    };
+}
+
+pub fn Product(comptime T: type) type {
+    return struct {
+        const Self = @This();
+        // This would be better as a tuple. Note for when we get tuple
+        // types.
+        const Result = struct { a: T, b: T };
+
+        iterator: Iterator(Result),
+        a: *Iterator(T),
+        b: *Iterator(T),
+        next_a: T,
+        next_b: T,
+        done: bool = false,
+
+        pub fn next(iterator: *Iterator(Result)) ?Result {
+            const self = @fieldParentPtr(Self, "iterator", iterator);
+            if (self.done)
+                return null;
+            const prev_a = self.next_a;
+            const prev_b = self.next_b;
+            if (self.a.next()) |aa| {
+                self.next_a = aa;
+            } else {
+                self.a.reset();
+                if (self.a.next()) |aa| {
+                    self.next_a = aa;
+                } else {
+                    // a iterator is empty.
+                    return null;
+                }
+                if (self.b.next()) |bb| {
+                    self.next_b = bb;
+                } else {
+                    // b iterator has been exhausted; all done
+                    self.done = true;
+                }
+            }
+            return Result{ .a = prev_a, .b = prev_b };
+        }
+
+        pub fn reset(iterator: *Iterator(Result)) void {
+            const self = @fieldParentPtr(Self, "iterator", iterator);
+            self.a.reset();
+            self.b.reset();
+        }
+
+        pub fn init(a: *Iterator(T), b: *Iterator(T)) Self {
+            const prev_a = a.next().?;
+            const prev_b = b.next().?;
+            return Self{
+                .a = a,
+                .b = b,
+                .next_a = prev_a,
+                .next_b = prev_b,
+                .iterator = Iterator(Result){
+                    .nextFn = next,
+                    .resetFn = reset,
+                },
+            };
+        }
+    };
+}
+
+const testing = std.testing;
+test "range ascend" {
+    var range = try Range(u32, 1).init(0, 10);
+    var iter = &range.iterator;
+    var correct: u32 = 0;
+    while (iter.next()) |n| {
+        testing.expectEqual(correct, n);
+        correct += 1;
+    }
+    testing.expectEqual(correct, 10);
+    testing.expectEqual(iter.next(), null);
+}
+
+test "range descend" {
+    var range = try Range(i32, -1).init(10, 0);
+    var iter = &range.iterator;
+    var correct: i32 = 10;
+    while (iter.next()) |n| {
+        testing.expectEqual(correct, n);
+        correct -= 1;
+    }
+    testing.expectEqual(correct, 0);
+    testing.expectEqual(iter.next(), null);
+}
+
+test "range skip" {
+    var range = try Range(u32, 2).init(0, 10);
+    var iter = &range.iterator;
+    var correct: u32 = 0;
+    while (iter.next()) |n| {
+        testing.expectEqual(correct, n);
+        correct += 2;
+    }
+    testing.expectEqual(correct, 10);
+    testing.expectEqual(iter.next(), null);
+}
+
+test "range runtime" {
+    var start: u32 = 0;
+    while (start < 10) : (start += 1) {
+        var range = try Range(u32, 1).init(start, 10);
+        var iter = &range.iterator;
+        var correct: u32 = start;
+        while (iter.next()) |n| {
+            testing.expectEqual(correct, n);
+            correct += 1;
+        }
+        testing.expectEqual(correct, 10);
+        testing.expectEqual(iter.next(), null);
+    }
+}
+
+test "reverse" {
+    const word: []const u8 = "This is some text.";
+    var backwards = Reversed(u8).init(word);
+    var idx: isize = word.len - 1;
+    while (backwards.next()) |letter| {
+        testing.expectEqual(word[@intCast(usize, idx)], letter);
+        idx -= 1;
+    }
+    testing.expectEqual(idx, -1);
+}
+
+test "product" {
+    const R = Range(u32, 1);
+    var a = try R.init(0, 10);
+    var b = try R.init(10, 20);
+    var product = Product(u32).init(&a.iterator, &b.iterator);
+    var pi = &product.iterator;
+
+    var correct_a: u32 = 0;
+    var correct_b: u32 = 10;
+    while (pi.next()) |ab| {
+        testing.expectEqual(ab.a, correct_a);
+        testing.expectEqual(ab.b, correct_b);
+        correct_a += 1;
+        if (correct_a == 10) {
+            correct_a = 0;
+            correct_b += 1;
+        }
+    }
+    testing.expectEqual(correct_b, 20);
+    testing.expectEqual(pi.next(), null);
+}

          
A => src/rangespeed.zig +74 -0
@@ 0,0 1,74 @@ 
+const std = @import("std");
+const iterators = @import("iterators.zig");
+
+const test_loops = 100_000;
+
+fn standardLoop() void {
+    var n: u64 = 0;
+
+    while (n < test_loops) : (n += 1) {
+        asm volatile (""
+            :
+            :
+            : "memory"
+        );
+    }
+}
+
+fn iterLoop() !void {
+    var range = try iterators.Range(u64, 1).init(0, test_loops);
+    var iter = &range.iterator;
+    while (iter.next()) |_| {
+        asm volatile (""
+            :
+            :
+            : "memory"
+        );
+    }
+}
+
+fn hackyFastLoop() !void {
+    const Range = iterators.Range(u64, 1);
+    var range = try Range.init(0, test_loops);
+    var iter = &range.iterator;
+    while (Range.next(iter)) |_| {
+        asm volatile (""
+            :
+            :
+            : "memory"
+        );
+    }
+}
+
+pub fn main() anyerror!void {
+    // Range comparison
+    var n: u64 = 0;
+    const start = std.time.nanoTimestamp();
+    while (n < test_loops) : (n += 1) {
+        standardLoop();
+    }
+    const end = std.time.nanoTimestamp();
+    const stdout = std.io.getStdOut().writer();
+    try stdout.print("Normal Zig-style: {}ns\n", .{(end - start)});
+
+    n = 0;
+    const iterstart = std.time.nanoTimestamp();
+    var range = try iterators.Range(u64, 1).init(0, test_loops);
+    var iter = &range.iterator;
+    while (iter.next()) |_| {
+        try iterLoop();
+    }
+    const iterend = std.time.nanoTimestamp();
+    try stdout.print("Iterator-style:   {}ns\n", .{(iterend - iterstart)});
+
+    n = 0;
+    const hackystart = std.time.nanoTimestamp();
+    const Range = iterators.Range(u64, 1);
+    range = try Range.init(0, test_loops);
+    iter = &range.iterator;
+    while (Range.next(iter)) |_| {
+        try hackyFastLoop();
+    }
+    const hackyend = std.time.nanoTimestamp();
+    try stdout.print("Hacky fast-style: {}ns\n", .{(hackyend - hackystart)});
+}