Least-recently-used against a policy that can see the future

Least-recently-used against a policy that can see the future

Three access patterns through a memory holding 6 blocks, each replayed twice: once evicting the least recently used block, and once evicting the block whose next use is furthest away — which requires knowing the whole future and is therefore not a policy anything can run. On the loop one block wider than memory, LRU evicts precisely the block wanted next and misses every time, 3.2× the optimum. On the other two the gap closes.

Drawn at 700 × 292, wide on the page. Everything above is what policy-gap returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

1 essay calls policy-gap. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.