Developer/SchedulingQueueingDisciplines/LIFO/Fundamentals/lifo-stacks-and-scheduling-cache-locality-vs-fairness

LIFO: Stacks and Scheduling — Cache Locality vs. Fairness

Concept

Last-in-first-out inverts FIFO's fairness guarantee on purpose: the most recently added item is served next, not the oldest one. As a pure data structure this is just a stack — function call frames, undo history, backtracking/DFS traversal, expression parsing — anywhere "the last unresolved thing" is exactly what needs to be resolved next. But LIFO also shows up as a scheduling discipline in systems that have nothing to do with stacks as a data type, and that's the more interesting engineering case: production schedulers deliberately use LIFO for a subset of work not because order doesn't matter, but because LIFO improves cache locality in a way FIFO structurally cannot.

The Go runtime scheduler is a clean production example. Each logical processor (P) has a local run queue for goroutines, plus a single-slot runnext field that holds one goroutine with LIFO priority over the rest of the queue. When a goroutine spawns another goroutine, the new one goes into runnext and runs next, ahead of everything already waiting in that P's FIFO-ordered local queue. The reasoning is memory locality: a newly spawned goroutine is very likely to share hot data (stack frames, recently-touched heap objects, CPU cache lines) with the goroutine that just spawned it. Running it immediately, while that data is still warm in cache, is measurably faster than making it wait behind unrelated, already-queued work — even though this means older queued goroutines could in principle starve if spawning never stopped. Go bounds this risk with time-slice inheritance: a runnext goroutine inherits the remaining time budget of its spawner rather than getting a fresh slice, which caps how long the LIFO fast path can keep preempting the FIFO queue behind it.

The same tradeoff appears in thread-pool designs generally: a worker's local LIFO stack of just-submitted tasks (as opposed to a shared global FIFO queue) is a common work-stealing pattern precisely because the most recently submitted task on a given worker is the one most likely to still have warm caches on that worker's core — see Thread Pool Sizing and Worker Pool Design for the general pool-sizing tradeoffs this interacts with.

Tradeoffs

Discipline	Cache locality	Fairness / starvation risk	Where it's used
Pure FIFO queue	Poor — served item may be cold, unrelated to recently-touched data	None — strict arrival order, no starvation	Task queues, message brokers, anywhere order = correctness
Pure LIFO stack	Best-case excellent — most recent item is likeliest to be cache-warm	Real — an old item can starve indefinitely if newer items keep arriving	Function call stacks, undo/redo, DFS/backtracking, parser expression evaluation
Hybrid: LIFO fast-path + FIFO fallback (Go's `runnext`, work-stealing local stacks)	Captures most of LIFO's locality win for the common case	Bounded — time-slice inheritance / stealing thresholds cap how long FIFO items wait	Language runtime schedulers, thread pools under work-stealing

The pure forms are rarely what production schedulers actually run — the interesting engineering decision is how much LIFO priority to grant before falling back to fairness, not a binary choice between the two.

When to use / when not to

Use LIFO as a pure data structure whenever the problem is inherently "undo the most recent thing" or "resolve the innermost unresolved thing first" — call stacks, undo stacks, DFS, backtracking, bracket/expression matching. This isn't a performance choice, it's what correctly models the problem.
Use a bounded LIFO fast-path (like runnext) in a scheduler specifically to exploit producer-consumer cache locality between a task and the work it just spawned — but only when paired with a fairness bound (time-slice inheritance, a steal threshold, a max consecutive LIFO dispatches) so it can't starve the rest of the queue indefinitely.
Don't use unbounded LIFO for any workload where older items represent real user-facing latency (e.g., HTTP request queues, customer-facing job queues) — an unbounded LIFO scheduler there means the unluckiest request, the one that arrived first during a burst, could wait arbitrarily long while newer requests keep cutting in front of it.
Don't reach for a LIFO fast-path as a locality optimization unless profiling actually shows queueing/dispatch is the bottleneck — it adds real complexity (a second priority tier, a fairness bound to reason about) that isn't worth it if raw compute, not scheduling overhead, dominates.

Common pitfall

Adding a LIFO or "process newest first" fast-path to a request-processing queue for a perceived throughput win, without bounding how long an older item can be preempted — this silently turns a system with bounded worst-case latency into one with unbounded tail latency under sustained load, because every newly arriving item keeps jumping ahead of the backlog. This is exactly the failure mode Go's runnext design avoids via time-slice inheritance: LIFO priority is real, but capped, so the FIFO-ordered rest of the queue has a hard upper bound on how long it waits, not an open-ended one.

Engineering Lens

The design-review question isn't "FIFO or LIFO" as if it's binary — it's "does this workload have a locality relationship between recently-added and next-to-run work, and if so, how is the resulting unfairness bounded." Go's scheduler is a good reference answer: it takes the LIFO locality win via runnext, but caps the unfairness with time-slice inheritance rather than leaving it open-ended. A scheduler that grants LIFO priority without an explicit fairness bound hasn't made a deliberate tradeoff — it's just deferred a starvation bug until the workload pattern that triggers it shows up in production.