012 loop optimization nested

○ Planned This feature is planned but not yet implemented.

Feature: Nested loop optimization

Code

// PERFORMANCE TEST: Loop Optimization - Nested Loops (Triangular Pattern)
// Goal: Prove compiler detects nested loop patterns and transforms both levels
// Pattern: Outer checker event + inner checker event (like nbody calculate-interactions)
// Baseline: Hand-written nested Zig while loops
// Threshold: 1.05x (5% overhead max)
//
// This tests NESTED loop optimization:
// - Outer loop: i from 0 to limit
// - Inner loop: j from i+1 to limit (triangular pattern - depends on outer var!)
// - Both transformed to native loops

const std = @import("std");

// Inner loop checker: j from start to limit
~tor inner-step { i: u64, j: u64, limit: u64, sum: u64 }
| continue { i: u64, j: u64, sum: u64 }
| done { i: u64, sum: u64 }

~proc inner-step|zig {
    if (j < limit) {
        // Triangular sum: add i*limit + j
        const new_sum = sum + (i * limit + j);
        return .{ .continue = .{ .i = i, .j = j, .sum = new_sum } };
    } else {
        return .{ .done = .{ .i = i, .sum = sum } };
    }
}

// Outer loop checker: i from 0 to limit
~tor outer-step { i: u64, limit: u64, sum: u64 }
| continue { i: u64, limit: u64, sum: u64 }
| done u64

~proc outer-step|zig {
    if (i < limit) {
        return .{ .continue = .{ .i = i, .limit = limit, .sum = sum } };
    } else {
        return .{ .done = sum };
    }
}

// Print result
~tor print { result: u64 }

~proc print|zig {
    std.debug.print("Sum: {}\n", .{result});
}

// Main flow: Nested label loops
// Outer loop: i from 0 to 5000
// Inner loop: j from i+1 to 5000 (triangular - depends on i!)
//
// Expected transformation:
// for (0..5000) |i| {
//     for (i+1..5000) |j| {
//         sum += i * 5000 + j;
//     }
// }

~#outer outer-step(i: 0, limit: 5000, sum: 0)
| continue c_outer |> #inner inner-step(c_outer.i, j: c_outer.i + 1, c_outer.limit, c_outer.sum)
    | continue c_inner |> @inner(c_inner.i, j: c_inner.j + 1, c_outer.limit, c_inner.sum)
    | done d_inner |> @outer(i: d_inner.i + 1, c_outer.limit, d_inner.sum)
| done d_outer |> print(d_outer.result)

input.kz

Supporting Files

// Hand-written Zig baseline for nested loop optimization test
// This is what the Koru optimizer SHOULD generate from nested checker event patterns

const std = @import("std");

pub fn main() !void {
    var sum: u64 = 0;

    // Nested loops - triangular pattern (inner depends on outer)
    var i: u64 = 0;
    while (i < 5000) : (i += 1) {
        var j: u64 = i + 1;
        while (j < 5000) : (j += 1) {
            sum += i * 5000 + j;
        }
    }

    std.debug.print("Sum: {}\n", .{sum});
}

baseline.zig

#!/bin/bash
# Benchmark: Loop Optimization - Basic Checker Event Pattern
# Compare Koru optimized loop vs hand-written Zig for loop

set -e

echo "Building baseline (Zig)..."
zig build-exe baseline.zig -O ReleaseFast

echo "Building Koru version..."
# Assuming output_emitted.zig or output exists from test runner
if [ -f "output_emitted.zig" ]; then
    zig build-exe output_emitted.zig -O ReleaseFast -femit-bin=koru_output
elif [ -f "output" ]; then
    # Already compiled, copy it
    cp output koru_output
    chmod +x koru_output
else
    echo "ERROR: No Koru output found (output_emitted.zig or output)"
    exit 1
fi

echo ""
echo "Running benchmarks with hyperfine..."

# Check if hyperfine is installed
if ! command -v hyperfine &> /dev/null; then
    echo "ERROR: hyperfine not installed"
    echo "Install with: brew install hyperfine (macOS) or cargo install hyperfine"
    exit 1
fi

# Run benchmark
# Use --shell=none to avoid shell startup overhead
# Use more runs for better statistics on fast benchmarks
hyperfine --warmup 5 --runs 30 --shell=none \
    --export-json results.json \
    --command-name "Baseline (Zig)" './baseline' \
    --command-name "Koru (Optimized)" './koru_output'

echo ""
echo "Benchmark complete! Results saved to results.json"

benchmark.sh

Flows

flow ~outer-step click a branch to expand · @labels scroll to their anchor

#outer outer-step (i: 0, limit: 5000, sum: 0)

Test Configuration

MUST_RUN THRESHOLD 1.05

Post-validation Script:

#!/bin/bash
# Post-validation: Check performance is within threshold

set -e

if [ ! -f "results.json" ]; then
    echo "⚠️  No benchmark results found (results.json missing)"
    echo "   Running benchmark..."
    bash benchmark.sh
fi

if [ ! -f "results.json" ]; then
    echo "❌ FAIL: Benchmark did not produce results.json"
    exit 1
fi

# Check if jq is installed
if ! command -v jq &> /dev/null; then
    echo "⚠️  jq not installed (needed to parse benchmark results)"
    echo "   Install with: brew install jq (macOS) or apt install jq (Linux)"
    echo "   Skipping performance validation..."
    exit 0
fi

THRESHOLD=$(cat THRESHOLD)

# Parse results (hyperfine format)
BASELINE_TIME=$(jq -r '.results[0].mean' results.json)
KORU_TIME=$(jq -r '.results[1].mean' results.json)

# Calculate ratio (Koru / Baseline)
RATIO=$(echo "scale=4; $KORU_TIME / $BASELINE_TIME" | bc -l)

echo ""
echo "Performance Results:"
echo "  Baseline (Zig):     ${BASELINE_TIME}s"
echo "  Koru (Optimized):   ${KORU_TIME}s"
echo "  Ratio:              ${RATIO}x"
echo "  Threshold:          ${THRESHOLD}x"
echo ""

# Compare to threshold
if (( $(echo "$RATIO > $THRESHOLD" | bc -l) )); then
    echo "❌ PERFORMANCE REGRESSION!"
    echo "   Koru is ${RATIO}x slower than baseline"
    echo "   Threshold is ${THRESHOLD}x"
    echo "   Regression: $(echo "scale=1; ($RATIO - 1) * 100" | bc -l)%"
    exit 1
elif (( $(echo "$RATIO < 0.95" | bc -l) )); then
    echo "✅ PERFORMANCE IMPROVED!"
    echo "   Koru is FASTER than baseline (${RATIO}x)"
else
    echo "✅ Performance within threshold"
    echo "   Overhead: $(echo "scale=1; ($RATIO - 1) * 100" | bc -l)%"
fi

exit 0

← 011 loop optimization basic 013 loop optimization work →