RFC: is optimizing `DecisionTree*`/`ExtraTree*` worth the effort/extra complexity?

I've been working quite a lot on trees lately (and on partitioning/sorting too, which helps here). And I have some ideas to optimize some things in `sklearn/tree`. Some of those ideas are backed-up by encouraging early experiments, some are not.

But I'm not super aware of the usage of `scikit-learn` today. I used it mostly between 2017 and 2020. So I'm not sure how relevant it is to put some possibly significant efforts into optimizing the trees. So I'm asking for opinions, cc @adam2392 @ogrisel @adrinjalali @thomasjpfan @jjerphan @lorentzenchr @glemaitre.

Here is the list of my ideas:
1. **improve partitioning in `partition_samples`**: small change and clear impact on `ExtraTrees*`. This one I'm decided to open a PR.
2. **F-order X in trees:** not too big of a change, but not as easy as it seems because it requires many careful changes in `sklearn/ensemble`, for now impact is hard to measure.
3. **Improve sorting**: this hard, but this could be huge, like 1.5x speedup  in average. The current sort (intro-sort) uses a 3-way partitioning scheme that is very efficient when there are a LOT of duplicates, but much slower when it's not the case. With no duplicates, the usual 2-way partitioning scheme is ~5-8x times faster! But with a LOT of duplicates, it can be up to 3x slower. I think it's possible to mix both to get the best of both worlds. **The hardest part here in this is doing reliable benchmarks**. It's very very data-dependent: I would need a lot if real-world use cases to build confidence in the speedup measurements.
5. **Specialized code for `n_outputs=1` (and maybe for `sample_weights=None`)**: might have some non-negligible impact on `ExtraTree*`
6. **Sort `y` (and possibly the weights) along with `feature_values`**: max possible speed-up: ~10% for both `DecisionTree*` and `ExtraTree*` I'd say (based on flame graphs). Increases memory usage.

COMMENT:
*What follows mostly are my inner thoughts, so I can keep track of my own process*

Recently, I've tried prototyping some fairly ambitious rewrites of decision trees with the goal to improve performance and implement binning (and get big performance gains along the way).

I found that the problem input has a highly variable geometry:
- number of samples
- number of features
- depth of the tree / number of samples per node 
- proportion of features considered at each split: might be 100%, might be 5%, which affects approaches where you partition `X` instead of relying on `sample_indices` to improve contiguity of memory accesses
- distribution of the data (small/high number of unique values, repeated values, etc.): this affects a lot the benefits or not of different sorting strategies (or not sorting).

And because of that, it's fairly impossible to find an approach that improves the current performance for all possible geometries of inputs.
Still, I was able to implement approaches that could be up to 10x faster in some non-niche cases. I'm prototyping in numba.

In addition, you have to support for many features:
- support for "best-first" tree builder (`max_leaf_nodes`)
- support for weights, missing values, multi-class, multi-output, sparse X.
- support for various criteria
- support for monotonic constraints
- support for many stopping conditions: `max_depth`, `min_samples_split`, `min_samples_leaf`, `min_weight_fraction_leaf`, `min_impurity_decrease`.
- futur support for categorical splits

This is really hard to know if a given idea/optimization is compatible with all those features.

----

**Conclusion:** if we want to optimize tree while avoid partial regressions, I think that complete rewrites aren't adapted (despite my preference for this approach 😅). I suggest to move slowly but surely from the current code-base and to specialize the code for common cases where important improvements can be made (e.g. features with a small numbers of unique values). This does not mean avoiding refactoring though, typically, my PR https://github.com/scikit-learn/scikit-learn/pull/32119 goes in the good direction of making the code more flexible and easier to modify I believe.

Labels: RFC