Expand description
The adjacency plane in its hot form: a run of neighbours per (node, label, direction), appended to and deleted from in place.
A graph without a query language is an adjacency structure with good
ergonomics, so this is what everything else in the graph model stands on.
11 section 2 gives adjacency two forms and this is the mutable one. The
other is zu’s node group CSR, which reaches 8 bits an edge because it never
changes; this one is 12 bytes an edge because every operation on it has to
be O(1).
§The shape
A run is the neighbours of one node under one label in one direction, and it
is contiguous. That is the whole performance argument: a one hop is a probe
for the run header and then a sequential read, and the read is over u64
node ids with nothing else interleaved, so eight neighbours arrive per cache
line.
The edge slots live in a second array indexed the same way. Keeping them
apart rather than storing (neighbour, edge) pairs costs nothing and saves
a third of the memory traffic on the common walk, because a traversal that
only wants to know where it can go next never reads an edge slot at all.
Interleaving them would also make every neighbour an unaligned load out of a
12 byte stride.
§Growing and shrinking
Runs are cut from two shared arenas rather than allocated one by one,
because a graph is mostly nodes with a handful of edges and a Vec header
per node would cost more than the edges do. A run’s capacity comes off a
fixed ladder: doubling while it is small, then a quarter more each step, so
the slack a hub carries is bounded by 25 per cent instead of by 100. Growing
copies the run into the next size up and gives the old block to a free list,
so the space is reused rather than lost.
Deleting is swap with last and a decrement, which is how 08 section 4
deletes from a dense member vector and it is the same reason: an O(1) delete
is worth giving up the order of a run that has no order to give up. A run
that falls to half of its capacity is moved down to the smallest size that
fits, which leaves 2x of hysteresis so a run sitting on a boundary does not
copy itself every time it gains and loses one edge.
§What it costs
Twelve bytes an edge is the payload and it is not the whole bill. There is one 32 byte run header per (node, label, direction) that has ever been linked, and there is the capacity slack. On a graph shaped like LiveJournal, most nodes with a few edges and a thin tail of hubs, the measured numbers are 18.1 bytes an edge as it is built and 15.2 after a sweep, which is 12.0 of payload and 3.2 of run headers against an average degree of 13. The test at the bottom of this file is where those come from.
The cold form is where 8 bits an edge comes from, and the ladder in 03 is
what lets both be true at once. Against what this replaces it is already the
cheap end: a pointer chased adjacency list is 16 bytes for the pair before
the per node allocation header, and Neo4j’s relationship store is 34.
§What this does not do
It does not look for a duplicate before it links. That check is linear in
the degree, and the degree is exactly the thing that can be a hub with
twenty thousand edges on it, so paying it on every insert would trade the
write path away to enforce something the layer above can enforce with one
probe. An edge table keyed by (source, destination, label) is where upsert
semantics belong, and it is what G.EADD will sit on.
It also does not delete a node, because finding every run a node has means knowing every label it was ever linked under, and that is the node table’s job rather than this one’s.
Structs§
- Adjacency
- The neighbours of every node, under every label, in both directions.
Enums§
- Dir
- Which end of an edge a run is stored under.