REF: codes-based MultiIndex engine

closes #18519
closes #18818
closes #18520
closes #18485
closes  #15994
closes #19086

- [x] tests added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

This PR provides a cleaner and more robust ``MultiIndex`` engine.

asv benchmarks
```
       before           after         ratio
     [93033151]       [6e1ecec1]
+     4.26±0.03ms      20.8±0.08ms     4.87  multiindex_object.GetLoc.time_med_get_loc_warm
+     4.28±0.02μs       19.6±0.1μs     4.58  multiindex_object.GetLoc.time_string_get_loc
+     4.12±0.02ms      18.1±0.09ms     4.40  multiindex_object.GetLoc.time_small_get_loc_warm
+      4.55±0.1μs       18.8±0.3μs     4.13  multiindex_object.GetLoc.time_med_get_loc
-         178±4ms        148±0.7ms     0.83  multiindex_object.GetLoc.time_large_get_loc
-         163±1ms        120±0.5ms     0.73  multiindex_object.Integer.time_get_indexer
-       336±0.6ms          167±1ms     0.50  multiindex_object.GetLoc.time_large_get_loc_warm

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

... clearly show that the engine increases performance for large indexes, and significantly decreases performance for ``get_loc`` on small/medium indexes. For reference, on the ``small`` test case (10 elements), 16 μs. are lost on each ``get_loc`` call, while on the ``large`` test case (1 million elements),  146 μs. are gained on each ``get_loc`` call. I think the tradeoff is acceptable, also considering that with this approach, any improvement to flat indexes automatically transfers to ``MultiIndex``. But most importantly, I think we have no other options to fix several annoying open issues (and more bugs - I'm sure - which were never reported) about incoherence between flat indexes and ``MultiIndex``.

Notice that moving the engine into ``index.pyx`` is problematic because cython does not support multiple inheritance. Anyway, trying to cythonize a couple of methods brought no gain at all (as the overhead is mostly due to the multiple ``get_loc(val)`` calls on the different levels).
  
Hello @toobaz! Thanks for updating the PR.







Cheers ! There are no PEP8 issues in this Pull Request. :beers: 

##### Comment last updated on January 27, 2018 at 18:16 Hours UTC # [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/19074?src=pr&el=h1) Report
> Merging [#19074](https://codecov.io/gh/pandas-dev/pandas/pull/19074?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/24d95098789c8685e7c0ce6a57982d0372ffc3e0?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/19074/graphs/tree.svg?height=150&width=650&token=eZ4WkYLtcO&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/19074?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #19074      +/-   ##
==========================================
- Coverage   91.63%   91.62%   -0.01%     
==========================================
  Files         150      150              
  Lines       48726    48722       -4     
==========================================
- Hits        44648    44640       -8     
- Misses       4078     4082       +4
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `89.99% <100%> (-0.01%)` | :arrow_down: |
| #single | `41.75% <65.21%> (+0.01%)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/19074?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/multi.py](https://codecov.io/gh/pandas-dev/pandas/pull/19074/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9tdWx0aS5weQ==) | `95.14% <100%> (-1.09%)` | :arrow_down: |
| [pandas/util/testing.py](https://codecov.io/gh/pandas-dev/pandas/pull/19074/diff?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvdGVzdGluZy5weQ==) | `83.64% <0%> (-0.21%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/19074/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.57% <0%> (-0.06%)` | :arrow_down: |
| [pandas/plotting/\_converter.py](https://codecov.io/gh/pandas-dev/pandas/pull/19074/diff?src=pr&el=tree#diff-cGFuZGFzL3Bsb3R0aW5nL19jb252ZXJ0ZXIucHk=) | `66.95% <0%> (+1.73%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/19074?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/19074?src=pr&el=footer). Last update [24d9509...468bb08](https://codecov.io/gh/pandas-dev/pandas/pull/19074?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
 > .. clearly show that the engine increases performance for large indexes, and significantly decreases performance for get_loc on small/medium indexes. For reference, on the small test case (10 elements), 16 μs. are lost on each get_loc call, while on the large test case (1 million elements), 146 μs. are gained on each get_loc call. I think the tradeoff is acceptable, also considering that 

This is exactly why we changed this previously. Please look at the previous issue and how @jorisvandenbossche made the tradeoff chart. 

This needs a full asv run as well as significant code cleanup. But first if you can narrow the small indexing perf then that would be helpful. > This is exactly why we changed this previously. Please look at the previous issue

What do you mean by "this"? I don't think pandas ever had a ``MultiIndex`` engine similar to the one I am proposing. I saw #16319, but there we were talking about [a ~x1000](https://github.com/pandas-dev/pandas/issues/16319#issuecomment-300533260), not ~x5, performance impact.

> and how @jorisvandenbossche made the tradeoff chart.

pointer?

> But first if you can narrow the small indexing perf then that would be helpful.

I guess so. If you have any ideas, great. > pointer?


https://github.com/pandas-dev/pandas/pull/16324#issuecomment-300806285 @toobaz what I want to see since this is a regression on perf, how much it is relative to where we are. yes these seem like tiny numbers, but so did the other ones. > #16324 (comment)

Thanks, had missed that! So here is a comparison of the three engines:
http://nbviewer.jupyter.org/gist/toobaz/de76b3fbc6745266fd4c2a6e428bd2a4

And here is the figure equivalent to that in https://github.com/pandas-dev/pandas/pull/16324#issuecomment-300806285 :

![perf_warm_w_10](https://user-images.githubusercontent.com/1224492/34572291-504bb40e-f171-11e7-9253-f2c4e372471e.png)
 ok from a real world perspective then for < 1000 is slower, but how much in total time? > ok from a real world perspective then for < 1000 is slower, but how much in total time?

Assuming you are asking for the difference between UInt and Object in the "warm combination" case (dashed lines), we are in the order of 100 μs:

```
9        0.000178
100      0.000147
900      0.000059
10000   -0.000757
```

(this is tested with more iterations than the figure above, see the [updated notebook](https://gist.github.com/toobaz/de76b3fbc6745266fd4c2a6e428bd2a4)) @jbrockmendel's suggestion to cythonize did help reducing a bit the performance decrease:
```
       before           after         ratio
     [93033151]       [b3ba47c6]
+     3.97±0.02μs      17.4±0.04μs     4.39  multiindex_object.GetLoc.time_med_get_loc
+     4.13±0.02ms      18.0±0.08ms     4.36  multiindex_object.GetLoc.time_small_get_loc_warm
+     4.26±0.03μs       17.6±0.1μs     4.13  multiindex_object.GetLoc.time_string_get_loc
+     4.32±0.02ms      16.6±0.05ms     3.84  multiindex_object.GetLoc.time_med_get_loc_warm
-         181±5ms        153±0.8ms     0.84  multiindex_object.GetLoc.time_large_get_loc
-         170±2ms        123±0.5ms     0.73  multiindex_object.Integer.time_get_indexer
-       321±0.8ms        169±0.6ms     0.53  multiindex_object.GetLoc.time_large_get_loc_warm

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
``` Waiting to rebase on #19054 before pushing again New asv run shows some small additional improvement:
```
       before           after         ratio
     [9d8dbefb]       [b152cb80]
+     4.71±0.07μs       19.9±0.5μs     4.21  multiindex_object.GetLoc.time_string_get_loc
+     4.69±0.05ms       18.2±0.2ms     3.88  multiindex_object.GetLoc.time_small_get_loc_warm
+      5.80±0.9μs       19.8±0.1μs     3.41  multiindex_object.GetLoc.time_med_get_loc
+      5.86±0.5ms       18.7±0.4ms     3.19  multiindex_object.GetLoc.time_med_get_loc_warm
+      12.8±0.1ms      18.2±0.05ms     1.42  multiindex_object.Values.time_datetime_level_values_copy
-         464±8μs          421±5μs     0.91  multiindex_object.Duplicates.time_remove_unused_levels
-         201±7ms        165±0.9ms     0.82  multiindex_object.GetLoc.time_large_get_loc
-         197±4ms        132±0.4ms     0.67  multiindex_object.Integer.time_get_indexer
-        426±20ms          182±2ms     0.43  multiindex_object.GetLoc.time_large_get_loc_warm

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
``` @jreback  ping @toobaz Do you think there is further potential in optimizing get_loc to reduce the performance degradation?

Performance is important, but correct and consistent (for different MI sizes) behaviour as well. And it seems this change improves a lot on that aspect (didn't look in detail at the the actual diff). > @toobaz Do you think there is further potential in optimizing get_loc to reduce the performance degradation?
> 
> Performance is important, but correct and consistent (for different MI sizes) behaviour as well. And it seems this change improves a lot on that aspect (didn't look in detail at the the actual diff).

Performance increase for large index is in absolute value way bigger than the performance loss on small ones, so even just performance-wise, I think this PR is an improvement. pandas (and numpy, by the way) users (should) expect good performance for big stuff and overhead for small stuff.

Then clearly if there was a way to reduce overhead, it would be worth doing. But the only new code which does take some cycles (as confirmed by profiling, before cythonizing) is ``codes_to_ints``, where I don't see room of improvement. Real improvement could come from having ``Index.get_loc`` not recur to ``Index.get_indexer``, but 1) I'm not sure 2) it could vary from class to class 3) anyway, could and should be done separately > Real improvement could come from having Index.get_loc

According to my profiling, the individual `get_loc` calls on the levels only account for around 20% of the time, so it will only give modest improvements for this case (but of course, for indexing in general that would certainly be welcome!)

Anyhow, as I said, I agree this is the other improvements here make it worth it! > if something is a helper method that is only used within the class, make this clear by using a _... name

Yeah, and the same holds for ``base`` vs. ``_base``... I think these simple conventions make code more readable than tons of docstrings nobody will read (not talking about the API, obviously). can you re-run and update the benchmarks at the very top of this PR (after you make changes). New changes reduced the overhead further...
```
       before           after         ratio
     [8acdf801]       [bbae39c8]
+      4.41±0.1ms       15.4±0.1ms     3.49  multiindex_object.GetLoc.time_small_get_loc_warm
+     4.73±0.06ms       15.1±0.5ms     3.19  multiindex_object.GetLoc.time_med_get_loc_warm
+     4.45±0.07μs       13.9±0.2μs     3.13  multiindex_object.GetLoc.time_string_get_loc
+     4.75±0.03μs      14.8±0.05μs     3.12  multiindex_object.GetLoc.time_med_get_loc
-         168±1ms          148±1ms     0.89  multiindex_object.Integer.time_get_indexer
-         183±6ms          156±3ms     0.85  multiindex_object.GetLoc.time_large_get_loc
-         349±5ms          169±2ms     0.49  multiindex_object.GetLoc.time_large_get_loc_warm

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

... but trying to ``cpdef`` any of the methods of the cython mother class (or ``cdef _extract_level_codes``, which is only used internally) as suggested by @jbrockmendel results in

``` python
Traceback (most recent call last):
  File "/usr/lib/python3/dist-packages/_pytest/config.py", line 379, in _importconftest
    mod = conftestpath.pyimport()
  File "/usr/lib/python3/dist-packages/py/_path/local.py", line 662, in pyimport
    __import__(modname)
  File "/home/nobackup/repo/pandas/pandas/__init__.py", line 42, in <module>
    from pandas.core.api import *
  File "/home/nobackup/repo/pandas/pandas/core/api.py", line 10, in <module>
    from pandas.core.groupby import Grouper
  File "/home/nobackup/repo/pandas/pandas/core/groupby.py", line 48, in <module>
    from pandas.core.index import (Index, MultiIndex,
  File "/home/nobackup/repo/pandas/pandas/core/index.py", line 2, in <module>
    from pandas.core.indexes.api import *
  File "/home/nobackup/repo/pandas/pandas/core/indexes/api.py", line 8, in <module>
    from pandas.core.indexes.multi import MultiIndex  # noqa
  File "/home/nobackup/repo/pandas/pandas/core/indexes/multi.py", line 54, in <module>
    libindex.UInt64Engine):
TypeError: multiple bases have instance lay-out conflict
ERROR: could not load /home/nobackup/repo/pandas/pandas/conftest.py

``` I solved the conflicts and pushed again.

I guess all suggested performance improvements have been applied... if new ones come out after this is merged, I'll be happy to take care of them. @jreback ping i don’t which issue is missing
maybe in api changes > i don’t which issue is missing

[Now you do](https://github.com/pandas-dev/pandas/pull/19074#discussion_r161219578)

> maybe in api changes

If there was an API change of a bug fix I wouldn't be asking you where to list it.


 so the main issue number is a perf entry (note that its for larger MI & a small regression on smaller) > so the main issue number is a perf entry (note that its for larger MI & a small regression on smaller)

Added, ping if you can rebase and ping on green, ok to merge. @jreback rebased, ping @toobaz Great work! this is failing the 32 bit builds
https://travis-ci.org/MacPython/pandas-wheels/jobs/334527944


if u can issue a follow up to fix
not easy to test this