PERF: fast non-unique indexing
State: closed

closes #15364 

This is essentially the same pull request as https://github.com/pandas-dev/pandas/pull/15372 but now from a proper branch.

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

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


```diff
@@            Coverage Diff             @@
##           master   #15468      +/-   ##
==========================================
+ Coverage   90.37%   90.37%   +<.01%     
==========================================
  Files         135      135              
  Lines       49473    49494      +21     
==========================================
+ Hits        44709    44730      +21     
  Misses       4764     4764
```


| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/15468?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/indexes/base.py](https://codecov.io/gh/pandas-dev/pandas/compare/e1d54074ce8448bfcc69dc08d8a800ef9ef918ff...d6bcef84227636ada9e67a10e424f2cd3dc6c744?src=pr&el=tree#diff-cGFuZGFzL2luZGV4ZXMvYmFzZS5weQ==) | `96.28% <100%> (+0.04%)` | :white_check_mark: |
| [pandas/core/common.py](https://codecov.io/gh/pandas-dev/pandas/compare/e1d54074ce8448bfcc69dc08d8a800ef9ef918ff...d6bcef84227636ada9e67a10e424f2cd3dc6c744?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvY29tbW9uLnB5) | `91.02% <ø> (-0.34%)` | :x: |
| [pandas/tseries/index.py](https://codecov.io/gh/pandas-dev/pandas/compare/e1d54074ce8448bfcc69dc08d8a800ef9ef918ff...d6bcef84227636ada9e67a10e424f2cd3dc6c744?src=pr&el=tree#diff-cGFuZGFzL3RzZXJpZXMvaW5kZXgucHk=) | `95.42% <ø> (+0.09%)` | :white_check_mark: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15468?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/15468?src=pr&el=footer). Last update [e1d5407...62cd783](https://codecov.io/gh/pandas-dev/pandas/compare/e1d54074ce8448bfcc69dc08d8a800ef9ef918ff...62cd783795986633d703cb33adba7ced3b2ad14b?el=footer&src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
Benchmark:

```python
import numpy as np
import pandas as pd
from time import time
from pandas import Index

n = 10000
r = 100


for j in range(1, 11):
    i = Index(list(range(j*n)) * r)
    slic = i[0:j*n]
    start = time()
    i.get_indexer_non_unique(slic)
    print(time() - start)
```

Elapsed time in seconds:

```
Previous | New
---------------
    0.92 | 0.18
    3.03 | 0.37
    6.25 | 0.64
   10.90 | 0.79
   17.82 | 1.00
   25.07 | 1.16
   31.49 | 1.33
   40.97 | 1.53
   51.54 | 2.03
   60.64 | 2.18
```
@Horta you are adding more and more code. I want LESS code. you are rewriting the world here.
pls add an asv.
@Horta we don't tolerate that type of language