You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
[Perf #478] DecisionTree Digits: profile split search and recover sklearn-scale training throughput #482
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.
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.
Activity
godofecht commentedon Aug 24, 2026
I chased the remaining plain-classifier allocation shape after confirming that
mainalready 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*Norder 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_classesfor every feature: directly scan the presorted row IDs and readX[row*cols+f]/class_of_row[row]. This removes exactly2*F*nscratch 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.mdml/allocation-free-presorted-decision-tree-builder.flowThe next production test should replace
left_order/right_orderwith ping-pong buffers, remove leafy_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.