A list and a block of memory

Every comparison this site draws between two algorithms has a confound in it. Merge sort and heapsort have different comparison counts and different access patterns, so when the two counts rank them differently there are two variables moving and the attribution is an argument rather than a measurement.

A graph offers something cleaner. Hold the same graph two ways, run the same traversal over it, and the number of edges examined, the order in which they are examined, and the vertices reached are all identical — the gate requires it. The only thing that differs is where in memory each edge record sits.

At $V = 2{,}048$ on a sparse random graph, both layouts examine 12,288 edge slots. Through a stated cache model, one takes 11,812 misses and the other takes 3,258.

The two layouts #

An adjacency list is what a graph looks like when it is built the obvious way. Each vertex owns a list; adding an edge appends a record to two of them; each record sits wherever the allocator put it at the moment it was created. Walking a vertex’s neighbours means following a chain of records that were allocated at scattered times and therefore live at scattered addresses.

CSR — compressed sparse row — is what the same graph looks like when it is built once and then frozen. Every edge record is copied into a single flat array, sorted by source vertex, and a second array of $V + 1$ offsets says where each vertex’s block begins. Walking a vertex’s neighbours means reading a contiguous run.

The model here assigns each edge record an address. In CSR it is the record’s index in the flat array. In list form it is the order in which the edge was created, which for a graph built from random pairs is uncorrelated with anything the traversal does. Both are models of what an allocator would produce and both are stated as such; neither is a claim about a specific runtime’s heap.

Feed the two address streams to the cache model — 64 lines of 8 elements, fully associative, LRU, parameters printed on the figure — and the miss counts are these:

Why 26% and not 12.5% #

The CSR miss rate at $V = 2{,}048$ is 26.5%, and a line holds eight elements, so a perfect sweep would miss once in eight — 12.5%. The gap is worth explaining because it is the whole difference between a graph and an array.

A CSR scan is contiguous within a vertex and jumps between vertices. Breadth-first search visits vertices in queue order, which is not index order, so consecutive vertex blocks are consecutive in the array only by accident. Each new vertex’s block starts with a fresh miss, and with average degree six a block is six slots — under one cache line — so nearly every vertex costs its own miss and there is not much sweeping to amortise it over.

On a dense graph the blocks are 260 slots long, and the miss rate falls to 12.7% — within a rounding error of the ideal 12.5%, and the sequentiality reaches 0.997. The layout gets better as the degrees get larger, which is the shape one would expect and is worth confirming rather than assuming.

The adjacency list gets worse as the graph grows: 83.6% missing at $V = 512$ and 96.1% at $V = 2{,}048$. At the smaller size a fair number of records still happen to be resident; at the larger size the working set has gone over the cliff and essentially every record is cold.

Where the advantage disappears #

A figure showing a consistent factor of four would be a figure with nothing to say about its own limits. The grid is where it stops.

At $V = 512$ the adjacency list is very slightly better, and at $V = 2{,}048$ the CSR advantage is 1.76 rather than 3.6.

Two things are happening and both are worth having.

The small grid fits. 512 vertices at degree four is 2,048 edge records, and the modelled cache holds 512 elements. That is a working set four times the capacity rather than twenty-four times, and at that ratio a lot of the list’s scattered records are still resident when they are needed again. The layout matters least when the data nearly fits, which is the general lesson of the working-set cliff restated.

A grid’s edges are created in a helpful order. The generator emits edges by scanning the lattice row by row, so an adjacency list built from it is already nearly sorted by source vertex — accidentally, and only because the generator happens to work that way. A grid loaded from an edge list in arbitrary order would not have this property. That is a warning about the measurement as much as a result: the list layout’s cost depends on the insertion order, which is not part of the graph.

So the honest summary is not “CSR is 3.6 times better”. It is: CSR’s locality is a property of the structure and the list’s is a property of the history, so CSR’s number is reproducible and the list’s is whatever the construction happened to leave behind. On a graph built by random insertion the list is 3.6 times worse; on one built by a scan it is level; on one built by an adversary it would be worse still.

What this costs to have #

CSR is not free and the price is exactly the thing the graph field is otherwise about.

It cannot be modified. Adding an edge means inserting into the middle of the flat array and shifting everything after it, which is $\Theta(E)$. An adjacency list appends in constant time. So CSR is for graphs that are built once and traversed many times, and every real graph library offers both for this reason.

It costs a build pass. Constructing CSR from an edge list means counting degrees, prefix-summing the offsets and scattering the edges — two passes and a full copy. On a graph traversed once, the copy costs more than the locality saves.

It fixes the order. Sorting edges by source is one choice; sorting them by a space-filling curve over the vertex coordinates is another and is better still on a grid. CSR makes the layout explicit, which means it also makes it something that has to be chosen.

The trade is the same shape as a growth factor: a knob with no dominant setting, where the right answer depends on the ratio of reads to writes in a workload the library cannot see. What is different here is the magnitude. A growth factor moves the amortised append cost by a factor of three; a layout moves the miss count by a factor of five.

A third layout, and the floor #

CSR fixes where a vertex’s edges live relative to each other. It says nothing about where the vertices live relative to each other, and that is a second decision with its own effect.

Relabel the vertices in breadth-first order — vertex 0 becomes the source, its neighbours become 1, 2, 3, and so on — then build the CSR from the relabelled edge list. Nothing about the graph has changed; the same vertices are joined by the same edges and the traversal examines the same slots in the same order. Only the integers naming them are different.

12.5% is not an arbitrary number. A cache line here holds eight elements, so a perfect sequential sweep misses exactly once every eight accesses, and 12.5% is the floor. Relabelling reaches it on both families — on the grid with a sequentiality of 1.000, meaning every single access after the first in each line steps to the adjacent slot.

So the ordinary CSR result is not the end of the story. Plain CSR gets from 96% to 26%; relabelling gets from 26% to the theoretical minimum, and the second step is another factor of two on the sparse family.

Three things follow.

The full gap is a factor of 7.7, not 3.6. An adjacency list built by random insertion against a CSR whose vertices are numbered in traversal order is 11,812 misses against 1,537, on identical counted work. That is the widest separation between two counts anywhere in this collection by some distance.

The improvement is only available for a known traversal. BFS order is optimal for BFS from that source, and it is a different ordering for a different source and a different traversal. Real libraries approximate it with an ordering that is good for many traversals at once — a space-filling curve over vertex coordinates for a mesh, or a recursive bisection for a general graph — and the approximation gets most of the way.

The floor exists and is reachable, which is unusual. Merge sort comes within 2% of the comparison floor and cannot close the rest. Here the floor is a property of the line size, the gap to it is entirely a question of layout, and one relabelling pass closes it exactly.

Why this is the widest gap on the site #

The sorting field’s cleanest instance of two counts disagreeing is heapsort against merge sort: comparison counts within a factor of two, modelled miss counts much further apart, and the rankings differ. It is a good example and it has a confound, because the two algorithms are doing different work.

Here the confound is gone. Not reduced — gone, and the gate enforces it. The two layouts must report the same edge scans, the same visits and the same trace length, and must differ in the addresses; if they ever agreed on the addresses the assertion fails, on the grounds that a comparison between two identical traces is not a comparison.

That leaves a single-variable experiment: hold the algorithm fixed, hold the input fixed, hold the operation sequence fixed, vary only the addresses, and the modelled cost moves by a factor of five.

It is the strongest form of the field’s claim available anywhere in this collection. The count is not the cost, and here it is not the cost while being exactly, provably, the same count.

Two more settings of the same model say what the factor is a function of, and neither of them is the graph.

What CSR is actually for #

The layout is not a graph-library curiosity. Compressed sparse row is the standard representation for sparse matrices, and a sparse matrix and an adjacency structure are the same object — the non-zeros of row $i$ are the neighbours of vertex $i$, and a matrix-vector product is a traversal that touches every edge once.

That is worth knowing because it means the measurement here is about a much larger body of code than graph traversal. Every sparse linear solver, every iterative eigenvalue method and every graph-neural-network kernel spends most of its time in the operation this figure is measuring, and every one of them uses CSR for the reason this figure gives.

It also explains why the relabelling result matters more than it might appear. Reordering the rows and columns of a sparse matrix to improve locality is a whole small field — reverse Cuthill–McKee, nested dissection, space-filling curves — and what those methods are buying is the factor of two between plain CSR and the relabelled CSR above.

The list costs the memory as well #

Everything above holds the counted work fixed and varies only the addresses, which is what makes it a single-variable experiment. It also hides a second difference, and the second difference makes the first one worse.

An adjacency-list record has to say where the next record is. Whether that is a pointer, an index or an object header depends on the language, but something has to be stored beyond the neighbour’s identity, so an edge slot costs at least two words. A CSR edge slot costs one — the neighbour — plus the shared offsets array of $V+1$ entries.

At $V = 2{,}048$ on the sparse family that is 12,288 slots either way, so:

The list is about 1.7 times the memory for the same graph, and the ratio worsens as the average degree falls, because the offsets array amortises over fewer edges while the per-record overhead does not amortise at all.

That compounds with the locality result rather than sitting beside it. A structure occupying more bytes occupies more cache lines, so it fits in a given cache at a smaller graph size and reaches the cliff sooner. The model in this essay charges by the element rather than by the word, so it does not see any of this — which is a fourth item for the list below and, like the other three, one that favours the layout already losing.

The order that helps is the answer to the question #

The relabelling result is the largest single improvement on the page and it has a circularity in it worth stating plainly, because it decides when the technique is available.

Numbering the vertices in breadth-first order requires a breadth-first traversal. So the ordering that makes a traversal cheap is produced by the traversal, and the first one cannot benefit from it. What the relabelling buys is every traversal after the first, from that source, and nothing at all if the graph is traversed once.

That places it exactly where CSR itself sits. Both are investments paid at build time and recovered over repeated traversals; both are worthless on a graph read once; and both are worth measuring as a break-even in traversals rather than as a speedup. The relabelling costs one traversal plus a scatter, and it saves 1,721 misses per traversal on the sparse family — so it pays for itself on the second or third pass and is pure profit after that.

It also explains why real systems do not use breadth-first order. An ordering tuned to one source is an ordering that helps that source’s traversal and no other, and a graph is usually queried from many sources. What the reordering literature supplies instead — reverse Cuthill–McKee, recursive bisection, a space-filling curve over vertex coordinates — are orderings that are good for every traversal at once, by making neighbours have near-by numbers rather than by following any particular walk. They reach a worse number than the 12.5% floor above and they reach it for all sources, which on a real workload is the better trade.

The floor in the table is therefore an upper bound on what any general reordering can deliver, reached by an ordering that knows the question in advance. That is a useful thing for a benchmark to have: it says how much of the remaining gap is available to be closed at all.

Three things the model still does not see #

The usual caveats, and one of them is specific enough to change the number.

Prefetching. A hardware prefetcher detects a forward stride and fetches ahead, so a CSR sweep’s remaining 12.7% of misses would largely be hidden on a real processor. The adjacency list’s would not, because there is no stride to detect. The model has no prefetcher, so it understates the gap, and understating it is the safe direction.

Dependent loads. An adjacency-list walk reads the next pointer out of the current record, so the address of the next miss is not known until the current one returns. Those misses cannot overlap. A CSR scan’s addresses are all known in advance and its misses can be in flight together. This is memory-level parallelism and the model is blind to it, and again it is blind in the direction that makes the list look better than it is.

The vertex array. Both layouts also touch a per-vertex structure — the visited flags, the distance array, the queue — and none of that is in the trace here, which counts only edge-record accesses. On a sparse graph those per-vertex touches are a comparable number of accesses with their own locality, and including them would move both numbers up and the ratio down. The measurement is of the edge scanning specifically, and the caption says so.

All three point the same way as the earlier honest limits in the machine field: the simplifications are not neutral between the two things being compared, they favour the loser, and so the measured gap is a lower bound on the real one.