This is the mail archive of the mailing list for the libstdc++ project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: New power of 2 hash policy

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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]