23 Minutes Before the Freeze: Shortest Paths at Hackathon Raptors: Speed Demon

08:38 on Monday, November 2, Ann Arbor time. I push, and a few minutes later the live board says 0.0960 s.

Twenty-two minutes earlier, the same code had run in 0.0854 s. Code freeze is at 10:00. Whatever sits on my branch then is my entry, and the final time is the mean of the middle three of five runs, so a version that is fast only on good days is a bad version.

I'll come back to 08:38. First, what the 0.0960 was measuring.

The task

Speed Demon 2026 is a 72-hour performance championship run by Hackathon Raptors. Everyone gets the same task, the same data and the same scoring machine: an Intel i5-13500 with six P-cores, 12 threads, turbo off, a fixed 2.5 GHz, 8 GB of memory. Output has to match the expected answers byte for byte. The efficiency score mixes wall time, peak memory, lines of code and dependencies, and human judges decide the rest.

Track D: answer 2,000 shortest-path queries on a road network with 1.74 million nodes and 5 million one-way, weighted edges. The clock starts before the input file is read. So the job is half graph building, half searching, and you pay for both.

I entered solo, under the team name sweetdreams. All the code and a step-by-step log with every board run ID are here: github.com/swapnilb222/sweet-dreams-demon-sub (Track D is in track-d/).

Here is every Track D push that reached the board. Black dots were kept. Open circles were tried on the board and thrown out. Gray squares are the same code run again.

Figure 1. Every Track D push that reached the live board. (a) Wall time. The red stepped line is the best time so far for code I kept; it ends at the code I froze. Step 1 (447 ms) is off the scale. (b) Peak memory; steps 1 and 2 are off the scale. Shaded bands group the pushes by session.

Sunday, 03:08: trackd step1

That was the commit message. I am not proud of my commit messages from Sunday morning.

Step 1 was plain parallel C++: memory-map the file, parse it on 12 threads, build a compressed graph, run a bidirectional Dijkstra per query. 447 ms, 169 MB.

It was slow for a boring reason. The node ids in the input are a random permutation of the map. Two intersections a block apart can sit megabytes apart in memory, so almost every step of a search missed the cache. The search was mostly waiting.

04:05: three ideas in one push

An hour later, step 2 brought it to 109 ms and 65 MB. Three changes, all aimed at the same waiting.

Figure 2. The four stages of the final program. All four are inside the timed run.

Chain contraction. About 30% of the nodes in a road network just continue a road: at most two ways out, nothing to decide. If one of them isn't a query endpoint, no search ever needs to stop there. So when an edge leads into a chain of them, I follow the chain to the first node that has to stay and point the edge straight at it, with the weights summed.

Figure 3. Chain contraction. (a) Hollow nodes have at most two ways out and are not query endpoints. (b) The search never stops at them: the edge from A points straight at B, with the weights summed.

The graph drops from 1.74M nodes and 5.0M edges to 1.22M and 3.96M. Every search shrinks with it.

Renumbering by breadth-first search. Each thread grows compact BFS regions over the graph and hands out new ids in the order it visits nodes. Nodes that are close on the map end up close in memory. Three pushes later, in step 5, contraction moved inside this same pass, so now it costs no extra scan.

A bucket queue instead of a binary heap. The weights are mostly small integers (the median is about 120), so distances can be grouped into fixed-width buckets in a ring, with a tiny heap for the rare long jump. Each query also starts with a short forward-only search, which settles nearby targets by itself. Only then does it search from both ends, always growing the side that has done less work.

That push did more than all the later ones put together. The rest of this post is about the other 24 ms.

Sunday afternoon: three memory peaks

Memory improv little, 13:25. Then 2groupthreads trackd, 13:49.

Memory carries a fifth of the efficiency formula's weight, so I logged the program's memory over time and found three separate peaks, in three different phases. While building, the parsed edges and the new rows were alive together; the parsed edges now sit in page-sized bins that get released group by group. While searching, each bucket kept the largest size it ever reached, about 100,000 entries per direction, when only about 3,000 are live at once; buckets now borrow from shared, recycled blocks. Renumbering got one-byte degrees instead of four-byte ones.

65 MB went to 55 MB. Then I learned something annoying: releasing memory while other threads are working stalls all of them, because the kernel has to flush every core's address translations. So the releases moved to the gaps between build passes.

The race I left in on purpose

When a BFS region claims a node during renumbering, it uses a plain read and a plain write. Two threads can race and both claim the same node. An atomic compare-and-swap on every claim fixes that, and it cost 4 to 10 ms, which is more than most of my later steps saved.

On a real road graph a double claim just makes a harmless duplicate. So I kept the race.

Then a 32-node test case started failing in some runs. On a graph with nothing to contract, the duplicates could push the node count past the width of the node-id field inside an edge word. A later stress run found that the same race could also overrun a thread's edge buffer on a tiny graph.

The fix keeps the cheap claims and checks afterwards. If the duplicates would overflow the id field, a thread's buffer or the raw graph, the whole pass runs again with exact atomics. On full-size inputs that never happens. On tiny graphs it does, and since then every version has gone through 1,500 to 2,500 runs of the 41 small test cases, at 1, 2, 5 and 12 threads, with and without the address sanitizer. You can decide for yourself whether that's engineering or a bet with a good alibi. I'd make it again.

About "the two-line change that halved it"

The side quest asks for one. I don't have one. The biggest jump was step 2, and that was about 220 new lines. After step 2, the wins came in 4 to 9 ms pieces.

The closest thing to a two-line change was step 9. In C++, a store through one u32* may change any other u32 in memory unless the compiler can prove it doesn't. My hot loops store u32 values while reading u32 arrays. So after every store, GCC reloaded the row offsets, the row end, an edge counter, even the array pointers themselves.

The real diff was 35 lines in and 26 out, across several loops, but the idea fits in two:

// the shape of the fix, simplified
u32* __restrict out = state.out;   // copy into locals, promise no aliasing
const u32 end = row_end;           // the compiler can keep these in registers now

Renumbering went from about 29 ms to 22 to 25 ms. On the board: 100 ms to 96 ms. Not half. About 4%.

The change I'm happiest with came right after it, in step 10. The renumbering pass visits nodes in a random order, and with separate offset and edge arrays each visit cost two cache misses in a row: one to find the row, one to read it. Now every node has four fixed edge slots, which covers 97% of the nodes in this network. A node's edges are one miss away, and a prefetch can fetch them straight from the node id.

Figure 4. (a) One edge is one 32-bit word. The head field is sized from the node count at run time: 21 bits for this graph. (b) The raw graph gives every node four fixed slots, so its edges are at a known address.

Every edge is a single 32-bit word: head node in the low 21 bits, weight above it. The 0.1% of weights that don't fit go to a side table. An empty slot is all ones, which no real edge can be because the id field is sized from n + 1. Step 10: 96 ms to 89 ms.

Step 8, before both of these, was the same kind of fix: find one specific stall and remove it. "Is this new path shorter?" is close to a coin flip in a Dijkstra, so the branch predictor guessed wrong about half the time. The relaxation now always writes the smaller distance and always writes the queue entry, and only the counter moves when the path actually improved. Together with prefetching in the chain walks, that took the board from 109 ms to 100 ms.

The control group

Somewhere around step 15 I noticed the board drifted. Identical code ran 87 ms in one session and 91 ms in another. That's the size of most of my improvements.

My Track A entry, a log-parsing task in the same repo, never changed between Track D pushes, and the board ran it on every push. So Track A's time worked as a thermometer for the machine. When Track A came back 20% slow, I didn't believe the Track D number from that push either.

That rule caught a false negative. Step 19 cut instructions in the search and the parser, landed on a busy box (Track A 24% to 38% slow), and measured 94 ms. I reverted it. Forty minutes later, at 23:03, I pushed the identical code again in a quieter period: 86 ms, my best at the time.

Three ideas didn't survive the board at all. Unmapping the input file from the parsing threads, to shorten exit, made things slower, probably because each unmap interrupts every other thread. Putting the reverse graph on 2 MiB pages, on the theory that the i5-13500 only covers 8 MB with small-page translations, measured exactly the same. A barrier that spins briefly before sleeping changed nothing.

The profile I read wrong

I developed on a laptop with two P-cores among its twelve, and turbo. Profiled there, the program looked memory-bound: memory stalls seemed to be the biggest cost. So I spent a chunk of Monday morning checking my sizes against the scoring machine's caches, with Valgrind's cachegrind configured for 48 KB of L1 and the i5-13500's 24 MB last level.

Figure 5. Estimated cycles for variants of the program, compared with the code at the time. Valgrind's cachegrind ran with the i5-13500's cache sizes. I converted its counts to cycles with a rough model: 2.5 instructions per cycle, 30 cycles for an L1 miss that hits a lower cache, 200 cycles for a miss that goes to memory.

The laptop's smaller cache exaggerated memory costs by about 6%, which was reassuring: contraction is still clearly worth it, and my big choices hadn't been tuned for the wrong cache. 64-node BFS blobs looked 2.7% better in the simulator. In 40 interleaved wall-clock runs they lost 2 to 3 ms. The simulator counts misses. It can't see how many of them the CPU overlaps.

The real correction was arithmetic I should have done on Sunday night, when step 19 was already cutting instructions on a hunch. The board ran about 2.9 billion instructions in 85 ms. Spread across six cores at a fixed 2.5 GHz, that's about 2.3 instructions per cycle per core, averaged over the whole run. On the scoring machine the program was close to instruction-bound. My laptop turbos to almost twice that clock, which makes instructions cheap and memory look expensive. There had been a hint earlier, too: deeper prefetching in the search never helped, at any distance.

I'll come back to what that changed. First, 08:38.

Back to 08:38: the 16-bit labels

A search spends much of its time reading and writing distance labels, so their size decides how many cache lines it touches. Almost every answer in this task is small: median about 1,200, 99th percentile about 8,500. So at 08:12 I pushed searches with 16-bit labels, a quarter the size of 64-bit ones. A label saturates at 65,535, and anything below that is a real path length, so a result under it is exact. Queries that hit the ceiling, or have no path, get answered again with 64-bit labels. That was 16 of the 2,000, about 1.5% of query time. Locally, the query phase went from 22.9 ms to 21.0 ms.

The board gave it 85.5 and 94.9 ms on a busy box, then 85.4 ms on another busy box. Two ties with my best. And then 96.0 ms for the 08:38 push, on a quiet box, with Track A at its normal time.

Figure 6. Board runs for each version tried on Monday morning. Open circles: the box was busy, because my unchanged Track A ran slower than usual in the same push. Filled dots: Track A ran at its usual time. The red dot is the quiet-box run that made me revert. The shaded band is every run of the step 23 program before I reverted to it. The dashed line is the final 84.9 ms.

Four runs: two great, two bad. Up to then, the step 23 code it was replacing had never run outside 85.5 to 87.4 ms. With the mean of the middle three of five runs deciding the score, the 16-bit version was the riskier bet, whatever its best run said. My own first wall-clock comparison had also shown it slightly behind overall, even with the faster query phase, and I never found out why.

08:43: back to step 23's code, minus 8 header lines already included. The header cleanup stayed because it changes nothing in the binary and still saves lines.

09:21: fewer instructions for a fixed clock

If the machine is instruction-bound, count instructions. Valgrind's per-line counts said the search's inner loop spent about 50 instructions per edge relaxation (18.7 million relaxations), and the parser about 108 per input line. Three changes, all with the same answers and the same memory accesses:

• A fast path for light edges. An edge lighter than the bucket ring's reach can't land outside the ring when it's relaxed from the bucket being settled. That's every edge except the 0.1% with escaped weights. So the range check only runs for heavy edges, out of line.
• A sentinel bucket tail. Every empty bucket points at one permanently full block. A single "is the tail block full?" test now covers both the full case and the empty case.
• Digits converted with SSE. Three multiply-shift-mask steps per number became two instructions, pmaddubsw and pmaddwd.

Figure 7. (a) Instructions per full run, counted exactly with Valgrind. Simulated cache misses did not change. (b) The arithmetic that says the scoring machine was close to instruction-bound.

On the laptop it was even. On the board, with Track A at its normal time: 84.9 ms, 56.6 MB. My best run of the event.

09:33

I had 27 minutes left and one more idea: 32-bit labels, which kept the instruction count the same and cut simulated L1 misses by 10%. I pushed it as a board test. It came back at 94.5 ms on a box where Track A was 23% slow. Across every narrow-label version I'd tried, three of five board runs had been slow.

09:37: back to step 28's code for the freeze.

The freeze landed at 10:00 with step 28 on the branch, and Track D was 3rd on the live leaderboard. The final scores, measured on a holdout dataset nobody has seen, come out on November 13.

The 16-bit labels are still in the history, commit ca05322. I still don't know why the quiet box hated them.

Speed Demon 2026 was run by Hackathon Raptors. Full code, the Track D performance log with every board run ID, and the other three tracks: github.com/swapnilb222/sweet-dreams-demon-sub.

More about me: swapnilb222.github.io.

Connect with me on LinkedIn: linkedin.com/in/swapnilbhole22.