Adjacency list against CSR: identical work, different addresses

Adjacency list against CSR: identical work, different addresses

Breadth-first search over the same graphs, laid out two ways. An adjacency list places each edge record where the allocator put it, so a scan is a pointer chase; a compressed-sparse-row array places every edge of a vertex contiguously, so a scan is a sweep. Both examine 12,288 edge slots at V = 2048. The modelled misses differ by a factor of 3.6, and the sequentiality of the two traces is 0.001 against 0.834.

Drawn at 690 × 400, wide on the page. Everything above is what list-against-csr 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 list-against-csr. 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.