This is the mail archive of the libstdc++@gcc.gnu.org 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/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.


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