ENH reuse parent histogram in HGBT #26189
Open
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Simple benchmarkOn the higgs dataset, this PR gives ~4% speed-up, which is about the expected amount (1 / 28 features = 3.5%). Running on main gives On this PR: |
thomasjpfan
reviewed
Apr 17, 2023
lorentzenchr
force-pushed
the
hgbt_reuse_parent_hist
branch
from
9fb9006 to
b1efb34
Compare
thomasjpfan
reviewed
Jan 21, 2024
Comment on lines
584
to
+591
| if n_samples_left < n_samples_right: | ||
| smallest_child = left_child_node | ||
| largest_child = right_child_node | ||
| is_left_child = True | ||
| else: | ||
| smallest_child = right_child_node | ||
| largest_child = left_child_node | ||
| is_left_child = False |
There was a problem hiding this comment.
Nit:
is_left_child = n_samples_left < n_samples_right
if is_left_child:
smallest_child = left_child_node
largest_child = right_child_node
else:
smallest_child = right_child_node
largest_child = left_child_node| unsigned int split_bin_end | ||
| unsigned char is_categorical | ||
| BITSET_INNER_DTYPE_C [:] left_cat_bitset | ||
| bint has_parent_hist = False |
There was a problem hiding this comment.
Suggested change
| bint has_parent_hist = False | |
| bint has_parent_hist = parent_split_info is not None |
Comment on lines
+170
to
+171
| if parent_split_info is not None: | ||
| has_parent_hist = True |
There was a problem hiding this comment.
Suggested change
| if parent_split_info is not None: | |
| has_parent_hist = True | |
| if has_parent_hist: |
| @@ -141,8 +156,30 @@ cdef class HistogramBuilder: | |||
| dtype=HISTOGRAM_DTYPE | |||
| ) | |||
| bint has_interaction_cst = allowed_features is not None | |||
| # Feature index of the feature that the parent node was split on. | |||
| int split_feature_idx | |||
There was a problem hiding this comment.
Suggested change
| int split_feature_idx | |
| int parent_split_feature_idx |
Comment on lines
+162
to
+164
| unsigned int split_bin_start | ||
| # End (+1) of the bin indices belonging to the feature that was split on. | ||
| unsigned int split_bin_end |
There was a problem hiding this comment.
I think these are also for the parent.
Suggested change
| unsigned int split_bin_start | |
| # End (+1) of the bin indices belonging to the feature that was split on. | |
| unsigned int split_bin_end | |
| unsigned int parent_split_bin_start | |
| # End (+1) of the bin indices belonging to the feature that was split on. | |
| unsigned int parent_split_bin_end |
| @@ -422,6 +422,13 @@ Changelog | |||
| In effect, less memory has to be allocated and deallocated. | |||
| :pr:`27865` by :user:`Christian Lorentzen <lorentzenchr>`. | |||
|
|
|||
| - |Efficiency| :class:`ensemble.HistGradientBoostingClassifier` and | |||
There was a problem hiding this comment.
This needs to be moved to 1.5
|
@lorentzenchr: should we continue and merge this PR, or not? |
Only if I get the commitment of 2 core devs willing to review and finally approve. |
|
I would be glad reviewing this PR, but I would rather finish what I started first. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Reference Issues/PRs
None
What does this implement/fix? Explain your changes.
This PR reuses the parent's histogram for the feature that was split on. This saves a little time.
Any other comments?
The implementation is no beauty. If we want to include this improvement, suggestions or alternative PRs are welcome.