PERF: high memory in MI
State: closed

closes #13904

Creates an efficient MultiIndexHashTable in cython. This allows us to efficiently store a multi-index for fast indexing (``.get_loc()`` and ``.get_indexer()`), with the current tuple-based (and gil holding) use of the PyObject Hash Table.

This uses the ``pandas.tools.hashing`` routines to hash each of the 'values' of a MI to a single uint64.

So this makes MI more memory friendly and much more efficient. You get these speedups, because the creation of the hashtable is now much more efficient.

```
    before     after       ratio
  [48fc9d61] [f47131ce]
-  871.05ms   423.93ms      0.49  reindex.Reindexing.time_reindex_multiindex
-  230.31ms    72.51ms      0.31  indexing.MultiIndexing.time_is_monotonic
-  747.11ms   199.49ms      0.27  indexing.MultiIndexing.time_multiindex_get_indexer

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

This doesn't quite close the above issue yet. Still working on getting rid of all/most of the actual instantiation of array-of-tuples. but that's the next stage.


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

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


```diff
@@            Coverage Diff             @@
##           master   #15245      +/-   ##
==========================================
+ Coverage   90.34%   90.36%   +0.01%     
==========================================
  Files         135      135              
  Lines       49378    49425      +47     
==========================================
+ Hits        44613    44661      +48     
+ Misses       4765     4764       -1
```


| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/15245?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/types/cast.py](https://codecov.io/gh/pandas-dev/pandas/compare/bbb583c30bcee83ed3a2e9a3acfc83535f270632...7df6c344670c8592f78ad054664a6bb3da8e8c2a?src=pr&el=tree#diff-cGFuZGFzL3R5cGVzL2Nhc3QucHk=) | `85.42% <ø> (ø)` | :white_check_mark: |
| [pandas/io/pytables.py](https://codecov.io/gh/pandas-dev/pandas/compare/bbb583c30bcee83ed3a2e9a3acfc83535f270632...7df6c344670c8592f78ad054664a6bb3da8e8c2a?src=pr&el=tree#diff-cGFuZGFzL2lvL3B5dGFibGVzLnB5) | `93.9% <100%> (ø)` | :white_check_mark: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/compare/bbb583c30bcee83ed3a2e9a3acfc83535f270632...7df6c344670c8592f78ad054664a6bb3da8e8c2a?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.87% <100%> (ø)` | :white_check_mark: |
| [pandas/indexes/multi.py](https://codecov.io/gh/pandas-dev/pandas/compare/bbb583c30bcee83ed3a2e9a3acfc83535f270632...7df6c344670c8592f78ad054664a6bb3da8e8c2a?src=pr&el=tree#diff-cGFuZGFzL2luZGV4ZXMvbXVsdGkucHk=) | `96.72% <100%> (+0.14%)` | :white_check_mark: |
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/compare/bbb583c30bcee83ed3a2e9a3acfc83535f270632...7df6c344670c8592f78ad054664a6bb3da8e8c2a?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `94.47% <100%> (-0.01%)` | :x: |
| [pandas/tools/hashing.py](https://codecov.io/gh/pandas-dev/pandas/compare/bbb583c30bcee83ed3a2e9a3acfc83535f270632...7df6c344670c8592f78ad054664a6bb3da8e8c2a?src=pr&el=tree#diff-cGFuZGFzL3Rvb2xzL2hhc2hpbmcucHk=) | `99.01% <100%> (ø)` | :white_check_mark: |
| [pandas/indexes/base.py](https://codecov.io/gh/pandas-dev/pandas/compare/bbb583c30bcee83ed3a2e9a3acfc83535f270632...7df6c344670c8592f78ad054664a6bb3da8e8c2a?src=pr&el=tree#diff-cGFuZGFzL2luZGV4ZXMvYmFzZS5weQ==) | `96.23% <100%> (ø)` | :white_check_mark: |
| [pandas/tseries/index.py](https://codecov.io/gh/pandas-dev/pandas/compare/bbb583c30bcee83ed3a2e9a3acfc83535f270632...7df6c344670c8592f78ad054664a6bb3da8e8c2a?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/15245?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/15245?src=pr&el=footer). Last update [bbb583c...7df6c34](https://codecov.io/gh/pandas-dev/pandas/compare/bbb583c30bcee83ed3a2e9a3acfc83535f270632...7df6c344670c8592f78ad054664a6bb3da8e8c2a?src=pr&el=footer&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
cc @chris-b1 @jorisvandenbossche @wesm 
ok, updated. had an insiduous condition in ``MultiIndex.equals`` with NaT only tuples. This was a latent bug.
ok this is all set. any more comments

@wesm @jorisvandenbossche 
@wesm @jorisvandenbossche any comments?
Will take a closer look at this today if possible
@chris-b1 suggestion. not bad (this is vs changed repr, NOT master)
```
    before     after       ratio
  [dab01796] [403a0864]
-  256.41ms   200.36ms      0.78  indexing.MultiIndexing.time_multiindex_string_get_loc
-  432.21ms   246.25ms      0.57  reindex.Reindexing.time_reindex_multiindex

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```
and vs. master
```
    before     after       ratio
  [e8840725] [403a0864]
-  228.14ms    74.52ms      0.33  indexing.MultiIndexing.time_is_monotonic
-  867.72ms   240.69ms      0.28  reindex.Reindexing.time_reindex_multiindex
-  740.27ms   197.37ms      0.27  indexing.MultiIndexing.time_multiindex_string_get_loc
-  726.79ms   175.35ms      0.24  indexing.MultiIndexing.time_multiindex_get_indexer

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```
@jorisvandenbossche fixed up. ``__contains__`` was tested much, so behavior wasn't nailed down.
They already compare equal, also on your PR branch. So nothing to change
(only the test)

(github is doing annoying, and I cannot find this thread in the web
interface, but the above is about the `midx.equals(Index(midx.values))`)
We have this in 0.19.2 / master
seems odd
```
In [1]:         midx = MultiIndex.from_product([['A', 'B'], [1, 2]])
   ...:         df = DataFrame(np.random.randn(4, 4), columns=midx)
   ...: 

In [2]: 'A' in df
Out[2]: True

In [3]: ('A', ) in df
Out[3]: True

In [4]: del df['A']

In [5]: 'A' in df
Out[5]: True

In [6]: ('A', ) in df
Out[6]: False
```
In [5] seems certainly like a bug. Possibly because it's looking in the full level and not the actually used one?
all changes pushed. WIll merge on pass tomorrow sometime unless any more comments.
neat article about hash collisions: https://medium.com/@robertgrosse/generating-64-bit-hash-collisions-to-dos-python-5b21404a5306#.wi6ivpqtv (more about cryptographic hashing, but still neat)