I think the numa-aware optimisation is low priority compared to the np.zeros and the low decision-tree nodes issues as the numa-related issue is likely to impact a significantly lower number of users.

Thanks a lot for the report, I'll look into it.

A very easy partial fix is to replace zeros by empty in compute_histograms_subtraction. That wouldn't work for compute_histograms_brute though, we still need to initialize the arrays to zero.

we still need to initialize the arrays to zero.

The arrays can be initialized to zero (e.g. using memset to avoid using GIL) in parallel in the prange threads using a with nogil, parallel(): context manager: https://cython.readthedocs.io/en/latest/src/userguide/parallelism.html#cython.parallel.parallel

@ogrisel @NicolasHug I have prepared replacing of np.zeroes in this PR #14380

The arrays can be initialized to zero (e.g. using memset to avoid using GIL) in parallel

Yes of course. Though unless with have tons of features, since max_bins is caped to 255 I don't think we need to do that in parallel. I think LightGBM has a heuristic rule for that.

On top of initialization, we can start looking at memory allocation. LightGBM uses a LRU cache for the histograms and we could too. A simple one would be to re-use the histograms of any parent whose children have been splitted (splitted = split_info is computed).

Scikit-learn’s code spends too much time in np.zeroes() functions

@SmirnovEgorRu may I ask how you came to this conclusion? What tools did you use?

I replaced usage of np.zeroes() by np.empty() and scaling was improved, for max number of threads performance improvement – around 30%.

Did you also make sure to initialize the arrays to zero when compute_histogram_brute is called? Else the fast training time might just be due to histogram values being super random and split-points being essentially wrong.

For reference here are the times (in seconds) I observed for scaling on a 12 physical core cpu:

OMP_NUM_THREADS=$i python benchmarks/bench_hist_gradient_boosting_higgsboson.py \
    --n-leaf-nodes 255 --n-trees 100

Versions:

lightgbm==2.2.1
xgboost==0.90
scikit-learn==0.21.2

Here is the raw data with other data in (tidy format)

I hate tidy data

y is 200/mean, so it's a speedup over sklearn with a single core (approximately)

@thomasjpfan current master of XGBoost contains additional optimizations 2-3x and more vs. 0.9 version depending on # of cores and algorithm parameters, PR with optimizations.
Could you, please, check your measurements with the latest version?

@SmirnovEgorRu I guess the main concern in this issue is the scalability of our implementation w.r.t the number of threads, not how fast it is compared to XGBoost.

@NicolasHug I mean that it is possible to look at optimizations which have been done in XGBoost recently and move some of them into scikit.

oh ok thanks for the heads up. Is there a reasonably detailed summary of the optimizations that you implemented? Or is reading the code our only hope here ^^ ?

@NicolasHug some information is available in PRs ( dmlc/xgboost#4529, dmlc/xgboost#4433, dmlc/xgboost#4278, dmlc/xgboost#4310, dmlc/xgboost#3957) and here https://github.com/SmirnovEgorRu/xgboost-fast-hist-perf-lab
Also, I'm planning to publish a blog about this, but later.

Thanks, definitely ping us when the blog post is ready please :)

@SmirnovEgorRu On dmlc/xgboost@53d4272 here is the same benchmark:

Data that is still tidy

@thomasjpfan why do you hate me? (also I find plots easier to read than comparing lists that are far apart and have 6 decimals)

what is it GBDT
and what is it Histogram-based GBDT??
thanks

ok I see GBDT is GBM
now all clear

@Sandy4321 GBDT stands for Gradient Boosted Decision Trees which are basically GBM (Gradient Boosting Machines) with a Decision Tree as the weak learner).

@NicolasHug @thomasjpfan can you do a lscpu to check whether this is a single socket processor with 12 cores or 2 sockets with 6 cores (and therefore 2 NUMA nodes)?

Based on your scalability curves I would vote for single socket CPU but I would like to have the confirmation.

GBDT stands for Gradient Boosted Decision Trees which are basically GBM (Gradient Boosting Machines) with a Decision Tree as the weak learner)

I see thanks
and may you share link to read about algorithm of Histogram-based GBDT
my guess it is Histogram-based split?

@ogrisel Single socket

@ogrisel Have you experimented with OMP_PROC_BIND?: https://gcc.gnu.org/onlinedocs/libgomp/OMP_005fPROC_005fBIND.html

I ran some benchmarks on a machine with 2 Intel Xeon E5-2620 CPUs @ 2.10GHz (8 cores/16 threads each), so 2 NUMA nodes.

TLDR: The scikit-learn implementation scales just as well(bad) as lightgbm.

python benchmarks/bench_hist_gradient_boosting_higgsboson.py --n-leaf-nodes 255 --n-trees 200 --lightgbm

,hist building,split finding,splitting,predicting,total sklearn,total lightgbm
4,81.71,1.844,15.025,6.989,167.46,154.8
8,48.849,1.872,9.978,5.08,105.962,96.558
12,39.798,1.801,8.478,4.307,88.005,76.316
16,33.573,1.823,8.413,4.336,77.661,64.42
20,42.688,2.458,9.994,4.415,90.873,71.924
24,37.815,2.431,9.299,3.83,83.259,68.586
28,32.452,2.716,9.8,3.707,76.601,65.821
32,32.919,3.458,10.48,3.542,78.742,68.538

A few observations:

• LightGBM is faster
• Both sklearn and lightgbm plateau after 16 threads. They both follow the same variations. The scalability of both libraries is comparable.
• The variations are dictated by the histogram computation. This makes sense, since this is clearly the bottleneck.
• Split finding is slower as the number of threads increases. Might be because there are not many features in the higgs boson dataset? It's marginal anyway.

I did observe the CPUs only being used at around 90% for the sklearn parts. This could explain why lightgbm is faster.

Would appreciate your thoughts @SmirnovEgorRu @ogrisel @thomasjpfan :)

@NicolasHug, the blog what I mentioned above is here now: https://software.intel.com/en-us/download/parallel-universe-magazine-issue-38-august-2019
I hope you will find smth interesting :)

Very interesting, thanks!

If I understand correctly (please correct me if I'm wrong!), it seems that the main difference between our implementations is the histogram computation.

In scikit-learn each feature histogram is built independently (one thread per feature). For each feature, we loop through all the samples at the current node.

In contrast, XGBoost does not compute each feature histogram independently. Instead it loops over the samples and compute "partial histograms" (which I assume are of size n_features * n_bins) that are then aggregated together in a typical map/reduce procedure. The multi-threading is sample-wise, not feature-wise like in sklearn.

For that reason it makes sense for XGBoost to use a C-aligned bin matrix, while we are using a F-aligned matrix.

CC @ogrisel @adrinjalali who might be interested in that sort of details

Thanks. Indeed this is very interesting. /cc @jeremiedbb @glemaitre who might also be interested in this.

@NicolasHug in your benchmarks, how many physical cores (without hyperthreads) do you have on the host machine? If it's 16, then it's normal to reach a plateau at 16 openmp threads. But indeed the problem is not as bad as I remember. Still it would be interesting to re-benchmark sklearn on Higgs vs the latest xgboost master on a machine with many cores.

Edit: indeed you have 16 physical cores. I had not read the beginning of your comment.

@ogrisel my knowledge of CPUs is quite limited. Could you explain why it's normal to plateau at 16?

Hyperthreaded cores are fake core and it's quite often the case that they do not provide any speed-up for compute intensive algorithms. So I would only run benchmarks with n_threads <= n_physical_cores instead of n_threads <= n_logical_cores. It does not hurt to go measure beyond the physical cores limit but I would not expect miracles from hyperthreads.

For ref, the overhead induced by using np.zeros to initialize histograms was dealt with in #18341. Benchmarks above are (likely) outdated.

Some scalability issues w.r.t number of threads remain though -- we're still not as fast as LightGBM.

Going back to #14306 (comment), from microsoft/LightGBM#2791 (comment): like XGBoost, LightGBM 3.0 has also implemented sample-wise parallelism to build histograms, instead of feature-wise parallelism. This seems to be preferable for small numbers of threads and features.

Based on #18382, the scalability profile of scikit-learn is not too bad on large problems. On small problems it's bad when n_threads > n_physical cores. As hyperthreads are never useful, it would be good to improve joblib / loky to detect the number of physical cores and use that as the default number of openmp threads in HGBRT. Work on this is being tracked here: joblib/loky#223. Besides this over-subscription problem when n_threads > n_physical_cores, the scalability profile of scikit-learn is not too bad.

As @NicolasHug analyzed in #18382 (comment), we might also want to review the openmp pragmas used by LightGBM to see if there are things with missed to improve speed in critical parallem sections on smaller problems.

Finally LightGBM is indeed faster even in sequential model. This might be related to LightGBM 3.0 perf improvements (#14306 (comment)) but this is unrelated to multicore scalability.

I just merged #26082 to use only as many threads as physical cores by default. This should improve things a bit (a least avoid some catastrophic slow-downs when fitting many HGBDT models on small dataset on machines with many cores and Hyper Threading / SMT enabled) but this is not a complete fix.