In my experience, one of the detriments of our hash map is the potential for a long "probe length", i.e. when you have a collision, how many tries does it take you to find an open slot in your table.
I've been reading about some alternatives and Robin Hood hashing has come up quite a bit.
In fact it was the Rust HashMap's algorithm until it switched to hashbrown which uses a SwissTable hash map (https://github.com/rust-lang/hashbrown).
We should consider if using this is compatible with our hashes and if it would improve things at all.
This is a good comparison that shows average probe length of quadratic hash tables (ours) with robin hood https://thenumb.at/Hashtables/#linear-probing. Notably max probe length at 50% max load is 21 for existing and 49 for missing for quadratic, and only 12 and 12 for robin hood. In my testing I've definitely seen some probe lengths of 12 with our existing implementation.
I also considered whether we should just drop our max load down to 30% in some scenarios. This does seem to really improve performance for basic atomic types because it keeps the table more open, leading to less collisions. But it can lead to a significant increase in wasted memory particularly when you get above 10mil elements.
Here was my edit that included some logic about continuing to use our 50% load above a certain size threshold to avoid wasted memory
// Assume worst case, that every value is distinct, aiming for a load factor
// of at most 50%. We round up to power of 2 to ensure quadratic probing
// strategy works. Maximum power of 2 we can store in a uint32_t is 2^31,
// as 2^32 is 1 greater than the max uint32_t value, so we clamp sizes that
// would result in 2^32 to INT32_MAX to ensure that our maximum ceiling value
// is only 2^31. This will increase the max load factor above 50% for `x` with
// length greater than 1073741824 (2147483648 * .50), but it ensures that
// it can run. See https://github.com/r-lib/vctrs/pull/1760 for further
// discussion of why 50% was chosen.
static inline
uint32_t dict_key_size(SEXP x) {
const R_len_t x_size = vec_size(x);
if (x_size > R_LEN_T_MAX) {
// Ensure we catch the switch to supporting long vectors in `vec_size()`
r_stop_internal("Dictionary functions do not support long vectors.");
}
// The limit we are willing to use a 30% load factor up to
//
// Above this limit, we jump to `2 ^ 26` as the next power of
// 2, which takes us from ~33mil -> ~67mil to stay at a 30%
// load factor, which is a big jump in possibly wasted memory
// (a ~134 MB jump, `(2 ^ 26 - 2 ^ 25) * sizeof(R_len_t)`)
//
// - `2 ^ 25` is `33554432`
// - `33554432 * .3` is `10066330`
// - `10066330 - 1` is `10066329`
//
// This allows us to stay at `2 ^ 25` until we hit 16777216,
// at which point we move to `2 ^ 26`, and above that we continue
// to more slowly expand the table by shooting for a max load of 50%.
const R_len_t x_size_aggressive_load_size_limit = 10066329;
const double max_load_size = (x_size > x_size_aggressive_load_size_limit) ? 0.50 : 0.30;
const double load_adjusted_size = x_size / max_load_size;
//Rprintf("%i\n", (int)x_size);
//Rprintf("%i\n", (int)load_adjusted_size);
if (load_adjusted_size > UINT32_MAX) {
r_stop_internal("Can't safely cast load adjusted size to a `uint32_t`.");
}
uint32_t size = (uint32_t)load_adjusted_size;
// Clamp to `INT32_MAX` to avoid overflow in `u32_safe_ceil2()`,
// at the cost of an increased maximum load factor for long input
size = size > INT32_MAX ? INT32_MAX : size;
size = u32_safe_ceil2(size);
size = (size < 16) ? 16 : size;
if (x_size > size) {
// Should never happen with `R_len_t` sizes.
// This is a defensive check that will be useful when we support long vectors.
r_stop_internal("Hash table size must be at least as large as input to avoid a load factor of >100%.");
}
//Rprintf("%i\n", (int)size);
// Rprintf("size: %u\n", size);
return size;
}I do think this may be a valuable thing to consider doing, but I think longer term choosing a better implementation is probably the best approach.
One thing I noted was that for data frames (say 3 double columns, 10 mil rows), it actually got a little slower than the existing impl when using a 30% load, which doesn't make much sense to me.
In my experience, one of the detriments of our hash map is the potential for a long "probe length", i.e. when you have a collision, how many tries does it take you to find an open slot in your table.
I've been reading about some alternatives and Robin Hood hashing has come up quite a bit.
In fact it was the Rust HashMap's algorithm until it switched to hashbrown which uses a SwissTable hash map (https://github.com/rust-lang/hashbrown).
We should consider if using this is compatible with our hashes and if it would improve things at all.
This is a good comparison that shows average probe length of quadratic hash tables (ours) with robin hood https://thenumb.at/Hashtables/#linear-probing. Notably max probe length at 50% max load is 21 for existing and 49 for missing for quadratic, and only 12 and 12 for robin hood. In my testing I've definitely seen some probe lengths of 12 with our existing implementation.
I also considered whether we should just drop our max load down to 30% in some scenarios. This does seem to really improve performance for basic atomic types because it keeps the table more open, leading to less collisions. But it can lead to a significant increase in wasted memory particularly when you get above 10mil elements.
Here was my edit that included some logic about continuing to use our 50% load above a certain size threshold to avoid wasted memory
I do think this may be a valuable thing to consider doing, but I think longer term choosing a better implementation is probably the best approach.
One thing I noted was that for data frames (say 3 double columns, 10 mil rows), it actually got a little slower than the existing impl when using a 30% load, which doesn't make much sense to me.