Skip to content

[Perf #478] RandomForest Digits: remove per-tree training overhead and improve scaling #483

Open

Description

@godofecht

Parent: #478

Canonical v2 Digits: Flow fit 93.14 ms vs sklearn 28.95 ms; Flow predict 0.608 ms vs sklearn 0.919 ms. Prediction already wins; training is the entire regression. Iris end-to-end wins ~9.9x.

Profile bootstrap/sample generation, RNG, per-tree setup, tree fit, feature subsampling, allocation/free, tree storage and opportunities for parallel or batched work. Reuse #482 findings where the tree builder is shared.

Acceptance: tree-by-tree timing and allocation profile; distinguish forest orchestration from tree-core cost; scaled n_estimators/sample/feature sweeps; preserve bootstrap/RNG semantics and learned-state diagnostics; Digits fit >=0.95x first, target >=1.05x, without sacrificing the current prediction win.

Activity

  1. godofecht commented on Aug 25, 2026

    @godofecht
    OwnerAuthor

    I found a bootstrap-specific optimization that should be semantically exact and is worth A/B testing before attacking more tree-core code.

    A size-n bootstrap sample is completely represented by the per-source-row multiplicities m_i. For any classification-tree threshold, the explicit copied bootstrap class counts satisfy

    N^B_{L,c}(t) = sum_{i in L(t)} m_i 1[y_i=c],

    and likewise on the right. Therefore node counts, majority class, Gini/entropy, weighted child impurity and impurity decrease are identical between a materialized X_boot/y_boot and the original X/y plus multiplicities. With identical feature-subset RNG, threshold ordering and tie rules, the whole deterministic tree is identical by induction.

    That lets RandomForest generate the same bootstrap RNG stream but do multiplicity[draw] += 1 rather than copying the row into X_boot/y_boot. The tree builder operates on source-row IDs + weights; node n_samples remains the sum of multiplicities. Duplicate equal feature values must be consumed as one value group before testing the next threshold boundary.

    For the ordinary size-n bootstrap, E[U] = n(1-(1-1/n)^n) ~= 0.63212n unique rows. On Digits n=1797 this is ~1136 active source rows, ~661 fewer than the copied 1797-row representation. The root-level row-visit ratio is therefore ~0.632 if the weighted scan visits each active source row once. Materializing X_boot also costs at least 4nd + 4*n bytes per tree for f32 X/y, excluding allocator metadata and the bootstrap-index array.

    I independently checked explicit-vs-weighted best-split equivalence over 100 randomized multiclass bootstrap cases including repeated feature values; all matched. The complete derivation and an adjacent Flow witness are now in OpenProjects as ml/multiplicity-preserving-random-forest-bootstrap.{md,flow}.

    Next production test: add a multiplicity-aware RF fit path and require identical PRNG progression plus node-by-node feature/threshold/n_samples/impurity/leaf equality, then measure per-tree bootstrap time, tree time, U/n, copied bytes and row visits. This should tell us how much of #483 is still bootstrap orchestration versus the tree core.

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