The List That Got Slower Than Its Complexity

We swapped a vector for a linked list so insertions in the middle would be cheap. Insertions did get cheaper. But the nightly aggregation pass, which just walks the whole thing and sums a field, went from about 40 ms to nearly 400 ms on the same data. Nobody changed the loop.

// before: contiguous storage
total = 0
for i in 0 .. n-1:
    total += items[i].value

// after: node-per-element, allocated as records arrived
total = 0
node = head
while node != null:
    total += node.value
    node = node.next