get_indexer_non_unique for orderable indexes
State: closed

Tackles the performance issue raised at #15364 by looping simultaneously over source and target indexes, avoiding dictionary and set lookups in for/while loops.

I guess it can be further improved in terms of static typing. For example, if both source and target indexes are simple C types, the function `_indexer_non_unique_orderable_loop` should be way faster if we provide that information.


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

Comments:
using lists here is not really great (not that the original is much better). 
need an asv to see if this is actually better
The last commit speed up quite a lot:

```python
import numpy as np
import pandas as pd
from pandas import Index

from IPython import get_ipython
ipython = get_ipython()

i = Index(Index(np.arange(1000000)).tolist() + Index(np.arange(1000000)).tolist())

ipython.magic("timeit i.get_indexer_non_unique(i[0:1000000])")
```

Previous implementation: 1 loop, best of 3: 3.42 s per loop
Pull request implementation: 1 loop, best of 3: 681 ms per loop


@Horta Can you simply reuse `Int64Vector` instead of making a new `Int64List` type?
@shoyer I've tried and couldn't make it work. Also, I don't thing contiguous array is the way to go for such a problem as some indices might not repeat, or might repeat a lot.

But I'm working on another implementation that relies only on fixed-size arrays, which means that I won't need any of those two types (Int64List or Int64Vector).
>  I've tried and couldn't make it work

Can you clarify? You couldn't get it to compile or you couldn't understand how to use it?

> Also, I don't thing contiguous array is the way to go for such a problem as some indices might not repeat, or might repeat a lot.

Couldn't we simply accumulative the indexes of matching elements, e.g., by repeatedly appending to a Python list of integers? That's effectively what `Int64Vector` is for, except without the overhead of boxing in Python objects. It's essentially a C++ vector written in Cython.

I would rather not add new low level data structure for this specific method unless we absolutely need it. My understanding is that vectors are usually faster than linked lists, anyways. It's certainly more memory efficient.
> Can you clarify? You couldn't get it to compile or you couldn't understand how to use it?

I could not import it. Looks like it is private (only in pyx). I tried to export defining them on pxd and had some difficults. Then I tried to copy/paste Int64Vector and still had difficults. Basically it needs documentation...

> I would rather not add new low level data structure for this specific method unless we absolutely need it.

The implementation I'm working on makes no use of new types: I will be using basic C types. It is a matter of looping over the src and tgt values twice, calling Malloc twice and realloc once.
Take a look at the IntervalIndex PR: https://github.com/pandas-dev/pandas/pull/15309/files#diff-cdfa55be00a117a8466e28b72f60cfca

You should be able to just copy the lines from that change for pandas/hashtable.pxd and then use `from hashtable cimport Int64Vector`
I may acutally push some of the low-level code into master later / tomrrow if I get a chance to make this easier anyhow.
I just pushed these to master: https://github.com/pandas-dev/pandas/commit/010393c4cb650b78e3e51af417e7037737e8d3b6
pls update when you can
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15372?src=pr&el=h1) Report
> Merging [#15372](https://codecov.io/gh/pandas-dev/pandas/pull/15372?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/61a243b858fe41aac81d20a75e5f1e86baefd868?src=pr&el=desc) will **increase** coverage by `0.1%`.
> The diff coverage is `100%`.


```diff
@@            Coverage Diff            @@
##           master   #15372     +/-   ##
=========================================
+ Coverage   90.32%   90.43%   +0.1%     
=========================================
  Files         135      134      -1     
  Lines       49413    49376     -37     
=========================================
+ Hits        44633    44651     +18     
+ Misses       4780     4725     -55
```


| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/15372?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/indexes/base.py](https://codecov.io/gh/pandas-dev/pandas/compare/61a243b858fe41aac81d20a75e5f1e86baefd868...6916dad1a7219072621e8a9f38b68348de9321b6?src=pr&el=tree#diff-cGFuZGFzL2luZGV4ZXMvYmFzZS5weQ==) | `96.27% <100%> (+0.04%)` | :white_check_mark: |
| [pandas/core/common.py](https://codecov.io/gh/pandas-dev/pandas/compare/61a243b858fe41aac81d20a75e5f1e86baefd868...6916dad1a7219072621e8a9f38b68348de9321b6?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvY29tbW9uLnB5) | `91.02% <ø> (-0.34%)` | :x: |
| [pandas/tseries/offsets.py](https://codecov.io/gh/pandas-dev/pandas/compare/61a243b858fe41aac81d20a75e5f1e86baefd868...6916dad1a7219072621e8a9f38b68348de9321b6?src=pr&el=tree#diff-cGFuZGFzL3RzZXJpZXMvb2Zmc2V0cy5weQ==) | `97.13% <ø> (-0.13%)` | :x: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/compare/61a243b858fe41aac81d20a75e5f1e86baefd868...6916dad1a7219072621e8a9f38b68348de9321b6?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.87% <ø> (ø)` | :white_check_mark: |
| [pandas/io/auth.py](https://codecov.io/gh/pandas-dev/pandas/compare/61a243b858fe41aac81d20a75e5f1e86baefd868...6916dad1a7219072621e8a9f38b68348de9321b6?src=pr&el=tree#diff-cGFuZGFzL2lvL2F1dGgucHk=) | | |
| [pandas/util/terminal.py](https://codecov.io/gh/pandas-dev/pandas/compare/61a243b858fe41aac81d20a75e5f1e86baefd868...6916dad1a7219072621e8a9f38b68348de9321b6?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvdGVybWluYWwucHk=) | `47.82% <ø> (+2.89%)` | :white_check_mark: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15372?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/15372?src=pr&el=footer). Last update [61a243b...74ce239](https://codecov.io/gh/pandas-dev/pandas/compare/61a243b858fe41aac81d20a75e5f1e86baefd868...74ce239e4b3e306b1dba64a84086c5ae1e757ef5?el=footer&src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
```python
import numpy as np
import pandas as pd
from pandas import Index

from IPython import get_ipython
ipython = get_ipython()

i = Index(Index(np.arange(1000000)).tolist() + Index(np.arange(1000000)).tolist())

ipython.magic("timeit i.get_indexer_non_unique(i[0:1000000])")
```

The above test runs in '714 ms'. The implementation regarding the last commit https://github.com/pandas-dev/pandas/pull/15372/commits/bf4b3f585a8d65827bd984c76797c689e72c35fc makes use of fixed-size arrays only, no resize needed.

I think that is the best we can have in terms of data structure. But it can be further improved by, for example, getting rid of PyObject_RichCompare calls due to Python object comparisons. Maybe those Cython fuse types?

@Horta please rebase on origin/master.

``git rebase -i origin/master`` and ``git push yourremote thisbranch -f``
@jreback after doing `git rebase -i origin/master` now I got

```
> git status
interactive rebase in progress; onto be4a63fe7
Last commands done (6 commands done):
   pick 6afb8c910 wrong exception handling
   pick c7a1e0090 get_indexer_non_unique for orderable indexes
  (see more in file .git/rebase-merge/done)
Next commands to do (9 remaining commands):
   pick c1b657e19 get_indexer_non_unique for orderable indexes
   pick 47f7ce325 C level list
  (use "git rebase --edit-todo" to view and edit)
You are currently editing a commit while rebasing branch 'master' on 'be4a63fe7'.
  (use "git commit --amend" to amend the current commit)
  (use "git rebase --continue" once you are satisfied with your changes)

nothing to commit, working tree clean
```

Not sure what to do now...
so the issue is you are using your ``master`` branch like a branch which is generally not recommended, so to fix you can do:

```
git checkout yourbranch
git fetch origin/master
git rebase -ii origin/master
```
I think I need to start a new pull request because I don't know what is going on anymore... (I've tried the above command)
superseded by #15468