Reflecting on the challenges of the last attempt of refactoring the tree code, making sure that the changes are beneficial for everybody is crucial. There is a real risk that the PR is too hard to review to convince the historical tree maintainers ( @glouppe, @arjoly, @jmschrei ) that it is a benefit that comes without risks of code being wrong or other degraded functionality.

Maybe one direction to consider is to have both tree implementations in the codebase for a while, at least in the PR, to be able to write tests comparing one with the other.

This pull request introduces 3 alerts - view on lgtm.com

new alerts:

• 1 for Inconsistent equality and inequality
• 1 for Unreachable code
• 1 for Inconsistent equality and hashing

Comment posted by lgtm.com

I didn't realize you were working on this, nice :) Have you run https://github.com/guolinke/boosting_tree_benchmarks with the current code to see how bad it is?

I have stuff there: https://github.com/glemaitre/gbrt-benchmarks/blob/master/benchmark/benchmark_plotting.ipynb
I think this is not the last results (I might have forgot to turn on -O3 for XGBoost :))

What is sure is that I am currently comparing the exact method from XGBoost and usually, this is at least 5 times faster. I have an implementation which is as fast as XGBoost up to 10^5 samples. However, with larger number of samples, the performance decrease to get to the original performance of scikit-learn.
I am currently profiling the code to find the reason and the bottleneck.

What is the difference between the first two columns (cache vs not? What does that mean?).
And that is comparing against your branch or against master?

If you say "this" is at least 5 times faster, what is "this"? Also, I assume you limit XGBoost to a single core? You don't do binning, so as fast as XGBoost exact, I guess?

If you say "this" is at least 5 times faster, what is "this"? Also, I assume you limit XGBoost to a single core? You don't do binning, so as fast as XGBoost exact, I guess?

XGBoost exact vs sklearn master branch both on a single core. So no binning for the moment

cache vs not? What does that mean?

XGBoost has a cache-optimized version (offering a gain of ~ x2) by creating block of small data.

"this" is at least 5 times faster, what is "this

XGBoost exact is x5 faster than scikit-learn master. This is something that I am currently benchmarking and profiling while developing my branch.

I will update those benchmark to be sure once that I am going what I am working now right now.
I want to benchmark on several dataset to be sure.

Great that you're posting the benchmarks. It would be very useful to include a comparison of your approach to scikit-learn master, so that we know how much we are gaining.

Thanks for the explanation @glemaitre. I somehow assumed we were more than 5x slower from hearsay. Are the default parameters very different? Or is/was there a difference in early stopping?

(or maybe it's just that 5x plus multicore means 20x, which is kind of a lot lol)

I had considered jumping in on parallelizing the current tree architecture or looking into categorical support. Should I wait until this new architecture is added in? I've also forgotten, is this solely going to be for regression trees, or both CART?

Great that you're posting the benchmarks. It would be very useful to include a comparison of your approach to scikit-learn master, so that we know how much we are gaining.

Once that I fix my current stuff. I will provide a benchmark for different number of samples on Higgs dataset.

I had considered jumping in on parallelizing the current tree architecture or looking into categorical support. Should I wait until this new architecture is added in?

I've also forgotten, is this solely going to be for regression trees, or both CART?

Since gradient boosting used the regression tree, we call them like that. But I don't see any blocker to make it happening on classification tree. However, there is currently on implementation details which could be annoying for the random forest. Since that the trees are going by depth and that we take advantage of this to make only a single pass on the samples, it means that the randomly selected features will be the same for all nodes at this specific depth.

This is not an issue for gradient boosting since that usually you are not subsampling the features, but this is one for random forest since that you don't have this feature randomization. It would need to be well benchmark on different problem to see the influence of this particularity.

any news on a benchmark ;)

@amueller I got trap with side project at work which will take me until mid-March. Then I will be able to dedicate much more time and come back to the implementation.