Where we left off
When I wrote Every Map Everywhere All at Once, Shoal (our GPU-based sampler) was very fast on congressional maps and middling on anything bigger than about 50 districts, which became a problem rather quickly once we set out to build neutral ensembles for every state legislature. This post comes before a second one, in which we will release a complete dataset of neutral redistricting ensembles for state legislative chambers, but before that, I thought it would be worth a quick write-up of how we optimized the algorithm to draw these ensembles far faster than they could ever have been drawn with redist.11 For the uninitiated, redist is ALARM’s open-source R package and the standard tool for this, so every number here is measured against it on the same machine.
What changed
By the end of Every Map Everywhere All at Once, we had a first version of a state-of-the-art and fairly novel sampler for neutral maps, but while it was very, very fast on congressional maps, it struggled a lot more on larger problems like state legislatures. We came up with two algorithmic improvements since then, both aimed mainly at state legislative maps, though they ended up improving congressional maps substantially as well.
Shoal v2
The main breakthrough was utilizing the GPU to a much fuller extent than before. The v1 handed the GPU one run to complete at a time, which is acceptable, and not very noticeable, for 14 districts. However, when we benchmarked it on state legislative maps ahead of our big state legislative run,22 My Mac was next to me that night, and even though I was a few thousand miles away from the Mac mini, I could feel its fans running at max volume. we found that those runs leave most of the chip sitting idle, so Shoal v2 packs many independent runs into every GPU call. The same seeds go in and the exact same maps come out as before, just 1.4x to 3.4x faster depending on the state!
Shoal v3
Breaking up shared ancestry. Sequential samplers like Shoal and redist do not draw maps one at a time;33 This was the original thesis for why a GPU could parallelize the whole process. they work much more like natural selection, growing a broad batch of maps together, cutting off one district per round, and at each step dropping the weakest partial maps and copying the strongest.
This keeps the math exact, but on a state legislature, with 100 or more rounds in total, the copying compounds round after round, so by the conclusion of a run, a batch of maps likely traces back to only a handful of ancestors, and many of the “different” maps share most of their district lines with each other.
Shoal v3 adds one step to counter this: once a batch is finished, every map gets 4,096 small random moves along its district boundaries44 Each move is accepted or rejected so that the set of maps we are sampling from never changes, which is what keeps Shoal v3 exact., so the near copies drift apart into genuinely different maps. Each map then carries far more information than before, and on the North Carolina state house that one step takes Shoal from about 6x to about 19x faster than redist in independent maps per second, one of the biggest advances we have made to the algorithm.
How much faster
On congressional maps, Shoal v2 goes from an average of about 23x redist to about 36x, and Shoal v3 averages about 63x, though we were never really optimizing for congressional maps, because those finish quickly anyway. The state house numbers are the ones that matter, and there the first version barely beat redist at all (1.7x),55 In fairness to v1, a win is a win, and almost 2x is still good. while Shoal v3 is at 19x. To caveat these results, the moves do cost raw speed, since Shoal v3 draws a quarter to half as many maps per second as Shoal v2 on congressional maps, but each of those maps carries so much more new information than before that independent maps per second, the one number I have truly been optimizing for, still goes up everywhere!66 Independent maps per second counts how many genuinely distinct neutral maps a sampler produces each second, after discounting near copies: between-run effective samples per second, as a geometric mean over 4 statistics (cut edges, split counties and the two coordinates of an anchor district’s centroid).
More districts
Holding the state fixed at Pennsylvania and growing the map from its 17 congressional districts to its 50 senate and 203 house seats77 Pennsylvania’s is the second-largest state house in the country, after New Hampshire’s. tells a more honest story: Shoal’s lead shrinks, from 22x to 8x redist for Shoal v2 and from 61x to 20x for Shoal v3, because at that size every run in both samplers descends from a single ancestor and is worth about one independent map. The cliff is past that. At 300 districts redist never finished a batch of 10 runs in 3 hours, while Shoal v2 finished 31 of 32 in under 8 minutes, and at 400 neither sampler is usable yet.88 New Hampshire, with its 400 seats, is the real barometer for how good our algorithms are.
In wall-clock terms, at 203 districts, the largest size where every sampler finished, 1,000 independent maps of the Pennsylvania state house take redist about 14.5 hours on the Mac mini, and Shoal v3 a little under 44 minutes.
On a rented GPU
Once I was satisfied with v3, we had one more hill to climb before it could cook us up some state legislative ensembles: for all of this time, Shoal was built for and ran only on Apple’s Metal, and like anything else in the GPU world, it scales with compute. After a lot of wrangling with ChatGPT 6-Astra, Shoal runs on NVIDIA now. The CUDA version draws the same maps as the Apple one, but on a big enough card it runs much, much faster, about 5x faster than the Mac mini’s GPU on a single run and nearly 11x faster with 32 runs at once.
So, as one does, I went to a neocloud and rented a GPU. I ran Shoal on an RTX 5090, and since one run can’t fill a card that big, the fairer (and more impressive) test is running many at once: 32 congressional runs of North Carolina come out at 386x redist, against 36x for the Mac mini’s GPU on the same job. This, notably and unfairly, compares Shoal on a datacenter GPU with redist on a Mac mini’s CPU, so take the ratio with a grain of salt; a big server CPU would speed redist up, but nowhere near enough to close a gap like this.
| Mac mini GPU 10-core M4 | RTX 5090 rented | |
|---|---|---|
| North Carolina, Congress one run of 10,000 maps | 29x | 153x |
| North Carolina, Congress 32 runs at once | 36x | 386x |
| North Carolina, state house Shoal v2 | 5.7x | 27x |
| North Carolina, state house Shoal v3 | 19x | 37x |
What it is for
There is one peripheral caveat for state houses. On chambers of 100 or more districts, runs of finite size from either sampler, redist included, end up descending from a few ancestors and overstate cut edges slightly. Shoal v3’s final moves remove this artifact, and on the Indiana and Virginia houses it matches redist, so every state house in our dataset uses it.
State legislatures are where neutral ensembles have mostly been too slow to run, and in a lot of ways they are where most of the actual line drawing in the country happens, with thousands of seats, a patchwork and motley crew of state rules and very little of the luster congressional maps get.
You’ll see why we focus so much on state legislatures very soon.
All timings are full run times on an Apple M4 Mac mini unless noted, against redist 4.3.2 with default settings on all 10 CPU cores.
Citation
Please cite this work as:
Ryan McComb, "Cache Me If You Can", Cohese, October 2026.
Or use the BibTeX citation:
@article{mccomb2026cache,
author = {Ryan McComb},
title = {Cache Me If You Can},
journal = {Cohese},
year = {2026},
month = {October},
}