Re: New power of 2 hash policy

[FranÃois Dumont <frs dot dumont at gmail dot com>]

On 11/09/2015 15:23, Jonathan Wakely wrote:
> On 11/09/15 14:18 +0100, Jonathan Wakely wrote:
>> On 11/09/15 15:11 +0200, Michael Matz wrote:
>>> Hi,
>>>
>>> On Thu, 10 Sep 2015, François Dumont wrote:
>>>
>>>>    Here is a patch to offer an alternative hash policy. This one is
>>>> using power of 2 number of buckets allowing a faster modulo operation.
>>>> This is obvious when running the performance test that I have
>>>> adapted to
>>>> use this alternative policy. Something between current implementation
>>>> and the tr1 one, the old std one.
>>>>
>>>>    Of course with this hash policy the lower bits of the hash code are
>>>> more important. For pointers it would require to change the std::hash
>>>> implementation to remove the lower 0 bits like in the patch I proposed
>>>> some weeks ago.
>>>>
>>>>    What do you think ?
>>>
>>> No comment on if it should be included (except that it seems useful to
>>> me), but one observation of the patch:
>>>
>>>> +    1ul << 31,
>>>> +#if __SIZEOF_LONG__ != 8
>>>> +    1ul << 32
>>>> +#else
>>>
>>> This is wrong, 1ul<<32 is zero on a 32bit machine, and is also the 33rd
>>> entry in that table, when you want only 32.  Like you also (correctly)
>>> stop with 1ul<<63 for a 64bit machine.
>>
>> I'd prefer to see that table disappear completely, replaced by a
>> constexpr function. We need a static table of prime numbers because
>> they can't be computed instantly, but we don't need to store powers of
>> two in the library.
>>
>> I agree the extension is useful, and would like to see it included,
>> but I wonder if we can do it without adding any new symbols to the
>> shared library. We certainly don't need the table, and the few other
>> functions added to the DSO could probably be defined inline in
>> headers.
>
>
> Also there several comments that talk about finding "the next prime"
> which should talk about powers of two, and the smaller table for fast
> lookup of the next "prime" may not be needed for powers of two. There
> are fast tricks for finding the next power of two using bitwise
> operations.
>
> So I'm in favour of the change in general, but it needs a little bit
> of reworking where the prime number code has been copy&pasted.
>
Ok, thanks for the feedback. We can indeed implement it in a simpler
way, should be fine.

François