PERF Pass buffers via pointers in `PairwiseDistancesReductions` routines for sparse data by Micky774 · Pull Request #26765 · scikit-learn/scikit-learn

Micky774 · 2023-07-04T19:14:32Z

Reference Issues/PRs

Discussed a little here

What does this implement/fix? Explain your changes.

The {r}dist_csr methods now accept pointers rather than memory views since none of the peripheral data of memory views are used. This significantly decreases call overhead, which is especially beneficial for the tight loops in which these functions are often used.

This also includes a formatting fix for HaversineDistance

This also enforces contiguous layouts wherever possible.

Any other comments?

Benchmarks generated via: https://gist.github.com/Micky774/9daede3d638ebbdbb34bc26f884f2748

Benchmarks

Micky774 · 2023-07-04T19:15:49Z

@jjerphan @thomasjpfan In case either of you have interest in the PR. The scope/content is fairly limited.

github-actions · 2023-07-04T19:16:36Z

✔️ Linting Passed

All linting checks passed. Your pull request is in excellent shape! ☀️

_{Generated for commit: 92f7c12. Link to the linter CI: here}

jjerphan · 2023-07-04T20:01:03Z

Nice one! Those implementations get up to 1.5× speedups!

Two questions:

can you add a changelog entry?
are there any other places where buffers' pointers could be passed instead of memoryviews?

thomasjpfan

Given the performance improvement, I think this deserves a changelog entry in v1.4. Otherwise, LGTM.

jjerphan · 2023-07-05T18:16:16Z

Also, should we adjust the title of this PR to be more specific? For instance, how about this one?

PERF Pass buffers via pointers in `PairwiseDistancesReductions` routines for sparse data

Micky774 · 2023-07-07T15:50:16Z

are there any other places where buffers' pointers could be passed instead of memoryviews?

Almost certainly. Anywhere we don't use the associated attributes of a memory-view and are able to leverage contiguous memory, we could technically use pointers instead. With that being said, this is really only a benefit for function calls in tight loops where the overhead is a dominant factor. I'm not sure where else that pattern is present (maybe somewhere in linear models or trees?)

jjerphan

Thank you @Micky774!

LGTM modulo a comment.

As you indicated, other Cython implementations might be adapted similarly. I think we can keep them for first time Cython-contributions. What do you think?

@da-woods: are the optimisations that you have mentioned in #25608 (comment) similar to those ones?

jjerphan · 2023-07-07T16:19:13Z

doc/whats_new/v1.4.rst

+- |Performance| Computing pairwise distances for (CSR x CSR) and (CSR x Dense)
+  datasets is now 1.5x faster by improving the argument passing strategy used
+  in the computation routines in :class:`metrics.DistanceMetric`.


Nitpick: I think that we generally keep changelog entry short without giving too much technical details.

Suggested change

- |Performance| Computing pairwise distances for (CSR x CSR) and (CSR x Dense)

datasets is now 1.5x faster by improving the argument passing strategy used

in the computation routines in :class:`metrics.DistanceMetric`.

- |Performance| Computing pairwise distances via :class:`metrics.DistanceMetric` for CSR × CSR, Dense × CSR, and CSR × Dense datasets is now 1.5x faster.

Should we also add another one for estimators of module.neighbors?

Should we also add another one for estimators of module.neighbors?

I'm not sure -- there are a lot of estimators which at least partly use the DistanceMetric backend
(the following list is puled from #26329):

- NearestNeighbors - KNeighborsRegressor - KNeighborsClassifier - RadiusNeighborsRegressor - RadiusNeighborsClassifier - DBSCAN - OPTICS - Isomap - TSNE (self.method != "exact") - KernelDensity - AffinityPropagation - Birch - MeanShift - NearestCentroid

I don't quite know where to draw the line for this if we do include it for other estimators specifically. Most .predict methods, for example, benefit from this.

Micky774 · 2023-07-07T16:45:58Z

As you indicated, other Cython implementations might be adapted similarly. I think we can keep them for first time Cython-contributions. What do you think?

I think that's a good idea, though I'm not sure what the best way to discover where in the code these changes ought to be propagated. Perhaps an open ended meta-issue of "If you spot this pattern, feel free to open a PR fixing it" would be appropriate?

jjerphan · 2023-07-07T16:57:24Z

Yes, I guess we can spend some time to read implementations and list in a meta-issue candidate places for those optimisations.

da-woods · 2023-07-07T16:57:32Z

The one thing I'm slightly nervous of is that you look to be taking these pointers from non-contiguous memoryviews. I suspect practically they are contiguous in practice, but it might be nice to enforce that.

Passing a pointer is about as light-weight as you can get, so nothing Cython can do is ever likely to beat it. The changes I mentioned in the linked issue should bring memoryview slicing a lot closer, but pointers are still likely to win. (Essentially all I've done is noticed that taking multiple slices of the same array is a reference counting no-op, so you pay for one reference count at the start of the loop and that's it. From the point of view of this PR, it's a distraction though)

sklearn/metrics/_dist_metrics.pyx.tp

jjerphan

I think we need to operate on continuous buffers as mentioned by #26765 (comment).

Micky774 · 2023-07-20T16:58:39Z

I suspect practically they are contiguous in practice, but it might be nice to enforce that.

Good point!

I've now done so in the attribute declarations and some method signatures. I wanted to as well check if enforcing it in the {r}dist_csr signatures would offer any boost as an alternative to passing the raw pointer, but it seems to be a negligible difference wrt main. With the attributes' (e.g. {X, Y}_indices ) contiguity being enforced, we ought to be able to "safely" use the pointers directly now.

Let me know if there are any other spots you think we could tighten up our guarantees. Thanks to all 😄

Micky774 · 2023-07-20T23:12:19Z

@jjerphan Thoughts?

jjerphan

LGTM modulo a suggestion.

This must remove some of the dispatch cost that @Vincent-Maladiere and I typically have observed in the past with #25170.

sklearn/metrics/_dist_metrics.pyx.tp

…nes for sparse data (scikit-learn#26765)

Initial changes

dc5d802

github-actions bot added module:metrics cython labels Jul 4, 2023

Micky774 added No Changelog Needed module:metrics cython and removed module:metrics cython labels Jul 4, 2023

Micky774 changed the title ~~MNT Pass indices memory-view by reference rather than by value~~ PERF Pass indices memory-view by reference rather than by value Jul 4, 2023

thomasjpfan approved these changes Jul 5, 2023

View reviewed changes

thomasjpfan removed the No Changelog Needed label Jul 5, 2023

Micky774 changed the title ~~PERF Pass indices memory-view by reference rather than by value~~ PERF Pass buffers via pointers in PairwiseDistancesReductions routines for sparse data Jul 7, 2023

Added changelog entry

bf00106

Merge branch 'main' into memview_to_ptr

a099758

jjerphan approved these changes Jul 7, 2023

View reviewed changes

da-woods reviewed Jul 7, 2023

View reviewed changes

sklearn/metrics/_dist_metrics.pyx.tp Show resolved Hide resolved

Updated changelog

6672e72

Micky774 mentioned this pull request Jul 7, 2023

FEA Introduce PairwiseDistances, a generic back-end for pairwise_distances #25561

Closed

Merge branch 'main' into memview_to_ptr

d0790f6

jjerphan requested changes Jul 20, 2023

View reviewed changes

Micky774 added 2 commits July 20, 2023 12:34

Merge branch 'main' into memview_to_ptr

d9f771c

Enforce contiguity wherever possible

92f7c12

jjerphan approved these changes Jul 21, 2023

View reviewed changes

sklearn/metrics/_dist_metrics.pyx.tp Outdated Show resolved Hide resolved

Enforced continguous arrays

183b44b

jjerphan enabled auto-merge (squash) July 21, 2023 20:44

jjerphan merged commit 0486033 into scikit-learn:main Jul 21, 2023

Micky774 deleted the memview_to_ptr branch July 22, 2023 03:14

punndcoder28 pushed a commit to punndcoder28/scikit-learn that referenced this pull request Jul 29, 2023

PERF Pass buffers via pointers in PairwiseDistancesReductions routi…

22bb0bd

…nes for sparse data (scikit-learn#26765)

REDVM pushed a commit to REDVM/scikit-learn that referenced this pull request Nov 16, 2023

PERF Pass buffers via pointers in PairwiseDistancesReductions routi…

f7e202f

…nes for sparse data (scikit-learn#26765)

Uh oh!

Conversation

Micky774 commented Jul 4, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Reference Issues/PRs

What does this implement/fix? Explain your changes.

Any other comments?

Uh oh!

Micky774 commented Jul 4, 2023

Uh oh!

github-actions bot commented Jul 4, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

✔️ Linting Passed

Uh oh!

jjerphan commented Jul 4, 2023

Uh oh!

thomasjpfan left a comment

Choose a reason for hiding this comment

Uh oh!

jjerphan commented Jul 5, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Micky774 commented Jul 7, 2023

Uh oh!

jjerphan left a comment

Choose a reason for hiding this comment

Uh oh!

jjerphan Jul 7, 2023

Choose a reason for hiding this comment

Uh oh!

Micky774 Jul 19, 2023

Choose a reason for hiding this comment

Uh oh!

Micky774 commented Jul 7, 2023

Uh oh!

jjerphan commented Jul 7, 2023

Uh oh!

da-woods commented Jul 7, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

jjerphan left a comment

Choose a reason for hiding this comment

Uh oh!

Micky774 commented Jul 20, 2023

Uh oh!

Micky774 commented Jul 20, 2023

Uh oh!

jjerphan left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Micky774 commented Jul 4, 2023 •

edited

Loading

github-actions bot commented Jul 4, 2023 •

edited

Loading

jjerphan commented Jul 5, 2023 •

edited

Loading

da-woods commented Jul 7, 2023 •

edited

Loading