Open arthurprs opened 4 weeks ago
Your concern is legitimate and I have ran into this myself as well, unfortunately I don't currently see a zero-cost way of making it happen.
To reduce the size of hash maps RandomState
only contains the per-hasher randomness (a single u64
), while the rest of the random state is stored globally: https://github.com/orlp/foldhash/blob/92a8df96b576b4da841826ebd13bb98021c84b1c/src/seed.rs#L57.
We could sacrifice one bit of the per_hasher_seed
to indicate whether it should use the global deterministic initializer, or the global random initializer. But this would introduce extra code (and worse, a branch) in the actual hash path.
I could expand the RandomState
by 8 bytes (which inflates all hash maps by 8 bytes) to contain a reference to the global random data, and this reference would then either be the non-deterministic global seed or the deterministic static seed, but even this would add an extra mov
to the normal RandomState
path I believe.
The size rationale makes sense to me as this is a hashmap-optimized hasher.
Sacrificing one bit of the instance's seed sounds reasonable at first glance. It could be possible to massage that (predictable) branch to a conditional move. Maybe 3 more instructions in total.
let mut global_seed = &rand_global_seed;
if self.per_hasher_seed & 1 == 1 {
global_seed = &fixed_global_seed;
}
FoldHasher::with_seed(self.per_hasher_seed, global_seed.get())
Maybe 3 more instructions in total.
Unfortunately that is not acceptable. The current u64
hash is 5 instructions on modern x86-64:
view_assembly:
mov rax, qword ptr [rip + example::seed::GLOBAL_SEED_STORAGE::ha8aed685c422c912@GOTPCREL]
xor rdi, qword ptr [rsi]
mov rdx, rdi
mulx rax, rcx, qword ptr [rax]
xor rax, rcx
ret
It seems that storing a reference in RandomState
is fine in terms of codesize:
view_assembly:
mov rax, qword ptr [rsi]
xor rdi, qword ptr [rsi + 8]
mov rdx, rdi
mulx rax, rcx, qword ptr [rax]
xor rax, rcx
ret
So the question is just whether this feature is worth increasing the size of RandomState
from 8 to 16 bytes. I think the answer is probably yes.
Yeah, I think so, too. It makes it more practical, in my experience. You could even have a SmallRandomState variant that optimizes for size (but generates more code), probably more useful than FixedState.
Sometimes it's useful to create a deterministically seeded
RandomState
.Even if
FixedState
exists, it's a different type, so the user must choose one or another at the type level instead of creation time. I suppose there are uses for both patterns.