Inside the Erlang runtime system, persistent hashmaps are represented as hash-array-mapped-tries if they are big, and 'flatmaps' if they are small.
I recently was nerdsniped into looking for ways to optimize this. ^_^'
A flatmap has the following characteristics:
- There are at most 32 keys (and 32 values);
- They are stored unordered in a C array;
- There are no duplicate keys;
- Keys are unboxed: We can directly compare the two
uint64_t's together to check for a match.
The current implementation of this is:
uint64_t *original_flatmap_get(uint64_t *keys, uint64_t *vals, uint64_t key, uint64_t max_size) {
uint64_t n = max_size;
uint64_t i;
for (i = 0; i < n; ++i) {
if (keys[i] == key) {
return &vals[i];
}
}
return NULL;
}
(Simplified from the original)
But this does not use above info at all. I tried what happened if the compiler was made aware that
- there are at most 32 elements
- It's fine to return 'a' match rather than 'the first'; since the keys are unique there will only ever at most be a single match.
This lead to the following implementation:
uint64_t *latereturn_flatmap_get(uint64_t *keys, uint64_t *vals, uint64_t key, uint64_t max_size) {
uint64_t n = min(max_size, 32);
uint64_t i;
uint64_t *res = NULL;
for (i = 0; i < n; ++i) {
if (keys[i] == key) {
res = &vals[i];
}
}
return res;
}
Looking at Compiler Explorer we can see that Clang and GCC are able to vectorize and unroll the loop now. Benchmarking this shows a 5-15% speedup.
However, now for the question: Is it possible to go further?
For instance, is it possible to indicate to the compiler somehow that all elements in the array will be unique which might enable even more optimizations?
Or are there maybe ways to manually write some SIMD instructions directly which are even faster?