PERF: speed up CategoricalIndex.get_loc
State: closed

- [x] closes #20395
- [x] tests added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

This is the the final puzzle for #20395 and speeds up ``CategoricalIndex.get_loc`` for monotonic increasing indexes.

This PR supersedes #21699, so #21699 should be closed.

The problem with the current get_loc implementation is that ``CategoricalIndex._engine`` constantly recodes int8 arrays to int64 arrays:

https://github.com/pandas-dev/pandas/blob/dc45fbafef172e357cb5decdeab22de67160f5b7/pandas/core/indexes/category.py#L365-L369

Notice the ``lambda: self.codes.astype('i8')`` part, which means that every time ``_engine.vgetter`` is called, an int64-array is created. This is expensive and we would ideally want to just use the original array dtype (int8, int16 or whatever) always and avoid this conversion.

A complicating issue is that it is *not* enough to just avoid the int64 transformation, as ``array.searchsorted`` apparantly needs a dtype-compatible input or else it is *also* very slow:

```python
>>> n = 1_000_000
>>> ci = pd.CategoricalIndex(list('a' * n + 'b' * n + 'c' * n))
>>> %timeit ci.codes.searchsorted(1)  # search for left location of 'b'
7.38 ms   # slow
>>> code = np.int8(1)
>>> %timeit ci.codes.searchsorted(code)
2.57 µs  # fast
```

### Solution

As CategoricalIndex.codes may be int8, int16, etc, the solution must
(1) have an indexing engine for each integer dtype and
(2) have the code for the key be translated into the same dtype as the codes array before calling searchsorted.

This PR does that, essentially.

### Performance improvement examples

```python
>>> n = 100_000
>>> ci = pd.CategoricalIndex(list('a' * n + 'b' * n + 'c' * n))
>>> %timeit ci.get_loc('b')
2.05 ms  # master
8.96 µs  # this PR
>>> n = 1_000_000
>>> ci = pd.CategoricalIndex(list('a' * n + 'b' * n + 'c' * n))
>>> %timeit ci.get_loc('b')
18.7 ms  # master
9.09 µs  # this PR
```

So we go from O(n) performance to O(1) performance.

The indexing_engines.py ASV results:

```
[  0.00%] ·· Building for conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
[  0.00%] ·· Benchmarking conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
[ 50.00%] ··· Running indexing_engines.NumericEngineIndexing.time_get_loc                                                        7.18±1μs;...
[100.00%] ··· Running indexing_engines.ObjectEngineIndexing.time_get_loc                                                       7.04±0.4μs;...
```




Labels:
name: Indexing
description: Related to indexing on series/frames, not to indexes themselves
name: Performance
description: Memory or execution speed performance

Comments:
Hello @topper-123! Thanks for updating the PR.

 - There are no PEP8 issues in the file [`asv_bench/benchmarks/indexing_engines.py`](https://github.com/topper-123/pandas/blob/1d4bfd4dc6873fc0590fccc3d7d04548bc33a896/asv_bench/benchmarks/indexing_engines.py) !

 - There are no PEP8 issues in the file [`pandas/core/indexes/category.py`](https://github.com/topper-123/pandas/blob/1d4bfd4dc6873fc0590fccc3d7d04548bc33a896/pandas/core/indexes/category.py) !

 - There are no PEP8 issues in the file [`pandas/tests/indexing/conftest.py`](https://github.com/topper-123/pandas/blob/1d4bfd4dc6873fc0590fccc3d7d04548bc33a896/pandas/tests/indexing/conftest.py) !

 - There are no PEP8 issues in the file [`pandas/tests/indexing/test_indexing_engines.py`](https://github.com/topper-123/pandas/blob/1d4bfd4dc6873fc0590fccc3d7d04548bc33a896/pandas/tests/indexing/test_indexing_engines.py) !



##### Comment last updated on October 20, 2018 at 13:59 Hours UTC
Out of curiosity, does this fix improve `.get_loc` performance for MultiIndexes?
No, MultiIndex has a different implementation, and if I remember correctly, it always uses either int64 dtype or a pure python implementation. So the issue with recoding from int8 to int64 etc. should not be an issue there. (I have not studied the MultiEngine implementation in any great detail, so closer inspection might prove me wrong.)  
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/23235?src=pr&el=h1) Report
> Merging [#23235](https://codecov.io/gh/pandas-dev/pandas/pull/23235?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/14f25bb8b7ba0c709dd36d79966abea648d0f48b?src=pr&el=desc) will **increase** coverage by `<.01%`.
> The diff coverage is `100%`.

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

```diff
@@            Coverage Diff             @@
##           master   #23235      +/-   ##
==========================================
+ Coverage   92.22%   92.22%   +<.01%     
==========================================
  Files         169      169              
  Lines       50900    50902       +2     
==========================================
+ Hits        46943    46945       +2     
  Misses       3957     3957
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.65% <100%> (ø)` | :arrow_up: |
| #single | `42.29% <75%> (ø)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/23235?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/category.py](https://codecov.io/gh/pandas-dev/pandas/pull/23235/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9jYXRlZ29yeS5weQ==) | `97.84% <100%> (+0.01%)` | :arrow_up: |

------

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

All tests pass.

@jreback, I've simplified this new version a lot now by adding 'hashtable_name' and 'hashtable_dtype' to the ``dtype`` list in ``index_class_helper.pxi.in``. This means that we now avoid adding so many if-statements to the code.

lgtm. over to @jbrockmendel 
The explanation in the OP is exceptionally clear, thanks @topper-123.

If the possibly-unused imports are resolved, LGTM.
Actually, do we have tests that cover each of the dtypes that `codes` might take?
Currently, the algos in ``algos.pyx`` do not support uint32 and uint16. To get UInt32Engine and UInt16Engine to work we need to have at least ``ensure_uint32/_uint16`` and ``is_monotonic_uint32/uint_16``, but in that case we should probably just make all the algos have uint32/uint16 variants for consistency.

For exampel currently this fails:

```python
>>> arr = np.array([1,2,3,4], dtype=np.uint32)
>>> engine = pd._libs.index.UInt32Engine(lambda: arr, 4)
>>> engine.is_monotonic_increasing
AttributeError: module 'pandas._libs.algos' has no attribute 'ensure_uint32'
```
As I understood @jreback, UInt(32|16)Engine is desired, so I'll add the various uint32/uint16 variants to algos.pyx to make the uint indexing engines work, is that correct?

I'll also add a test_indexing_engines.py to capture such errors at the one above.
Added various stuff to get UInt(32|16)Engine to work, added tests for same and other minor stuff.
@jbrockmendel, I've made tests for ``CategoricalIndex._engine`` being of the correct type.

Also, I've made some tests for engine themselves in test_indexing_engine.py.  This last bit is needed because some engine types are not used yet in pandas. (These are ``UInt(8|16|32)Engine``), so we need to check directly that the cython methods work for those engine types.

can you merge master and push
thanks @topper-123