the amortized-cost versus worst-case-latency tradeoff

Suppose your morning commute averages 20 minutes, which sounds fine — until one day a closed road makes it 90 minutes and you miss a meeting. The average was honest, but it hid a rare, painful spike. An allocator has the same two-faced character. Amortized cost is the average cost per operation over a long run; worst-case latency is the longest any single operation can take. The deep tradeoff of allocator design is that the tricks which make the average wonderfully cheap can hide rare, very expensive operations — and for some programs that rare spike is what actually matters.

Here is the mechanism concretely. Most of a fast allocator's malloc and free calls are nearly free — pop or push a thread-local free list, a handful of instructions. But occasionally one call triggers a big job: the thread cache is empty so it must take the central lock and refill a batch; the central heap is empty so it must ask the operating system for more memory with mmap() (a system call, slow); or a coalescing or purging pass runs. Amortized analysis spreads the cost of those rare big jobs across the many cheap calls in between, and the per-call average stays low. That is genuinely the right way to think about throughput. But latency does not average: the unlucky single call that hits the mmap() or the lock or the purge can take hundreds or thousands of times longer than a normal one. Measure average latency and the allocator looks great; measure the 99.9th-percentile (tail) latency and that occasional spike is plainly visible.

Why this distinction is not academic: for a batch program that just needs to finish fast, amortized (average) cost is exactly what you care about, and a slightly higher rare cost is invisible. But for an interactive service, a trading system, or anything real-time, a single 5-millisecond stall in the middle of a request is a real, user-visible failure even if the average is microseconds — tail latency is the metric. This is why real-time and low-latency systems often avoid the general allocator on their hot path entirely, preallocating with pools or arenas so that no malloc call can ever wander into a slow path. The honest summary: amortized and worst-case are different questions, an allocator can be excellent at one and poor at the other, and you must know which your program is actually asking.