PERF: improve MultiIndex get_loc performance
State: closed

While I was timing the MultiIndex get_loc in https://github.com/pandas-dev/pandas/pull/16324, I saw some 'quick wins' with some further profiling.

Rationale:

- big part of the time was spent in checking for a hash collision: `_check_for_collisions`. This function was a generic one for one or multiple labels. I added a slightly adapted version specialized for a single tuple
- another important factor was the hash creation with `hash_tuples`. Again, added specialized version for a single tuple.

@jreback I have some questions (will add them as comments), as this is not my specialty, but good opportunity to get more familiar with the inner guts :-)

Some timings using

```
import string
mi_large = pd.MultiIndex.from_product(
    [np.arange(1000),
     np.arange(20), list(string.ascii_letters)],
    names=['one', 'two', 'three'])
```

master:

```
In [2]: %time mi_large.get_loc((999, 19, 'E'))   # <--- first slower cold one
CPU times: user 140 ms, sys: 8 ms, total: 148 ms
Wall time: 145 ms
Out[2]: 1039978

In [3]: %time mi_large.get_loc((999, 19, 'E'))
CPU times: user 0 ns, sys: 4 ms, total: 4 ms
Wall time: 4.33 ms
Out[3]: 1039978

In [4]: %time mi_large.get_loc((999, 19, 'E'))
CPU times: user 4 ms, sys: 4 ms, total: 8 ms
Wall time: 4.18 ms
Out[4]: 1039978

In [5]: %timeit mi_large.get_loc((999, 19, 'E'))
100 loops, best of 3: 2.56 ms per loop

In [6]: %%timeit
   ...: for _ in range(1000):
   ...:     mi_large.get_loc((999, 19, 'E'))
   ...: 
1 loop, best of 3: 2.62 s per loop

```

PR:

```
In [3]: %time mi_large.get_loc((999, 19, 'E'))   # <--- first slower cold one
CPU times: user 128 ms, sys: 24 ms, total: 152 ms
Wall time: 152 ms
Out[3]: 1039978

In [4]: %time mi_large.get_loc((999, 19, 'E'))
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 716 µs
Out[4]: 1039978

In [5]: %time mi_large.get_loc((999, 19, 'E'))
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 371 µs
Out[5]: 1039978

In [6]: %timeit mi_large.get_loc((999, 19, 'E'))
1000 loops, best of 3: 189 µs per loop

In [15]: %%timeit
    ...: for _ in range(1000):
    ...:     mi_large.get_loc((999, 19, 'E'))
    ...: 
1 loop, best of 3: 188 ms per loop
```

So something between a 5x and 15x improvement (big variability between individual timings)

Labels:
name: Performance
description: Memory or execution speed performance

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

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

```diff
@@            Coverage Diff             @@
##           master   #16346      +/-   ##
==========================================
- Coverage   90.38%   90.36%   -0.02%     
==========================================
  Files         161      161              
  Lines       50916    50920       +4     
==========================================
- Hits        46021    46015       -6     
- Misses       4895     4905      +10
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `88.14% <100%> (-0.01%)` | :arrow_down: |
| #single | `40.22% <14.28%> (-0.11%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/16346?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/util/hashing.py](https://codecov.io/gh/pandas-dev/pandas/pull/16346?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvdXRpbC9oYXNoaW5nLnB5) | `90.67% <100%> (+0.32%)` | :arrow_up: |
| [pandas/core/indexes/multi.py](https://codecov.io/gh/pandas-dev/pandas/pull/16346?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9tdWx0aS5weQ==) | `96.56% <100%> (ø)` | :arrow_up: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/16346?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `25% <0%> (-58.34%)` | :arrow_down: |
| [pandas/core/common.py](https://codecov.io/gh/pandas-dev/pandas/pull/16346?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvY29tbW9uLnB5) | `90.68% <0%> (-0.35%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/16346?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.68% <0%> (-0.1%)` | :arrow_down: |

------

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

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

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

```diff
@@            Coverage Diff             @@
##           master   #16346      +/-   ##
==========================================
- Coverage   90.38%   90.37%   -0.01%     
==========================================
  Files         161      161              
  Lines       50949    50963      +14     
==========================================
+ Hits        46052    46060       +8     
- Misses       4897     4903       +6
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `88.15% <100%> (ø)` | :arrow_up: |
| #single | `40.2% <26.31%> (-0.11%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/16346?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/multi.py](https://codecov.io/gh/pandas-dev/pandas/pull/16346?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9tdWx0aS5weQ==) | `96.56% <100%> (ø)` | :arrow_up: |
| [pandas/core/util/hashing.py](https://codecov.io/gh/pandas-dev/pandas/pull/16346?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvdXRpbC9oYXNoaW5nLnB5) | `92.96% <100%> (+2.61%)` | :arrow_up: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/16346?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `25% <0%> (-58.34%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/16346?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.69% <0%> (-0.1%)` | :arrow_down: |
| [pandas/core/common.py](https://codecov.io/gh/pandas-dev/pandas/pull/16346?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvY29tbW9uLnB5) | `91.39% <0%> (+0.33%)` | :arrow_up: |

------

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

Ran the benchmarks with the latest version of this PR:

Against master:

```
$ asv continuous upstream/master HEAD -b time_multiindex
...
     before      after     ratio
  [0ea0f25b] [c29dab95]
-     2.73s   298.28ms      0.11  indexing.MultiIndexing.time_multiindex_large_get_loc_warm
SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

Against 0.19.2 (which combines slowdown/improvement of the several PRs), also gives an improvement now for the that benchmark:

```
$ asv continuous v0.19.2 HEAD -b time_multiindex
...
    before     after       ratio
  [6f525eec] [c29dab95]
-  744.29ms   334.65ms      0.45  indexing.MultiIndexing.time_multiindex_large_get_loc_warm
-  716.03ms   175.14ms      0.24  indexing.MultiIndexing.time_multiindex_large_get_loc
-  736.39ms   166.29ms      0.23  indexing.MultiIndexing.time_multiindex_get_indexer
SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```
@jorisvandenbossche lgtm. merge when ready (for 0.20.2) is good.
@jreback thanks for the review!

nice fix @jorisvandenbossche !