fix series.isin slow issue with Dtype IntegerArray
State: closed

- [ ] closes #38340 
- [ ] tests added / passed
- [ ] passes `black pandas`
- [ ] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [ ] whatsnew entry


Labels:
name: Indexing
description: Related to indexing on series/frames, not to indexes themselves
name: Performance
description: Memory or execution speed performance
name: ExtensionArray
description: Extending pandas with custom dtypes or arrays.

Comments:
> this is not the appropriate place
> 
> in algorithms.isin itself instead

Hi, I've move this code to `algorithms.isin`, but due to circular import, we cannot import `IntegerArray` in that file. So I have to use `comp.__class__.__name__ is 'IntegerArray'` instead. If you got better solution, please give me some advices, thanks so much.
Hello @tushushu! Thanks for updating this PR. We checked the lines you've touched for [PEP 8](https://www.python.org/dev/peps/pep-0008) issues, and found:









There are currently no PEP 8 issues detected in this Pull Request. Cheers! :beers: 

##### Comment last updated at 2021-01-19 15:29:07 UTC
Here is the jupyter notebook how I analyze and fix this issue.
https://github.com/tushushu/tuopen/blob/main/pandas-pr-38379.ipynb
@tushushu suggest you follow what is going on in #38422 for this.
Thanks @jbrockmendel and @jreback , I am going to have a look at https://github.com/pandas-dev/pandas/pull/38422
@jbrockmendel @jorisvandenbossche Hi, I guess `isin(1, 2, pd.NA], [1, pd.NA])` could return `[True, False, True]` but not `[True, False, pd.NA]`.
Below are something might be useful, and I am also curious why `pd.NA in pd.Series([1, 2, pd.NA]` should return `False`?

```Python
None in [1, 2, 3, None]  # Will return True but not None
np.nan in np.array([1, 2, np.nan])  # Will return False but not np.nan
pd.NA in pd.Series([1, 2, pd.NA])  # Will return False but not pd.NA
```

Would you please give me some advices? Thanks~
>  I am also curious why pd.NA in pd.Series([1, 2, pd.NA] should return False?

I think this is what I'd expect - if `pd.NA` could be anything, then you don't know if it's in `pd.Series([1, 2, pd.NA])`
gentle ping @jorisvandenbossche can you weigh in here on desired behavior
some precommit hooks are failing
> do we have asvs for EA as targets (Floating,Integer,Boolean) with EAs as inputs? can you show the results
```Python
pd.Series([False, True], dtype="boolean").isin(pd.array([False], dtype="boolean"))
pd.Series([1, 5], dtype="Int64").isin(pd.array([1, 2, 3, 4], dtype="Int64"))
pd.Series([1.0, 5.0], dtype="Float64").isin(pd.array([1.0, 2.0, 3.0, 4.0], dtype="Float64"))
```
Sorry, but I am not sure what does `asvs` stand for here. All the three lines above can return the same result as below

```Python
0     True
1    False
dtype: boolean
```
Is this what you expected?
https://pandas.pydata.org/pandas-docs/dev/development/contributing.html#running-the-performance-test-suite

no performance tests
> some precommit hooks are failing

I've checked the error log, and it seems that some functions/methods are not fully type annotated, which are not caused by current PR.

> Sorry, but I am not sure what does `asvs` stand for here. All the three lines above can return the same result as below

@tushushu take a look at https://pandas.pydata.org/pandas-docs/stable/development/contributing.html#running-the-performance-test-suite for a reference

The `isin` benchmarks that this hits sit in `asv_bench/benchmarks/series_methods.py` - I don't think EA dtypes are covered
> > some precommit hooks are failing
> 
> I've checked the error log, and it seems that some functions/methods are not fully type annotated, which are not caused by current PR.

It's a weird set of errors but they're definitely to do with the changes here (we keep `mypy` passing on master)
> > Sorry, but I am not sure what does `asvs` stand for here. All the three lines above can return the same result as below
> 
> @tushushu take a look at https://pandas.pydata.org/pandas-docs/stable/development/contributing.html#running-the-performance-test-suite for a reference
> 
> The `isin` benchmarks that this hits sit in `asv_bench/benchmarks/series_methods.py` - I don't think EA dtypes are covered


Thanks~ I am adding `"Int64"` into the `params` in the codes below, I've never used asv_bench before and I guess that will work for EA?
```Python
class IsIn:

    params = ["int64", "uint64", "object"]
```
@jreback @arw2019 
The performance tests result is as below:
```
       before           after         ratio
     [0f587028]       [2348a600]
     <v1.3.0.dev0^0>       <ENH-implement-fast-isin>
+         344±5ms         381±30ms     1.11  series_methods.IsInLongSeriesLookUpDominates.time_isin('object', 5, 'monotone_misses')
-         238±6μs          213±5μs     0.89  series_methods.IsInDatetime64.time_isin_empty
-     2.80±0.02ms      2.15±0.01ms     0.77  series_methods.IsIn.time_isin('Int64')
```
> i dont' see an actual benchmark for Int64 isin. we also need for Float64 and Boolean. please add these in this PR. also something is failing on this, needs to be all green.
> 
> pls add a whatsnew note as well 1.3 / performance
> 
> and question about if isin should be in BaseMaskedArray instead of where you have it

Hi,
1. I have added the benchmark for Int64 locally, will push to this PR later. Will add Float64 and Boolean, too.
2. This mypy error seem to be weird, these functions/methods are not annotated before this PR. How could they pass the mypy test? Could you please give me some hint? Have you making these mypy errors ignored by configuration somewhere?
3. I am going to add a what's new note and 1.3 / performance.
4. The `isin` method should be in BaseMaskedArray, and it's already there.
> gentle ping @jorisvandenbossche can you weigh in here on desired behavior

Hi, do we have a conclusion about how the `isin` method deal with `pd.NA`?
@jreback Below is latest performance report, and the result seems to be good.
```
       before           after         ratio
     [8fe3dc62]       [7763b182]
     <master>         <ENH-implement-fast-isin>
-        96.4±2ms       76.8±0.5ms     0.80  series_methods.IsInFloat64.time_isin_many_different('Float64')
-         503±1ms        376±0.7ms     0.75  series_methods.IsInLongSeriesLookUpDominates.time_isin('Int64', 1000, 'monotone_hits')
-       575±0.7ms          420±2ms     0.73  series_methods.IsInLongSeriesLookUpDominates.time_isin('Int64', 1000, 'random_hits')
-     2.92±0.05ms      2.12±0.01ms     0.73  series_methods.IsIn.time_isin('Int64')
-         736±3ms          535±2ms     0.73  series_methods.IsInLongSeriesValuesDominate.time_isin('Float64', 'monotone')
-         727±2ms        527±0.6ms     0.73  series_methods.IsInLongSeriesLookUpDominates.time_isin('Float64', 1000, 'random_hits')
-       191±0.8ms          131±1ms     0.68  series_methods.IsInLongSeriesLookUpDominates.time_isin('Int64', 5, 'monotone_hits')
-         722±2ms          488±1ms     0.68  series_methods.IsInLongSeriesLookUpDominates.time_isin('Float64', 1000, 'monotone_hits')
-         846±3ms          536±1ms     0.63  series_methods.IsInLongSeriesLookUpDominates.time_isin('Int64', 1000, 'monotone_misses')
-         723±1ms        453±0.8ms     0.63  series_methods.IsInLongSeriesLookUpDominates.time_isin('Int64', 5, 'monotone_misses')
-         948±5ms          593±2ms     0.63  series_methods.IsInLongSeriesLookUpDominates.time_isin('Float64', 1000, 'monotone_misses')
-         712±2ms        437±0.6ms     0.61  series_methods.IsInLongSeriesLookUpDominates.time_isin('Float64', 5, 'monotone_hits')
-       201±0.3ms        120±0.4ms     0.60  series_methods.IsInLongSeriesLookUpDominates.time_isin('Int64', 5, 'random_hits')
-         734±4ms        438±0.8ms     0.60  series_methods.IsInLongSeriesLookUpDominates.time_isin('Float64', 5, 'random_hits')
-         744±2ms          437±1ms     0.59  series_methods.IsInLongSeriesLookUpDominates.time_isin('Float64', 5, 'random_misses')
-         627±1ms          353±1ms     0.56  series_methods.IsInLongSeriesValuesDominate.time_isin('Int64', 'monotone')
-         836±1ms        437±0.6ms     0.52  series_methods.IsInLongSeriesLookUpDominates.time_isin('Float64', 5, 'monotone_misses')
-     2.24±0.05ms      1.07±0.01ms     0.48  series_methods.IsInBoolean.time_isin('boolean')
-       316±0.7ms        122±0.8ms     0.39  series_methods.IsInLongSeriesLookUpDominates.time_isin('Int64', 5, 'random_misses')
-      1.88±0.01s          564±8ms     0.30  series_methods.IsInLongSeriesValuesDominate.time_isin('Float64', 'random')
-      2.05±0.01s          535±2ms     0.26  series_methods.IsInLongSeriesValuesDominate.time_isin('Int64', 'random')
-         678±1ms         66.0±2ms     0.10  series_methods.IsInFloat64.time_isin_nan_values('Float64')
-         683±3ms         65.5±2ms     0.10  series_methods.IsInFloat64.time_isin_few_different('Float64')

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE INCREASED.
```
great can reduce the sample size of the benchmarks by 10x
looking good, needs tests
> looking good, needs tests

hmm this is a good point
yeah let's make sure that isin tests are parameterizing over all the added types (we might be but let's check that)
@tushushu thanks a lot for working on this! (and sorry for the slow reply on the original issue that I opened as well)

Reading through the PR comments here, I think there are two main outstanding issues:

**1\) What is the exact behaviour we want for the nullable dtypes (when involving NAs)?**

(re https://github.com/pandas-dev/pandas/pull/38379#discussion_r541315635, https://github.com/pandas-dev/pandas/pull/38379#issuecomment-751460846)

On current master, when having NA in the values, and not in the Series values, but not in the set values, you get False:

```python
In [3]: pd.Series([1, 2, pd.NA], dtype="Int64").isin([1])
Out[4]: 
0     True
1    False
2    False
dtype: bool
```

and True when the NA is present in the specified set:

```python
In [3]: pd.Series([1, 2, pd.NA], dtype="Int64").isin([1, pd.NA])
Out[4]: 
0     True
1    False
2     True
dtype: bool
```

This follows the current behaviour we have for NaNs with float dtype.

As @MarcoGorelli mentioned above, since pd.NA is unknown, it could also *propagate* (as it does for comparison operations). 
So the first example above could look like:

```python
>>> pd.Series([1, 2, pd.NA], dtype="Int64").isin([1])
0     True
1    False
2       NA
dtype: boolean
```

The question is then: what if NA is present in the values set to compare with? (the second case: `isin([1, pd.NA])`) Still propagate pd.NA, or then actually return True as we do now?

I think the question also boils a bit down to: do we see `s.isin([1, 2, ...])` as a shortcut for `(s ==1) & (s == 2) & ...` or as a shortcut for `[val in [1, 2, ...] for val in s]`? 
In tutorials, I typically explain it as a shortcut for multiple equality comparisons at once. But semantically, it could also perfectly makes sense that we say it should follow the behaviour of `in` (membership check with `__contains__`). And that's something that we recently discussed regarding NAs in https://github.com/pandas-dev/pandas/pull/37867 (where we decided that `NA in pd.array([1, 2]]) -> False` and `NA in pd.array([1, 2, NA]) -> True` (so no propagation of NA).

It might be worth checking how other data science languages that might have similar functionality deal with this issue.

Final note here: the behaviour we choose should also be explicitly tested and documented for the nullable dtypes (which is not yet the case in this PR). And eg @jbrockmendel mentioned above the case of other missing value sentinels (np.nan, pd.NaT, None) in the values set, which we should also cover in the tests. 


**2\) Adding `isin` to the ExtensionArray interface**

To be clear, I am fully on board with adding an `isin` method. But, if we do that, it needs some more work than just the addition for nullable dtypes: we need to update the documentation for EA authors in base.py (*EDIT: which I see now is already mostly done!*), we need to add base extension tests (eg in `pandas/tests/extension/base/methods.py`) and ensure they pass for the different test extension arrays. 
And we also need to think about how external EA authors can implement this using the pandas provided functionalities Currently, the `isin` algorithm is only exposed as the Series method. Maybe this is enough, but for example for `take`, we exposed the base algorithm function to the `pd.api.extensions` namespace so external authors can make use of this. We should maybe do the same for `isin`?

BTW, for me it is fine to leave this more general topic for a separate PR, to limit the scope of this PR somewhat, and special case the masked arrays in this PR (although the tests might be overlapping anyway)






let's keep this PR. very focused on the perf impl not on NA semantics
> @tushushu thanks a lot for working on this! (and sorry for the slow reply on the original issue that I opened as well)
> 
> Reading through the PR comments here, I think there are two main outstanding issues:
> 
> **1) What is the exact behaviour we want for the nullable dtypes (when involving NAs)?**
> 
> (re [#38379 (comment)](https://github.com/pandas-dev/pandas/pull/38379#discussion_r541315635), [#38379 (comment)](https://github.com/pandas-dev/pandas/pull/38379#issuecomment-751460846))
> 
> On current master, when having NA in the values, and not in the Series values, but not in the set values, you get False:
> 
> ```python
> In [3]: pd.Series([1, 2, pd.NA], dtype="Int64").isin([1])
> Out[4]: 
> 0     True
> 1    False
> 2    False
> dtype: bool
> ```
> 
> and True when the NA is present in the specified set:
......

> BTW, for me it is fine to leave this more general topic for a separate PR, to limit the scope of this PR somewhat, and special case the masked arrays in this PR (although the tests might be overlapping anyway)

Hi, @jorisvandenbossche, thanks so much for explaining the details for me. I learned a lot from your comments. Back to this topic. From the user’s perspective, the doc of pd.Series.isin says:
"
Whether elements in Series are contained in values.

Return a boolean Series showing whether each element in the Series matches an element in the passed sequence of values exactly.
"
The `isin` method should be equivalent with `[val in [1, 2, ...] for val in s]` according to the docstring. So it makes sense to make the `isin` behavior consistent with  `__contains__ ` method.
thanks @tushushu very nice!

sometimes takes a while to get it over the line, but done!
could use a follow-up with tests
Indeed, and some other follow-ups from my comment above https://github.com/pandas-dev/pandas/pull/38379 as well
Thanks @jreback @jbrockmendel @jorisvandenbossche @arw2019 , it's my first time to contribute to Pandas. Really learnt a lot from you.