Bounded Accord：圖構建少掃描三次，耗時反增 12%

Bounded Accord’s Speed Demon engineering notes, written on October 31, 2026 and updated after our last push on November 2. Live-board results are practice scores, separate from final judging.

The last graph-construction change in this account removed three complete reads of a five-million-edge array. It preserved the order of every adjacency list and left the shortest-path search unchanged. It passed the correctness checks. The measured program took about 12% longer.

That result came from our entry in Speed Demon, organised by Hackathon Raptors. Bounded Accord implements four tasks in Rust: log aggregation, Boolean and phrase search, a CSV join, and directed shortest paths. The entry repository contains the implementations and their performance records.

The comparisons below cover rejected changes, an officially scored storage improvement, and an input-partitioning change that reached the live board on the last day.

One graph pass can carry more expensive work

Track D stores the graph in two compressed sparse row structures: one for outgoing edges and one for incoming edges. Each row’s edges are contiguous. A forward search from the source and a reverse search from the target can then read their own adjacency arrays without searching the original edge list.

The accepted constructor first parses triples of source, destination and weight. For each direction, it counts degrees, computes row offsets, allocates edge storage, and scans the triples again to fill that storage. There are four full triple scans after parsing.

The candidate counts both degrees while parsing, then fills both adjacency arrays in one shared triple scan. Each edge still appears in its original relative order within its row. Parallel edges, exact duplicates, self-loops and zero weights remain intact. The input byte buffer is released before the edge arrays are allocated in both versions.

The following comparison includes reading, construction, all queries and writing the output:

Times are means of the middle three of five runs per version, after fixed warm-ups. Baseline and candidate runs were interleaved on the same Intel Core i5-12500H machine running Ubuntu 24.04 under WSL2. The images were pinned, six workers were used, and the published child timer excluded container startup. RSS came from separate native runs; it is not the official container-memory measurement.

The time ratio, baseline divided by candidate, was 0.894317. Memory fell by about 3.7%. Both timing spread checks passed, but the candidate missed our previously fixed efficiency requirements. We restored the accepted source and executable and checked the full output hash again.

The comparison establishes that this implementation was slower in this environment. It does not identify a cache-miss rate, a memory-bandwidth limit, or the cost of each added write. Counting loop passes supplied a hypothesis; it did not measure the cost of the resulting access pattern.

An exact small-key representation did pay

Track C joins CSV records to countries and counts distinct names per country. Splitting records at every newline would be wrong: a quoted field can contain a newline. In the officially scored pipeline, the producer carries quote parity across input blocks and dispatches only complete logical records. Six workers decode fields and accumulate numeric totals.

Distinctness spans all workers. The accepted design groups requests into 64 mutex-protected shards. Under a shard’s lock, the first occurrence of an exact (name, country) pair sets a membership bit and increments one worker’s count. Summing those counts is valid because the first-pair decision is shared.

The useful storage change was deliberately narrow. When there are at most 256 country groups, including the unmatched group, names of at most 16 bytes fit in two words plus a length. Four words hold the country-membership bits. The key contains every name byte; it is not a fingerprint used as identity. Length distinguishes a short name from a longer zero-padded value. Longer names and larger country tables keep the full-byte fallback.

Against the preceding accepted pipeline, this change reduced pinned-image time from 0.186579 to 0.152485 seconds and native peak RSS from 24,060 to 19,828 KiB. It passed its fixed adoption requirements. Its subsequent official run, run-52f0819fc621, recorded 55.455380 machine points, up from the previous best of 51.737524.

The tests targeted the representation’s boundaries: every inline-key byte position, lengths around 16 and 17 bytes, zero bytes, country-bit boundaries, tables through 513 countries, concurrent first-pair updates and reused scratch storage. Fast-path checks alone would have missed the fallback’s obligations.

A small time saving can lose the combined comparison

A later Track C candidate scanned each complete record for outside-quote commas and quote counts. That metadata let it derive decoded note lengths without visiting every note byte in the decoder. Unescaped names borrowed their input bytes; escaped names used scratch storage. Record framing and membership storage stayed unchanged.

It was correct across the tested cases, including split vector blocks, escaped quotes, embedded newlines, Unicode, BOM bytes and a two-megabyte note. It also reduced measured process time slightly:

The speed ratio was 1.022018, below our fixed 1.18 adoption requirement. Both timing spread checks passed. The source increase also mattered: Speed Demon’s coefficient charges for source size as well as time, memory and dependencies. Using our local RSS and line-count proxies gave a coefficient ratio of 0.988437, below our required 1.05. These counts differ from the host’s formatted-source and container-memory axes, so the ratio is an estimate, not a predicted official score.

We rejected this implementation before submission. Its shorter decoding path did not produce enough whole-program benefit to cover the measured trade-off.

Finding five boundaries without listing every record

A later input-partitioning change reached the local adoption threshold. The first version mapped the immutable CSV file read-only and divided it into six complete-record ranges. Workers borrowed those ranges directly, eliminating the producer’s owned buffers and channels. Its partitioner still scanned the entire input sequentially, collecting record-end offsets to choose just five internal cuts. That version saved memory but missed the time requirement.

The next version computes quote parity in six parallel byte ranges. A prefix XOR supplies the quote state at each proposed cut; a forward scan then finds the next newline outside a quoted field. An escaped quote contributes two quote bytes, so even a cut between them receives the correct starting state. Long quoted records may send several cuts to the same boundary, producing valid empty ranges. After partitioning finishes, six parsing workers borrow the resulting slices. The parser and shared membership tables stay unchanged.

This comparison uses a new fixed batch against the previously accepted producer pipeline:

The time reduction was 16.7%, and the measured memory reduction was 9.6%. The local coefficient ratio was 1.087865, above the fixed 1.05 requirement. That calculation uses time, memory, source size and direct runtime dependencies; image size is a separate build limit. Both implementations had a dependency-axis value of one.

Memory was read from the Docker cgroup with host data prewarmed and a common trusted holder keeping the cgroup available after the timer exited. This measures the container’s recorded peak, but it does not reproduce the host’s parent harness or isolation. The source count is also a local proxy. The baseline had one slower run; the predeclared middle-three mean excluded the fastest and slowest of five runs from each version, with all raw values retained.

Eleven Rust tests, seventeen validation groups and all fourteen image outputs passed. The checks included quote pairs split at every byte position, long records, Unicode, BOM handling and the final record without a newline. The source was frozen before fresh seeds 137 and 138 and reserved seed 139 were generated.

A separate diagnostic sampled the unchanged candidate twice. It captured 620 and 621 CPU events, with text decoding accounting for about 20% in each capture. The earlier producer pipeline also placed text decoding near 21%. These are exclusive CPU sample locations, not elapsed-time shares; they do not establish that a previously rejected parser change should be tried again.

The change's first live-board run, run-e08fc96bfae2, recorded 57.147738 machine points; the previous best was 55.455380. The board measured 0.160190 seconds instead of 0.187834, and 17,788,928 bytes of peak memory instead of 20,283,392. Formatted source grew from 401 to 483 lines. On the board the coefficient rose by a factor of 1.081, close to the local estimate of 1.088, although the two use different time, memory and source-size measurements.

The local winner that lost on the board

An earlier Track D experiment reordered vertices with breadth-first numbering. Its final local version remapped queries early enough to release the permutation before constructing the final adjacency arrays. The fixed native comparison improved from 0.849322 to 0.705578 seconds: about 16.9% less elapsed time. The RSS ratio was 0.997095, and the local coefficient proxy passed its gate.

The official trial was valid but scored 49.524627 machine points. The retained best was 50.424918. We restored the prior source.

Those official values are separate historical runs, not an interleaved experiment isolating the numbering change. The board observation was enough to reject that trial as an improvement over the retained best; it was not enough to explain the reversal. A later local diagnostic compared native and container execution contexts and still did not establish the cause.

This also changed how we described unchanged-source results. A repository push can run tracks whose source did not change. Our best recorded A and D values came from such runs. They belong in the measurement record, but their variation cannot be credited to a new algorithm. On the final day, the unchanged Track A source took 0.189345 seconds in one run and 0.146796 in the next, against its best of 0.130583.

Correctness evidence has a separate job

For the fused graph candidate, seven Rust property tests passed. One checked that parsing preserved the ordered rows in both directions. Another tested every directed three-node graph whose nine possible edges were absent, zero-weight or unit-weight: 19,683 graphs, with every source-target pair checked against Bellman–Ford.

The wider checks covered 117 adversarial and random graphs, repeated queries, large path sums, zero cycles and directed reachability. Seven host examples ran with one, two, six and twelve workers. Fresh tiny seeds 127 and 128 passed before reserved seed 129, with the source frozen. Published sample/full hashes and all fourteen measured or warm-up image outputs matched.

These checks made a performance comparison meaningful by ruling out the tested wrong-answer cases. They do not prove every possible input correct or turn a slower result into a useful optimisation. The graph invariants still have to hold: path sums remain 64-bit, reverse edges retain their own weights, and bidirectional search cannot stop merely because it found a meeting.

The entry at code freeze

Our last push before the November 2, 15:00 UTC code freeze was commit f00c64fca46bb4124462c053305a1395c596035f. It only updated the performance records; its source is the same as commit 29a57dc3752e417842e5bc2bf4796170c2ead170, which carried the parallel-parity change. The table lists the best live-board value for each track. The values come from different recorded runs, not a simultaneous four-track timing batch.

The A and D bests came from pushes that changed other tracks, with their own source unchanged. C's best came from the final, documentation-only push, which re-ran the parallel-parity source; its first run had scored 57.147738. These are practice-board machine results, not final judging or an award: final scoring reruns the recorded commit on a held-out dataset, and judges contribute 35% of each track total. The per-track PERF.md files retain the unsuccessful comparisons alongside the accepted changes; MEASUREMENTS.json binds the best values to run IDs and source hashes.

For the next graph-construction change, the missing evidence is where the modified access pattern spends time. For the CSV pipeline, the open question is whether the board's 8% coefficient gain holds on the held-out dataset.

The implementations, validation and this article were developed with Codex; Claude Code added the November 2 board results. Algorithm references, measurement limits and assistance disclosures are retained in the entry repository. Task definitions and the official scoring procedure are published by Hackathon Raptors.