CHAMP

[NikZak]

Sorry, for the lack of knowledge on the question. This https://en.wikipedia.org/wiki/Hash_array_mapped_trie says that CHAMP was an improvement on HAMT, is that right and if yes are there plans to add that algo to the repo?

[jneem]

I don't have any such plans, no. We already had a few rounds of optimization of the HAMT representation, so I'm not sure how much it differs from what CHAMP proposes. If someone wants to try it out and measure the results, I'd be happy to take a look.

[nickz-t3]

Sure, here is what I got from benchmarking with https://github.com/YuriyKrasilnikov/champ-trie

| Impl | Size | Build | Throughput | Insert / elem | Get / elem | Remove / elem | Memory |
|------|------|-------|------------|---------------|------------|---------------|--------|
| imbl | 1 | 34 ns | 29.41 M/s | 152 ns | 4 ns | 83 ns | 0.02 MiB |
| rpds | 1 | 114 ns | 8.77 M/s | 204 ns | 9 ns | 83 ns | <0.01 MiB |
| champ | 1 | 57 ns | 17.54 M/s | 113 ns | 8 ns | 42 ns | <0.01 MiB |
| imbl | 1K | 267.1 µs | 3.74 M/s | 302 ns | 6 ns | 280 ns | 0.12 MiB |
| rpds | 1K | 254.4 µs | 3.93 M/s | 250 ns | 13 ns | 208 ns | 0.14 MiB |
| champ | 1K | 157.6 µs | 6.35 M/s | 207 ns | 11 ns | 223 ns | 1.12 MiB |
| imbl | 1M | 1.044 s | 957.8 K/s | 863 ns | 9 ns | 1.1 µs | 119.52 MiB |
| rpds | 1M | 1.043 s | 959.2 K/s | 625 ns | 21 ns | 570 ns | 129.73 MiB |
| champ | 1M | 707.25 ms | 1.41 M/s | 1.0 µs | 20 ns | 1.4 µs | 1727.47 MiB |

In short this Champ implementation has good performance on smaller hashmaps but bad performance (and terrible memory footprint) on larger ones. I think the reason could be in the implementation details (arena allocator massively over-allocating. At 1M entries, the working set doesn't fit in L3 cache) but the algorithm seems sound

[NikZak]

Also a small video

champ_hampt.mp4