The Scoreboard Is a Formula: Systems Rust for Speed Demon 2026

The scoreboard in a systems competition does not time your program; it evaluates a mathematical function.

Building engines for Speed Demon 2026 across Tracks A (Ingest), C (Join), and D (Traverse) with zero external Rust crate dependencies, our initial instinct was to chase the clock. But the harness did not evaluate raw latency alone. It evaluated a multi-variable objective function balancing wall-clock runtime ($T$), peak memory working set ($M$), stripped source line count ($S$), and external dependency weight ($D$).

Treating the scoreboard as a formal optimization problem inverted our systems engineering priorities:

• We permitted working memory to expand when runtime rewards outweighed memory penalties.
• We avoided all external crates to bypass an immediate 9.88% dependency penalty.
• We overhauled our benchmarking harness when Windows cold-start phenomena introduced a 35 to 50 ms measurement bias.
• We made the hot execution path boring: dynamic hash tables and pointer indirections were replaced by flat contiguous arrays, dense integer ranks, and Compressed Sparse Row (CSR) tables.

This formula-driven approach unlocked sub-second execution across multi-million record datasets, with Track A achieving an official Linux leaderboard score of 76.622 points at 0.038 seconds.

TL;DR:

1. Optimize the formula, not just the clock: Runtime dominates memory with a 2.5:1 sensitivity ratio ($T^{0.50}$ vs $M^{0.20}$). However, adding a single external crate levies an immediate 9.88% penalty on $K$ ($D^{0.15}$), requiring an 18.8% reduction in runtime just to break even. We operated with zero external Rust crate dependencies ($D = 1.0$), relying on the Rust standard library, direct POSIX FFI, and architecture-specific SIMD intrinsics.
2. Make the hot path boring: Dynamic hash tables introduce pointer indirection, non-contiguous memory access, and dynamic reallocations. Replacing dynamic maps with flat lookup arrays, dense integer ranks, and Compressed Sparse Row (CSR) tables eliminated pointer chasing and reduced wall-clock latency across all tracks.
3. Verify the benchmark first: Unwarmed executions on Windows imposed a 35 to 50 ms cold-start penalty on whichever binary executed first in an alternating sequence. Pre-run warmups and randomized trial ordering reduced observed order bias to 1.71 ms ($p = 0.4359$, showing no detectable order effect), while a separate paired difference test supported a measurable 4.04 ms speedup ($p = 4.62\times 10^{-4}$).

Headline Results: Track A scored 76.622 points officially on the Linux scoring runner (0.038 s, 31 MB peak working set as reported on the leaderboard). Tracks C and D achieved 0.1275 s (54.64 MB peak working set) and 0.6600 s (160 MB peak working set) in local benchmark measurements on our development host; official competition scores for C and D remain unmeasured.

The Scoreboard Is a Formula: Why Clock Chasing Failed

In Speed Demon 2026, the efficiency coefficient $K$ and speed points are computed using four orthogonal axes:

K = (T_ref / T)^0.50 * min(M_ref / M, 50)^0.20 * min(S_ref / S, 1)^0.15 * (D_ref / D)^0.15
points = 50 * log10(K)

Per scoring.py line 57, speed points scale logarithmically with $K$. The reference baselines evaluated on the official Linux harness come from the competition kit (calibration-seed1.json and reference_axes.json):

Status and reference baselines:

• Track A Official Submission: Commit 7168b09 is the sole evaluated official submission, achieving $K = 34.074745$ (76.622 points, 0.038 s, 31 MB as shown on the leaderboard, 286 scored lines).
• Track A Candidate: Candidate commit adbd3f1 was tested strictly locally on our Windows development host as a native executable (improving paired median runtime from 63.86 ms to 59.59 ms, $p = 4.62\times 10^{-4}$); it was not evaluated on the official leaderboard.
• Tracks C and D: Have no official scores. Line counts (454 and 802) are raw, unformatted source counts from track-c/src/main.rs and track-d/src/main.rs; memory figures report peak working set in MB as logged locally in track-c/PERF.md and track-d/PERF.md.

Official Linux Harness Reference Baselines

All reference baselines use (D_{\text{ref}} = 1) across all tracks.

• Track A: (T_{\text{ref}} = 32.047276\text{ s}), (M_{\text{ref}} = 217\text{ MiB}) (227,983,360 bytes), (S_{\text{ref}} = 56)
• Track C: (T_{\text{ref}} = 14.444059\text{ s}), (M_{\text{ref}} = 350\text{ MiB}) (367,435,776 bytes), (S_{\text{ref}} = 108)
• Track D: (T_{\text{ref}} = 72.692655\text{ s}), (M_{\text{ref}} = 851\text{ MiB}) (892,915,712 bytes), (S_{\text{ref}} = 43)

Mathematical Sensitivity & Exponent Derivation

The scoring exponents dictate our system architecture:

∂(points)/∂ ln(1/T)       0.50
───────────────────  =  ──────  =  2.50
∂(points)/∂ ln(1/M)       0.20

1. Runtime Dominates Memory (Sensitivity Ratio 2.5:1): Wall-clock runtime is uncapped, and its exponent ($0.50$) is 2.5 times larger than the memory exponent ($0.20$). A 1% reduction in runtime produces the same point increase as a 2.5% reduction in memory. Therefore, any architectural optimization that reduces memory at the expense of runtime must satisfy:

$$\frac{T_{\text{new}}}{T_{\text{old}}} < \left( \frac{M_{\text{old}}}{M_{\text{new}}} \right)^{0.20 / 0.50} = \left( \frac{M_{\text{old}}}{M_{\text{new}}} \right)^{0.40}$$

1. The 9.88% Crate Tax ($D_{\text{ref}} = 1, D^{0.15}$): Per final_scoring.py line 275, $D = 1 + \text{direct_dependencies}$, and $D_{\text{ref}} = 1$. Importing even a single external crate moves $D$ from 1 to 2. The dependency factor drops to:

$$(1 / 2)^{0.15} \approx 0.901250 \quad (-9.875\%)$$

This imposes an immediate deduction of:

$$\Delta \text{points} = 50 \times \log_{10}(0.901250) \approx -2.258\text{ points}$$

To offset this loss purely through execution speed, the new runtime $T'$ must satisfy:

$$(T / T')^{0.50} \times 0.901250 \ge 1 \implies \frac{T}{T'} \ge (1 / 0.901250)^2 = 2^{0.30} \approx 1.23114$$

An external crate must make your program at least 23.11% faster (reducing runtime by $18.78\%$) merely to break even. Rather than taking on this dependency penalty against generic libraries, we implemented zero external Rust crate dependencies ($D = 1.0$), using standard library primitives, direct POSIX FFI, and architecture-specific SIMD intrinsics.

1. The 50x Memory Cap & The Track A Multi-Pass Trade-Off: The memory term is clamped at $\min(M_{\text{ref}} / M, 50)^{0.20}$. Beyond a 50x reduction, further memory cuts yield exactly zero additional points. For Track A ($M_{\text{ref}} = 227,983,360\text{ bytes}$), the cap occurs at:

$$M_{\text{cap}} = \frac{227,983,360}{50} = 4,559,667\text{ bytes} \approx 4.56\text{ MB}$$

Because retaining 3.1 million raw log records in RAM takes over 6.2 MB even with packed 16-bit integers, hitting this cap would require streaming from disk in multiple passes. In our experimental 4-pass streaming prototype (evidence/multipass_experiment.txt), peak working set dropped from ~30 MB to approximately 19.69 MB. However, re-reading chunks from disk on the same Windows test host increased mean runtime from ~63.8 ms to ~223.8 ms (runs logged between 208.58 and 246.19 ms).

Because this 3.5x runtime slowdown far exceeded the allowable threshold $(\frac{30}{19.69})^{0.40} \approx 1.18$, multi-pass streaming was decisively discarded.

1. The Streaming Buffer Penalty in Track C: In iteration v5 (track-c/PERF.md:145-155), switching from memory mapping to 1 MiB chunk streaming cut peak working set by 48.2% (from 379.29 MB to 196.27 MB, saving 183 MB). However, managing record splits and quoted field boundaries across chunk edges increased runtime by 45.3% (from 0.4933 s to 0.7168 s).

Applying the formula:

$$\text{Factor on } K = \left(\frac{379.29}{196.27}\right)^{0.20} \times \left(\frac{0.4933}{0.7168}\right)^{0.50} = 1.1408 \times 0.8296 = 0.9464 \quad (-5.36\%)$$

The net score dropped by $1.20\text{ points}$. In iteration v6, we discarded chunk streaming in favor of whole-file memory mapping with 64-bit hash sorting, which dropped runtime to 0.1275 s and peak working set to 54.64 MB simultaneously.

When Our Benchmark Lied to Us: The Windows Cold-Start Trap

Before trusting performance data, we had to fix our benchmark harness.

During early Track A development on Windows 11, paired A/B benchmarks exhibited severe measurement hysteresis: whichever executable ran first in an alternating sequence suffered an artificial 35 to 50 ms penalty.

Unwarmed Alternating Runs (Raw Wall Clock):
Run 1 (Binary A, Cold):  112.4 ms  <-- Absorbs initialization overhead
Run 2 (Binary B, Warm):   64.1 ms  <-- Benefits from warm file & system caches
Run 3 (Binary B, Cold):  108.9 ms  <-- Reversal: B absorbs initialization overhead
Run 4 (Binary A, Warm):   63.7 ms  <-- A runs fast

Plausible Contributing Factors

While we did not instrument low-level Windows kernel events using ETW (Event Tracing for Windows), plausible contributing factors include:

• NTFS Path and Metadata Caching: First-time directory parsing and handle resolution incur file-system lock acquisition and disk metadata traversal.
• Virtual Memory Allocation & Soft Faults: The initial process allocation must commit pages from the zeroed-page pool; subsequent process spawns benefit from standby page list reuse.
• CPU Frequency Scaling & Power States: Modern processors (such as the Intel Core i5-13420H) transition through hardware P-states and Intel SpeedStep scaling. Unwarmed binaries execute while the CPU frequency ramps up from idle governor states.

The Corrected Experimental Protocol

To address this measurement artifact, we revised our benchmark protocol with two safeguards:

1. Mandatory Untimed Warmups: Every measured binary executed an untimed preliminary run immediately before the timed trials to populate OS file-system cache and transition the CPU core to active performance states.
2. Randomized Trial Sequencing: In each paired comparison $i \in {1 \dots 30}$, execution order was randomly chosen between baseline-first ($B\text{-first}$) and candidate-first ($C\text{-first}$) using randomized trial ordering (pseudo-random selection via Python's standard random generator with a fixed seed).

Warmup & Randomized Protocol:
[Untimed Warmup B] -> [Untimed Warmup C]
Trial 1: Random(B, C) -> Timed C -> Timed B
Trial 2: Random(B, C) -> Timed B -> Timed C
...
Trial 30: Random(B, C) -> Timed C -> Timed B

Statistical Analysis: Order Bias vs. Paired Speedup

Our audit of the 30 paired validation runs (evidence/cold_start_benchmarks.txt) revealed two distinct statistical dimensions:

Benchmark Dataset: Track A full-seed1 (3,100,000 lines, 72 hours)
Sample Size: N = 30 paired runs
Baseline (commit 7fe5e92):   Median = 63.86 ms | Mean = 63.79 ms | SD = 3.75 ms
Candidate (commit adbd3f1):  Median = 59.59 ms | Mean = 59.75 ms | SD = 3.75 ms
Paired Difference (B - C):   Median = +3.69 ms | Mean = +4.04 ms

1. The Order Effect Audit ($p = 0.4359$): Stratifying the trials by execution sequence:
   • When Baseline ran first ($N_B = 13$): Mean paired difference $= +5.01\text{ ms}$, Median $= +4.10\text{ ms}$
   • When Candidate ran first ($N_C = 17$): Mean paired difference $= +3.30\text{ ms}$, Median $= +3.59\text{ ms}$
   • Observed order bias ($\bar{d}_B - \bar{d}_C$): $1.71\text{ ms}$
   • Welch's two-sample $t$-test: $t = 0.7935$, degrees of freedom $\text{df} = 25.8$, $p = 0.4359$

Statistical Interpretation: The high $p$-value ($p = 0.4359$) indicates that the difference in observed speedup between orderings is statistically indistinguishable from zero noise. However, failing to reject the null hypothesis of order bias does not prove that bias is entirely absent, nor does it establish that the candidate code is faster.

1. The Paired Performance Difference ($p = 4.62\times 10^{-4}$): The statistical evidence for performance improvement is provided separately by the paired difference Student's $t$-test across the 30 trials:

$$t = \frac{\bar{d}}{\text{SE}_d} = \frac{4.04\text{ ms}}{1.0237\text{ ms}} = 3.9466 \quad (\text{df} = 29)$$

• Two-tailed $p$-value: $p = 4.62 \times 10^{-4}$
• 95% Confidence Interval for mean difference: $[1.95\text{ ms}, 6.13\text{ ms}]$
• Cohen's $d_z$ effect size: $d_z = \frac{4.04}{5.61} \approx 0.72$ (medium-to-large effect)

Under this paired testing protocol, Candidate Minimized (adbd3f1) demonstrated a statistically significant paired mean runtime reduction of 4.04 ms ($p = 4.62\times 10^{-4}$, 95% CI: $[1.95\text{ ms}, 6.13\text{ ms}]$) relative to the baseline on our Windows development host. Crucially, this local improvement is distinct from the official Linux leaderboard result (0.038 s on commit 7168b09), as Windows measurements include file-system and scheduling overhead inherent to the local OS.

Architecture Evolution Across Tracks

To achieve sub-second execution without external crates, each track evolved from conventional idiomatic Rust into flat, hardware-friendly data pipelines:

flowchart TD
    subgraph TrackA["Track A: Ingest Pipeline"]
        A1["Raw Log Stream (3.1M lines)"] --> A2["Parallel Chunk Slicing via std::thread::scope"]
        A2 --> A3["64-bit Unaligned SWAR Parse<br>(p+5: month, day, hour in 1 read)"]
        A3 --> A4["Direct Endpoint Rank Lookup<br>(CRC32 + Linear Probing, Rank below 1,842)"]
        A4 --> A5["Direct Bucket Scatter<br>(ep_buckets[rank].push(lat))"]
        A5 --> A6["Parallel pdqsort on Small Slices<br>(Avoids sorting full 32K hourly arrays)"]
    end

    subgraph TrackC["Track C: Join Pipeline"]
        C1["Hostile CSV File (3.32M rows)"] --> C2["Memory-Mapped Slice (direct POSIX mmap FFI)"]
        C2 --> C3["256-bit AVX2 SIMD Quote Scanner<br>(_mm256_cmpeq_epi8 + trailing_zeros)"]
        C3 --> C4["1 MB Flat Region Vector<br>(O(1) array read for region_id below 1M)"]
        C4 --> C5["64-bit Multiplicative Hash<br>(hash_slice into u64)"]
        C5 --> C6["Thread-Local Vector Sort and Dedup<br>(madvise advisory hints in 8 MB chunks)"]
    end

    subgraph TrackD["Track D: Traverse Pipeline"]
        D1["Graph Data (1.74M nodes, 5M edges)"] --> D2["Two-Pass Parallel CSR Build<br>(Atomic counts + Relaxed cursor stores)"]
        D2 --> D3["Packed 6-Byte Edge Arrays<br>(repr(C, packed) Edge: u32 to, u16 weight)"]
        D3 --> D4["Balanced Bidirectional Dijkstra<br>(Expand smaller frontier, tie resolves to forward)"]
        D4 --> D5["2 MB Thread-Local SmallMap<br>(Key + Val in contiguous 8-byte MapEntry)"]
        D5 --> D6["4-Ary Flattened Min-Heap<br>(Heap4Fast: halved tree depth)"]
    end

Track A: Ingest (Sub-40 Milliseconds in Plain Rust)

The Problem in One Sentence

Ingest 3,100,000 lines of space-delimited logs spanning a 72-hour window, extract microsecond timestamps, intern 1,842 endpoints, and compute hourly p50, p90, and p99 latencies without external crates (specs/a-ingest.md).

Profiling: Where the Time Actually Went

Instrumentation of Phase 2 with profile_phase2.rs (evidence/transcript_step889_profile.txt) across 12 worker threads revealed 215.48 ms of cumulative CPU time (23.35 ms wall-clock time):

• pdqsort: 91.29 ms (42.4% CPU share)
• Formatting and percentiles: 91.71 ms (42.6% CPU share)
• Writer mutex serialization: 20.85 ms (9.7% CPU share)
• Key packing: 11.64 ms (5.4% CPU share)

Sorting latencies was our primary compute bottleneck: merging records into a single hourly array forced sorting $\sim 32,291$ keys per active hour.

The Optimization: Direct Bucket Scattering

Instead of grouping latencies into a unified hourly buffer and sorting the entire array, we scattered latencies directly into per-endpoint rank vectors during parsing:

ep_buckets[rank].push(lat);

Sorting small, per-endpoint vectors in parallel was substantially faster than sorting one large array. In a strict 30-pair benchmark on our Windows development host, direct bucket scattering dropped paired median runtime from 63.86 ms to 59.59 ms ($p = 4.62\times 10^{-4}$).

Sorting Micro-Benchmarks vs. End-to-End Execution

To evaluate sorting strategies for Phase 2, we benchmarked three isolated sorting kernels on the active hour data (evidence/transcript_steps898_913_sorts.txt):

• Counting Sort (cand_p2_counting.exe): Median = 79.00 ms (allocating and scanning 65,536 frequency bins was penalized by cache clearance overhead).
• 2-Pass Radix Sort (cand_p2_radix.exe): Median = 53.26 ms (two 8-bit passes over latency keys).
• Direct Slice Scatter (cand_p2_direct.exe): Median = 51.42 ms (direct push into rank vectors followed by standard pdqsort on populated slices).

Clarification: The 51.42 ms figure was an isolated micro-benchmark measuring Phase 2 latency sorting alone. The 59.59 ms figure represents the complete end-to-end binary execution (including disk I/O, timestamp parsing, endpoint interning, Phase 2 sorting, and stdout formatting).

Approach & Annotated Code Snippet

Log timestamps follow RFC 3339 within a strict 72-hour window (2026-10-30T18:00:00 to 2026-11-02T17:59:59.999999Z). We parse them branchlessly at byte offset $p + 5$ using an unaligned 64-bit SWAR (SIMD Within A Register) read:

// SWAR timestamp parse: single unaligned 64-bit load at byte offset p + 5
let w_ts = unsafe { (b.as_ptr().add(p + 5) as *const u64).read_unaligned() };
let m = ((w_ts >> 8) & 0xFF) as usize - 48;
let d = (((w_ts >> 24) & 0xFF) as usize - 48) * 10
    + (((w_ts >> 32) & 0xFF) as usize - 48);
let hr = (((w_ts >> 48) & 0xFF) as usize - 48) * 10
    + (((w_ts >> 56) & 0xFF) as usize - 48);
// Compute hour bucket index (ranges 18..89 inside 96 slots) via arithmetic
let h = ((d + 31 * m) - 30) * 24 + hr;

Detailed Arithmetic Trace & Specialization Invariants:

On a little-endian x86-64 architecture, loading 8 bytes from offset $p + 5$ of the 27-byte timestamp "YYYY-MM-DDTHH:MM:SS.ffffffZ " maps characters into register w_ts:

• Byte 0 (offset 5): '1' (first digit of month)
• Byte 1 (offset 6): '0' for October ($m = 0$), '1' for November ($m = 1$)
• Byte 2 (offset 7): '-'
• Byte 3 (offset 8): Day tens digit ('3' or '0')
• Byte 4 (offset 9): Day units digit ('0', '1', or '2')
• Byte 5 (offset 10): 'T'
• Byte 6 (offset 11): Hour tens digit ('0', '1', or '2')
• Byte 7 (offset 12): Hour units digit ('0' through '9')

Because October has 31 days, November days are offset by $+31$. For Oct 30, $h = (30 - 30) \times 24 + hr = hr \in [18, 23]$. For Nov 2, $h = (2 + 31 - 30) \times 24 + hr = 72 + hr \in [72, 89]$. The entire 72-hour window maps cleanly into hours $18 \dots 89$ within a 96-slot array in zero branches and zero heap allocations.

Important Boundary Invariant: This parser is strictly specialized for the competition dataset: it assumes little-endian byte ordering, a fixed 4-digit year of 2026, fixed 2-digit fields, 6 fractional digits, and dates restricted to Oct 30–Nov 02. It is not a general RFC 3339 parser. Input from other months or variable fractional lengths would produce invalid hour indices or out-of-bounds array writes.

Track A Progression Milestones

Track C: Join (Hostile CSVs and the Zero-Collision Gamble)

The Problem in One Sentence

Parse 3,320,000 rows of hostile, multi-line quoted CSV records, join them against 2.2 MB of regional geographic mappings, and compute aggregates and distinct name counts across 240 countries without external crates (specs/c-join.md).

The Zero-Collision Gamble: Probabilistic Hashing

Distinct name counting across 3,320,000 records was our main bottleneck. In our initial v1 baseline using a per-country HashSet<Vec<u8>>, execution took 5.5230 s with a peak working set of 405.69 MB (track-c/PERF.md:11-13).

We replaced heap-allocated string storage with a custom 64-bit multiplicative hash (hash_slice in track-c/src/main.rs:34-45):

#[inline(always)]
unsafe fn hash_slice(mut p: *const u8, len: usize) -> u64 {
    let mut h = (len as u64) ^ 0x517cc1b727220a95;
    let mut rem = len;
    while rem >= 8 {
        let v = (p as *const u64).read_unaligned();
        h = (h ^ v).rotate_left(27).wrapping_mul(0x94d049bb133111eb);
        p = p.add(8);
        rem -= 8;
    }
    if rem > 0 {
        let mut tail = 0u64;
        std::ptr::copy_nonoverlapping(p, &mut tail as *mut u64 as *mut u8, rem);
        h = (h ^ tail).rotate_left(27).wrapping_mul(0x94d049bb133111eb);
    }
    h
}

In Phase 2, each country's 64-bit hash vectors were merged, sorted with sort_unstable(), and deduplicated with dedup(). The final vector length provided the distinct count.

Birthday Bound Derivation & Idealized Assumptions:

Under the assumption of an idealized uniform and independent random hash function, the probability $p$ of observing at least one collision among $n = 100{,}520$ distinct names in a $2^{64}$ hash space is given by the classical birthday-bound approximation:

$$p \approx \frac{100520 \times 100519}{2 \times 2^{64}} = \frac{10,104,169,880}{3.68935 \times 10^{19}} \approx 2.7387 \times 10^{-10}$$

This calculation yields approximately 1 in 3.65 billion ($1 / (2.7387 \times 10^{-10}) \approx 3.651 \times 10^9$).

Distinction of Theoretical vs. Empirical Guarantees:

• Idealized Model vs. Custom Function: The $2.7387 \times 10^{-10}$ figure is derived assuming a uniform random oracle. It is not a formal upper bound for our custom SplitMix-style multiplicative hash function (hash_slice), which could exhibit higher collision rates under adversarial or structured string patterns.
• Empirical String Set Audit: To verify correctness on actual data, we audited full-seed1 against an exact Python baseline. The audit extracted all original unescaped name strings into an exact Python set of strings, confirming 100,520 distinct strings. Hashing each string with hash_slice produced 100,520 distinct 64-bit integers. No hash collisions were observed among the 100,520 distinct strings in this dataset (track-c/PERF.md:184-189).
• Formal Correctness Scope: Probabilistic hashing remains a calculated trade-off. While it achieved 100% test pass rates and enabled dropping peak working set to 54.64 MB and execution time to 0.1275 s, it does not provide the deterministic exactness guarantee required of a general-purpose database engine.

Approach & Annotated Code Snippet

In our final design, records.csv is mapped via direct POSIX FFI using a manually declared extern "C" mmap binding. Worker threads scan records using 256-bit AVX2 SIMD intrinsics while issuing madvise(..., MADV_DONTNEED) advisory requests in 8 MB batches (track-c/src/main.rs:27-31):

// AVX2 256-bit SIMD scanner: locate quote delimiter across 32 bytes in parallel
while q.add(32) <= end_ptr {
    let chunk = _mm256_loadu_si256(q as *const __m256i);
    let mask = _mm256_movemask_epi8(_mm256_cmpeq_epi8(chunk, v_quote)) as u32;
    if mask != 0 {
        q = q.add(mask.trailing_zeros() as usize);
        break;
    }
    q = q.add(32);
}

Advisory Nature of madvise: madvise(..., MADV_DONTNEED) is an advisory request to the operating system kernel indicating that mapped pages are no longer needed. It does not guarantee immediate physical page-cache reclamation or immediate resident memory release; its actual effect on working-set memory depends on kernel page reclamation policy, memory pressure, and whether the mapping is private or shared.

Memory Safety Invariant: The loop condition q.add(32) <= end_ptr guarantees that vector loads never cross past the end of the memory-mapped file slice. Tail bytes are processed by a scalar fallback loop.

Track C Progression Milestones

Track D: Traverse (2,000 Shortest Paths in Sub-Second Runtime)

The Problem in One Sentence

Navigate a 1,740,512-node, 5,000,000-edge directed graph to answer 2,000 shortest-path point-to-point queries under 1 GB of memory without external crates (specs/d-traverse.md).

The Bidirectional Memory Explosion

In iteration v3, unidirectional Dijkstra across 12 worker threads answered 2,000 queries on full-seed1 in 2.5154 s (track-d/PERF.md:34-37). In v4, balanced bidirectional Dijkstra dropped runtime to 0.8019 s (a 3.14x speedup, track-d/PERF.md:52-55).

However, peak working set exploded from 223.79 MB to 418.71 MB. Because storing two 64-bit distance arrays across 1,740,512 nodes required 14 MB per array, 12 concurrent worker threads consumed:

$$12 \times 2 \times 13.92\text{ MB} = 334.18\text{ MB of distance arrays alone}$$

The Solution: Thread-Local SmallMap & Packed Edges

To resolve this explosion, we implemented SmallMap (track-d/src/main.rs:150-208): a thread-local open-addressing table with linear probing. Because road network queries explore only a small fraction of the 1.74M node graph, each thread allocates a 2 MB table ($2^{18} = 262,144$ entries) storing packed 8-byte MapEntry structs.

#[derive(Clone, Copy)]
#[repr(C)]
struct MapEntry {
    key: u32,
    val: u32,
}

Cache Terminology Note: While this 2 MiB per-thread table was designed with CPU L3 cache budgets in mind (the host Core i5-13420H features a 12 MB shared L3 cache), we did not instrument PMU hardware performance counters (such as L3 miss rates). We characterize SmallMap strictly as a compact in-memory thread-local flat structure.

Settled Nodes vs. Explored Entries & Table Capacity Limits

In analyzing SmallMap, we must explicitly distinguish between two graph search metrics:

1. Settled Nodes: Nodes popped from the priority queue whose shortest distances are final.
2. Explored/Reached Entries: Every neighboring node encountered during edge relaxation is probed via probe_entry. If new, it is inserted into SmallMap and its slot index is pushed to touched.

In dense road networks, the count of explored nodes in the active frontier is substantially larger than the count of settled nodes.

Capacity Limits & Termination Behavior:
SmallMap allocates a fixed capacity of 262,144 entries ($2^{18}$). It uses multiplicative Fibonacci hashing ((k as usize).wrapping_mul(0x9e3779b9) & mask) and linear probing (idx = (idx + 1) & mask). Crucially, the implementation contains no load-factor limits, no dynamic resizing, and no maximum probe length limit.
If a search on an adversarial or dense graph causes the number of distinct explored nodes to reach 262,144 (a 100% load factor), probe_entry will enter an infinite loop scanning the table, freezing the worker thread. For the competition dataset full-seed1, query frontiers touched far fewer than 262,144 nodes, keeping probe sequences short.

Distance Overflow Guard & dijkstra64 Behavior

Tracing the edge relaxation logic in track-d/src/main.rs:656-659:

let nd = df + ew;
if nd >= best || nd >= 65534 {
    continue;
}

Every distance relaxation in both forward and backward searches is guarded by:
if nd >= best || nd >= 65534 { continue; }.

Analysis of the Overflow Invariant:

1. No 16-Bit Integer Wraparound in Fast Path: Because the search immediately drops any relaxation where $nd \ge 65,534$, nd is guaranteed to be $< 65,534$ when executing let nd16 = nd as u16;. Therefore, nd as u16 does not wrap around modulo 65,536 during table updates.
2. Pruning of Cumulative Distances $\ge 65,534$: The bidirectional fast path cannot discover shortest paths whose cumulative length is $\ge 65,534$; such transitions are pruned.
3. Fallback Limitations: When the search finishes, it evaluates:

   let ans = if best != u32::MAX {
       best as i64
   } else if had_large {
       dijkstra64(&head_ref, &edges_ref, &large_ref, s, t)
   } else {
       -1
   };

Notice that had_large is set only when an individual edge weight is 65,535 (if ew == 65535 { had_large = true; }). The fallback dijkstra64 uses 64-bit distances and resolves large edge weights via large_map. It was designed specifically to handle individual edge-weight overflow.
If a graph contains a reachable path whose cumulative distance exceeds 65,534 composed solely of smaller edge weights ($< 65,535$), had_large remains false. The fast path prunes the route, best remains u32::MAX, and the function returns -1 (unreachable). On full-seed1, all 2,000 queries were answered with 100% digest precision because query distances remained within limits or traversed large-weight links. For general graphs, however, this remains an architectural limitation.

Edge Memory Layout & Rust Alignment Verification

The graph edge structure is declared in track-d/src/main.rs:24-28:

#[derive(Clone, Copy)]
#[repr(C, packed)]
struct Edge {
    to: u32,
    weight: u16,
}

Alignment Audit: In standard Rust, an unadorned struct Edge { to: u32, weight: u16 } would have size_of = 8 and align_of = 4 due to 2 bytes of trailing alignment padding. Because we explicitly declared #[repr(C, packed)], padding was eliminated:

• size_of::<Edge>() is exactly 6 bytes.
• align_of::<Edge>() is 1 byte.

Across 5,000,000 edges, this dropped CSR graph memory from 40 MB to 30 MB (a 25% reduction). To avoid undefined behavior from taking unaligned references (&edge.to), code always reads fields by value copy (let to = e.to;), compiling to unaligned 32-bit register loads supported natively by x86-64 hardware.

Distinguishing Iterations v5 and v6

• Iteration v5 (0.7400 s median, 160 MB peak working set): Introduced packed 6-byte edges, custom 4-ary min-heap (Heap4Fast), and the initial 2 MB SmallMap (track-d/PERF.md:77-80).
• Iteration v6 (0.6600 s median, 0.5500 s minimum, 160 MB peak working set): Unified key and value into contiguous 8-byte MapEntry structs, implemented direct slot index resetting (clear_slots), and preallocated worker buffers (65,536 elements for Heap4Fast and 131,072 elements for touched), eliminating dynamic allocations during search (track-d/PERF.md:95-97).

Approach & Annotated Code Snippet

To maximize spatial locality, probe_entry performs membership checking and slot reservation in a single probe sequence:

// Unified probe: check membership and reserve slot in a single probe sequence
fn probe_entry(&mut self, k: u32) -> (usize, u32, bool) {
    let mut idx = (k as usize).wrapping_mul(0x9e3779b9) & self.mask;
    loop {
        let entry = unsafe { self.entries.get_unchecked(idx) };
        if entry.key == k { return (idx, entry.val, false); }
        if entry.key == !0u32 {
            unsafe { self.entries.get_unchecked_mut(idx).key = k; return (idx, !0u32, true); }
        }
        idx = (idx + 1) & self.mask;
    }
}

Each MapEntry occupies 8 bytes, so eight consecutive entries span 64 bytes. This compact layout improves spatial locality during linear probing, although probe sequences can cross cache-line boundaries and vary in length.

Track D Progression Milestones

Why the Obvious Optimization Failed

Systems performance engineering is defined as much by what you discard as by what you deploy. Across all three tracks, intuitive optimizations consistently lost to formula-aware designs:

Correctness and Verification

Optimizing for the score formula is meaningless if output digests fail validation. We established a verification framework distinguishing between official reference hashes, differential tests against earlier commits, and stress testing:

• Digest Validation: Output SHA-256 hashes matched byte-for-byte on all competition datasets.
• Track A Differential Testing: Verified against official reference digests on tiny-seed1, sample-seed1, and full-seed1. Additionally, 8 differential edge tests ran against commit 7fe5e92 (testing zero records, single records, hash table collisions, and Zipfian skew).
• Track C Matrix Testing: Tested across 7 thread configurations ($n \in {1 \dots 16}$) and 4 buffer sizes (64 B to 1 MB) for a total of 144 / 144 PASS tests (track-c/PERF.md:202-204). Multi-seed datasets (seeds 2, 3, 4) were verified against outputs generated by the competition Python reference reference/c_join.py.
• Track D Stress Testing: Verified against the official calibration hash on full-seed1 (a23dbdf0a3e49cc8901310a9ee1dc6a9a569a85297b6da75c2a7002cb2ed277e). Stress-tested across 60 distinct synthetic graphs (seeds 2 through 61) with 60 / 60 PASS tests matched against reference/d_traverse.py (track-d/PERF.md:59).

Portability, Safety, and Unsafe Invariants

Hardware Architecture & OS Environment

• Track C Target: Uses 256-bit AVX2 SIMD instructions (_mm256_loadu_si256, _mm256_cmpeq_epi8, _mm256_movemask_epi8). Target builds specify x86-64-v3 with AVX2 and SSE4.2 enabled (track-c/Dockerfile, track-d/Dockerfile). Executing Track C on a CPU lacking AVX2 will trigger an Illegal Instruction (SIGILL) fault.
• Operating System Separation & POSIX FFI:
  • Track A: Developed and profiled natively on Windows 11 as a standalone .exe using Win32 psapi memory metrics, while its official competition submission (7168b09) was evaluated in Linux on the official contest runner.
  • Tracks C and D: Rely on Unix/POSIX system calls (mmap, munmap, madvise, std::os::unix::io::AsRawFd). Because AsRawFd is only available under cfg(unix), these source trees cannot compile directly on native Windows with MSVC without a POSIX layer. Local development, benchmarking, and verification were conducted inside WSL2 (/mnt/c/ workspace mounts) and containerized via Docker (rust:1-slim-trixie / debian:13-slim). Neither Track C nor Track D was submitted for official competition leaderboard scoring.

Unsafe Invariant Audit

Across all three tracks, 42 unsafe blocks were audited:

1. Guarded SIMD Loads: All vector loads are bounded by explicit pointer arithmetic checks (while q.add(32) <= end_ptr). Tail bytes are handled strictly by scalar loops, preventing page boundary over-reads.
2. Unaligned Memory Reads: Unaligned loads (read_unaligned::<u64>()) are bounded by buffer capacity checks, executing safely on little-endian x86-64 architectures.
3. Memory Mapping & madvise: Direct extern "C" mmap and munmap bindings wrap valid file descriptors; madvise calls pass standard POSIX flags (MADV_DONTNEED = 4, MADV_WILLNEED = 3) as advisory kernel hints.
4. Packed Struct Field Access: Edge fields are copied by value rather than by reference, preventing unaligned reference undefined behavior.

What We Would Change in Production

While these engines achieved sub-second execution across multi-million record datasets under hackathon constraints, production deployment would require several architectural adjustments:

1. Replace Probabilistic Hash with Keyed Fingerprinting and Exact Equality Checks: Even a 128-bit hash remains probabilistic and is theoretically vulnerable to collisions or adversarial hash-flooding. In production systems where deterministic correctness is required, a keyed hash (such as SipHash or HighwayHash) should be combined with exact byte-string equality checks on hash matches rather than relying on hashes alone.
2. Dynamic SmallMap Resizing & Load Guards: In Track D, SmallMap uses a fixed capacity of 262,144 entries without load-factor guards. On adversarial graphs with $> 262,144$ explored nodes, linear probing would enter an unbounded loop. A production implementation requires dynamic power-of-two table resizing when load factor exceeds 50%.
3. General RFC 3339 Timestamp Parsing: Track A hardcodes assumptions for October and November 2026. A production ingestion engine should validate calendar boundaries or utilize a generalized vectorized ISO 8601 parser.
4. Cumulative Distance Overflow Handling: In Track D, tentative distances $\ge 65,534$ are pruned, and fallback to dijkstra64 only occurs if an edge with weight 65,535 was encountered. Production engines must support 32-bit or 64-bit distance fields across all relaxation stages, ensuring long multi-hop paths are not falsely classified as unreachable.

AI Assistance Disclosure

In the spirit of transparency in competitive systems engineering and technical publication:

• Author Strategy and Technical Decisions: The overarching optimization strategy—prioritizing the scoreboard objective function over raw latency, targeting zero external dependencies ($D = 1.0$), eliminating dynamic allocations in favor of flat tables and CSR representations, identifying the Windows cold-start benchmarking artifact, and directing all iterative profiling—was designed and driven by the author.
• AI Assistance During Development & Debugging: Generative AI tools (Google's Gemini-powered Antigravity coding assistant and claude for system design and approach) were used during development and debugging. Specific tasks assisted by AI included rapid prototyping of iterative candidate implementations, drafting low-level bitwise operations (such as AVX2 SIMD quote masking and 64-bit SWAR date parsing arithmetic), brainstorming algebraic implications of the scoring formula exponents, diagnosing edge-case test failures, and assisting in the structuring, editorial refinement, and formatting of this technical article.
• Local Experiments and Measurements: All local benchmark measurements—including the 30-pair randomized A/B trials on Windows for Track A, the 144-case thread/buffer matrix tests for Track C, the 60-seed synthetic graph stress tests for Track D, and the memory progression logs in track-c/PERF.md and track-d/PERF.md—were executed, recorded, and audited directly on the author's local hardware (Intel Core i5-13420H) across native Windows and local WSL2 environments.
• Official Competition vs. Local Status: Only Track A was officially submitted to and scored on the Speed Demon 2026 competition leaderboard (76.622 points at 0.038 s, 31 MB peak working set). Tracks C and D were developed, validated, and profiled locally (achieving 0.1275 s and 0.6600 s in local testing); neither received an official competition submission or official leaderboard score.
• Verification & Responsibility: Every benchmark number, code snippet, statistical calculation, and technical claim in this article was verified against repository source code and primary execution logs. The author takes full responsibility for the accuracy, claims, and technical conclusions presented.

Reproduce It

Spec and harness files come from the competition kit, not this repository. Because Tracks C and D utilize direct POSIX FFI (mmap, madvise, AsRawFd), they must be built in a Linux environment (Linux, WSL2, or Docker).

Environment Overview

• Development Host: Windows 11 (Intel Core i5-13420H, 12 logical cores)
• Local POSIX / Container Environment: WSL2 & Docker Desktop (rust:1-slim-trixie / debian:13-slim)
• Official Contest Scoring Runner: Remote Linux x86-64-v3 evaluation host
• Toolchain: rustc 1.99.1, rustfmt 1.10.0 (Edition 2021)

Option 1: Native Linux or WSL2 (Fastest Local Reproduction)

# Build all three release binaries in Linux or WSL2
cargo build --release --manifest-path track-a/Cargo.toml
cargo build --release --manifest-path track-c/Cargo.toml
cargo build --release --manifest-path track-d/Cargo.toml

# Run benchmarks or evaluations
./track-a/target/release/track-a /path/to/data /path/to/out
./track-c/target/release/track-c --data /path/to/data --out /path/to/out
./track-d/target/release/track-d --data /path/to/data --out /path/to/out

Option 2: Docker Multi-Stage Containers (Matching Competition Spec)

# Build standalone competition container images
docker build -t speed-demon-a track-a/
docker build -t speed-demon-c track-c/
docker build -t speed-demon-d track-d/

# Run containerized evaluations with mounted host directories
docker run --rm -v "$(pwd)/data:/data:ro" -v "$(pwd)/out:/out" speed-demon-a /data /out
docker run --rm -v "$(pwd)/data:/data:ro" -v "$(pwd)/out:/out" speed-demon-c --data /data --out /out
docker run --rm -v "$(pwd)/data:/data:ro" -v "$(pwd)/out:/out" speed-demon-d --data /data --out /out

Option 3: Native Windows (Track A Only)

Track A is pure standard library Rust and builds natively on Windows without POSIX shims:

# In PowerShell:
cargo build --release --manifest-path track-a/Cargo.toml
.\track-a\target\release\track-a.exe path\to\data path\to\out

See the Code

• Track A source: track-a/src/main.rs | Notes: track-a/PERF.md
• Track C source: track-c/src/main.rs | Notes: track-c/PERF.md
• Track D source: track-d/src/main.rs | Notes: track-d/PERF.md