[C++] Performance of building up HashTable (MemoTable) in is_in kernel

[jorisvandenbossche]

From some benchmarking in pandas, @phofl noticed that the "is_in" implementation of Arrow is considerably slower compared to pandas' (khash-based) implementation, if the value_set is big (and thus when the execution time is mostly dominated by creating the hashtable, and not by the actual lookups).

Small illustration comparing pc.is_in with pandas.core.algorithms.isin (the equivalent pandas function) using a larger value_set with a small array (so that we are mostly timing the hashtable creation):

arr = pa.array(np.random.choice(np.arange(1000), 100))
for n in [10_000, 100_000, 1_000_000, 10_000_000]:
    print(n)
    value_set = pa.array(np.arange(n))
    %timeit pc.is_in(arr, value_set)
    %timeit pd.core.algorithms.isin(np.asarray(arr), np.asarray(value_set))

gives

10000
158 µs ± 581 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
66.8 µs ± 473 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
100000
8.51 ms ± 110 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
627 µs ± 41.8 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
1000000
103 ms ± 8.74 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
28.5 ms ± 4.09 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
10000000
1.26 s ± 33 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
171 ms ± 22 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

So pandas is often 4-10x faster. I am not familiar with our HashTable implementation or whether it's a fully fair comparison, but it seems this is at least an indication there is room for performance improvement (and I suppose this might be for HashTable-based functions in general, not just "is_in").

[js8544]

I found out that we can pre-allocate buffer space for the hash table before inserting elements into it. This completely avoids rehashing during the insertion process and yields some performance improvements. On my machine I get:

Before

100
4.49 µs ± 94.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
16.2 µs ± 515 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
1000
8.75 µs ± 51.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
22.4 µs ± 414 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
10000
71.4 µs ± 1.84 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
53.7 µs ± 937 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
100000
3.78 ms ± 267 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
375 µs ± 1.33 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
1000000
41.2 ms ± 929 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
17.7 ms ± 705 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
10000000
679 ms ± 24.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
127 ms ± 1.46 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 

After

100
3.73 µs ± 57.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
17 µs ± 156 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
1000
7.75 µs ± 190 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
23.2 µs ± 602 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
10000
44.5 µs ± 751 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
54.4 µs ± 926 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
100000
519 µs ± 27 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
378 µs ± 1.43 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
1000000
38.3 ms ± 520 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
17.4 ms ± 379 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
10000000
557 ms ± 18.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
124 ms ± 3.22 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

The improvement is outstanding for input size <= 100000 (up to serveral times faster), however it won't be too much for larger inputs as the rehashing cost was already amortized. There is still a large performance gap during the Lookup phase that remains unsolved.

Nevertheless I'll submit a PR for this improvement.

[westonpace]

If someone really wanted to be adventurous a swiss table is generally better suited for columnar batch operations (more vectorization friendly).

We have one in src/arrow/acero/swiss_join_internal.h. However, we probably can't use it directly since it is built around the row encoding and is doing a lot more work than would strictly be needed for an is_in operation. Even so, I can perform a full hash_join of two tables faster than is_in (it's about 2-3x slower than pandas on my system) so that is encouraging. It could be used for inspiration.

[phofl]

Can we reopen this? It looks like it’s only addressing parts of the difference

[pitrou]

@phofl You can open another issue if you think performance can be further improved.