Performance of get_loc on non-unique MultiIndex
- [x] tests passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

The second commit is related only in the sense that the docs mentioned a ``PerformanceWarning`` due to (non-)sorting, while it was actually due to (non-)uniqueness.
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/19464?src=pr&el=h1) Report
> Merging [#19464](https://codecov.io/gh/pandas-dev/pandas/pull/19464?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/7725fa028aad7a8817c10b7fe67a34cf7fe8ee5c?src=pr&el=desc) will **decrease** coverage by `0.23%`.
> The diff coverage is `100%`.

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

```diff
@@            Coverage Diff             @@
##           master   #19464      +/-   ##
==========================================
- Coverage   92.06%   91.82%   -0.24%     
==========================================
  Files         169      153      -16     
  Lines       50694    49493    -1201     
==========================================
- Hits        46671    45448    -1223     
- Misses       4023     4045      +22
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.22% <100%> (-0.25%)` | :arrow_down: |
| #single | `41.85% <80%> (-0.47%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/19464?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/multi.py](https://codecov.io/gh/pandas-dev/pandas/pull/19464/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9tdWx0aS5weQ==) | `95.08% <100%> (-0.17%)` | :arrow_down: |
| [pandas/util/\_doctools.py](https://codecov.io/gh/pandas-dev/pandas/pull/19464/diff?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvX2RvY3Rvb2xzLnB5) | `0% <0%> (-12.88%)` | :arrow_down: |
| [pandas/core/reshape/util.py](https://codecov.io/gh/pandas-dev/pandas/pull/19464/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvcmVzaGFwZS91dGlsLnB5) | `90.32% <0%> (-9.68%)` | :arrow_down: |
| [pandas/util/\_decorators.py](https://codecov.io/gh/pandas-dev/pandas/pull/19464/diff?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvX2RlY29yYXRvcnMucHk=) | `82.25% <0%> (-9.09%)` | :arrow_down: |
| [pandas/core/common.py](https://codecov.io/gh/pandas-dev/pandas/pull/19464/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvY29tbW9uLnB5) | `92.01% <0%> (-5.33%)` | :arrow_down: |
| [pandas/core/arrays/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/19464/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2Jhc2UucHk=) | `83.95% <0%> (-3.91%)` | :arrow_down: |
| [pandas/io/formats/printing.py](https://codecov.io/gh/pandas-dev/pandas/pull/19464/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2Zvcm1hdHMvcHJpbnRpbmcucHk=) | `89.38% <0%> (-3.71%)` | :arrow_down: |
| [pandas/core/groupby/groupby.py](https://codecov.io/gh/pandas-dev/pandas/pull/19464/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZ3JvdXBieS9ncm91cGJ5LnB5) | `92.66% <0%> (-3.5%)` | :arrow_down: |
| [pandas/core/dtypes/missing.py](https://codecov.io/gh/pandas-dev/pandas/pull/19464/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZHR5cGVzL21pc3NpbmcucHk=) | `91.95% <0%> (-1.62%)` | :arrow_down: |
| [pandas/core/reshape/tile.py](https://codecov.io/gh/pandas-dev/pandas/pull/19464/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvcmVzaGFwZS90aWxlLnB5) | `93.37% <0%> (-1.37%)` | :arrow_down: |
| ... and [100 more](https://codecov.io/gh/pandas-dev/pandas/pull/19464/diff?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/19464?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/19464?src=pr&el=footer). Last update [7725fa0...b72f9c5](https://codecov.io/gh/pandas-dev/pandas/pull/19464?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
 rebase when you can and pls show perf > rebase when you can and pls show perf

Unfortunately I found out that performance drops dramatically in some cases... until I'm able to fix and merge #19539. ok https://github.com/pandas-dev/pandas/pull/19464#issuecomment-368243824

keep open then? > keep open then?

definitely... I think they are both significant improvements, I just need to understand what's wrong with 2.7 on Windows
 Rebased, and #19539 did improve things significantly... but results are still not what one expects from a performance fix!

```
       before           after         ratio
     [2299693d]       [cd7fd6b1]
+         125±6ms          247±1ms     1.98  multiindex_object.Duplicated.time_duplicated_loc
-      14.4±0.3μs       11.9±0.1μs     0.82  multiindex_object.GetLoc.time_string_get_loc

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

I will have to investigate more. can you rebase closing as stale. if you'd like to continue pls ping.