ENH Break cyclic references in Histogram GBRT #18334

ogrisel · 2020-09-03T16:58:26Z

Resolves #18152
This is an alternative to #18163 and #18242

This is a minimal fix to:

break the cyclic references that cause the GC to fail to collect all the TreeNode instances (and there histogram attributes) for all the TreeGrower instances (as an alternative to the manual memory management workaround implemented in ENH Greatly reduces memory usage of histogram gradient boosting #18242).
early delete the references to the histograms attribute of each TreeNode instance as soon as no longer needed (as done in HistGradientBoosting memory improvement #18163).

For the reproducer snippet of #18242:

from sklearn.datasets import make_classification
from sklearn.experimental import enable_hist_gradient_boosting
from sklearn.ensemble import HistGradientBoostingClassifier
from memory_profiler import memory_usage

X, y = make_classification(n_classes=2,
                           n_samples=10_000,
                           n_features=400,
                           random_state=0)

hgb = HistGradientBoostingClassifier(
    max_iter=100,
    max_leaf_nodes=127,
    learning_rate=.1,
    random_state=0,
    verbose=1,
)

mems = memory_usage((hgb.fit, (X, y)))
print(f"{max(mems):.2f}, {max(mems) - min(mems):.2f} MB")

I get:

Fit 100 trees in 36.711 s, (12700 total leaves)
Time spent computing histograms: 28.150s
Time spent finding best splits:  5.183s
Time spent applying splits:      1.046s
Time spent predicting:           0.016s
282.35, 144.09 MB

(instead of 6GB+ on master).

thomasjpfan · 2020-09-03T17:09:03Z

Hm I am getting 983.82, 790.27 MB with this PR.

ogrisel · 2020-09-03T17:20:21Z

Hm I am getting 983.82, 790.27 MB with this PR.

That's weird... maybe my Python GC is smarter than yours? I am running Python 3.8.3.

ogrisel · 2020-09-03T17:41:33Z

Anyways I am fine with closing this in favor of the manual memory management in #18242 if it ensures a more reliable memory usage. I also updated #18242 to remove the useless attributes that introduced the cyclic refs as clean-up.

NicolasHug · 2020-09-03T17:47:32Z

Why do you say this PR is less reliable @ogrisel?

ogrisel · 2020-09-03T17:48:17Z

I re-ran the snippet several times (restarting Python each time) and I consistently get ~140 MB increments instead of the 790.27 MB observed by @thomasjpfan on his machine.

ogrisel · 2020-09-03T17:49:50Z

Why do you say this PR is less reliable @ogrisel?

@thomasjpfan still observes a 790.27 MB increment with this PR on his machine so the GC does not seem to free memory as fast as needed. Therefore, explicit memory management as done in #18242 might still be useful for some users.

NicolasHug · 2020-09-03T17:58:25Z

I too consistently observe about 140MB on this PR with Python 3.8.2, on 2 different machines. (1, 4, and 16 threads. Not that it should matter anyway.)

@thomasjpfan can you double check the benchmark you ran make sure you used the same snippet above?

NicolasHug

Thanks @ogrisel

I have a preference for this solution considering its simplicity and it because of its "unitaryness" (brain is frozen, can't think of a word)

We can still use np.empty and initialize histograms in parallel. However I'd rather leave that for a different PR. I feel like #18242 does too many things at once and it's hard to determine the effect of each change.

My only concern here is: how do we prevent cyclic refs from sneaking in in the future? I guess we should write a memory benchmark in asv?

sklearn/ensemble/_hist_gradient_boosting/grower.py

ogrisel · 2020-09-03T18:07:37Z

We can still use np.empty and initialize histograms in parallel. However I'd rather leave that for a different PR.

I agree. It was in the back of my head but I wanted to wait a bit before adding it.

@thomasjpfan what's your feeling w.r.t. the need to introduce the HistogramPool?

NicolasHug · 2020-09-03T18:13:18Z

I think we should:

merge this. It's a net improvement, irrespective of benchmark results: it removes useless attributes and can be considered pure maintenance.
use np.empty and initialize histograms in parallel in another PR, and evaluate the speed improvement
Consider adding the pool then, in yet another PR.

If 1 does its job then I doubt 3 would add a significant memory improvement but it might add a small speed improvement, since it will remove the need from allocating memory each time.

thomasjpfan · 2020-09-03T18:15:19Z

@thomasjpfan what's your feeling w.r.t. the need to introduce the HistogramPool?

Let's merge this one first.

On linux with 3.8, I get 245.16, 131.90 MB.
On linux with 3.7, I get 256.35, 140.72 MB.
On OSX with 3.8, memory profiler does not work with 3.8 yet on osx. edit: When I look at the process with htop I see the memory go to ~1GB. which is consistent with OSX with 3.7.
On OSX with 3.7, I get 983.82, 790.27 MB

ogrisel · 2020-09-03T18:51:20Z

Thanks @thomasjpfan for the investigation. Let me add a what's new entry to this PR if you want to merge it as it is. However the results on macOS makes me think that we will need to add the HistogramPool anyway.

ogrisel · 2020-09-03T19:02:19Z

Done. Feel free to merge and then rework #18242 on top of this...

sklearn/ensemble/_hist_gradient_boosting/grower.py

Co-authored-by: Nicolas Hug <contact@nicolas-hug.com>

thomasjpfan

LGTM

Co-authored-by: Nicolas Hug <contact@nicolas-hug.com>

ogrisel added 2 commits September 3, 2020 18:49

Remove useless TreeNode attributes to break cyclic references

4827570

Free histograms memory as soon as possible

aecda18

github-actions bot added the module:ensemble label Sep 3, 2020

ogrisel mentioned this pull request Sep 3, 2020

HistGradientBoosting memory improvement #18163

Closed

NicolasHug approved these changes Sep 3, 2020

View reviewed changes

sklearn/ensemble/_hist_gradient_boosting/grower.py Outdated Show resolved Hide resolved

ogrisel added 2 commits September 3, 2020 20:52

Wording in comment

46c398a

Add whats new entry

b6aec72

NicolasHug reviewed Sep 3, 2020

View reviewed changes

sklearn/ensemble/_hist_gradient_boosting/grower.py Outdated Show resolved Hide resolved

Update sklearn/ensemble/_hist_gradient_boosting/grower.py

80add09

Co-authored-by: Nicolas Hug <contact@nicolas-hug.com>

thomasjpfan approved these changes Sep 3, 2020

View reviewed changes

thomasjpfan changed the title ~~Break cyclick references in Histogram GBRT~~ ENH Break cyclic references in Histogram GBRT Sep 3, 2020

thomasjpfan merged commit e325f16 into scikit-learn:master Sep 3, 2020

ogrisel deleted the hgbrt-break-cyclick-refs branch September 3, 2020 22:35

ogrisel mentioned this pull request Sep 4, 2020

ENH Greatly reduces memory usage of histogram gradient boosting #18242

Closed

lorentzenchr mentioned this pull request Sep 5, 2020

[MRG] GBDT: Reuse allocated memory of other histograms #14392

Closed

ogrisel mentioned this pull request Sep 11, 2020

sklearn HistGBT szilard/GBM-perf#36

Open

jayzed82 pushed a commit to jayzed82/scikit-learn that referenced this pull request Oct 22, 2020

ENH Break cyclic references in Histogram GBRT (scikit-learn#18334)

1883041

Co-authored-by: Nicolas Hug <contact@nicolas-hug.com>

thomasjpfan mentioned this pull request Nov 28, 2023

ENH reuse parent histograms as one of the child's histogram #27865

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ENH Break cyclic references in Histogram GBRT #18334

ENH Break cyclic references in Histogram GBRT #18334

ogrisel commented Sep 3, 2020

thomasjpfan commented Sep 3, 2020 •

edited

Loading

ogrisel commented Sep 3, 2020

ogrisel commented Sep 3, 2020

NicolasHug commented Sep 3, 2020

ogrisel commented Sep 3, 2020

ogrisel commented Sep 3, 2020 •

edited

Loading

NicolasHug commented Sep 3, 2020 •

edited

Loading

NicolasHug left a comment

ogrisel commented Sep 3, 2020

NicolasHug commented Sep 3, 2020

thomasjpfan commented Sep 3, 2020 •

edited

Loading

ogrisel commented Sep 3, 2020 •

edited

Loading

ogrisel commented Sep 3, 2020

thomasjpfan left a comment

ENH Break cyclic references in Histogram GBRT #18334

ENH Break cyclic references in Histogram GBRT #18334

Conversation

ogrisel commented Sep 3, 2020

thomasjpfan commented Sep 3, 2020 • edited Loading

ogrisel commented Sep 3, 2020

ogrisel commented Sep 3, 2020

NicolasHug commented Sep 3, 2020

ogrisel commented Sep 3, 2020

ogrisel commented Sep 3, 2020 • edited Loading

NicolasHug commented Sep 3, 2020 • edited Loading

NicolasHug left a comment

Choose a reason for hiding this comment

ogrisel commented Sep 3, 2020

NicolasHug commented Sep 3, 2020

thomasjpfan commented Sep 3, 2020 • edited Loading

ogrisel commented Sep 3, 2020 • edited Loading

ogrisel commented Sep 3, 2020

thomasjpfan left a comment

Choose a reason for hiding this comment

thomasjpfan commented Sep 3, 2020 •

edited

Loading

ogrisel commented Sep 3, 2020 •

edited

Loading

NicolasHug commented Sep 3, 2020 •

edited

Loading

thomasjpfan commented Sep 3, 2020 •

edited

Loading

ogrisel commented Sep 3, 2020 •

edited

Loading