PERF, BENCH: Fix performance issue when indexing into non-unique DatetimeIndex/PeriodIndex.
State: closed

This PR fixes a number of issues involving non-unique non-numeric indexing:
- The `NonNumericSeriesIndexing` benchmark incorrectly assumes `tm.makeStringIndex()` returns a monotonic `Index`. It does not and unfortunately invalidates the existing results here.
  - While modifying this, figured should add `PeriodIndex` and `non_monotonic` cases
- The `setup()` function creates an index but does not trigger the engine mapping to be populated. This leads to noisy and erroneous results.
  - See here for examples and compare with below: https://pandas.pydata.org/speed/pandas/#indexing.NonNumericSeriesIndexing.time_getitem_scalar
- A `PeriodIndex` or `DatetimeIndex` with non-unique, monotonic data creates an entirely new `Index` when being sliced. This means the engine mapping gets recomputed on every list-like query.
- A `PeriodIndex` is actually a `PeriodEngine` plus a separate `Int64Index` (with associated `Int64Engine`). The former contains a mapping of `{Period: value}` while being a subclass of `Int64Engine`. This means calls to `_bin_search()` fail as the underlying array consists of `Period` objects. This only occurs when the index is non-unique, monotonic, *and* `>= 1M` elements long.
  - We add an explicit test for this failure mode
- A number of index calls pass `value.ordinal` to the `PeriodEngine`; as that is a `{Period: value}` mapping, all such calls fail.
  - We instead pass `value.ordinal` queries to the `Int64Engine`, where they succeed.
- Finally, `PeriodIndex.get_memory()` does not account for the memory of its associated `Int64Index`. This is fixed by simply adding it to the total.

```
       before           after         ratio
     [2811464a]       [a68caa2a]
     <import_bench~1>       <period_fix>
           failed         62.4±2μs      n/a  indexing.NonNumericSeriesIndexing.time_get_value('period', 'unique_monotonic_inc')
           failed         216±20μs      n/a  indexing.NonNumericSeriesIndexing.time_getitem_label_slice('period', 'unique_monotonic_inc')
           failed      2.74±0.05ms      n/a  indexing.NonNumericSeriesIndexing.time_getitem_list_like('period', 'unique_monotonic_inc')
           failed        160±0.5μs      n/a  indexing.NonNumericSeriesIndexing.time_getitem_pos_slice('period', 'unique_monotonic_inc')
           failed       43.0±0.2μs      n/a  indexing.NonNumericSeriesIndexing.time_getitem_scalar('period', 'unique_monotonic_inc')
-        718±10μs         207±10μs     0.29  indexing.NonNumericSeriesIndexing.time_getitem_label_slice('period', 'non_monotonic')
-     2.53±0.05ms         701±10μs     0.28  indexing.NonNumericSeriesIndexing.time_getitem_list_like('period', 'non_monotonic')
-      33.8±0.9ms      2.32±0.04ms     0.07  indexing.NonNumericSeriesIndexing.time_getitem_list_like('period', 'nonunique_monotonic_inc')
-      62.7±0.5ms          532±3μs     0.01  indexing.NonNumericSeriesIndexing.time_getitem_list_like('datetime', 'nonunique_monotonic_inc')

       before           after         ratio
     [2811464a]       [a68caa2a]
     <import_bench~1>       <period_fix>
+      40.7±0.7μs       46.8±0.8μs     1.15  indexing.NonNumericSeriesIndexing.time_get_value('period', 'non_monotonic')
+        27.0±2μs       30.4±0.6μs     1.12  indexing.NonNumericSeriesIndexing.time_getitem_scalar('period', 'non_monotonic')
```

- [ ] closes #xxxx
- [ ] tests added / passed
- [ ] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [ ] whatsnew entry


Labels:
name: Datetime
description: Datetime data dtype
name: Performance
description: Memory or execution speed performance
name: Period
description: Period data type

Comments:
Hello @qwhelan! Thanks for updating this PR. We checked the lines you've touched for [PEP 8](https://www.python.org/dev/peps/pep-0008) issues, and found:











There are currently no PEP 8 issues detected in this Pull Request. Cheers! :beers: 

##### Comment last updated at 2019-07-06 21:25:48 UTC
lgtm. ping on green.
thanks @qwhelan