[Perf #478] DecisionTree Digits: profile split search and recover sklearn-scale training throughput

[godofecht]

Parent: #478

Canonical v2 Digits: Flow fit 30.49 ms vs sklearn 16.84 ms and predict 0.123 ms vs 0.098 ms; end-to-end ~0.553x. Iris already wins ~6x, so the regression appears with feature/sample scale rather than basic API overhead.

Profile node construction, candidate-threshold enumeration, sort/re-sort work, impurity calculation, feature scans, sample partitioning, temporary allocation and tree memory layout. Compare number of evaluated thresholds/nodes with sklearn to distinguish algorithmic work from low-level throughput.

Acceptance: per-stage/node profiling; node/threshold operation counts; scaled samples/features/depth curves; preserve or improve current accuracy and learned-tree diagnostics; fit and predict separately reach >=0.95x, target >=1.05x; Iris must remain a Flow win.

[godofecht]

I chased the remaining plain-classifier allocation shape after confirming that main already has the global presort/stable-partition optimization.

There is a stronger allocation-free formulation that preserves the current deterministic tree semantics exactly: keep two global F*N order matrices and represent every recursive node by one shared [lo, hi) segment across feature blocks. Stable-partition the current segment from source buffer into destination buffer, recurse left with buffers swapped, then recurse right with buffers swapped. Because the two child ranges are disjoint, left-subtree recursion can never overwrite the right sibling's source segment. A stable subsequence of a sorted feature order remains sorted, so no third order buffer or re-sort is required.

This gives an exact depth-independent order-storage bound of 2*F*N*sizeof(i32). For Digits (N=1797, F=64) that is 920,064 bytes (~0.88 MiB). The current recursive child-order allocation shape has a valid maximally-unbalanced 50-level witness of 23,148,032 bytes (~22.08 MiB) live order storage. That is a worst-shape bound, not a claim about the canonical tree's actual peak.

There is also no need to gather sort_values + sort_classes for every feature: directly scan the presorted row IDs and read X[row*cols+f] / class_of_row[row]. This removes exactly 2*F*n scratch writes per internal node while preserving candidate sequence, count updates, floating-point operation order, strict tie comparison and thresholds. At the Digits root alone that is 230,016 scratch writes.

Full proof + Flow witness are in godofecht/OpenProjects:
ml/allocation-free-presorted-decision-tree-builder.md
ml/allocation-free-presorted-decision-tree-builder.flow

The next production test should replace left_order/right_order with ping-pong buffers, remove leaf y_subset, then require exact learned-tree structural parity (feature/threshold/children/value/impurity/n_samples per node) before timing. If timing does not move materially, this cleanly falsifies recursive allocation/gather traffic as the dominant remaining cause.