Horton

Thread

  1. Re: Small optimization with expanding dynamic hash table

    cca5507 <cca5507@qq.com> — 2025-07-08T07:16:57Z

    &gt;&nbsp;Will this still work if new_bucket is not equal to hctl-&gt;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&nbsp;relocation: hashvalue &amp; (low_mask + 1) != 0


--
Regards,
ChangAo Chen

  2. Re: Small optimization with expanding dynamic hash table

    Rahila Syed <rahilasyed90@gmail.com> — 2025-07-08T08:32:50Z

    Hi,


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
>
>
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,
Rahila syed

  3. Re: Small optimization with expanding dynamic hash table

    Rahila Syed <rahilasyed90@gmail.com> — 2025-07-08T11:06:29Z

    Hi,

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
>>
>>
> Thanks 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

  4. Re: Small optimization with expanding dynamic hash table

    cca5507 <cca5507@qq.com> — 2025-07-08T11:56:50Z

    &gt;&nbsp;One thing to note is that in this scenario, there is no safeguard if the&nbsp;hashvalue is 0x111 and new_bucket is 0x110.

But the hash table is already&nbsp;corrupted if the hashvalue 0x111 in old_bucket 0x010, all hashvalue in old_bucket should have: hashvalue &amp; low_mask == old_bucket's no.


--
Regards,
ChangAo Chen

  5. Re: Small optimization with expanding dynamic hash table

    cca5507 <cca5507@qq.com> — 2025-07-10T02:45:44Z

    Hi,

The v2 patch maybe more clear:


We can calc bucket just by hashvalue &amp; high_mask when expanding table because the if condition in calc_bucket() must be false.


--
Regards,
ChangAo Chen

  6. Re: Small optimization with expanding dynamic hash table

    wenhui qiu <qiuwenhuifx@gmail.com> — 2025-07-11T09:33:52Z

    Hi
> The v2 patch maybe more clear:
> We can calc bucket just by hashvalue & high_mask when expanding table
because the if condition in calc_bucket() must be false.
I think you may add a comment to this path so that code reviewers can
clearly see your optimization.

Thanks

On Thu, Jul 10, 2025 at 10:46 AM cca5507 <cca5507@qq.com> wrote:

> Hi,
>
> The v2 patch maybe more clear:
>
> We can calc bucket just by hashvalue & high_mask when expanding table
> because the if condition in calc_bucket() must be false.
>
> --
> Regards,
> ChangAo Chen
>
>

  7. Re: Small optimization with expanding dynamic hash table

    cca5507 <cca5507@qq.com> — 2025-07-11T12:30:25Z

    Hi,

The v3 patch attached. (Add some comment in commit msg)


--
Regards,
ChangAo Chen