This is the mail archive of the
mailing list for the libstdc++ project.
Re: New power of 2 hash policy
- From: Jonathan Wakely <jwakely at redhat dot com>
- To: Michael Matz <matz at suse dot de>
- Cc: François Dumont <frs dot dumont at gmail dot com>, "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: Fri, 11 Sep 2015 14:23:16 +0100
- 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>
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.