Thread: Re: Small optimization with expanding dynamic hash table
> Will this still work if new_bucket is not equal to hctl->low_mask + 1?
Yes, for example:
low_mask: 0x011, high_mask: 0x111, old_bucket: 0x010, new_bucket: 0x110
The old_bucket's hash value like 0x***010 or 0x***110, the later is in the old_bucket is because we didn't have new_bucket before, so only hash value like 0x***110 needs relocation: hashvalue & (low_mask + 1) != 0
--
Regards,
ChangAo Chen
Hi,
Yes, for example:low_mask: 0x011, high_mask: 0x111, old_bucket: 0x010, new_bucket: 0x110The old_bucket's hash value like 0x***010 or 0x***110, the later is in the old_bucket is because we didn't have new_bucket before, so only hash value like 0x***110 needs relocation: hashvalue & (low_mask + 1) != 0
Thanks for explaining, that clarifies things for me.
It may be worthwhile to check if this change has led to any performance improvements.
Thank you,
Thank you,
Rahila syed
Hi,
Yes, for example:low_mask: 0x011, high_mask: 0x111, old_bucket: 0x010, new_bucket: 0x110The old_bucket's hash value like 0x***010 or 0x***110, the later is in the old_bucket is because we didn't have new_bucket before, so only hash value like 0x***110 needs relocation: hashvalue & (low_mask + 1) != 0Thanks for explaining, that clarifies things for me.It may be worthwhile to check if this change has led to any performance improvements.
One thing to note is that in this scenario, there is no safeguard if the hashvalue is 0x111 and new_bucket is 0x110.
This means max_bucket is 0x110, but with your change, even 0x111 would meet the condition for relocation
to the new bucket, which would be incorrect.
Although it’s unlikely that 0x111 would be passed into this check, if it is passed, there is currently no check to
prevent it from being relocated to the new bucket. In the current code, however, we do have such a check in
place in calc_bucket, specifically: if (bucket > hctl->max_bucket)
Thank you,
Rahila Syed
> One thing to note is that in this scenario, there is no safeguard if the hashvalue is 0x111 and new_bucket is 0x110.
But the hash table is already corrupted if the hashvalue 0x111 in old_bucket 0x010, all hashvalue in old_bucket should have: hashvalue & low_mask == old_bucket's no.
--
Regards,
ChangAo Chen