Everyone is doing lists wrong

I started by trying to invent a better list. I wanted values packed together like an array, cheap access by index, and less work whenever something was inserted or removed. There were circular blocks, little tables of offsets, and increasingly elaborate explanations of how to move fewer things. Then a simpler question interrupted the design: did the values need to stay in that order?

Sometimes, obviously. A paragraph, a queue, and a replay log would be rather different objects if deletion shuffled their contents. But suppose I have a collection of live particles, and the update is independent for each particle. When one dies, the remaining particles do not need to preserve the history of which array slots they arrived in.

That is the complaint behind the title. We reach for a list when we need a collection, inherit a promise about order, and then spend time maintaining it. I was about to design a fairly complicated data structure to keep a promise I could have declined.

The expensive part was the promise#

Consider four values: [40, 10, 30, 20]. Remove the second one while preserving the relative order of the survivors, and the result must be [40, 30, 20]. In a conventional contiguous array, the values after the hole slide left. Put the hole near the beginning of a much longer array and nearly everything moves.

Keeping a literal array layout means element i lives at an address computed from the base, the index, and the element size. If logical positions change but that address rule stays fixed, some values have to change addresses. A compiler cannot optimize away an observable ordering requirement just because moving the bytes is annoying.

The circular-block idea relaxed that address rule: small offsets would describe how to read each block in order. That remains an interesting experiment for ordered editing. Once order became optional, though, most of that machinery lost its job.

Take the last value and put it in the hole instead. The result is [40, 20, 30]. All three survivors are still present, all live slots are still adjacent, and only one survivor changed position. Rust already calls this operation swap_remove. There is no new deletion algorithm hiding here.

fn remove_at<T>(values: &mut Vec<T>, index: usize) -> Option<T> {    if index >= values.len() {        return None;    }    Some(values.swap_remove(index))}fn main() {    let mut values = vec![40, 10, 30, 20];    assert_eq!(remove_at(&mut values, 1), Some(10));    assert_eq!(values, [40, 20, 30]);    assert_eq!(remove_at(&mut values, 99), None);    values.push(5);    values.sort_unstable();    assert_eq!(values, [5, 20, 30, 40]);}

This is enough for the small version of the experiment: a wrapper around a vector whose contract allows reordering. Call it PackedBag. Duplicates are welcome; membership tests are still a scan unless we add an index. An array position is a temporary location, not a permanent name for an entry.

For a fixed-size value, removing a known position takes a constant number of element operations. Finding that position can still take linear time. A large inline record takes more bytes to move than a small integer, and destroying an owned resource can do arbitrary work. The narrow claim is that deletion no longer moves the surviving suffix.

Identity costs something else#

Positions becoming temporary sounds fine until another object remembers one. Suppose a particle emitter keeps a reference to a particular particle. Replacing the contents of slot 12 must not silently make that reference identify whatever happened to be at the end.

I would keep persistent identity optional. The plain bag pays nothing for it. A tracked bag adds a table mapping an identity to its current position, plus a parallel array that records which identity owns each packed value. Removing an entry repairs the mapping for the value moved into the hole.

Before removing apple:  values        [ pear, apple, plum ]  slot IDs      [    7,     2,    9 ]  locations     7 -> 0, 2 -> 1, 9 -> 2After removing apple:  values        [ pear, plum ]  slot IDs      [    7,    9 ]  locations     7 -> 0, 2 -> vacant, 9 -> 1Plum moved. Its handle still names slot 9.

A handle also needs a generation. When slot 2 is reused, its new generation makes the old handle invalid instead of pointing at a replacement. A robust implementation needs a policy for counter exhaustion; retiring the slot avoids wrapping back to an old identity. Handles must also be tied to their owning collection, through a runtime owner tag or a type-level distinction. These are details a demo can omit and an actual container cannot.

This territory is already well explored. Rust's slotmap documentation describes generational keys and a dense variant with contiguous values and additional indirection. The useful experiment is deciding where those costs belong in a language's default collection, rather than pretending dense storage with handles has just been invented.

Stable handles also do not give stable addresses. The value can move during removal, sorting, or allocation growth. Direct references therefore need borrowing rules that prevent structural mutation while they are live. Address-sensitive values need a different representation, such as a packed array of pointers to separately allocated objects.

Sort when there is a reason#

The appealing workflow is to collect, update, and remove values cheaply, then sort when a consumer needs an order. A report might need names alphabetically. A renderer might need a particular draw order. Until that consumer runs, maintaining its ordering after every edit may buy nothing.

Sorting is still work. Rust's sort_unstable provides an in-place comparison sort with an O(n log n) worst-case bound. A fixed-width integer key permits a different experiment: four byte-wise radix passes for a 32-bit unsigned value, with temporary storage. That gives linear algorithmic work for that key width, but deciding which implementation is faster requires measurements.

A tracked bag cannot sort its payload alone. Doing so would leave handles pointing at the wrong entries. One approach is to sort a temporary array of identity IDs, then apply that permutation to the values while repairing the location table. The comparisons move small IDs; the final permutation needs only linear-many payload swaps. Finish all user comparisons before starting that permutation, and a comparator panic cannot leave the payload halfway rearranged with stale mappings.

Sometimes I would leave the payload where it is and sort a view of indices or references. That trades record movement for indirection during the next scan. Large records and small integers need not make the same trade. Either view also needs an invalidation rule when its backing collection changes.

There is an easy mistake here: sorting does not recover discarded insertion order. Chronology needs a stored sequence number. Deterministic output among equal keys needs a tie-breaker. A stable sort preserves the order it receives among equal elements; it cannot reconstruct the order that swap-removal already destroyed.

And if the next operation always needs the smallest value, repeatedly sorting the whole bag is a poor plan. A priority queue expresses that requirement directly. The decision depends on how often order is consumed, not just how often values change.

Growing the array is still a separate problem#

Unordered deletion solves the hole. It does not conjure spare storage after a full buffer. I would keep length and capacity separate, reserve ahead when the eventual size is known, and otherwise grow geometrically. If capacities double, the old capacities copied along the way form a geometric sum: total relocation over many appends is linear, even though one unlucky append can still move the entire buffer.

The Rust prototype delegates that job to Vec. Its documented guarantees include amortized constant-time push without promising a particular growth factor. A full-buffer append can reallocate; an ordinary removal does not automatically shrink capacity. Those are useful defaults to preserve in the experiment.

Shrinking storage after every removal would undo some of the benefit. A runtime could trim only after capacity has been substantially underused, or expose an explicit trim operation. Removing a thousand values and returning a thousand slots to the operating system are different jobs. So is running a thousand destructors.

What Wasm changes#

Compiling the same Rust wrapper to WebAssembly should not be confused with improving its data structure. Swap-removal remains a few loads and stores. Sorting still needs its passes. The more interesting question is what we could do if we controlled the language runtime as well as the collection.

Wasm 3.0 allows a module to address multiple linear memories directly. For a workload dominated by one large bag, I would try giving its payload a memory of its own, keeping both handle metadata and sorting workspace elsewhere. This is a proposed runtime layout, not what an ordinary Rust target flag creates.

Memory 0   [ runtime state | handle tables ]Memory 1   [ live values   | spare capacity ] -> grow hereMemory 2   [ reusable sorting workspace    ]

The distinction is between making the module's memory larger and making one allocation inside it larger. In a shared heap, another allocation may sit immediately after the bag. Growing linear memory does not move that neighbor out of the way. With a dedicated payload memory, the bag owns the growing end, so it need not allocate a replacement buffer merely to extend its capacity.

Successful memory.grow preserves existing Wasm offsets and appends storage, as specified by the memory-growth rules. The engine can still relocate the host allocation. Wasmtime's reservation documentation explicitly describes copying when growth exceeds the available reservation. That makes reservation size and growth latency part of the benchmark, not a detail we can wish away.

There are two substantial limits. Core Wasm has no matching memory-shrink instruction, so freeing a bag does not shrink its linear memory. And the memory selector is an instruction operand, not an ordinary runtime array index. A few dedicated regions are plausible; giving every dynamically created list its own interchangeable memory is a different engineering project.

I would reuse sorting scratch space and expose batch operations to the host. Memory64 offers more address space, not an automatic speedup. SIMD is worth investigating for scans and numeric kernels, but ordinary SIMD and bulk-memory operations already existed in Wasm 2.0. The 3.0 label alone tells us little about the generated loop.

Give the compiler an honest contract#

With a new language, I would distinguish a bag from a sequence in the type system. Sequence operations preserve an order. Bag operations promise membership and whatever explicit identity scheme the type provides. Asking for an ordered view becomes visible in the program, as does asking for persistent handles.

That contract gives the compiler useful room. A bulk filter can compact survivors in a single pass rather than repeatedly close individual holes. Construction with a known output length can reserve once. A numeric scan can operate directly over the packed values. None of this permits reordering observable callbacks, resource cleanup, or floating-point reductions without additional semantic permission.

Ownership is part of the design too. Bend's affine arrays are an interesting way to express mutation with a single owner. But an array-shaped API does not establish a particular backend layout. A Bend2 port would still need its lowering inspected before claiming the same contiguous-storage behavior or performance as the Rust version.

The first benchmark should be deliberately unexciting: the wrapper against a raw vector using swap-removal, then the tracked version to measure the price of handles. Ordered removal belongs in a separate comparison because it promises more. After that, measure scans, random reads, growth spikes, sorting, and peak memory in native and Wasm builds. There is no measured Wasm speedup to report for this experiment yet.

Keep the order that earns its keep#

Plenty of programs really do need sequences. A queue's next element, a document's next word, and an event log's next record are part of their meaning. Even the particle example stops being safely unordered if updates depend on earlier updates. Those requirements deserve an ordered representation.

But a collection whose order nobody observes can be much simpler. Keep the values packed, append at the end, fill holes from the tail, and establish a useful order at the point where something consumes it. Add handles only when something must remember an entry.

I still like the idea of a better list. In this case, the useful improvement was noticing that I did not need a list for most of the work.