three layouts that failed before the flat one worked

The generator for a memory-hard puzzle produces many millions of items and then visits their neighbours in a pattern with almost no locality. The natural data structure is a matrix of buckets. The natural implementation of that, in a language whose library type is a growable vector of growable vectors, is a nested structure — and that implementation was written, measured and thrown away three separate times.

Each attempt failed for a different reason, and all three reasons were the same reason: the layout of memory was being decided by the shape of the type rather than by the access pattern. Nested vectors put every row in its own allocation, so a pass touching all rows pays an indirection per row and the prefetcher learns nothing. A counting redistribution moved the cost instead of removing it, because every item was still written twice. A two-dimensional nesting made iteration quadratic in the number of buckets.

What worked was copying the reference design without improving on it: one flat allocation, an index computed from bucket coordinates before any item exists, and capacities sized from tail bounds so nothing is resized mid-pass. Items are born in the bucket they will finally occupy, so the redistribution step does not exist.

The honest summary is that three attempts went into learning that a data structure is a memory layout, and that the model worth copying was already correct. The residue is a benchmark that now says where the next bottleneck is, and it is not placement.