scikit-learn Onboarding LabChapter VII — Compiled extensions: performance-critical inner loops✓ 0/5Contents
Chapter VII

Compiled extensions: performance-critical inner loops

DecisionTreeClassifier and its siblings in sklearn/tree/_classes.py are thin Python orchestrators: they validate input and pick a Splitter, but the actual recursive tree growth and per-sample prediction run in sklearn/tree/_tree.pyx, a Cython file compiled by meson into its own optimized C extension. Because that hot loop is compiled, not interpreted, editing it doesn't take effect like editing a .py file — the extension must be rebuilt (meson-python does this automatically on import under an editable install).

From Python estimator to compiled tree core
meson-built extension modulesklearn/tree/meson.build
DepthFirstTreeBuilder / BestFirstTreeBuildersklearn/tree/_tree.pyx
Splitter / Criterion (compiled)sklearn/tree/_classes.py
Tree (array-based structure)sklearn/tree/_tree.pyx
DecisionTreeClassifier.fit (Python)sklearn/tree/_classes.py
Figure I · Click a node to see what it does, where it lives in the code, and its labeled connections — the annotation opens beside it.
walkthrough

Growing a tree without Python recursion

sklearn/tree/_tree.pyx · lines 126–261
lines 126–138

Building starts by pushing the root node's sample range (the whole training set) onto an explicit stack, all inside a with nogil: block so the entire build runs without touching the Python interpreter.

lines 140–155

Each iteration pops one pending node off the stack, restores its (start, end) sample range and parent-impurity bookkeeping, then asks the Splitter to reset its internal state to that range.

lines 157–167

Cheap stopping checks (max depth, min samples, min weight, near-zero impurity) decide whether this node must be a leaf before any expensive split search is attempted.

lines 169–179

If the node isn't already forced to be a leaf, the Splitter searches for the best split; the outcome can still turn it into a leaf, e.g. when the improvement falls below min_impurity_decrease.

lines 181–188

The decided node (leaf or split) is written into the Tree's preallocated C arrays via _add_node; running out of capacity surfaces as INTPTR_MAX and aborts the build (a MemoryError is raised once outside the nogil block).

        with nogil:            # push root node onto stack            builder_stack.push({                "start": 0,                "end": n_node_samples,                "depth": 0,                "parent": _TREE_UNDEFINED,                "is_left": 0,                "impurity": INFINITY,                "n_constant_features": 0,                "lower_bound": -INFINITY,                "upper_bound": INFINITY,            })             while not builder_stack.empty():                stack_record = builder_stack.top()                builder_stack.pop()                 start = stack_record.start                end = stack_record.end                depth = stack_record.depth                parent = stack_record.parent                is_left = stack_record.is_left                parent_record.impurity = stack_record.impurity                parent_record.n_constant_features = stack_record.n_constant_features                parent_record.lower_bound = stack_record.lower_bound                parent_record.upper_bound = stack_record.upper_bound                 n_node_samples = end - start                splitter.node_reset(start, end, &weighted_n_node_samples)                 is_leaf = (depth >= max_depth or                           n_node_samples < min_samples_split or                           n_node_samples < 2 * min_samples_leaf or                           weighted_n_node_samples < 2 * min_weight_leaf)                 if first:                    parent_record.impurity = splitter.node_impurity()                    first = 0                 # impurity == 0 with tolerance due to rounding errors                is_leaf = is_leaf or parent_record.impurity <= EPSILON                 if not is_leaf:                    splitter.node_split(                        &parent_record,                        &split,                    )                    # If EPSILON=0 in the below comparison, float precision                    # issues stop splitting, producing trees that are                    # dissimilar to v0.18                    is_leaf = (is_leaf or split.pos >= end or                               (split.improvement + EPSILON <                                min_impurity_decrease))                 node_id = tree._add_node(parent, is_left, is_leaf, split.feature,                                         split.threshold, parent_record.impurity,                                         n_node_samples, weighted_n_node_samples,                                         split.missing_go_to_left)                 if node_id == INTPTR_MAX:                    rc = -1                    break
step 1 of 5
        cdef const float32_t[:, :] X_ndarray = X        cdef intp_t n_samples = X.shape[0]        cdef float32_t X_i_node_feature         # Initialize output        cdef intp_t[:] out = np.zeros(n_samples, dtype=np.intp)         # Initialize auxiliary data-structure        cdef Node* node = NULL        cdef intp_t i = 0         with nogil:            for i in range(n_samples):                node = self.nodes                # While node not a leaf                while node.left_child != _TREE_LEAF:                    X_i_node_feature = X_ndarray[i, node.feature]                    # ... and node.right_child != _TREE_LEAF:                    if isnan(X_i_node_feature):                        if node.missing_go_to_left:                            node = &self.nodes[node.left_child]                        else:                            node = &self.nodes[node.right_child]                    elif X_i_node_feature <= node.threshold:                        node = &self.nodes[node.left_child]                    else:                        node = &self.nodes[node.right_child]                 out[i] = <intp_t>(node - self.nodes)  # node offset         return np.asarray(out)
sklearn/tree/_tree.pyx · lines 954–996
Figure II · Once fit, predicting for a single sample is a pointer-chasing walk down the raw Node array entirely in C: no attribute lookups, no Python objects, just comparisons against threshold and feature until a leaf (left_child == _TREE_LEAF) is reached. This is the payoff of compiling the core — an O(depth) traversal per row that never re-enters the Python interpreter.
checkpoint

Check your understanding

Answered in place — nothing is graded, everything is explained. 0 / 3 passed

How does DepthFirstTreeBuilder grow the tree without Python-level recursion?

Why does the tree-building and prediction code run inside `with nogil:` blocks?

You edit a splitting rule inside sklearn/tree/_tree.pyx. What has to happen before your change actually affects DecisionTreeClassifier.fit()?