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:
I had a spare minute and wondered what kind of benchmark cases/scenarios would highlight the differences between scikit-learn and lightgbm's random forest classifier implementation. I used lightgbm because it looks like it has a useful RF implementation. So I asked Cursor to generate a benchmark script. 

<details><summary>Prompt</summary>
<p>

create a script that benchmarks the random forest classifier implementation in scikit-learn again the one in LightGBM. Make sure to compare different numbers of features, number of samples, feature types (numerical, categorical) and number of classes. the run time of the smallest benchmark should be a few seconds. Bigger benchmarks should take longer. try to create at least one benchmark case that is really optimised towards LightGBM's strengths. use all the cores on the computer

</p>
</details> 

This is the script it generated https://gist.github.com/betatim/d322fc2902c4439e8db51ed051499037, gist includes the output from running it on my macbook with a M1 pro and 32GB of memory.

The script itself looks reasonable, even though it is quite verbose.

What I was most interested in is getting a feeling for which scenarios are good for scikit-learn and which for lightgbm. My take away is that larger datasets and high cardinality favour lightgbm. What I find surprising, but haven't thought about much, is that the log loss is so different.

Anyway, I thought this might be an interesting source of inspiration.

Labels: RFC