PERF/REF: improve performance of Series.searchsorted, PandasArray.searchsorted, collect functionality
State: closed

- [x] closes #14565
- [x] ASV's added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

Numpy's searchsorted doesn't like being given values to search for that aren't of the same type as the array being searched. By ensuring that the input value has the same dtype as the underlying array, the search is sped up significantly.

```python
>>> n = 1_000_000
>>> s = pd.Series(([1] * n + [2] * n + [3] * n), dtype='int8')
>>> %timeit s.searchsorted(1)  # python int
15.2 ms  # master
9.75 µs  # this PR
```

## ASV results

```
      before           after         ratio
     [b9754556]       [fd6c117b]
-        93.9±9μs         10.9±0μs     0.12  series_methods.SearchSorted.time_searchsorted('int64')
-        95.4±0μs         10.9±2μs     0.11  series_methods.SearchSorted.time_searchsorted('float64')
-        140±10μs       10.7±0.4μs     0.08  series_methods.SearchSorted.time_searchsorted('str')
-      1.34±0.1ms       10.8±0.3μs     0.01  series_methods.SearchSorted.time_searchsorted('uint16')
-     1.52±0.03ms         10.7±0μs     0.01  series_methods.SearchSorted.time_searchsorted('int16')
-      1.79±0.1ms         12.5±2μs     0.01  series_methods.SearchSorted.time_searchsorted('int8')
-      1.46±0.1ms       10.2±0.8μs     0.01  series_methods.SearchSorted.time_searchsorted('int32')
-        1.46±0ms         9.54±1μs     0.01  series_methods.SearchSorted.time_searchsorted('uint8')
-      1.46±0.1ms         9.38±2μs     0.01  series_methods.SearchSorted.time_searchsorted('float32')
-      1.71±0.2ms       10.4±0.9μs     0.01  series_methods.SearchSorted.time_searchsorted('uint32')
-      1.82±0.1ms         10.7±0μs     0.01  series_methods.SearchSorted.time_searchsorted('uint64')
-     2.14±0.04ms         10.7±0μs     0.00  series_methods.SearchSorted.time_searchsorted('float16')

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

The improventents are largest when the dtype  isn't int64 or float64, but for those cases the improvement is also significant (10x).


Labels:
name: Performance
description: Memory or execution speed performance
name: Algos
description: Non-arithmetic algos: value_counts, factorize, sorting, isin, clip, shift, diff

Comments:
The appveyor failure is a resource error, so unrelated to this PR.
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/22034?src=pr&el=h1) Report
> Merging [#22034](https://codecov.io/gh/pandas-dev/pandas/pull/22034?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/5557e3627df67211f5b6406d07995dccb02196f9?src=pr&el=desc) will **increase** coverage by `<.01%`.
> The diff coverage is `96.29%`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/22034/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/22034?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #22034      +/-   ##
==========================================
+ Coverage   91.73%   91.73%   +<.01%     
==========================================
  Files         173      173              
  Lines       52848    52869      +21     
==========================================
+ Hits        48482    48502      +20     
- Misses       4366     4367       +1
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.3% <96.29%> (ø)` | :arrow_up: |
| #single | `41.72% <66.66%> (+0.01%)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/22034?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/arrays/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/22034/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2Jhc2UucHk=) | `98.25% <ø> (ø)` | :arrow_up: |
| [pandas/core/series.py](https://codecov.io/gh/pandas-dev/pandas/pull/22034/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvc2VyaWVzLnB5) | `93.68% <100%> (-0.02%)` | :arrow_down: |
| [pandas/core/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/22034/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYmFzZS5weQ==) | `97.76% <100%> (ø)` | :arrow_up: |
| [pandas/core/arrays/numpy\_.py](https://codecov.io/gh/pandas-dev/pandas/pull/22034/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL251bXB5Xy5weQ==) | `93.66% <100%> (+0.14%)` | :arrow_up: |
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/pull/22034/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `94.77% <94.73%> (-0.01%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/22034?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/22034?src=pr&el=footer). Last update [5557e36...bcbe226](https://codecov.io/gh/pandas-dev/pandas/pull/22034?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

green.
Hello @topper-123! Thanks for updating the PR.















Cheers ! There are no PEP8 issues in this Pull Request. :beers: 

##### Comment last updated on February 23, 2019 at 20:27 Hours UTC
EDIT: New implementation before I go.

A few issues:
* I've decided *not* to downcast float64 to float32/16. Downcasting may lose precision and therefore give wrong results
* Tests should be made for when value is out of bounds for integer dtype
* where do I put ASVs for Index.searchsorted?

Tests (Series only atm) are still good, see below. I don't expect ASVs for Int64 and Float64 to show any meaningful change, while UInt64Index should get a nice improvement.

```
      before           after         ratio
     [9c118668]       [67efbda4]
-        77.7±1μs         24.4±1μs     0.31  series_methods.SearchSorted.time_searchsorted('int64')
-        80.1±6μs       10.7±0.8μs     0.13  series_methods.SearchSorted.time_searchsorted('float64')
-         107±2μs         9.94±1μs     0.09  series_methods.SearchSorted.time_searchsorted('str')
-      1.56±0.3ms         26.8±2μs     0.02  series_methods.SearchSorted.time_searchsorted('int32')
-        1.42±0ms         23.2±2μs     0.02  series_methods.SearchSorted.time_searchsorted('uint16')
-      1.45±0.1ms         23.2±1μs     0.02  series_methods.SearchSorted.time_searchsorted('uint32')
-     1.42±0.03ms         22.0±0μs     0.02  series_methods.SearchSorted.time_searchsorted('int16')
-        1.56±0ms       22.1±0.4μs     0.01  series_methods.SearchSorted.time_searchsorted('uint8')
-     1.71±0.09ms         22.0±1μs     0.01  series_methods.SearchSorted.time_searchsorted('uint64')
-        1.95±0ms         18.9±2μs     0.01  series_methods.SearchSorted.time_searchsorted('int8')
-      1.34±0.1ms       9.94±0.7μs     0.01  series_methods.SearchSorted.time_searchsorted('float32')
-        2.08±0ms         9.38±0μs     0.00  series_methods.SearchSorted.time_searchsorted('float16')

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

I'll get back to this in about two week, probably. Comments obviously welcome until then.

In the latest commit, Im automatically casting ints and uints to the correct dtype, bur also do some overflow checks, so we're not downcasting out-of-bound values. I think this is a good solution and is very fast.

But floats downcasting is more confusing, i.e. if the input in float64 and the array is float32 or float16, should we downcast?

Some options for floats:
1. Throw an error if input is not dtype compatible with array.
2. Silently force casting of input to the dtype of the array (fastest, but risks of wrong results?)
3. Keep current behaviour, i.e. just delegate decision to numpy (i.e. is slow, because we force upcasting of array for float32 and float16)
4. Keep current behaviour, but emit a warning if input and array are not dtype compatible (slow, but allows the user himself to fix the speed problem. Can be annoying with warnings)
5. Keep current behaviour, but add an boolean option to pd.options to emit a warning if input and array are not dtype compatible + add suitable explanation about the issue to the searchsorted doc string (Like option 4, but  avoids annoying with warnings)

I'm favoring option 4 or 5, but edge toward 5.

The reason is that in many use cases performance is really not the user's prime concern, and they just want things to work with minimal effort. Other users (beginners) may not understand types that well. So emitting dtype warnings would annoy/confuse such users. So, IMO option 5 would be best.

don’t do anything for floats
ints are worth it because we commonly have non int64 and you do search on them

for floats you very rarely search and all of the above are too complex 
I've made a new version where I've made a common implementation for Series and Index.

I've skipped making changes for floats as suggested. That means searching in float16/32 Series with a float64 value is still slow, and we don't achieve the speed up for float16 and float32 that is shown in the table above. Other speedups are still there.

Ints:
I've dropped making it an error, when the value is outside of bounds of the array dtype. Instead I delegate to numpy is that case. This is most consistent IMO as we maintain an unchanged API, which is good. 
The "cost" is that searching for ints outside of bounds is slow, but that's ok IMO.

As the API is unchanged, I've not made any more tests. Series|Index.searchsorted is already tested in various places.

Is this ok?

Implementation on common for series and index, speed is much faster and it API-compatible with previous implementation...
@topper-123 if you would update
needs a rebase
@topper-123 can you comment on the added code
@topper-123 happy to have this if it can be done in a reasonbale way. pls update or close.
I'll look into in the coming week, maybe the weekend.
@topper-123 if you have time to rebase this and address comment
I've now collected the searchsorted functionality for Index, Series and PandasArray, making a common searchsorted implementation.

The Speed improvements are now also for PandasArray:

```python
>>> n = 100_000
>>> arr = pd.array([1]*n + [2]*n +[3]*n, dtype=np.int8)
>>> %timeit arr.searchsorted(2)
5.57 ms ± 332 µs per loop  # master
21.4 µs ± 3.55 µs per loop  # this PR
>>> ser = pd.Series(arr)
>>> %timeit ser.searchsorted(2)
1.52 ms ± 9.33 µs per loop  # master
21 µs ± 2.81 µs  # this PR
```

I still need to make the ASV's for PandasArray, will make it later today.

I've moved the searchsorted function to algorithms.py.

Where do PandasArray ASV's be placed? Can't find a logical location and having a pandas_array.py seems perhaps excessive for something that in most cases is a thin wrapper around numpy.array.

pls merge master
The azure bugs*seem* unrelated to this PR, as I don't touch I/O or the html repr:

```
··· frame_methods.Repr.time_html_repr_trunc_mi                  failed
2019-02-03T09:40:31.5401600Z [ 11.57%] ···· Traceback (most recent call last):
2019-02-03T09:40:31.5401919Z                  File "/home/vsts/miniconda3/envs/pandas-dev/lib/python3.7/site-packages/asv/benchmark.py", line 1039, in main_run_server
2019-02-03T09:40:31.5402018Z                    main_run(run_args)
2019-02-03T09:40:31.5402334Z                  File "/home/vsts/miniconda3/envs/pandas-dev/lib/python3.7/site-packages/asv/benchmark.py", line 913, in main_run
2019-02-03T09:40:31.5402415Z                    result = benchmark.do_run()
2019-02-03T09:40:31.5402718Z                  File "/home/vsts/miniconda3/envs/pandas-dev/lib/python3.7/site-packages/asv/benchmark.py", line 412, in do_run
2019-02-03T09:40:31.5402779Z                    return self.run(*self._current_params)
2019-02-03T09:40:31.5403097Z                  File "/home/vsts/miniconda3/envs/pandas-dev/lib/python3.7/site-packages/asv/benchmark.py", line 506, in run
2019-02-03T09:40:31.5403275Z                    min_run_count=self.min_run_count)
2019-02-03T09:40:31.5403615Z                  File "/home/vsts/miniconda3/envs/pandas-dev/lib/python3.7/site-packages/asv/benchmark.py", line 569, in benchmark_timing
2019-02-03T09:40:31.5403707Z                    timing = timer.timeit(number)
2019-02-03T09:40:31.5403992Z                  File "/home/vsts/miniconda3/envs/pandas-dev/lib/python3.7/timeit.py", line 176, in timeit
2019-02-03T09:40:31.5404050Z                    timing = self.inner(it, self.timer)
2019-02-03T09:40:31.5404485Z                  File "<timeit-src>", line 6, in inner
2019-02-03T09:40:31.5404530Z                  File "/home/vsts/work/1/s/asv_bench/benchmarks/frame_methods.py", line 226, in time_html_repr_trunc_mi
2019-02-03T09:40:31.5404570Z                    self.df3._repr_html_()
2019-02-03T09:40:31.5404627Z                  File "/home/vsts/work/1/s/pandas/core/frame.py", line 651, in _repr_html_
2019-02-03T09:40:31.5404671Z                    import IPython
2019-02-03T09:40:31.5404898Z                  File "/home/vsts/miniconda3/envs/pandas-dev/lib/python3.7/site-packages/IPython/__init__.py", line 55, in <module>
2019-02-03T09:40:31.5404967Z                    from .terminal.embed import embed
2019-02-03T09:40:31.5405198Z                  File "/home/vsts/miniconda3/envs/pandas-dev/lib/python3.7/site-packages/IPython/terminal/embed.py", line 16, in <module>
2019-02-03T09:40:31.5405245Z                    from IPython.terminal.interactiveshell import TerminalInteractiveShell
2019-02-03T09:40:31.5405502Z                  File "/home/vsts/miniconda3/envs/pandas-dev/lib/python3.7/site-packages/IPython/terminal/interactiveshell.py", line 81, in <module>
2019-02-03T09:40:31.5405705Z                    if not _stream or not hasattr(_stream, 'isatty') or not _stream.isatty():
2019-02-03T09:40:31.5405746Z                ValueError: I/O operation on closed file
2019-02-03T09:40:31.5405794Z 
```

I don't think this  is related to this PR.
Comments addressed.
thanks @topper-123