Noted while fixing #6300 (PR #6306) and left out of it on purpose: #6300 was about algo.mst's own edge arrays, and this is the allocation underneath every procedure in the package, so it belongs in one place rather than in whichever procedure the next issue happens to name.
The gap
#6263 priced "the dense working set an algorithm builds beside the graph" - walk buffers, embedding matrices, distance matrices. #6300 added algo.mst's edge arrays. The graph representation itself is priced by neither, and it is loaded first:
// AlgoAPSP, and the same order in every procedure that reserves anything
final GraphData graph = loadGraph(db, null, relTypes, context); // <- allocates, unpriced
final int n = graph.nodeCount;
...
newMemoryBudget(db).reserve(matrixBytes(n, n, DOUBLE_BYTES), "the distance matrix", ...); // <- first check
Three allocations, none of them reserved:
List<Vertex> on the OLTP path - one loaded record per vertex, held for the whole call.Map<RID, Integer> from buildRidIndex - a boxed Integer and a HashMap.Node per vertex, so ~50-60 bytes per vertex on top of the RID. At 10M vertices that is over half a gigabyte for the index alone.int[][] from GraphData.adjacency - 4 bytes per edge plus a 32-byte row header per node. At 100M edges that is ~400 MB, and Vertex.DIRECTION.BOTH materialises each edge twice.
So a call can be refused for a 64 MB matrix having already allocated a multi-gigabyte graph to measure it against - and a call that is accepted holds that graph for its whole duration with the budget none the wiser. The setting is named arcadedb.cypher.algoMaxWorkingMemory, and the largest thing the working set contains is outside it.
Why it is awkward, and what makes it tractable
The reason #6300 did not do this: the node count is known cheaply (countType over the vertex types), but the edge count is not, and the adjacency is the larger of the two. The same problem #6300 hit for algo.mst, and the same answer applies - MemoryBudget.capacityFor(bytesPerItem), added in PR #6306, turns the budget into a bound the walk carries, so the load stops at the point the budget runs out rather than completing and then being refused. loadGraph and adjacency are exactly the two places to spend it.
The CSR path needs a different treatment and is the easier half: a GraphTraversalProvider already knows its own footprint (GraphAnalyticalView.getMemoryUsageBytes()), and adjacency() copies out of it rather than building it, so what is worth pricing there is the copy - or better, not making it. GraphData.neighborView() already offers the zero-allocation form, and the procedures that call adjacency() purely to iterate could take it instead. That would remove the allocation rather than bound it, for the same reason the Borůvka alternative was attractive in #6300.
Suggested order
- Price the OLTP
List<Vertex> and RID index in loadGraph, using capacityFor against the vertex count so a graph too large to serve is refused before it is loaded rather than after.
- Price the
int[][] in GraphData.adjacency the same way, per edge as it is filled.
- Separately, move the procedures that only iterate
adj[i] onto neighborView(), which prices at zero.
Steps 1 and 2 make the setting mean what its name says. Step 3 is what makes it rarely bind.
Related
#6300, #6263, PR #6306, #6216, #6065.
Noted while fixing #6300 (PR #6306) and left out of it on purpose: #6300 was about
algo.mst's own edge arrays, and this is the allocation underneath every procedure in the package, so it belongs in one place rather than in whichever procedure the next issue happens to name.The gap
#6263 priced "the dense working set an algorithm builds beside the graph" - walk buffers, embedding matrices, distance matrices. #6300 added
algo.mst's edge arrays. The graph representation itself is priced by neither, and it is loaded first:Three allocations, none of them reserved:
List<Vertex>on the OLTP path - one loaded record per vertex, held for the whole call.Map<RID, Integer>frombuildRidIndex- a boxedIntegerand aHashMap.Nodeper vertex, so ~50-60 bytes per vertex on top of the RID. At 10M vertices that is over half a gigabyte for the index alone.int[][]fromGraphData.adjacency- 4 bytes per edge plus a 32-byte row header per node. At 100M edges that is ~400 MB, andVertex.DIRECTION.BOTHmaterialises each edge twice.So a call can be refused for a 64 MB matrix having already allocated a multi-gigabyte graph to measure it against - and a call that is accepted holds that graph for its whole duration with the budget none the wiser. The setting is named
arcadedb.cypher.algoMaxWorkingMemory, and the largest thing the working set contains is outside it.Why it is awkward, and what makes it tractable
The reason #6300 did not do this: the node count is known cheaply (
countTypeover the vertex types), but the edge count is not, and the adjacency is the larger of the two. The same problem #6300 hit foralgo.mst, and the same answer applies -MemoryBudget.capacityFor(bytesPerItem), added in PR #6306, turns the budget into a bound the walk carries, so the load stops at the point the budget runs out rather than completing and then being refused.loadGraphandadjacencyare exactly the two places to spend it.The CSR path needs a different treatment and is the easier half: a
GraphTraversalProvideralready knows its own footprint (GraphAnalyticalView.getMemoryUsageBytes()), andadjacency()copies out of it rather than building it, so what is worth pricing there is the copy - or better, not making it.GraphData.neighborView()already offers the zero-allocation form, and the procedures that calladjacency()purely to iterate could take it instead. That would remove the allocation rather than bound it, for the same reason the Borůvka alternative was attractive in #6300.Suggested order
List<Vertex>and RID index inloadGraph, usingcapacityForagainst the vertex count so a graph too large to serve is refused before it is loaded rather than after.int[][]inGraphData.adjacencythe same way, per edge as it is filled.adj[i]ontoneighborView(), which prices at zero.Steps 1 and 2 make the setting mean what its name says. Step 3 is what makes it rarely bind.
Related
#6300, #6263, PR #6306, #6216, #6065.