Make `numpy.searchsorted` match NumPy when first argument is unsorted by brandonwillard · Pull Request #7005 · numba/numba

brandonwillard · 2021-05-06T23:09:32Z

This PR makes Numba's searchsorted implementation match NumPy's when the first argument isn't sorted.

Here's an example of the discrepancy under the current Numba implementation:

import numpy as np
import numba


@numba.njit
def numba_searchsorted(a, b):
    return np.searchsorted(a, b, "right")


a = np.array([0.29769574, 0.71649186, 0.20475563])
v = np.array(
    [
        [0.18847123, 0.39659508],
        [0.56220006, 0.57428752],
        [0.86720994, 0.44522637],
    ]
)

numba_searchsorted(a, v)
# array([[0, 1],
#        [1, 1],
#        [3, 1]])

np.searchsorted(a, v, side="right")
# array([[0, 1],
#        [3, 3],
#        [3, 1]])

gmarkall · 2021-05-07T10:55:47Z

Thanks very much for the PR, I've queued it for review.

stuartarchibald

Thanks for the patch, looks good, there's a few minor things to resolve in the comments, main concern is ensuring that this change is well tested. Thanks again!

stuartarchibald · 2021-05-10T12:06:27Z

+            hi = n
+        else:
+            lo = 0
+            hi = hi + 1 if hi < n else n


The tests don't appear to exercise the true branch?

All the tests, or just the unordered one?

I threw in some print statements and all the branches appear to be visited under the current tests.

I manually checked the coverage of the branches and both are covered by the unordered tests.

I found the branches a bit confusing. From what I understand the values of lo and hi are initialized anyway in the searchsorted_imp and not v_last < v is only needed when the array to insert into isn't sorted. When reading the code it seems odd that one branch initializes only hi and the other both hi and lo. Perhaps, in the interest of comprehensibility write the following instead:

if not v_last < v: lo = 0 hi = hi + 1 if hi < n else n

And perhaps add a comment to describe why this is needed?

I just saw the numpy implementation, it seems like this code matches that implementation, so probably best to leave as is.

stuartarchibald · 2021-05-10T12:11:46Z

+        a = np.array([0.29769574, 0.71649186, 0.20475563])
+        v = np.array(
+            [
+                [0.18847123, 0.39659508],
+                [0.56220006, 0.57428752],
+                [0.86720994, 0.44522637],
+            ]
+        )
+        check(a, v)


I think it would be good to add more tests to cover:

the seemingly missed branch

some variations on "unsorted" values and the side kwarg.

It also might be good to also use trivial single digit values in the tests so it's easier to debug if things go wrong etc.

I just changed the test values to simple integers.

some variations on "unsorted" values and the side kwarg.

It looks like the check method tries both side values (and perhaps the left one twice?).

I'd be inclined to make sure those branches are hit with "unsorted" data too. Maybe testing with some random data as well? I'm not sure that Numba can absolutely guarantee matching NumPy internals, but if this sufficient, doesn't hit performance, and helps out in other projects, then I think it's a change worth making.

I'd be inclined to make sure those branches are hit with "unsorted" data too. Maybe testing with some random data as well?

No problem, I can set that up.

I'm not sure that Numba can absolutely guarantee matching NumPy internals, but if this sufficient, doesn't hit performance, and helps out in other projects, then I think it's a change worth making.

It's also fine if you folks aren't comfortable making this change. Again, it's just a closer copy of NumPy's exact implementation, and since the argument should be sorted for this to make sense, exact parity in the unsorted case is just a nicety.

Thanks for adding additional tests. Think this should be ok because, as noted, it's closer but also doesn't explicitly make the guarantee.

some variations on "unsorted" values and the side kwarg.

It looks like the check method tries both side values (and perhaps the left one twice?).

I think that, It runs the left one twice because we check both the kwarg and non-kwarg variants and the default is left, so it gets checked twice.

esc

I made a suggestion (which is also partially a question). I also looked at the docs at:

https://numpy.org/doc/stable/reference/generated/numpy.searchsorted.html

and there is no mention of what happens if the array isn't sorted. I would have expected an error to be raised, since this may qualify as undefined behaviour.

Also, maybe it would be good, if you copied this implementation from NumPy too add a link to the respective place in the NumPy code base (based on a git-sha, so that it doesn't change).

Lastly, I would like to suggest adding a test case, where the first argument is "complete mumbo jumbo" i.e. an array of 10 values or so, which is barely sorted, rather than a simple array where only the last value is out of place.

esc · 2022-06-02T07:39:05Z

Oh, one last thing, can you merge in current main so that we can get Python 3.10 support on this one? I'd like to check this on the build-farm, across different NumPy's and Pytons.

brandonwillard · 2022-06-03T08:22:53Z

Also, maybe it would be good, if you copied this implementation from NumPy too add a link to the respective place in the NumPy code base (based on a git-sha, so that it doesn't change).

A permalink to the NumPy source has been added to the docstring, but it sounded like you also wanted the C++ source? I'm not sure how to include the actual source, especially since the Numba implementation doesn't really have a one-to-one enough relationship with it.

Lastly, I would like to suggest adding a test case, where the first argument is "complete mumbo jumbo" i.e. an array of 10 values or so, which is barely sorted, rather than a simple array where only the last value is out of place.

Done, I think; you'll have to check to see if the new test matches your description adequately.

Oh, one last thing, can you merge in current main so that we can get Python 3.10 support on this one? I'd like to check this on the build-farm, across different NumPy's and Pytons.

Done.

esc

LGTM, thank you for the patch.

brandonwillard requested review from esc, sklam and stuartarchibald as code owners May 6, 2021 23:09

brandonwillard changed the title ~~Make numpy.searchsorted match NumPy when first argument is unsorted~~ Make numpy.searchsorted match NumPy when first argument is unsorted May 6, 2021

gmarkall added 3 - Ready for Review Effort - short Short size effort needed labels May 7, 2021

gmarkall added this to the Numba 0.54 RC milestone May 7, 2021

stuartarchibald reviewed May 10, 2021

View reviewed changes

stuartarchibald added 4 - Waiting on author Waiting for author to respond to review and removed 3 - Ready for Review labels May 10, 2021

sklam modified the milestones: Numba 0.54 RC, Numba 0.55 RC Jun 24, 2021

stuartarchibald modified the milestones: Numba 0.55 RC, Numba 0.56 RC Nov 18, 2021

sklam assigned esc Jun 1, 2022

esc requested changes Jun 2, 2022

View reviewed changes

brandonwillard force-pushed the unsorted-searchsorted branch from 464fa48 to 395a7d1 Compare June 3, 2022 08:04

brandonwillard added 3 commits June 3, 2022 03:26

Make numpy.searchsorted match NumPy when first argument is unsorted

55cb103

Simplify searchsorted unordered test values

a6bff25

Added another unordered searchsorted test with a larger array

24fe303

brandonwillard force-pushed the unsorted-searchsorted branch from 63ef11e to 24fe303 Compare June 3, 2022 08:26

esc approved these changes Jun 7, 2022

View reviewed changes

esc added 5 - Ready to merge Review and testing done, is ready to merge and removed 4 - Waiting on author Waiting for author to respond to review labels Jun 8, 2022

sklam merged commit 9e98315 into numba:main Jun 9, 2022

Conversation

brandonwillard commented May 6, 2021

Uh oh!

gmarkall commented May 7, 2021

Uh oh!

stuartarchibald left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

esc left a comment

Choose a reason for hiding this comment

Uh oh!

esc commented Jun 2, 2022

Uh oh!

brandonwillard commented Jun 3, 2022

Uh oh!

esc left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants