[ENH] introducing IntpHashMap and making unique_label_indices use intp
State: closed

- [x] tests added / passed
- [x] Ensure all linting tests pass, see [here](https://pandas.pydata.org/pandas-docs/dev/development/contributing.html#code-standards) for how to run them

Introduces IntpHashMap. Instead of making it from the scratch, we map the functionality either to Int32HashMap or Int64HashMap depending on the plattform. This has the advantage, that the resulting so/pyd-files don't get bigger.


Labels:
name: Enhancement

Comments:
@jbrockmendel  FYI: this is implementation of your idea in #40635 (https://github.com/pandas-dev/pandas/pull/40635#issuecomment-808324219). I think it should work, but let's see...
Can the kh_foo do the same thing?  In particular unique_label_indices i think should take and return intp
> Can the kh_foo do the same thing?

In my understanding `np.intp` is just an alias for np.int64 on 64bit system and for np.int32 on 32bit system, thus calling right `kh_foo_intXX` (XX=64 or 32) with `np.intp_t` would do the right thing.

>  In particular unique_label_indices i think should take and return intp. 

Here we need `unique_label_indices_int64` (we have) and `unique_label_indices_int32` (we don't have yet), then we could map `unique_label_indices`either to int64- or int32-version, which would become the `intp`-version.
@jbrockmendel do you really need `IntpHashMap` or just `unique_label_indices` which takes intp and returns intp?
> @jbrockmendel do you really need IntpHashMap or just unique_label_indices which takes intp and returns intp?

If unique_label_indices was changed to intp i would find that immediately useful.  IntpHashMap I _expect_ would become useful, but I don't have anything immediately in mind.
@jbrockmendel I have introduced `unique_label_indices_intp`. If this solution is too clever, we could do the "boring" dance and introduce IntpHashMap similar to the way other maps are done.

You either can replace `unique_label_indices` one after another through `unique_label_indices_intp` or redefine `unique_label_indices` in one go.


unique_label_indices is only called in one non-test place, so we only need the intp version.  Does that simplify things?  The solution I was going to try before you got to it first was going to look something like:

```
if np.dtype(np.intp) == np.dtype(np.int64):
    IntpHashTable = Int64HashTable
    IntpVector = Int64Vector
    IntpVectorData = Int64VectorData
    kh_resize_intp = ky_resize_int64
    [... whatever else is needed for unique_label_indices]
elif np.dtype(np.intp) == np.dtype(np.int32):
    [... same as above but with int32]
else:
    raise ValueError(np.dtype(np.intp))
```

And the part I hadn't figured out would be figuring out intp at compile-time so these could all be made cdef
@jbrockmendel now  unique_label_indices uses intp.

Not sure, the failures are due to my changes.


failures look unrelated, yah
tangential: would it be feasible to make a kh_base_t or something that all the other kh_foo_t subclass?  I think we could de-duplicate a bunch of code if we could declare `cdef readonly kh_base_t table` on `cdef class HashTable`
> tangential: would it be feasible to make a kh_base_t or something that all the other kh_foo_t subclass? I think we could de-duplicate a bunch of code if we could declare `cdef readonly kh_base_t table` on `cdef class HashTable`

I don't see, how this could be easily done. E.g. in c++ the typical solution is to use templates, i.e. `std::map<K,T>` and I haven't seen any other solutions really getting any kind of traction. Here we have a very similar situation - just using tempita rather than templates.

A different example are Java's Maps (at least prior to 1.5), but Java is somewhat different because everything is an Object and dynamic cast is pretty good supported by the language itself (and yet I always fellt c++ solution to be "clearer" and also faster).

Trying to use type erasion (e.g. casting key-pointer to void* and creating virtual table for kh_-function depending on type) would probably work but I doubt the code will be clearer and simpler/less error prone than now.

A slightly tangential remark: Because tempita is quite powerful, I think it would not be that easy to switch to fused types or at least some artificial tricks will be needed to achieve something similar without tempita (so the question is really whether the resulting code will be really easier). For me the only real downside of using tempita are the big resulting object files - there is not really a code duplication (because different code versions are created by tempita) as far as I can see.




This pull request is stale because it has been open for thirty days with no activity. Please update or respond to this comment if you're still interested in working on this.
@realead can you merge master to resolve conflicts
@simonjayhawkins Done. I think the failing tests are unrelated.
@jbrockmendel @jreback 

Is this PR still needed/should be pursued further?
you good here @jreback?
will look later 

any resolution on the numpy pin?
> any resolution on the numpy pin?

simon has a PR that i think will be ready soonish to handle that.  this PR should be unaffected
@realead is this still relevant?
@jreback it was a request by @jbrockmendel  (https://github.com/pandas-dev/pandas/pull/40635#issue-841062044) not sure, whether it is still needed/wanted.
> not sure, whether it is still needed/wanted

the motivation hasn't changed: the one place where we use unique_label_indices we have ndarray[intp] and have to use `ensure_int64` before calling unique_label_indices.  So ideally unique_label_indices would take ndarray[intp] directly.

In practice, it's not _that_ big of a deal since on most platforms ensure_int64 is a no-op.  So there's a reasonable case to be made that it isn't worth the effort or build-size increase.
ok this seems reasonable for completeness.
ok this seems reasonable for completeness.
thanks @realead