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*: 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: >>> 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. François

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

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