The memory hierarchy and information retrieval

Two articles, one cost model¶

Wikipedia files computer memory under hardware and information retrieval under library and information science. Read the two articles side by side and the same sentence keeps appearing in different vocabulary. The memory article says storage is organised in a hierarchy because fast storage is expensive and small; the retrieval article says an index exists because reading every document is unaffordable. Both are statements about a budget of accesses, and both are solved the same way: keep a small thing that tells you where the large thing is.

Put concretely, every classical retrieval structure is a hierarchy device.

Five retrieval structures and the level of the storage hierarchy each is built to reach. The middle column is the structure’s definition; the right column is the reason it was invented. Sources: Bayer and McCreight (1972) for the B-tree; Moffat and Zobel (1996) for skip pointers; Jégou, Douze and Schmid (2011) for product quantisation. Table: Programming Language Atlas.

The claim this page defends is narrower and more testable than “locality matters”. It is that the complexity class of a retrieval structure does not predict its cost, and the pair (bytes per item, access pattern) does. Two structures with identical asymptotics differ by 3.0× on the same keys below, and one representation beats another by 34× in one regime and loses to that same one by 89× in another. None of those numbers are visible in a complexity class, and all of them fall out of the hierarchy.

The rest of the page is in three movements: the hierarchy measured from C, the retrieval structures measured on the same machine, and the history that explains why the winning structure has changed roughly once a decade without the algorithms changing at all.

Back to top

The hierarchy, measured¶

The hierarchy is usually presented as a table of numbers from a vendor’s manual. It does not have to be: five lines of C measure it directly. Fill an array with a single random permutation cycle, one element per cache line, and walk it. Because the address of each load is the value the previous load returned, the processor cannot start the next access until the last one has finished, and it cannot prefetch — there is no arithmetic pattern in the addresses to extrapolate. What the loop reports is load-to-use latency, and nothing else.

/* The whole measurement. `next` holds one permutation cycle over the working
   set, one element per 64-byte line, so the address of the next load is the
   value returned by the last one and nothing overlaps. */
for (long i = 0; i < steps; i++)
    p = buf[p];

Sweeping the size of that array and plotting the time per load gives the levels directly. Each plateau is a level of storage; each rise between plateaus is a capacity being exceeded.

The plateaus are unambiguous and they line up with what the machine reports about itself. The flat region up to 32 KiB is the L1 data cache, whose size /sys gives as exactly 32 KiB. The step to roughly 4.2 ns from 48 KiB is L2. The long shelf either side of 4 MiB is the shared L3. Past that, every load is a round trip to DRAM.

The useful way to read those numbers is not in nanoseconds but in the work they displace. At 2.8 GHz, a load that hits L1 costs about 4 cycles; one that reaches DRAM costs around 361. A modern core retires up to four instructions per cycle, so a single miss to memory is worth on the order of a thousand instructions that could have run instead. This is the number that makes retrieval a memory problem: an index that saves a comparison and costs a miss has lost.

Working set is the size of the chased array. Lines is that size in 64-byte cache lines, which is also the number of distinct addresses the cycle visits.

The complete sweep. Each figure is the median of three back-to-back runs, each of which already reported the minimum of five timed passes; the spread is the largest minus the smallest of those three medians. The last column is the cost of address translation, and it is discussed in its own section below. Source: data/memory/latency.c.

Back to top

The unit of transfer is a line¶

C’s model of storage is byte-addressed: sizeof(char) is 1, a pointer names a byte, and the standard is careful to say that an object is a region of bytes. No machine that runs C has moved a single byte between memory and cache in decades. The unit of transfer is a cache line, 64 bytes on every target this page touches, and it is fetched whole. Reading one byte and reading its 63 neighbours are the same operation at the same price.

That has a directly measurable consequence: a loop that touches every element of an array and one that touches every sixteenth element read the same number of lines, and should therefore take a similar time, while doing sixteen times less arithmetic. Sweeping the stride over a 64 MiB array — far larger than any cache here, so every line must be fetched — tests exactly that.

A stride of 16 elements is exactly one 32-bit element per 64-byte line, which is the point where the two cost columns must coincide.

A stride sweep over a 64 MiB array of 32-bit integers. The third column is what the loop costs per element it read; the fourth is that cost re-expressed per cache line, which is the unit actually moved. Source: data/memory/stride.c, minimum of seven passes.

The two columns say different things and both are worth reading. Per element, the cost rises 8.9× between stride 1 and stride 16 — the loop is doing a sixteenth of the arithmetic and getting slower, because the arithmetic was never the cost. Per line, the cost falls, from 10.4 ns to 5.8 ns, because at stride 1 that figure includes sixteen additions and at stride 16 it includes one. Past stride 16 there is nothing left to save and the cost rises again: at 128-byte stride the pair-line prefetch that was helping stops helping, and each line arrives on its own.

So much for the transfer. The other half of the cost is order, and it is bigger. Three loops over the same 64 MiB array, visiting the same one million lines, one line apart, differing only in the order of visits and in whether one visit’s address depends on the last one’s value:

The gap between the first and last bar is 21×, on identical data doing identical work. But the middle bar is the one that carries the lesson. It is the same random order as the third, over the same addresses; the only difference is that its indices are read from an array rather than from the array being walked, so the processor can compute several addresses before any of them has returned and keep a dozen misses in flight at once. That costs 2.1× sequential, not 21×.

The line has a second consequence that this page does not measure and the atlas does. Two threads writing to different objects in the same line contend for it as though they were writing to the same object, which is why the synchronisation page can take a four-counter structure from 21 ns to 1.4 ns per increment by adding _Alignas(64) and changing nothing else. Same 64 bytes, same declaration-order lever, seen from the other side.

Back to top

Which wall you hit: cache, or TLB¶

The two series in Figure 2 are the same program, over the same addresses, in the same order, with the same cache hierarchy underneath. They differ in one system call. One maps its buffer with the default page size and the other adds madvise(MADV_HUGEPAGE), which on this kernel — transparent huge pages set to madvise — gets 2 MiB pages instead of 4 KiB ones.

/* The only difference between the two series. mmap rather than malloc so the
   page size is this program's decision; MADV_HUGEPAGE is advice, so the run
   reads /proc/self/smaps_rollup afterwards and prints what it actually got. */
size_t *buf = mmap(NULL, bytes, PROT_READ | PROT_WRITE,
                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (huge && madvise(buf, bytes, MADV_HUGEPAGE) != 0)
    fprintf(stderr, "# MADV_HUGEPAGE refused\n");

Advice is not a guarantee, so the run reports what it was given rather than what it asked for. The default run prints AnonHugePages: 0 kB and the huge-page run prints AnonHugePages: 524288 kB, which is the entire 512 MiB mapping. That control is the reason the comparison is worth making: without it, a silently refused madvise would look like a result.

The effect is confined to one end of the sweep, and that is the whole point. Below 8 MiB the two curves are on top of each other: page size cannot matter while the working set fits in cache, because the translation of a resident line is already cached too. From 16 MiB up, the 4 KiB series sits a consistent 1.23× above the 2 MiB one, across nine sizes and a factor of thirty-two in working set.

Sizes below 16 MiB are omitted: the two series are within their own run-to-run spread of each other there, so a ratio would be reporting noise.

The DRAM-resident part of the sweep, where the working set is far beyond any cache and the only variable left is address translation. Source: data/memory/latency.c.

That difference is not a cache effect. It is the page walk. Every load has to turn a virtual address into a physical one, and the translation lookaside buffer caches the results; when the buffer misses, the processor walks the page tables, which is itself a chain of dependent loads into memory. A second-level TLB of the size Intel documents for this microarchitecture — 1536 entries, shared between page sizes — reaches 6 MiB of address space with 4 KiB pages and 3 GiB with 2 MiB ones. The chase visits a new page on nearly every hop, so past 6 MiB the 4 KiB series is paying for a walk on essentially every load, and the 1.23× is what a walk costs when the tables themselves are in cache.

Back to top

What C says about memory, and what it does not¶

C is the language this page is written in, and not by accident. The connection runs in both directions and each one is worth stating precisely, because the usual summary — “C is close to the metal” — is wrong in a way that matters here.

What the language gives you¶

C’s model of storage is the one the hierarchy rewards. An object is a region of data storage; it has a size in bytes, an alignment, and a representation that the program may inspect. Arrays are contiguous, so index arithmetic is address arithmetic. Structure members appear in declaration order. None of that is inevitable: in a language whose aggregate is a reference to a heap node, a programmer who wants two fields adjacent in memory has no way to ask for it. In C the layout is written down in the declaration.

The parts of the C standard that make layout a programmable property. None of these mentions a cache, and all of them are about where bytes are. Source: ISO/IEC 9899:2024 (C23), clauses as cited.

Put those together and a cache-conscious data structure is ordinary C. The B-tree node measured further down is a declaration and a loop:

/* The node of the static B-tree measured further down. Sixteen 32-bit keys is
   exactly 64 bytes, and alignas puts the array on a line boundary, so a visit
   to a node is one line fetched and never two. Both halves of that sentence
   are C -- and neither the 16 nor the 64 is: the standard has no name for a
   cache line, so the number is a constant this program was told. */
#include <stdalign.h>
#define B 16                       /* keys per node = 64 / sizeof(unsigned) */

alignas(64) unsigned btree[NBLOCKS * B];

/* Rank within one node: sixteen independent compares over one line, summed
   rather than branched on, so nothing has to be predicted and the sixteen
   loads all hit the line that the first one brought in. */
static unsigned rank(const unsigned *node, unsigned x)
{
    unsigned r = 0;
    for (unsigned i = 0; i < B; i++) r += node[i] < x;
    return r;
}

What the language withholds¶

Everything about the hierarchy itself. The standard describes an abstract machine in which every access costs the same, which is to say it describes no cost model at all. There is no portable way to ask how large a cache line is, how many levels of cache exist, whether an address is resident, or whether a load will be prefetched — and the standard is right not to offer one, because a conforming implementation may target a machine with no cache at all.

The hierarchy is entirely outside the language. Every row is something a cache-conscious program needs and every answer is an extension, a platform interface, or a measurement. Source: ISO/IEC 9899:2024, and the named compiler and POSIX interfaces.

So the position is exact, and it is the reason C keeps showing up in retrieval systems. C hands the programmer complete control over where bytes are and complete ignorance of what that costs. The control is what makes a cache-conscious index expressible; the ignorance is what makes measurement compulsory. Every number on this page exists because there was no way to look it up in the standard.

The atlas takes the layers under this in two other places: what the implementation is permitted to do with your code between the source and the instructions, on the C article, and where the language stops and the platform ABI begins, on the calling conventions page. For how other languages in the index answer the same question, the memory and runtime page classifies all of them.

Back to top

The anatomy of an inverted index¶

An inverted index answers “which documents contain this term” by storing, for every term, the sorted list of documents that contain it. It is called inverted because the natural direction of a document collection is document → terms and this is the transpose. Everything a Boolean or ranked retrieval system does on top of it — conjunction, disjunction, phrase matching, scoring — is arithmetic over those sorted lists.

The two structures have opposite characters, and the rest of this page measures them separately for exactly that reason.

The two halves of an inverted index, and why they need different measurements. The bottom row names the two sweeps that follow. Table: Programming Language Atlas.

The conjunction itself — the AND of two terms — is the oldest operation in the field and the one every implementation still spends its time in. Two sorted lists, one output: advance whichever cursor is behind, and emit when they agree. The algorithm has not changed since the 1960s. What has changed, several times, is how the integers are stored, and the diagram below is the reason the change was worth making.

Two design pressures pull in opposite directions here, and every representation measured below is a different resolution of them. Compressing the postings makes each list smaller, so more of it fits in a faster level of the hierarchy and fewer bytes cross the bus — but a compressed sequence has no random access, so it cannot be skipped, only decoded. Blocking restores the skip at the cost of a header per block and slightly worse compression. Which resolution wins is not an algorithmic question. It is a question about the machine, and the answer has changed with the machine roughly once a decade.

Back to top

Finding the term: six layouts of one key set¶

The dictionary problem, reduced to its core: given n sorted 32-bit keys, is a given key present? Six implementations, one key set, one query stream, one machine. Every variant but the first is O(log n) or O(1), so complexity theory says five of the six should be indistinguishable and the sixth catastrophically worse. The measurements say something else.

The six variants. All six answer the identical query over the identical keys, and all six are checked against each other for every size before any of them is timed. Source: data/memory/search.c.

Read the right-hand end first, at 16 Mi keys — 64 MiB of them, well past every cache on this machine. Binary search costs 576 ns. The B-tree over the same keys costs 189 ns, which is 3.0× faster for the same answer, the same key count, the same complexity class and, at every size in this sweep, a structure of exactly the same size. Nothing about that gap is algorithmic. Binary search touches one cache line per comparison and uses four bytes of it, so it pays about 24 line fetches for 24 useful comparisons; the B-tree reads a whole line and uses all sixteen keys in it, so it pays six.

The breadth-first (Eytzinger) layout is the same idea applied more weakly, and it is the clearest illustration of what layout can and cannot buy. It is the identical binary search over the identical keys with only the order they are stored in changed, so that the nodes visited early are adjacent. The margin that buys is a median 3.9× and stays above two all the way from sixteen keys to 1,048,576, where it is still 2.5× — five orders of magnitude of key count for a change that touches no code. Then it decays, and by 16,777,216 keys it has all but gone — 1.03×, which is within the run-to-run spread of no difference at all. Once the structure is large enough that even the top of the tree is evicted between queries, adjacency has nothing left to buy, and the deep levels of a breadth-first array are scattered where the deep levels of a sorted one are at least locally ordered. Layout buys residency, and residency runs out.

The sign of that last comparison is the least stable number on this page: rerunning the sweep has put the breadth-first array a few per cent either side of the sorted one at 16 Mi keys. The decay reproduces; which of the two is fractionally ahead at the end of it does not, and no argument here rests on it.

The hash table is the flattest line on the chart, from 7.4 ns at sixteen keys to 27.8 ns at sixteen million, and it is worth being precise about why: not because O(1) beats O(log n), but because it makes exactly one dependent load where the trees make several. Its cost curve is the DRAM latency curve from the first section, shifted. It also pays for that with size — at load factor 0.5 the table is 8 bytes per key against 4 — which is why it leaves cache an octave before the sorted array does, and why it is the wrong structure the moment the query stops being exact-match.

Bytes per key is a property of the layout rather than a measurement: the arrays hold each key once, the hash table runs at load factor one half, and the B-tree would pad its last node at a size that is not a multiple of sixteen — none of these are, so it does not.

Five points off the sweep, in nanoseconds per query, with the growth from the smallest size to the largest in the final column. A structure whose cost is a complexity class would grow by the ratio of the logarithms, which is 6×; none of them does. Source: data/memory/search.c, GCC 13.3 at -O2.

A digression that turns out to be the point¶

The branchless variant is the same binary search with the comparison folded into the index arithmetic instead of driving a jump. Under GCC it is not measurably different from the branchy version at any size. Under Clang it is a different program.

/* The source that is supposed to be branchless. Whether it is depends
   entirely on whether the compiler chooses a conditional move. */
while (len > 1) {
    unsigned half = len >> 1;
    base += (base[half - 1] < x) ? half : 0;
    len -= half;
}

GCC 13.3 at -O2 emits one cmov in the entire program; Clang 18.1 emits four. The consequence is not subtle.

Clang’s branchless search is 3.8× faster than its branchy one at sixteen keys, where the whole array is in L1 and the only cost left is the misprediction the branchless form removes. It stays ahead up to 1,048,576 keys. At 2,097,152 keys it is 1.2× slower, and it stays slower for the rest of the sweep.

The crossover is not arbitrary. 1,048,576 keys is 4 MiB of array and 2,097,152 keys is 8 MiB, against a pointer chase that was still on its L3 plateau at 8 MiB and off it at the next size up. The rewrite stops paying just before the array stops fitting, which is what it should do: a binary search is only partly resident long before it is wholly evicted, since the top of the tree is visited on every query and the bottom on none twice. The mechanism is this: a mispredicted branch is a speculative load down the wrong half of the array, and while the working set is in cache that speculation is wasted work, but once it is in DRAM that load is, half the time, a prefetch of the half the search was about to want — and a prefetch is worth far more than a mispredict costs. Removing the branch removes the speculation, and out of cache the speculation was the only thing overlapping the misses.

Back to top

Intersecting the lists: five representations¶

Same discipline as the dictionary sweep: five representations, one pair of postings lists, one answer, checked against each other before anything is timed. The collection is 8,388,608 documents, and the two sweeps below vary the two things that actually decide the outcome — how long the lists are, and how different their lengths are from each other.

The five representations. The bytes-per-posting column is a property of the encoding rather than a measurement; the varied figure is because a shorter list has larger gaps between its docids and so needs more bytes for each. Source: data/memory/postings.c.

Two results here, and the first one is unwelcome. Compression loses. At every equal length, the flat variable-byte encoding is slower than reading raw 32-bit docids — by 2.9× at the largest size — despite moving a quarter of the bytes. The reason is in the third section: the merge reads both lists in address order, which is the case the hardware prefetcher exists for, so the three bytes per posting it saves were nearly free to move anyway; and variable-byte decoding is a chain of dependent shifts and branches on the continuation bit, which is exactly the shape that does not overlap. Cutting the encoding into blocks makes it slower again at every size but the largest, because blocked gaps restart at each boundary and there is nothing here to skip. At 4 Mi postings the two cross and the blocked form becomes the quicker of the two, by 2% — the first sign of the effect the next sweep is entirely about.

The second result is the bitmap. Its cost is flat — about 492 µs, which is what it takes to read 2048 KiB of bits and popcount them — because a bitmap is sized by the collection and not by the term. That makes it 89× worse than a merge for a term appearing in 1,024 documents, and 34× better for one appearing in half of them. On this collection the crossing falls between 64 Ki and 256 Ki postings per list.

List lengths are the actual lengths generated rather than the requested powers of two: the generator stops when its cumulative gaps reach the end of the collection.

Equal-length lists, microseconds per conjunction. Every representation returns the identical count, which is checked before the timing starts. Source: data/memory/postings.c.

Everything changes. Against a list of 4 Mi postings, a linear merge of raw docids takes 11.3 ms and galloping takes 190 µs: 60× faster, because it never reads most of the long list. The flat compressed encoding gets none of that — 0.92× the merge, which is to say no better — because it cannot skip: to know where the thousandth posting is, it must decode the nine hundred and ninety-nine before it.

The blocked encoding gets both. It costs 279 µs, within 1.5× of galloping over uncompressed data, while storing the list at 1.12 bytes per posting rather than 4. That is a 3.6× smaller index for a 47% slower query, and it is the trade every production search engine has taken since Moffat and Zobel described self-indexing inverted files in 1996. It is also 37× faster than the same compression without the headers, which is the entire contribution of that paper, reproduced here in one column.

Skewed lists, microseconds per conjunction, with the shorter list fixed at 1,024 postings. The first row is the same measurement as the first row of the previous table, run again from the same seeds. It is also the shortest and so the noisiest, and the two runs of it agree only to within 12%. That is the honest bound on an absolute time here, and the reason every claim on this page is a ratio between two things measured in the same run rather than a magnitude. Source: data/memory/postings.c.

Back to top

Reading the crossovers¶

Collecting the two sweeps. Two of these bars are honest algorithm changes and are marked as such: a bitmap and a merge have different complexity, and so do a gallop and a merge. Every other bar is the same algorithm over the same data with the bytes somewhere else or touched in a different order, and those run from 1.2× to 37×. The point of putting them on one axis is that a reader cannot tell, from the sizes alone, which kind each one is.

The choice is made from three properties of the data, in this order.

1. Footprint. Bytes per item times items. Compare it against the capacities in Figure 1: that comparison, and nothing else, tells you which level will be answering. A structure that halves its bytes per item does not become twice as fast, but it does move its crossing point an octave to the right.
2. Dependency. Can the next address be computed before the current load returns? If yes, misses overlap and the structure runs at bandwidth; if no, they serialise and it runs at latency. That is the 10× between the second and third bars of Figure 4, and it is the reason a hash probe and a six-level tree descent are not comparable just because both are “random”.
3. Skew. Only then, the shape of the query. Lists of similar length want a merge; lists of very different length want a skip. This is the only one of the three that is about the algorithm.

A decision table derived from the two sweeps. The right-hand column is the measured margin at the size where the rule starts to hold, not a general claim: every one of these crossings moves with the cache sizes of the machine. Table: Programming Language Atlas, from data/memory/search.c and data/memory/postings.c.

Notice what the table does not contain. There is no row that says “use the structure with the better asymptotic bound”, because at no size measured here was that the right advice. And every threshold in it is a cache size, which is why the next four sections are history: the thresholds have moved before, and each time they moved, the field rewrote its indexes.

Back to top

How memory got its levels¶

The hierarchy was not discovered by measurement; it was predicted. In 1946, before any of the machines below existed, Burks, Goldstine and von Neumann wrote that an ideal memory — large, fast and cheap — was not obtainable, and that the practical answer was a graded series of stores with the fastest and smallest closest to the arithmetic unit. Every level added since has been an instance of that argument, and each one was added because a gap opened between two existing levels that was large enough to be worth filling.

The additions that changed the shape of the hierarchy rather than its speed. The fourth column is an order of magnitude for the technology as first shipped, not a specification. Sources: Burks, Goldstine and von Neumann (1946); Wilkes (1965); Dennard, US patent 3,387,286; Denning (1968); Wulf and McKee (1995); JEDEC standards for SDRAM, DDR and HBM; and the Wikipedia article Computer memory for the chronology.

Two features of that list matter more than the individual entries. The first is that the gap the hierarchy exists to hide has widened, not closed. In the era of core memory a fetch and an arithmetic operation cost roughly the same, which is why nobody built a cache: there was no gap to hide, and the dates bear that out — the cache is proposed in 1965 and shipped in 1968, a decade after semiconductor logic began outrunning the store it was attached to. On the machine measured here, a DRAM access costs 84 times an L1 hit, and an L1 hit is itself several cycles from the registers. Every level since has been added because the level below it got relatively further away.

The second is that bandwidth and latency stopped moving together around 1990. Every generation of SDRAM, DDR and HBM since has multiplied the bytes per second and left the time to first byte roughly where it was. That divergence is the single most important fact for retrieval, and it is why the measurements in this page keep separating “how many bytes” from “how many dependent accesses”: those two costs are now paid to different budgets.

Back to top

How retrieval got its index¶

Information retrieval starts, by common agreement, with an essay about a machine that was never built. Vannevar Bush’s Memex, described in 1945, stores a library on microfilm and lets its reader mark associative trails through it — the point being that the difficulty is not storing documents but reaching them. Everything since is a way of paying for that reach.

The results that changed what an index is, rather than how well one scores. Sources: Bush, As We May Think (1945); Luhn (1957); Cleverdon’s Cranfield reports; Salton (1961 onwards); Bayer and McCreight (1972); Spärck Jones (1972); Robertson et al. at TREC-3 (1994); Witten, Moffat and Bell (1994); Moffat and Zobel (1996); Brin and Page (1998); Jégou, Douze and Schmid (2011); Malkov and Yashunin (2016); and the Wikipedia article 'Information retrieval' for the chronology.

Three entries in that table are memory-hierarchy papers wearing retrieval clothes, and they are the ones whose results are reproduced in this page’s measurements. Bayer and McCreight’s B-tree is defined by matching the node to the block of the storage underneath — a disk block in 1970, and a cache line in the sweep above, which is the same design at three orders of magnitude smaller. Witten, Moffat and Bell’s compression is an argument about bytes crossing a bus. Moffat and Zobel’s skip headers exist because compression had destroyed random access and random access was worth more.

Back to top

One history, told twice¶

Set the two timelines beside each other and they are not two timelines. Each generation of retrieval practice is a response to the shape of the hierarchy it was built on, and each change of practice follows a change in that shape by a few years. The algorithms barely move: a conjunction in 1965 and a conjunction in 2025 are the same merge of two sorted lists. What moves is the answer to “what is expensive here”.

The retrieval design of each era, against the hierarchy it was designed for. The rightmost column is the same question every time and a different answer every time, and the answer is a property of the hardware rather than of the problem. Table: Programming Language Atlas.

Three episodes are worth stating as cause and effect, because in each one the field reversed a position it had held firmly.

Compression became compulsory, then stopped being. When the index lived on a disk, a byte not read was ten milliseconds not spent, and Managing Gigabytes could show compression paying for itself many times over. The equal-length sweep above shows the same variable-byte coding losing to raw 32-bit docids by 2.9× on a resident index, because a sequential read from DRAM is fast enough that three saved bytes are worth less than the dependent shifts it takes to decode them. Neither result is wrong. The storage under the argument changed.

Random access was destroyed, then rebuilt. Compression made a postings list unaddressable, which cost nothing while lists were read end to end and everything once queries began pairing a rare term with a common one. Skip headers were the answer in 1996 and are still the answer: the skewed sweep above puts the blocked encoding 37× ahead of the same compression without them.

The bottleneck moved from bytes to dependencies. Once the index is resident and the bus is wide, the cost of a query is no longer the volume it reads but the number of loads it must wait for one at a time. That is why the 2010s work is about branch-free decoding, batching, and structures whose next address is arithmetic rather than a loaded value — and why the largest single ratio in the third section of this page, 21×, separates two loops that touch identical addresses.

Back to top

The wall since 1995, and the next one¶

In 1995 Wulf and McKee published a two-page note observing that processor speed was improving by roughly half again per year while DRAM latency improved by a few per cent, and that whatever the hit rate, the average access time would eventually be dominated by the misses. They called it hitting the memory wall and expected it within a decade.

What happened is more interesting than either the prediction or its dismissal. Single-thread speed stopped improving at the predicted rate around 2005, which slowed the divergence; and the industry spent the intervening thirty years buying its way around the latency with everything except lower latency: more cache levels, wider buses, deeper out-of-order windows, hardware prefetchers, simultaneous multithreading, and stacked memory. Every one of those is a way of overlapping misses rather than shortening them. The measurements on this page are what that looks like from the inside: the difference between a random access that can be overlapped and one that cannot is 10×, and it is larger than the difference between random and sequential.

For retrieval, three things follow, and all three are visible in the sweeps above.

• Bytes per item is the design variable. Not the complexity class, and not the instruction count. It decides which level holds the structure, and that decides everything else. Vector quantisation is the current instance: a 768-dimensional float vector is 3 KiB and a product-quantised one is tens of bytes, and the entire argument for the technique is which level of the hierarchy the candidate set then fits in.
• Dependent traversal is the thing to avoid. Graph-based approximate nearest neighbour search is a pointer chase, which is the 21× bar in Figure 4. The research response — batching queries, prefetching neighbour lists, packing adjacency into contiguous blocks — is the same response the B-tree was.
• New levels are still arriving. CXL-attached memory sits between local DRAM and storage, and is the first genuinely new level since flash. Whatever index design is currently optimal will be re-derived for it, which is what the previous section says has happened roughly once a decade since 1955.

The one prediction this page is willing to make is structural rather than technical. As long as the ratio between the fastest and slowest level keeps growing — it is 84× between L1 and DRAM on the machine measured here, before storage is considered at all — retrieval will keep being a memory-layout discipline that happens to be about documents.

Back to top

How these numbers were produced¶

The machine and the method. Every figure on this page came from this configuration; nothing is quoted from a vendor document or another paper. Source: this page’s own measurement runs.

The four programs are published with the site, and each one prints the table this page renders:

• data/memory/latency.c — the pointer chase, in both page sizes. About ninety seconds per sweep.
• data/memory/stride.c — the stride sweep and the three access orders.
• data/memory/search.c — the six dictionary layouts. Run it under both compilers; the difference is a result.
• data/memory/postings.c — the five postings representations and the two sweeps. About five minutes.

cc -O2 -o latency  latency.c  && ./latency && ./latency huge
cc -O2 -o stride   stride.c   && ./stride
cc -O2 -o search   search.c   && ./search
cc -O2 -o postings postings.c && ./postings

What is not claimed¶

• That these are good absolute numbers. They are one virtualised guest with a shared last-level cache. The shapes — the plateaus, the crossings, the orderings — are what the page argues from, and every one of them was reproduced across runs.
• That the L3 boundary is where this machine puts it. It moved between sweeps by more than a factor of two, which is what a shared cache does, and the spread column says so.
• That the retrieval variants are state of the art. They are the textbook forms, written plainly, so that the comparison is between layouts rather than between optimisation efforts. A SIMD codec or a hand-tuned gallop would move the numbers and not the ordering.
• That any of this measures a real search engine. The collection is synthetic and the postings gaps are uniform where a real term’s are heavy-tailed. That choice keeps the bytes per posting stable so that what varies between rows is the thing being tested.
• That single-threaded numbers predict throughput. Nothing here is measured under concurrency, and the shared L3 is exactly what concurrency would contend for.

One further caution about reproduction. Run these on an idle machine, one at a time. Two of the sweeps in the making of this page were run concurrently by accident and had to be discarded: they share a last-level cache, so each was measuring the other.

Back to top

Sources¶