PERF: CategoricalIndex.get_loc should avoid expensive cast of .codes to int64
State: closed

- [x] closes #20395
- [ ] tests added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [ ] whatsnew entry

This is the the final puzzle for #20395.

The problem with the current 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 very 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 options

As CategoricalIndex.codes may be int8, int16, etc, the solution must be to (1) have an indexing engine for each integer dtype or an indexing engine that accepts all int types, not just int64 *and* (2) that the key must be translated into the same dtype as the codes array before calling searchsorted. So either:
1. Change Int64Engine to be a IntEngine (i.e. accept all integer dtypes)
2. Make new IntEngine classes, with the appropriate flexibility for accepting all integer dtypes, but defers to Int64 version if/when needed (e.g. if codes is int8, but we only have ``algos.is_monotonic_int64`` for checking monotonicity)
3. Do everything in Python.

I assume option 1 is not desired, and option 3 assumedly likewise. In the updated PR I've made a proposal in Cython, that attains the needed speed.

Benchmarks from ``asv_bench/indexing.py``

```
      before           after         ratio
     [dc45fbaf]       [bc03b8bd]
-     1.54±0.02ms         9.80±0μs     0.01  indexing.CategoricalIndexIndexing.time_get_loc_scalar('monotonic_incr')

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```


Labels:
name: Performance
description: Memory or execution speed performance
name: Categorical
description: Categorical Data Type

Comments:
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21699?src=pr&el=h1) Report
> Merging [#21699](https://codecov.io/gh/pandas-dev/pandas/pull/21699?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/3ab9dbd64b4a057eda53b841f43999fb319869e9?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/21699/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/21699?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #21699      +/-   ##
==========================================
+ Coverage   92.18%   92.19%   +<.01%     
==========================================
  Files         169      169              
  Lines       50820    50821       +1     
==========================================
+ Hits        46850    46852       +2     
+ Misses       3970     3969       -1
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.6% <100%> (ø)` | :arrow_up: |
| #single | `42.38% <57.14%> (ø)` | :arrow_up: |

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

------

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

so 2) is the prefered solution here. you can simply use the templating like we do in most modules which generates code. its not trivial but not super complicated either.
@topper-123 what issues were you running into with Cython? As far as generating the indexes goes I would think you could just add the appropriate types below:

https://github.com/pandas-dev/pandas/blob/2b136054db3b8f4c8d1aa33160c4bbe3b8ce940e/pandas/_libs/index_class_helper.pxi.in#L14

Not sure how you were planning to dynamically select the appropriate engine in `category.py` but as far as generating those engines in the Cython layer I think most of the foundation is already in place
Ok, I think I understand the design now, at least. What is the templating language used and how is the pxi-file generated?

So would the correct approach be to:
* add int8_t, int16_t etc. to that list in index_helper_pxi.in,
* similarly add them to the list in algos.common_helper.pxi.in,
* ensure that CategoricalIndex._engine is of the correct type,
* avoid the  casting to int64 in  ``CategoricalIndex._engine``?


Ok, got algos.common_helper.pxi.in compiling and works fine.

index_helper.pxi throws a compiler error. I added to the dtype list in index_helper.pxi.in:

```
          ('Int8', 'int8', 'int8_t'),
```

but get this error when compiling:

```cython
cythoning pandas\_libs/index.pyx to pandas\_libs\index.c

Error compiling Cython file:
------------------------------------------------------------
...

    cdef _maybe_get_bool_indexer(self, object val):
        cdef:
            ndarray[uint8_t, ndim=1, cast=True] indexer
            ndarray[intp_t, ndim=1] found
            ndarray[int8_t] values
                         ^
------------------------------------------------------------

pandas\_libs\index_class_helper.pxi:179:26: Invalid type.
````

It appears the compiler does not like the int8_t type. Using ``('UInt8', 'uint8', 'uint8_t'),`` instead compiles without errors.

Any ideas what's happening?
you need to do the imports of ``int8_t`` in ``index.pyx`` itself (see the top). 
Thanks, got everything compiling with Int8Engine, which is good.

However, when running, it complains there is no Int8HashTable. Seems like there isn't an easy way to create an Int8HashTable, is that correct?

```python
~\Documents\Python\pandasdev\pandasdev\pandas\_libs\index_class_helper.pxi in pandas._libs.index.Int8Engine._make_hash_table()
    212
    213     cdef _make_hash_table(self, n):
--> 214         return _hash.Int8HashTable(n)

AttributeError: module 'pandas._libs.hashtable' has no attribute 'Int8HashTable'
```

I tried looking into using a Int64HashTable in Int8Engine, but that seems to bring a different set of tradeoffs...

Is there an easy way to create a Int8HashTable, or is it reasonable to use a Int64HashTable in Int8Engine?
you might need to create the other hash tables  (definitions) as well
i think we only have 32 & 64 hits atm
Ok, I've tried creating the int8 hash table, but got some issues. Everything compiles up till and including " add Int8Index", but that runs into the issue that no Int8HashTable existst. I've tried creating a Int8HashTable (see the commit "add Int8HashTable"), but I can't get  to compile.

It gives this compilation error:

```
Error compiling Cython file:
------------------------------------------------------------
...
        self.external_view_exists = True
        return self.ao

    cdef inline void append(self, int8_t x):

        if needs_resize(self.data):
                      ^
------------------------------------------------------------

pandas\_libs\hashtable_class_helper.pxi:287:23: no suitable method found

Error compiling Cython file:
------------------------------------------------------------
...


cdef class Int8HashTable(HashTable):

    def __cinit__(self, size_hint=1):
        self.table = kh_init_int8()
                                ^
------------------------------------------------------------

pandas\_libs\hashtable_class_helper.pxi:1291:33: undeclared name not builtin: kh_init_int8
```

I've tried messing with khash.pxd to get that kh_*_int8 working, but can't get it running.

What does khash.pxd do? It seems to in turn depend on khash_python.h, which only seems to have int64, int32 anf float64 version available. Must that be changed before getting a Int8HashTable working?

Guidance would be very much appreciated.

hmm, i guess khash doesn't support this either.

ok, so maybe let's do a precursor PR to do this properly 
Ok, just to confirm, so you/someone else will do the PR to get Int8HashTable etc. working, and I'll wait for that and afterwards I will implement Int8Engine etc?
@topper-123 well I suppose someone can do a PR to make other types of hashtables work. cc @pandas-dev/pandas-core 
That would be great. If someone makes the hash tables I will take this the rest of the way.
I've made a solution for the problem of not having Int8HashTable, Int16HashTable and Int32HashTable by using Int64HashTable in Int8Engine etc. All the tests pass and performance is the same as above.

Is this an ok approach? I could then add some tests and ASVs as needed.

A nice side effect BTW is that we now have and can use ``pd._libs.algos.is_monotonic_int8``, so we don't have to convert to int64 when checking for monoticity and uniqueness:

```python
>>> n = 1_000_000
>>> ci = pd.CategoricalIndex(list('a' * n + 'b' * n + 'c' * n))
# the below is called in ci.is_monotonic etc. in master
>>> %timeit pd._libs.algos.is_monotonic_int64(ci.codes.astype('int64'), False)
21.6 ms  # master
# the below is called in ci.is_monotonic etc. in this PR
>>> %timeit pd._libs.algos.is_monotonic_int8(ci.codes, False)
5.6 ms  # this PR
```

So all code that calls CategoricalIndex.is_monotonic/.is_unique will benefit also.

Hey, ``array.astype('int64', copy=False)`` won't work as explained above.

I don't see any good way forward other than someone commiting to make an Int8/16/32HashTable at some point. The question is thought if this PR needs to wait for that, or can be pulled in now and the relevant lines be changed when the hash table is implemented. 

I argue pulling this in now, as index operations are critical for performance and that would allow me to pursue a few more index-related performance issues. 
``algos.ensure_int64(values)`` ends up calling ``values.astype(np.int64)``, and therefore also causes the slowdown for int8/16/32 arrays that we want to avoid.

A *technically* possible solution to avoid that if statement while keeping the speed improvements would be to input a int64 array into _engine:

```python
    def _engine(self):
        codes = self.codes.astype('int64')
        return self._engine_type(lambda: codes, len(self))
```

But that would keep an int64 array in memory, in addition to an int8 array, so doesn't make any sense memorywise. We want to just use the existing int8 array.

I made another solution, where I've moved this specific implementation to index_class_helper.pxi.in. This makes its location more specific to the problem it solves.
I've addressed the comments. Haven't made any new ASVs though, will look at it tomorrow, but  many of the new index engines are not currently used, so have to think about how to speed test them.

The travis failure is the unexpected ResourceWarning, so unrelated to this PR.
I added a commit with ASVs. I check ``*Engine.get_loc`` and get these result:

```
[  0.00%] · For pandas commit hash 166c72e4:
[  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
[ 25.00%] ··· Running indexing_engines.NumericEngineIndexing.time_get_loc                                                     3.81±0.08μs;...
[ 50.00%] ··· Running indexing_engines.ObjectEngineIndexing.time_get_loc                                                      5.20±0.07μs;...
[ 50.00%] · For pandas commit hash 03707400:
[ 50.00%] ·· Building for conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
[ 50.00%] ·· Benchmarking conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
[ 75.00%] ··· Running indexing_engines.NumericEngineIndexing.time_get_loc                                                              failed
[100.00%] ··· Running indexing_engines.ObjectEngineIndexing.time_get_loc                                                               failed
SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

The failure at commit hash 03707400 is ok, as most indexing engines were not made yet there (Int8Engine etc. are new). The speed of 4.07μs is as expected.

I didn't make timing checks for ``is_monotonic*`` and ``is_unique``, as those are both cached, so it won't give any benefits timing them.

Is there anything else that should be timed?

Sorry I havent followed this closely, but you’ve added new indexing engines? Can you measure the size of the unzipped wheel before and after your changes?

________________________________
From: topper-123 <notifications@github.com>
Sent: Saturday, August 11, 2018 10:00:22 PM
To: pandas-dev/pandas
Cc: Tom Augspurger; Team mention
Subject: Re: [pandas-dev/pandas] PERF: CategoricalIndex.get_loc should avoid expensive cast of .codes to int64 (#21699)


I added a commit with ASVs. I check *Engine.get_loc and get these result:

· Running 2 total benchmarks (2 commits * 1 environments * 1 benchmarks)
[  0.00%] · For pandas commit hash 9df4167d:
[  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.EngineIndexing.time_get_loc                                                      4.07±0.4μs;...
[ 50.00%] · For pandas commit hash 03707400:
[ 50.00%] ·· Building for conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
[ 50.00%] ·· Benchmarking conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
[100.00%] ··· Running indexing_engines.EngineIndexing.time_get_loc                                                              failed
SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.


The failure at commit hash 0370740<https://github.com/pandas-dev/pandas/commit/0370740034978d3a63d4b8e5e2c96ff54e7e08ba> is ok, as most indexing engines were not made yet there (Int8Engine etc. are new). The speed of 4.07μs is as expected.

I didn't make timing checks for is_monotonic* and is_unique, as those are both cached, so it won't give any benefits timing them.

Is there anything else that should be timed?

—
You are receiving this because you are on a team that was mentioned.
Reply to this email directly, view it on GitHub<https://github.com/pandas-dev/pandas/pull/21699#issuecomment-412315096>, or mute the thread<https://github.com/notifications/unsubscribe-auth/ABQHIkd-MExSV46oY6ryf1a6wGLwOaRrks5uP5pGgaJpZM4U-cO6>.

Hey @TomAugspurger. Yes, CategoricalIndex typically work on int8 or int16 datatypes, so we need a corresponding indexing engine (Int8Engine if codes dtype is int8, etc.) to avoid converting to int64 and slowing down.

Strictly speaking, this PR only requires we do integer engines, but It seems sensible to me to do engines for the smaller UInts and Floats also.

I haven't worked with wheels myself, how do I find/create them? The size of the build folder was 78,5 MB before and 80,5 MB after this PR.
python setup.py bdist_wheel will create a wheel. That can be unzipped to
get the distribution size.

I just want to raise the cost of templating across many dtypes, since
that's what tends to blow up the distribution size.

On Sun, Aug 12, 2018 at 2:17 PM topper-123 <notifications@github.com> wrote:

> Hey @TomAugspurger <https://github.com/TomAugspurger>. Yes,
> CategoricalIndex typically work on int8 or int16 datatypes, so we need a
> corresponding indexing engine (Int8Engine if codes dtype is int8, etc.) to
> avoid converting to int64 and slowing down.
>
> Strictly speaking, this PR only requires we do integer engines, but It
> seems sensible to me to do engines for the smaller UInts and Floats also.
>
> I haven't worked with wheels myself, how do I find/create them? The size
> of the build folder was 78,5 MB before and 80,5 MB after this PR.
>
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub
> <https://github.com/pandas-dev/pandas/pull/21699#issuecomment-412365348>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/ABQHIpLFpA-ViQmgBfNtZ3gwTWjSyCYqks5uQH8ugaJpZM4U-cO6>
> .
>

Ok, I get unzipped 24.5 MB (master) vs 24.8 MB (this PR)
Is this ok?
Seems OK, thanks for checking.

On Mon, Aug 13, 2018 at 11:19 AM topper-123 <notifications@github.com>
wrote:

> Is this ok?
>
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub
> <https://github.com/pandas-dev/pandas/pull/21699#issuecomment-412576244>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/ABQHIrkP96RDWBcY0RWTcD0s4YpILeheks5uQab7gaJpZM4U-cO6>
> .
>

hey @jreback , is this ok to pull in?
Changes according to comments.
Is this ok to merge in?
ping @jreback 
will have a look