The Twelve Millisecond Append

A request handler appends one row to a long-lived Python list per request. Median latency is 41 microseconds. p99.99 is 12 milliseconds, and the slow requests are scattered rather than bursty. What is the best reading of this?

Switch to a linked list, which gives worst case $O(1)$ append with the same scan performance.

Some appends trigger a reallocation that copies the whole backing array. Amortized $O(1)$ bounds the total over a sequence, never any single call, so presize the list or chunk it if the tail matters.

Amortized $O(1)$ means every call is constant once the container is warm, so the spikes must be garbage collection.

Amortized bounds are averages over random inputs, so a different traffic pattern will make the spikes go away.