This is the mail archive of the
mailing list for the libstdc++ project.
Re: New power of 2 hash policy
- From: FranÃois Dumont <frs dot dumont at gmail dot com>
- To: Jonathan Wakely <jwakely at redhat dot com>, Michael Matz <matz at suse dot de>
- Cc: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Sun, 13 Sep 2015 21:32:38 +0200
- Subject: Re: New power of 2 hash policy
- Authentication-results: sourceware.org; auth=none
- References: <55F1E20E dot 7080305 at gmail dot com> <alpine dot LSU dot 2 dot 20 dot 1509111508520 dot 30229 at wotan dot suse dot de> <20150911131815 dot GI2631 at redhat dot com> <20150911132316 dot GJ2631 at redhat 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:
>>> 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
>>> 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
> 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
> 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.