PERF: Introducing HashTables for datatypes with 8,16 and 32 bits
State: closed

- [x] tests added / passed
- [x] passes `black pandas`
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [ ] whatsnew entry

Starts work on #33287

Proof of concept for 32bit/16bit hash tables. If works it should become blue print for UInt32/Int16/UInt16/Float32-HashTables.


Labels:
name: Dtype Conversions
description: Unexpected or buggy dtype conversions

Comments:
FYI, @jbrockmendel 

This is  my idea, how adding further HashMap-versions could work. It probably needs more (direct) tests of HashTables, because right now they are tested somewhat indirectly via `test_algos.py` and  a lot of infrastructure is missing for testing the functionality of new versions.
Definitely needs more robust testing, but this looks like a really good start.  Thanks for following upon this.
couple of ideas for either follow-ups or to get testing for "free":

in core.algorithms add Int32HashTable to _hashtables dict and update algorithms._ensure_data to avoid casting int32 to int64 

in _libs.index_class_helper update hashtable_name for int32 (maybe also int16 and int8)

be still my beating heart you got the 8s and the 16s too!
@jreback @jbrockmendel 

I've added also 8bit versions: mostly for the sake of uniformity - otherwise there is always a special case. While using 8bit hashtable is better than converting to 16bit-datatype and using 16bit hash-table, it is still an overkill. If important, later on a special version could be written for 8bit data types.

Apart from some polishing and small(ish) test-issues, I consider this PR complete. Once it is merged, the upcasting can be dropped at one place after another. I'm however not really a pandas power user and cannot estimate the necessary work and hope somebody will be able to help.

One might not be satisfied with the simple hash-function used (identity), but it is more or less consistent with functions we use for (u)int64. The comments say: https://github.com/pandas-dev/pandas/blob/4cfa97a1808f31c8235d513a7aded32f87f8ae89/pandas/_libs/src/klib/khash.h#L62-L63

So if there are some problems, we could switch to Wang's or murmur2-hash.



@realead can you measure what this does to the size of the distribution? `python setup.py bdist_wheel` should do the trick.
@TomAugspurger  it adds about 0.7-0.8MB to the wheel.

This PR:
``` 
31.7 Nov 20 22:36 pandas-1.2.0.dev0+1209.g0b9d94a-cp38-cp38-linux_x86_64.whl
7,4M Nov 20 22:24 hashtable.cpython-38-x86_64-linux-gnu.so*
```

master:
```
31M Nov 20 22:51 pandas-1.2.0.dev0+1191.g8d1b8ab-cp38-cp38-linux_x86_64.whl
3.8M Nov 20 22:42 hashtable.cpython-38-x86_64-linux-gnu.so*
```

@jreback  @jbrockmendel 

I could not help myself and sneaked some changes in, which are not really necessary:

  - for the sake of consistency and to avoid undefined behavior, using unsigned ints also for 64bit integers. This is somewhat hacky (but the way khash has done it in the first place) See also this comment: https://github.com/pandas-dev/pandas/pull/37920#discussion_r527191378. Commit: https://github.com/pandas-dev/pandas/pull/37920/commits/897512d5eba6076340ca4e61068816ab54289f82

 - adding dependency on khash.h, otherwise changing it doesn't trigger rebuild (probably anything cimporting `khash.pxd` (e.g. via `cimport hashtable.pxd`) should have it as well, but I'm not sure). Commit:  https://github.com/pandas-dev/pandas/pull/37920/commits/17a3feed54890d806e25cd731e9559be60d27366

 - getting rid of unnecessary `default_na_value`, see this comment: https://github.com/pandas-dev/pandas/pull/37920#discussion_r526543906  Commit: https://github.com/pandas-dev/pandas/pull/37920/commits/3a4c2bcff2de207b3d993b3d5ec5dd7d2da291df

You can decide whether you want to keep some of them in this PR, or rather in as a new PR or just to drop.
> @TomAugspurger it adds about 0.7-0.8MB to the wheel.
> 
> This PR:
> 
> ```
> 31.7 Nov 20 22:36 pandas-1.2.0.dev0+1209.g0b9d94a-cp38-cp38-linux_x86_64.whl
> 7,4M Nov 20 22:24 hashtable.cpython-38-x86_64-linux-gnu.so*
> ```
> 
> master:
> 
> ```
> 31M Nov 20 22:51 pandas-1.2.0.dev0+1191.g8d1b8ab-cp38-cp38-linux_x86_64.whl
> 3.8M Nov 20 22:42 hashtable.cpython-38-x86_64-linux-gnu.so*
> ```

not nothing, but nbd
LGTM

Travis failure is an unrelated frame plotting test that im seeing locally too
thanks @realead very nice!
This is exciting thanks @realead