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] |

*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: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 +#elseThis 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.

**Follow-Ups**:**Re: New power of 2 hash policy***From:*FranÃois Dumont

**Re: New power of 2 hash policy***From:*FranÃois Dumont

**References**:**New power of 2 hash policy***From:*FranÃois Dumont

**Re: New power of 2 hash policy***From:*Michael Matz

**Re: New power of 2 hash policy***From:*Jonathan Wakely

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |