Skip to content

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

Open

Description

@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.

Activity

  1. godofecht commented on Aug 24, 2026

    @godofecht
    OwnerAuthor

    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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions