Allocation churn on the dense algo.* paths: a per-spur-node n x n mask in kShortestPaths, a boxed Integer[] sort in steinerTree

[lvca]

Two allocation-churn findings surfaced while reviewing PR #6285 (issue #6263), both deliberately left out of it: that PR bounds peaks, and neither of these raises a peak. They are performance questions, and both need a measurement rather than a guess - which is exactly why they do not belong in a PR about bounds.

1. algo.kShortestPaths reallocates an n x n mask per spur node

AlgoKShortestPaths.java, inside Yen's spur loop:

for (int ki = 1; ki < k; ki++) {
  for (int i = 0; i < prevPath.length - 1; i++) {
    ...
    final boolean[][] removedEdges = new boolean[n][n];   // fresh every spur node

Only one is ever live, so the budget added in #6263 prices it correctly as a peak of one. But the churn is k x pathLength allocations of n² bytes each: at 1000 nodes and a 20-hop path with k = 10, that is ~200 allocations of 1 MB, ~200 MB through the young generation for a single call.

The obvious fix - hoist it and clear it between spur nodes - is not obviously a win, which is the whole point of filing this rather than doing it. Arrays.fill over n² booleans per iteration is real work too, and a fresh boolean[n][n] is something the JVM can thread-locally bump-allocate and collect young for close to nothing when it dies immediately. It needs measuring at a few graph sizes before either version can be called better.

Worth measuring alongside: the mask is dense but the thing it represents - the edges removed for this spur node - is tiny (at most the number of previously-found paths sharing the root). A HashSet of packed long keys, or a per-row sparse structure, may beat both dense options and is O(paths) rather than O(n²) in both time and space.

2. algo.steinerTree sorts its terminal pairs through a boxed Integer[]

AlgoSteinerTree.java:

final Integer[] sortIdx = new Integer[pairs];
for (int i = 0; i < pairs; i++)
  sortIdx[i] = i;
Arrays.sort(sortIdx, (a, b) -> Double.compare(pW[a], pW[b]));

pairs is t(t-1)/2, so this is quadratic in the terminal count: at 2000 terminals it is ~2M boxed Integer objects (~48 MB where the int payload is 8 MB), plus a comparator call and two unboxings per comparison. CLAUDE.md asks for primitive arrays over boxed collections precisely on paths like this one.

#6285 prices it honestly rather than pretending it is primitive (that is what BOXED_INTEGER_BYTES = 24L is for), but pricing an inefficiency is not fixing it. The replacement is an index sort over primitives - the usual shapes are packing (weight, index) into a sortable long[] where the key permits it, or a small dual-pivot index sort keyed on pW. The catch is that the weights are double, so the packing trick needs care around sign and NaN; a hand-rolled index quicksort on pW is the straightforward version.

AlgoMST.java:155 has the identical Integer[] sortIdx = new Integer[ec] shape for Kruskal's, sized by the edge count. Same fix, same measurement.

3. While in there: MemoryBudget.reserve() mutates before it throws

AbstractAlgoProcedure.MemoryBudget.reserve() adds to the running total and then checks the limit, so on the rejection path the object records a reservation that was never granted. Harmless today - the exception aborts the call and the budget is call-scoped and discarded - and the code review that spotted it agreed it is not a bug in the current design. But "reserved reflects what was granted" is the invariant a reader will assume, and it costs three lines to make true:

final long total = saturatingSum(reserved, estimatedBytes);
if (total > limit)
  throw ...;
reserved = total;

Worth doing whenever this file is next open, so that a future retry or multi-attempt path cannot inherit the trap.

Related

#6263, PR #6285, #6216, #6222.