Move-to-Front Lists and the Working-Set Bound on Sequential Search

A sorted array gives binary search and a lower bound of log n comparisons. A linked list gives sequential search and no lower bound at all, because it cannot index. What a list can do instead is reorder itself: every successful search moves the found element to the front, so the next search for the same element costs one comparison. The policy is trivial to implement and has a provable guarantee against the best fixed ordering chosen with full knowledge of the future, which is a stronger statement than it first appears.

The operation and its cost

Move-to-front (MTF) requires a list that can unlink an element and relink it at the head in constant time. A doubly linked list with a sentinel does it in four pointer writes; a singly linked list needs a search for the predecessor, which turns the reordering step into O(n) and destroys the point.

/* Doubly linked ring with sentinel, as used by intrusive caches. */
void mtf_touch(struct dlist *l, struct dnode *n) {
    if (l->head.next == n) return;      /* already first: no work */
    unlink(n);
    insert_after(&l->head, n);
}

The guard matters more than it looks. In a workload with a dominant hot element, the element is already at the front most of the time, and skipping the splice avoids the two writes and the cache-line modification. The check costs one comparison and one load of the head’s successor, which is already in cache because the search just read it.

The search itself is a linear scan that stops on a match. Its cost is the position of the element in the current order, and the policy’s entire effect is on that position. For a request sequence with probabilities p₁ … pₙ, the expected cost of a fixed order sorted by decreasing probability is the entropy-like sum Σ i·pᵢ. MTF converges toward the same ordering but adapts to changes in the distribution, which is the property a fixed order lacks.

The competitive bound

The formal result is stated as an online algorithm competing against an offline optimum. The convention in the literature is that a request costs the position of the accessed item, with the front of the list at position 1. Let A be MTF and OPT be the best ordering for that sequence, chosen after seeing the entire sequence. Then for every sequence of m requests on n elements:

cost(MTF) ≤ 2 · cost(OPT)

The factor of two is not bounded by an additive term of order n alone: with the cost convention above, the guarantee is genuinely twice the offline optimum, which is stronger than the frequently quoted form with an additive term. The lower bound matches: no deterministic online algorithm attains a ratio below 2 against an offline optimum for this problem, so MTF is optimal among deterministic online orderings up to that constant.

The proof technique is a potential argument over the relative order of pairs. Define the potential as the number of pairs of elements whose relative order in MTF differs from their order in OPT’s final ordering. A request for element x costs its MTF position; the same request in OPT costs its position there. The difference in positions is bounded by the number of inverted pairs involving x, and moving x to the front changes the potential by exactly that many pairs in the favourable direction. Summing over the sequence yields the bound. This is the same accounting shape as the amortised analysis of a dynamic array, applied to a permutation rather than a buffer.

The bound is against a static optimum, not against an adaptive one. Against an adaptive adversary that can change the distribution, MTF still achieves a competitive ratio of 2 in the standard model, and the proof is a refinement of the same potential. What MTF does not achieve is optimality for every sequence: a request pattern that cycles through n elements in a fixed order makes every policy pay n per request on average, and MTF is no worse than that but also no better.

Why the constant is 2 and not 1

The factor of two is not an artefact of the proof. Consider two elements a and b that are requested alternately. Any ordering puts one of them behind the other, so half the requests pay at least two comparisons. MTF pays exactly that: after each access the requested element is at the front, and the other is at position two or beyond. A static ordering chosen optimally pays the same. The factor arises when the optimal ordering is better than MTF’s transient state, and the potential argument shows the transient disadvantage is bounded by the inversions that MTF has already been paid to fix.

There is a useful corollary for practical work: if the access distribution is stationary and known, a fixed order sorted by frequency beats MTF by up to the factor of two. If the distribution shifts on a timescale comparable to the list length, MTF wins because it tracks the shift with one splice per access. The decision is about whether the workload is stationary, not about which algorithm is asymptotically better.

The transpose heuristic and its weakness

An alternative self-organising policy swaps an accessed element with its immediate predecessor instead of moving it to the front. Transpose changes the order by one position per access, so a rarely accessed element migrates forward slowly and a frequently accessed one stays near the front without being repeatedly moved.

Transpose has no constant competitive ratio. An adversary can request the last element repeatedly: the first request costs n, and after it the element has moved forward by one position, so successive requests cost n − 1, n − 2, and so on. Over n requests the total is Θ(n²), while the optimal ordering has the element at the front and pays n in total. MTF pays n for the first request and 1 for each subsequent one, which is why it is the policy with the bound. On an alternation between the two ends of the list, transpose moves each requested element only one position, so neither reaches the front, and the requests keep paying close to n.

Transpose’s advantage is that it is stable. An element that is accessed once does not jump to the front, so a single burst of requests for an otherwise cold element does not disturb the order. MTF has no such inertia, and a scan through the list in order reverses it completely.

The scan problem

A sequential scan of all n elements is the worst case for MTF’s steady state. Before the scan, the order reflects the access frequencies. After the scan, the order is reversed, and the next scan pays the same n cost again but in the opposite direction. Repeated scans keep the list in a state where the next scan is maximally expensive relative to the previous access pattern.

This matters for caches and for page-replacement analogues. A workload that occasionally performs a full scan, such as a backup or a consistency check, destroys the recency information that MTF accumulated. Real systems mitigate this in two ways. The first is to treat a scan as a special access class that does not promote, which requires distinguishing scan requests from point requests at the interface. The second is to use a segmented policy, where new elements enter a probationary segment and are promoted only on a second access, which is the structure of the two-queue policies used in page replacement.

Where the list is the right container

MTF is a policy, not a data structure, and it composes with any container that supports O(1) relink. The linked list is the natural host because the splice is constant time and the elements do not move in memory. An array-based order would require shifting on every access, which makes the policy O(n) per access and removes its advantage.

The combination is used in three places.

Symbol tables with skewed frequencies. A compiler’s identifier table sees the same handful of names repeatedly within a function and a long tail of names once. MTF keeps the hot names at the front with one splice per access, and the list is short enough that the linear scan is cheaper than hashing. The crossover is usually a few dozen entries; beyond that, a hash table’s O(1) lookup dominates regardless of order.

LRU approximations. A strict LRU cache keeps a doubly linked recency list and moves a hit to the front, which is MTF on the cache’s entries plus eviction from the tail. The difference from a pure MTF list is that the list has a fixed capacity and the tail is discarded. The splice is the same; the policy adds a bound on length.

Instruction and branch caches in interpreters. A threaded interpreter’s dispatch can keep recently used handlers in a small front-loaded table, and MTF over that table adapts to the current bytecode without a profile.

In each case the list is small, the accesses are skewed, and the splice cost is comparable to the comparison it saves. For large n the linear scan is the problem, and the fix is an index rather than a better ordering.

Cost model details that change the decision

The competitive analysis counts comparisons. A real implementation also pays for the splice, and the splice is a write to two cache lines that the search has already read, so the marginal cost is small but not zero. Three effects shift the balance.

Write traffic in read-mostly structures. A shared list that is read by many threads and updated on every access needs a lock or an atomic on each access, which turns a read-only operation into a read-modify-write. MTF is a poor fit for concurrent read-mostly data for exactly this reason; the reordering is a write even when the logical operation is a read.

Cache-line ownership. In a multi-core system, moving an element to the front transfers ownership of the head’s line and the element’s line to the accessing core. If two cores access different hot elements, the head line bounces between them on every access, and the cost of that transfer can exceed the search saving.

Persistence. A list whose order is persisted pays a write per access. MTF is therefore inappropriate for structures backed by durable storage unless the reordering is batched.

The bound says nothing about any of these, because it counts comparisons. The engineering decision is whether the counted resource is the one that limits the workload.

A note on convergence

MTF converges to a stationary distribution in a precise sense: if each element is requested with a fixed probability pᵢ, the stationary probability that element i is at position k is the probability that exactly k − 1 other elements have been requested more recently, which for independent requests is a function of the pᵢ. The expected search cost at stationarity is therefore determined by the request probabilities and not by the initial order, which is the formal statement that the policy forgets its history.

The convergence rate is governed by the smallest probability in the distribution. An element requested with probability 10⁻⁶ stays near the front for on the order of a million requests after a single access, which is both the strength and the weakness of the policy: it retains a stale hot element far longer than a frequency-based policy would. Implementations that need to forget use a decay or a segmented structure rather than pure MTF.

The linked list’s role here is modest and essential: it makes the policy’s per-access cost independent of n for the update step, so the only term that grows with n is the search. The same splice primitive underlies Doubly Linked Lists and the Sentinel Header, and it is the same two-write relink that moves a freed block to the head of the list in Free Lists.