PERF: improve get_loc on unsorted, non-unique indexes
State: closed

- [x] closes #19478
- [x] tests passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

asv run:
```
     [bd4332f4]       [9ac7be34]
-         475±5μs          422±7μs     0.89  multiindex_object.Duplicates.time_remove_unused_levels
-      15.4±0.3ms       13.5±0.2ms     0.88  multiindex_object.GetLoc.time_small_get_loc_warm
-         197±5ns          171±2ns     0.87  index_object.Datetime.time_is_dates_only
-      8.68±0.3μs       6.88±0.1μs     0.79  index_object.Float64IndexMethod.time_get_loc
-          15.4μs       12.0±0.2μs     0.78  index_object.Indexing.time_get_loc_sorted('Float')
-         283±9μs          215±2μs     0.76  multiindex_object.Values.time_datetime_level_values_sliced
-          15.0μs           11.1μs     0.74  index_object.Indexing.time_get_loc('Float')
-     7.38±0.04μs      5.03±0.05μs     0.68  index_object.Indexing.time_get_loc_sorted('Int')
-     7.15±0.04μs      4.58±0.04μs     0.64  index_object.Indexing.time_get_loc('Int')
-       121±0.9ms           1.62ms     0.01  index_object.Indexing.time_get_loc_non_unique_sorted('Float')
-           136ms           1.51ms     0.01  index_object.Indexing.time_get_loc_non_unique('Float')
-         166±1ms      1.29±0.03ms     0.01  index_object.Indexing.time_get_loc_non_unique_sorted('Int')
-       175±0.9ms      1.29±0.01ms     0.01  index_object.Indexing.time_get_loc_non_unique('Int')

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:
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/19539?src=pr&el=h1) Report
> Merging [#19539](https://codecov.io/gh/pandas-dev/pandas/pull/19539?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/bd4332f4bff135d4119291f66e98f76cc5f9a80e?src=pr&el=desc) will **not change** coverage.
> The diff coverage is `n/a`.

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

```diff
@@           Coverage Diff           @@
##           master   #19539   +/-   ##
=======================================
  Coverage   91.81%   91.81%           
=======================================
  Files         153      153           
  Lines       49481    49481           
=======================================
  Hits        45430    45430           
  Misses       4051     4051
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.21% <ø> (ø)` | :arrow_up: |
| #single | `41.85% <ø> (ø)` | :arrow_up: |


------

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

seems to be failing 2.7 on windows and a gazillion warnings

```
 C:\projects\pandas\pandas\core\indexes\base.py:1726: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
    return getitem(key)
  C:\projects\pandas\pandas\core\indexes\base.py:1726: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
    return getitem(key)
  C:\projects\pandas\pandas\core\indexes\base.py:1726: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
    return getitem(key)
  C:\projects\pandas\pandas\core\indexes\base.py:1726: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
    return getitem(key)
  C:\projects\pandas\pandas\core\indexes\base.py:1726: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
    return getitem(key)
```
also can you see if this closes other issues as well (a couple of refernces in OP)
@jreback : fixed (wasn't that hard!), ping.

(I guess it shouldn't harm to include in 0.23.0)
@toobaz lgtm. can you just update the asv's as the top with latest code 
> can you just update the asv's as the top with latest code

Done.
thanks @toobaz