The scoreboard in a systems competition does not time your program; it evaluates a mathematical function.
Building zero-dependency Rust engines for Speed Demon 2026 across Tracks A (Ingest), C (Join), and D (Traverse), our instinct was to chase the clock. But the harness evaluated an equation balancing runtime (T), peak memory (M), source size (S), and external dependency weight (D).
Treating the scoreboard as an objective function inverted our priorities: allow memory to rise when runtime rewarded it, strip external crates to avoid a punitive dependency tax, and fix our benchmark protocol when Windows cold-starts deceived us. Making the hot path boring unlocked sub-second execution across multi-million record datasets, with Track A reaching 0.038 seconds.
TL;DR:
- Optimize the formula, not just the clock: Runtime dominates memory (T^0.50 vs M^0.20), while adding a single crate incurs an immediate 9.88% penalty on K. Zero-dependency standard Rust (D = 1.0) was mandatory.
- Make the hot path boring: Dynamic hash tables cause cache misses. Replacing hash lookups with flat arrays, dense integer ranks, and Compressed Sparse Row (CSR) tables reduced latency across all tracks.
- Verify the benchmark first: Windows working set initialization imposed a 35 to 50 ms cold-start penalty on whichever binary ran first. Warmup loops and randomized trial execution reduced order bias to 1.71 ms (p = 0.4359).
Headline Results: Track A scored 76.622 points officially on the Linux harness (0.038 s, 31 MB as shown 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) locally on our Windows dev machine; official 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 from four 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:
| Track | Score | Runtime (T) | Peak Memory (M) | Lines (S) | Commit & Environment |
|---|---|---|---|---|---|
| Track A (Official) | 76.622 | 0.038 s | 31 MB (as shown on leaderboard) | 286 (scored) |
7168b09 (official Linux harness) |
| Track A (Candidate) | submitted, official score pending | - | - | - |
adbd3f1 (official Linux harness) |
| Track C (Join) | NOT MEASURED | 0.1275 s | 54.64 MB peak working set | 454 (raw, unformatted) |
1be4222 (Windows dev machine, local) |
| Track D (Traverse) | NOT MEASURED | 0.6600 s | 160 MB peak working set | 802 (raw, unformatted) |
b36d7d1 (Windows dev machine, local) |
Status and baselines:
- Track A candidate (
adbd3f1) is submitted; official evaluation is pending. - Track A official leaderboard evaluation for commit
7168b09yielded K = 34.074745 (76.622 points). - Tracks C and D have no official scores; line counts (454 and 802) are raw unformatted counts; memory figures report peak working set in MB as logged.
- Official Linux harness reference baselines (D_ref = 1 across all tracks): Track A (T_ref = 32.047276 s, M_ref = 217 MiB [227,983,360 B], S_ref = 56); Track C (T_ref = 14.444059 s, M_ref = 350 MiB [367,435,776 B], S_ref = 108); Track D (T_ref = 72.692655 s, M_ref = 851 MiB [892,915,712 B], S_ref = 43).
The scoring exponents dictate system architecture:
- Runtime dominates memory (T^0.50 vs M^0.20): Wall clock is uncapped; faster code always scores higher. The memory ratio is capped at 50x with exponent 0.20 (less than half of time's 0.50). Sacrificing compute time to trim RAM is almost always a losing trade.
- The 9.88% crate tax (D_ref = 1, D^0.15): Per final_scoring.py line 275, D_ref = 1 across all tracks, where D = 1 + direct_dependencies. Importing one crate moves D to 2. Because (1/2)^0.15 is approximately 0.90125, one crate levies an instant 9.88% penalty on K, requiring roughly a quarter faster runtime to break even. In our three tracks, std-only code was enough. We kept all three tracks at D = 1.0.
-
The memory reduction trap in Track A: Early multi-pass streaming dropped peak working set on Windows from ~30 MB to 4.56 MB. But re-reading chunks slowed runtime on our Windows dev machine from our official Linux baseline of 0.038 s to 0.080-0.120 s. Plugging these figures into
scoring.pyproduced a computed estimate score drop from ~75.8 to ~70 points (an estimated ~5.8 points loss; evidence/multipass_experiment.txt). We discarded it. - The streaming buffer penalty in Track C: In iteration v5, 1 MiB streaming buffers cut peak working set by 48.2% (from 379.29 MB to 196.27 MB, saving 183 MB). However, managing record splits across chunk boundaries increased runtime by 45.3% (from 0.4933 s to 0.7168 s), degrading net score. In iteration v6, we discarded chunk streaming for 64-bit hash sorting, dropping 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 testing on Windows, paired A/B benchmarks showed that whichever binary ran first in sequence suffered an artificial 35 to 50 ms penalty.
Windows working set initialization and page caching caused the delta: the first run absorbed disk faults and virtual memory allocation, while the second run benefited from warm OS cache.
We rebuilt our protocol with two rules:
- Mandatory untimed warmup executions to saturate file caches.
- Randomized trial execution orders across 30 paired runs.
Order bias collapsed from 35 to 50 ms down to 1.71 ms (p = 0.4359; logged in evidence/cold_start_benchmarks.txt), enabling reliable micro-benchmarking.
Make the Hot Path Boring: Dense Arrays Over Hash Tables
Our second architectural rule was removing dynamic hash tables from hot paths.
Hash tables incur pointer indirection, cache misses, collision branches, and allocations. Instead, we designed dense, flat indexing:
- In Track A, endpoints are interned once and assigned dense integer ranks (0 <= rank < 1,842), turning Phase 2 group joins into single array lookups.
- In Track C, region IDs map to country codes via a flat 1 MB lookup vector covering 1,000,000 IDs, making lookups O(1) array reads.
- In Track D, graph edges and offsets are stored in Compressed Sparse Row (CSR) arrays, eliminating pointer-chasing adjacency lists.
Predictable memory strides reduce latency.
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.
The Surprising Part: Where the Time Actually Went
Profiling Phase 2 with profile_phase2.rs (evidence/profile_phase2.rs) on Windows across 12 threads revealed 215.48 ms CPU time (23.35 ms wall time):
- pdqsort: 91.29 ms (42.4% CPU share).
- Formatting and percentiles: 91.71 ms (42.6% CPU share).
- Writer mutex: 20.85 ms (9.7% CPU share).
- Key packing: 11.64 ms (5.4% CPU share).
Sorting latencies was our true bottleneck: merging records for each hour into one array forced sorting ~32,000 keys per hour.
Instead of sorting an entire hour, we scattered latencies directly into per-endpoint rank vectors (ep_buckets[rk].push(lat)). Sorting small slices in parallel was faster than sorting one unified array. In a strict 30-pair benchmark on Windows, direct bucket scattering dropped latency from 63.86 ms to 59.59 ms (p = 4.6e-4).
Analogy: Endpoint ranking is like giving marathon runners bib numbers: match the name once at check-in, assign a numeric bib, and track subsequent split times by integer.
Approach & Annotated Code Snippet
Timestamps follow RFC 3339 within a fixed window (2026-10-30T18:00 to 2026-11-02T17:59:59.999999Z). We parse them branchlessly at byte offset 5 using an unaligned 64-bit SWAR 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;
Reading 8 bytes in one instruction extracts month, day, and hour digits using bitwise shifts and subtractions of 48 (ASCII '0'), eliminating branches, allocations, and calendar math.
Evidence Table
All rows except the last are progression milestones across development iterations on our Windows dev machine; the final row is a same-session paired benchmark:
| Optimization Step | Before | After | Mechanism | Type |
|---|---|---|---|---|
| Sequential to Parallel | 0.797 s | 0.471 s | Sliced body across cores via std:🧵:scope. | Progression milestone |
| Threads to 1 MiB stream | 0.471 s (peak 269 MB) | 0.324 s (peak 45 MB) | Chunk streaming via Read::take. | Progression milestone |
| Custom serializer | 0.324 s | 0.261 s | Custom integer formatting over write! macros. | Progression milestone |
| Dynamic hour reduce | 0.261 s | 0.163 s | Parallel reduce with AtomicUsize work stealing. | Progression milestone |
| SWAR + lock-free table | 0.163 s | 0.077 s | 64-bit SWAR date parsing and CRC32 table. | Progression milestone |
| Direct bucket scatter | 63.86 ms | 59.59 ms | Direct scatter into rank vectors (p = 4.6e-4). | Paired trial (30 runs) |
What We Rejected
- Counting & Radix Sort: Counting sort (79.00 ms) and 2-pass radix sort (53.26 ms) both lost to direct indexing at 51.42 ms in the same scratch series. However, candidate minimized still used pdqsort on small slices because sorting only populated per-endpoint vectors avoids clearing and traversing unpopulated latency bins.
- Multi-pass streaming: Dropping peak working set on Windows to 4.56 MB slowed local runtime to 0.080-0.120 s (vs our official 0.038 s baseline), yielding a computed score estimate loss of ~5.8 points (evidence/multipass_experiment.txt).
- Mutex locks in Phase 2: Commit 7267621 eliminated 1,152 Mutex allocations in bucket aggregation via atomic ownership.
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.
The Surprising Part: The Zero-Collision Gamble
Distinct name counting across 3,320,000 records was our main bottleneck: in our initial v1 baseline using a per-country HashSet of names, execution took 5.5230 s with a peak working set of 405.69 MB (as logged).
We replaced string storage with a custom 64-bit multiplicative hash (hash_bytes). Worker threads hashed unescaped name slices into u64 values and pushed them into thread-local country vectors. In Phase 2, each country's hash vectors were merged, sorted with sort_unstable(), and deduplicated with dedup(). The resulting vector length was the distinct count.
Track C's 64-bit hashing is probabilistic, trading theoretical exactness for speed. While a 64-bit hash could theoretically collide, our empirical check on full-seed1 against Python's exact set confirmed zero collisions across all 100,520 distinct names. Birthday-bound collision probability for 100,520 names in a 64-bit hash is about n^2 / 2^65, roughly 3e-10 (computed, not measured).
This eliminated string allocations, cutting peak working set to 54.64 MB and runtime to 0.1275 s.
Analogy: The flat region table functions like postal pigeonholes: rather than asking where an address belongs, you place the letter directly into slot 1,000, where the country code is permanently labeled.
Approach & Annotated Code Snippet
In our final design, records.csv is memory-mapped via libc mmap. Worker threads partition the memory-mapped slice, scanning records with AVX2 SIMD intrinsics while issuing madvise(..., MADV_DONTNEED) in 8 MB batches to purge completed pages from OS page cache.
// AVX2 256-bit SIMD scanner: find 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);
}
This vector instruction evaluates 32 bytes against quotes in parallel; trailing_zeros() resolves match offsets in one instruction.
AVX2 Portability Note: Track C targets x86-64-v3 (AVX2) via RUSTFLAGS in Dockerfile and .cargo/config.toml. Lacking runtime feature detection (is_x86_feature_detected!) or scalar fallbacks, it would crash on CPUs without AVX2. Track A's build used x86-64-v3, which includes AVX2, and ran cleanly on the official Linux harness (scoring 76.622), confirming AVX2 availability.
Evidence Table (Progression Milestones)
Track C has no official leaderboard evaluation yet. Timings are progression milestones across development iterations on our Windows dev machine:
| Iteration | Median Runtime | Peak Working Set | Architectural Changes |
|---|---|---|---|
| v1 Baseline | 5.5230 s | 405.69 MB | Single-threaded; HashMap regions; HashSet names. |
| v2 Direct Table | 2.1155 s | 395.74 MB | Replaced HashMap with flat 1M-entry Vec and dense country IDs. |
| v3 Global Dictionary | 1.2767 s | 210.32 MB | Replaced per-country sets with global name dictionary and bitsets. |
| v4 Parallel Chunking | 0.4933 s | 379.29 MB | Two-pass parallel quote counting and boundary alignment (12 threads). |
| v5 Streaming Buffers | 0.7168 s | 196.27 MB | Streamed 1 MiB chunks; cut memory by 183 MB but slowed runtime 45.3%. |
| v6 64-Bit Hash Dedup | 0.1275 s | 54.64 MB | Replaced name dicts with 64-bit hash blocks and parallel dedup. |
What We Rejected
- Per-country HashSet: Storing raw string vectors in hash sets pinned peak working set at 405.69 MB.
- 1 MiB Streaming Buffers: In v5, streaming 1 MiB chunks via file reads cut peak working set by 183 MB, but handling record splits across boundaries added 45.3% runtime overhead (0.4933 s to 0.7168 s). While our buffer-size test matrix (64 B to 1 MB) verified deterministic aggregates, the final design adopted whole-file memory mapping with 8 MB madvise eviction to keep memory low without chunk-boundary overhead.
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.
The Surprising Part: The Bidirectional Memory Explosion
In iteration v3, unidirectional Dijkstra across 12 worker threads answered 2,000 queries in 2.5154 s on full-seed1. In v4, balanced bidirectional Dijkstra dropped runtime to 0.8019 s (a 3.14x speedup).
Then peak working set spiked from 223.79 MB to 418.71 MB (measured median logged in track-d/PERF.md line 55), because storing two 64-bit distance arrays across 1,740,512 nodes took 14 MB per array, or 28 MB per worker thread (12 threads * 28 MB = 336 MB).
We resolved this in iteration v5 with SmallMap: a cache-line-resident open-addressing table with linear probing. Because road queries explore a fraction of the 1.74M graph, each thread gets a 2 MB table (262,144 entries) storing packed 8-byte MapEntry structures. Upon termination, clear_slots resets touched slots in O(touched) time.
This cut peak working set from 418.71 MB (track-d/PERF.md:55) to 160 MB while reducing median runtime to 0.6600 s.
Analogy: Bidirectional Dijkstra is like two search parties walking toward each other from opposite ends of a trail: halving the search radius can shrink the explored area a lot.
Approach & Annotated Code Snippet
To optimize cache performance, graph edges are packed into 6-byte structs (Edge { to: u32, weight: u16 }), and SmallMap lookup merges probing and insertion into a single operation:
// Unified probe: check membership and reserve slot in one cache-line probe
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;
}
}
Storing keys and values in contiguous 8-byte structs allows an L1 cache line to hold 8 entries, scanned via linear probing with zero pointer dereferencing.
Evidence Table (Progression Milestones)
Track D has no official leaderboard evaluation yet. Timings are progression milestones across development iterations on our Windows dev machine on full-seed1:
| Iteration | Median Runtime | Peak Working Set | Architectural Changes |
|---|---|---|---|
| v2 Multi-Query | 2.6477 s | 223.77 MB | 2,000 queries distributed across 12 threads via std:🧵:scope. |
| v3 Parallel CSR | 2.5154 s | 223.79 MB | Two-pass parallel CSR graph construction via atomic degree counting. |
| v4 Bidirectional | 0.8019 s | 418.71 MB | Balanced bidirectional search; cut runtime by 3.14x; spiked memory. |
| v5 Packed SmallMap | 0.7400 s | 160 MB | Packed 6-byte edges; 2 MB SmallMap replaced 336 MB distance vectors. |
| v6 Unified MapEntry | 0.6600 s | 160 MB | 8-byte contiguous MapEntry; O(touched) reset; 4-ary min-heap. |
What We Rejected
- 64-bit edge weights in CSR: Edge weights rarely exceed 65,535. Storing 64-bit weights would increase graph memory by 25%. We packed weights into u16 and routed rare weights >= 65535 to a full 64-bit Dijkstra search (dijkstra64).
- Standard BinaryHeap: Replacing standard 2-ary BinaryHeap with a cache-aligned 4-ary min-heap (Heap4Fast) reduced tree depth during frontier pops.
- Unidirectional search on disconnected graphs: In road graphs with unreachable targets, unidirectional search explores the whole reachable region. Bidirectional search halts as soon as the backward frontier finds zero in-edges, returning -1 immediately.
Correctness and Verification
Optimizing for the score formula is meaningless if output digests fail validation. We verified each track rigorously, maintaining clear separation between official reference hash validation and differential tests against earlier commits.
Output SHA-256 matched on all official datasets; digests are in the repo.
Differential vs Reference Testing Scope
- Track A: 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, cache collisions, and Zipfian skew).
- Track C: Matrix tested across 7 thread counts (1..16) and 4 buffer sizes (64 B..1 MB) for 144 / 144 passes. Edge datasets (edge1, edge2, edge3) and multi-seed tests (seeds 2, 3, 4) were verified against outputs generated by official Python reference reference/c_join.py.
- Track D: Verified against the official calibration hash on full-seed1. Stress-tested across 60 separate tiny datasets (seeds 2 through 61) with 60 / 60 passes, matched byte-for-byte against outputs generated by official Python reference reference/d_traverse.py.
Reproduce It
Spec and harness files come from the competition kit, not this repo.
Environment
- Local Machine: Windows 11 (Intel Core i5-13420H, 12 logical cores)
- Official Scoring Host: Linux x86-64-v3 runner
- Toolchain: rustc 1.99.1, rustfmt 1.10.0 (Edition 2021)
Build Commands
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 Commands
./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
Trade-offs and Limits
- Fixed Spec Windows: Track A assumes timestamps fall within the 72-hour window across October 30 to November 2; timestamps outside this range panic.
- Fixed-Offset Parsing: Track A assumes 27-byte RFC 3339 timestamps with 6 fractional digits; different layouts invalidate SWAR byte offsets.
- Table Capacities: Track A's endpoint table holds 4,096 entries (spec guarantees 1,842). Track C assumes region IDs stay under 1,000,000. Track D's SmallMap holds 262,144 entries per worker; settling > 131,072 nodes increases probe lengths.
- Unsafe Operations: All tracks use unchecked indexing, unaligned SIMD/SWAR reads, and raw buffer over-reads to bypass bounds checks.
- Memory Duplication: Tracks A and C duplicate 10 to 15 MB across thread-local buffers to achieve lock-free ingestion.
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
Top comments (0)