PERF/BUG: reimplement MultiIndex.remove_unused_levels
State: closed

* Add a large random test case for remove_unused_levels that failed the
previous implementation

* Fix #16556, a performance issue with the previous implementation

* <strike>Add inplace functionality</strike>

* Always return (if not inplace) at least a view instead of the original
index

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

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

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

```diff
@@            Coverage Diff             @@
##           master   #16565      +/-   ##
==========================================
- Coverage   90.75%   40.16%   -50.6%     
==========================================
  Files         161      161              
  Lines       51073    51078       +5     
==========================================
- Hits        46350    20513   -25837     
- Misses       4723    30565   +25842
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `?` | |
| #single | `40.16% <6.25%> (-0.01%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/multi.py](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9tdWx0aS5weQ==) | `32.27% <6.25%> (-64.38%)` | :arrow_down: |
| [pandas/types/concat.py](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree#diff-cGFuZGFzL3R5cGVzL2NvbmNhdC5weQ==) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/tools/hashing.py](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree#diff-cGFuZGFzL3Rvb2xzL2hhc2hpbmcucHk=) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/parser.py](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree#diff-cGFuZGFzL3BhcnNlci5weQ==) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/io/sas/sas\_constants.py](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree#diff-cGFuZGFzL2lvL3Nhcy9zYXNfY29uc3RhbnRzLnB5) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/tslib.py](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree#diff-cGFuZGFzL3RzbGliLnB5) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/io/sas/sas7bdat.py](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree#diff-cGFuZGFzL2lvL3Nhcy9zYXM3YmRhdC5weQ==) | `0% <0%> (-90.67%)` | :arrow_down: |
| [pandas/io/sas/sas\_xport.py](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree#diff-cGFuZGFzL2lvL3Nhcy9zYXNfeHBvcnQucHk=) | `0% <0%> (-90.28%)` | :arrow_down: |
| [pandas/core/tools/numeric.py](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvdG9vbHMvbnVtZXJpYy5weQ==) | `10.44% <0%> (-89.56%)` | :arrow_down: |
| [pandas/io/json/normalize.py](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree#diff-cGFuZGFzL2lvL2pzb24vbm9ybWFsaXplLnB5) | `8.16% <0%> (-88.78%)` | :arrow_down: |
| ... and [111 more](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/16565?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/16565?src=pr&el=footer). Last update [ee8346d...dbd9ddc](https://codecov.io/gh/pandas-dev/pandas/pull/16565?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/16565?src=pr&el=h1) Report
> Merging [#16565](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/db419bfad9afb363156f23acd0810f01e1b2c9a8?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/16565/graphs/tree.svg?token=eZ4WkYLtcO&src=pr&width=650&height=150)](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #16565      +/-   ##
==========================================
- Coverage   90.75%   90.75%   -0.01%     
==========================================
  Files         161      161              
  Lines       51095    51097       +2     
==========================================
+ Hits        46370    46371       +1     
- Misses       4725     4726       +1
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `88.59% <100%> (-0.01%)` | :arrow_down: |
| #single | `40.16% <0%> (-0.01%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/multi.py](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9tdWx0aS5weQ==) | `96.65% <100%> (ø)` | :arrow_up: |
| [pandas/core/indexes/datetimes.py](https://codecov.io/gh/pandas-dev/pandas/pull/16565?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9kYXRldGltZXMucHk=) | `95.23% <0%> (-0.1%)` | :arrow_down: |

------

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

@jreback, I removed `RandomState` from the tests as you asked, but the test now occasionally fails for me when I run pytest because of the non-determinism. (The levels are no longer guaranteed to be strictly smaller in the output.) Is this actually better? I'd rather not change the inequality checks to be `<=` because I want to assert that `remove_unused_levels` is doing something. Which is best: a weaker test, a test that has a small random chance of failing, or a test that uses `RandomState`?

(Oh look, it just failed like this [in CI](https://ci.appveyor.com/project/pandas-dev/pandas/build/1.0.2402/job/k29say03umdhdbmv).)
> @jreback, I removed RandomState from the tests as you asked, but the test now occasionally fails for me when I run pytest because of the non-determinism. (The levels are no longer guaranteed to be strictly smaller in the output.) Is this actually better? I'd rather not change the inequality checks to be <= because I want to assert that remove_unused_levels is doing something. Which is best: a weaker test, a test that has a small random chance of failing, or a test that uses RandomState?

oh that's fine. wasn't really sure why you were explicity setting the random. yes *sometime* you will not remove levels based on the filter, so ok putting it back.
@rhendric lgtm. can you add an asv for this (asv/benchmarks/indexing.py) is ok. you can use your test example (just the int/int is fine). and pls post the result.
I'm new to asv; what is the result you want me to post? Console output? A file somewhere?
implement a suitable asv. then you run ``asv continuous master yourbranch -b regexttoselectit``

it should run and then post results. see http://pandas-docs.github.io/pandas-docs-travis/contributing.html#running-the-performance-test-suite
```
       before           after         ratio
     [fb47ee56]       [83bdc590]
-         185±2ms          846±2μs     0.00  indexing.MultiIndexing.time_remove_unused_levels
```
ok that's *slightly* better 😄 
thanks!