[Discuss][C++] Replace MemoTable with a SwissTable implementation

[js8544]

Describe the enhancement requested

This is a follow up of #36059 (comment). There are many cases where we use a MemoTable, e.g. set lookup functions, vector hash functions, the count_distinct aggregate function, dictionary unification etc. Their performance can be boosted with a SwissTable.

We can either:

1. Use an existing swiss table library. This requires some work on dependency management. I recommend absl::flat_hash_map since they are the original author of swiss tables and we already has absl in our 3rd party toolchain.
2. Write one by ourselves. The current one in acero is too customized for the join node and it seems hard to extract a general hashtable from it. If I were to write one I would probably follow the structure of absl's and replace things like memory management and bit tweaking with Arrow ones.

What do you think? @pitrou @westonpace

Component(s)

C++

[pitrou]

I don't know what a "Swiss table" is. Can you point to a general description?

[pitrou]

More generally, I'm all for a faster associative table implementation.

[mapleFU]

Maybe we should first having an memory-usage / performance benchmark on this?

[js8544]

There's an Abseil's article and a CppCon talk that provide a good intro. The key idea is, when looking up a key via linear probing, it can check multiple slots at once.

[pitrou]

Ah, so it's a hash table with SIMD-optimized lookup?

[js8544]

Maybe we should first having an memory-usage / performance benchmark on this?

Okay, I'll try to draft a proof of concept with the is_in kernel.

[pitrou]

If you're going to use SIMD lookups, then I would ask that it relies on xsimd instead of intrinsics.

[js8544]

Ah, so it's a hash table with SIMD-optimized lookup?

Well it's a speedup even without SIMD instructions. To put it in a oversimplified term each slot occupies 1 byte so with int64 we can already check 8 slots at the same time. But SIMD can definitely make it even faster.

If you're going to use SIMD lookups, then I would ask that it relies on xsimd instead of intrinsics.

Sure, if we decide to write our own version.

[pitrou]

Well it's a speedup even without SIMD instructions. To put it in a oversimplified term each slot occupies 1 byte so with int64 we can already check 8 slots at the same time. But SIMD can definitely make it even faster.

I see, thanks for the explanation.

Sure, if we decide to write our own version.

Well, we don't want to depend on Abseil, so our own version it should probably be :-)

[llama90]

There's an Abseil's article and a CppCon talk that provide a good intro. The key idea is, when looking up a key via linear probing, it can check multiple slots at once.

Thank you for explaining. I was also curious about what Swiss Join is too. :)

[js8544]

I wrote a simple proof of concept for IndexIn [1] with a slightly tweaked version of absl::flat_hash_map. (Tweak is [2], a couple of operations can be skipped because our MemoTable doesn't need to support deletion). And the existing IndexIn benchmarks (results below) show about 20% ~ 60% improvement depending on the value_set size, the larger the better.

The benchmarks are run on my Mac M1 so the results may vary on a x86 machine. But I think the diff is compelling enough for us to proceed with a Swiss table implementation.

[1] https://github.com/apache/arrow/compare/main...js8544:jinshang/swiss_proof_of_concept?diff=split#diff-d288c253c3a5959aa1b6840a649a8dafe42d14ac49d1837b19dd3a44c58f7fd9R93
[2] 7d14d10

Benchmark Results

Before

After

[pitrou]

Can you post benchmark numbers on string values? While hashing integers is nice, I'm not sure that's a dominant use case.