Loc enhancements
State: closed

- [x] closes #9466
- [x] tests added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

Improves performance of `IndexEngine.get_indexer_non_unique` by using binary search when:
* the index is monotonically increassing, and
* the length of the iterable loc key is sufficiently small

For now I've conservatively set the loc key size threshold to 5 items -- any keys larger than this will resort to the current full index scan. It would probably make sense to increase this threshold for larger indexes, but that might require further analysis. Any feedback appreciated.

```
     [ab9dbd64]       [b704c5bb]
     <master>         <loc-enhancements>
-         383±4ms          211±3ms     0.55  indexing.NonNumericSeriesIndexing.time_getitem_list_like('datetime', 'nonunique_monotonic_inc')
-        59.0±2ms         11.9±1ms     0.20  indexing.CategoricalIndexIndexing.time_get_indexer_list('monotonic_incr')
-      69.4±0.6ms          445±3μs     0.01  indexing.NumericSeriesIndexing.time_getitem_list_like(<class 'pandas.core.indexes.numeric.Int64Index'>, 'nonunique_monotonic_inc')
-      66.3±0.3ms          423±1μs     0.01  indexing.NumericSeriesIndexing.time_getitem_list_like(<class 'pandas.core.indexes.numeric.Float64Index'>, 'nonunique_monotonic_inc')
-      66.1±0.6ms          320±2μs     0.00  indexing.NumericSeriesIndexing.time_ix_list_like(<class 'pandas.core.indexes.numeric.Float64Index'>, 'nonunique_monotonic_inc')
-      69.2±0.4ms          330±3μs     0.00  indexing.NumericSeriesIndexing.time_ix_list_like(<class 'pandas.core.indexes.numeric.Int64Index'>, 'nonunique_monotonic_inc')
-      65.7±0.3ms          286±3μs     0.00  indexing.NumericSeriesIndexing.time_loc_list_like(<class 'pandas.core.indexes.numeric.Float64Index'>, 'nonunique_monotonic_inc')
-      69.3±0.5ms          295±2μs     0.00  indexing.NumericSeriesIndexing.time_loc_list_like(<class 'pandas.core.indexes.numeric.Int64Index'>, 'nonunique_monotonic_inc')

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

Labels:
name: Indexing
description: Related to indexing on series/frames, not to indexes themselves
name: Performance
description: Memory or execution speed performance

Comments:
Hello @rtlee9! Thanks for submitting the PR.

 - There are no PEP8 issues in the file [`asv_bench/benchmarks/indexing.py`](https://github.com/rtlee9/pandas/blob/8b704c5bb8899bea1dcff20ffae78eea6477bbed/asv_bench/benchmarks/indexing.py) !


# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/22826?src=pr&el=h1) Report
> Merging [#22826](https://codecov.io/gh/pandas-dev/pandas/pull/22826?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/3ab9dbd64b4a057eda53b841f43999fb319869e9?src=pr&el=desc) will **increase** coverage by `<.01%`.
> The diff coverage is `n/a`.

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

```diff
@@            Coverage Diff             @@
##           master   #22826      +/-   ##
==========================================
+ Coverage   92.18%   92.19%   +<.01%     
==========================================
  Files         169      169              
  Lines       50820    50827       +7     
==========================================
+ Hits        46850    46860      +10     
+ Misses       3970     3967       -3
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.61% <ø> (ø)` | :arrow_up: |
| #single | `42.37% <ø> (-0.01%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/22826?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/io/formats/format.py](https://codecov.io/gh/pandas-dev/pandas/pull/22826/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2Zvcm1hdHMvZm9ybWF0LnB5) | `98.35% <0%> (-0.01%)` | :arrow_down: |
| [pandas/core/strings.py](https://codecov.io/gh/pandas-dev/pandas/pull/22826/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvc3RyaW5ncy5weQ==) | `98.63% <0%> (ø)` | :arrow_up: |
| [pandas/core/indexes/multi.py](https://codecov.io/gh/pandas-dev/pandas/pull/22826/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9tdWx0aS5weQ==) | `95.45% <0%> (ø)` | :arrow_up: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/22826/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.2% <0%> (ø)` | :arrow_up: |
| [pandas/core/generic.py](https://codecov.io/gh/pandas-dev/pandas/pull/22826/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZ2VuZXJpYy5weQ==) | `96.67% <0%> (ø)` | :arrow_up: |
| [pandas/io/formats/style.py](https://codecov.io/gh/pandas-dev/pandas/pull/22826/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2Zvcm1hdHMvc3R5bGUucHk=) | `96.43% <0%> (ø)` | :arrow_up: |
| [pandas/core/series.py](https://codecov.io/gh/pandas-dev/pandas/pull/22826/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvc2VyaWVzLnB5) | `93.74% <0%> (ø)` | :arrow_up: |
| [pandas/core/nanops.py](https://codecov.io/gh/pandas-dev/pandas/pull/22826/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvbmFub3BzLnB5) | `95.14% <0%> (+0.01%)` | :arrow_up: |
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/pull/22826/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `94.72% <0%> (+0.02%)` | :arrow_up: |
| [pandas/io/parsers.py](https://codecov.io/gh/pandas-dev/pandas/pull/22826/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL3BhcnNlcnMucHk=) | `95.6% <0%> (+0.05%)` | :arrow_up: |
| ... and [3 more](https://codecov.io/gh/pandas-dev/pandas/pull/22826/diff?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/22826?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/22826?src=pr&el=footer). Last update [3ab9dbd...4ad3006](https://codecov.io/gh/pandas-dev/pandas/pull/22826?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

I think this would close #15364  as well (add in the whatsnew and at the top), and pls add that example if its needed

*might* close this #19464 
Thanks for the feedback. This PR only improves performance if the index is sorted, so I'll have to take a look at those issues in more detail later tonight or tomorrow.
would this also increase the speed of multi-index loc calls (on sorted multi-index dfs)?
@jreback here's an example:

```python
import pandas as pd
import numpy as np

# create a dataframe of length 10^7 with a non-unique, monotonically increasing index
N = 10 ** 7
repeat_loc = 362
df = pd.DataFrame(np.random.random((N, 1)))
df.index = list(range(N))
df.index = df.index.insert(item=df.index[repeat_loc], loc=repeat_loc)[:-1]

# benchmark performance
%timeit df.loc[repeat_loc]  # 225 µs
%timeit df.loc[[repeat_loc]]  # 633 ms using pandas 0.23.4, 354 µs using this commit
```
My understanding is that issue #15364 isn't specific to sorted indices (based on [this](https://github.com/pandas-dev/pandas/issues/15364#issuecomment-279052694) example), in which case this PR would not close that issue. Same thing for #19464 -- for this issue I confirmed by pulling down the asv benchmarks from their commits and found no difference in performance. Please let me know if I'm misunderstanding anything.
thanks @rtlee9 if you would like to have a look at those referenced issues to see if they are closable now would be great.
No problem. I took another look at those issues and I don't think they're closable -- here's why:
> My understanding is that issue #15364 isn't specific to sorted indices (based on this example), in which case this PR would not close that issue. Same thing for #19464 -- for this issue I confirmed by pulling down the asv benchmarks from their commits and found no difference in performance. Please let me know if I'm misunderstanding anything.

Please let me know if you think otherwise though.