From: Jonathan Wakely <jwakely@redhat.com>
To: "François Dumont" <frs.dumont@gmail.com>
Cc: "libstdc++@gcc.gnu.org" <libstdc++@gcc.gnu.org>,
gcc-patches <gcc-patches@gcc.gnu.org>
Subject: Re: libstdc++/90277 Review rehash policy
Date: Fri, 03 May 2019 12:10:00 -0000 [thread overview]
Message-ID: <20190503121016.GE2599@redhat.com> (raw)
In-Reply-To: <0cfcaf27-610e-0c12-bb5b-8a51fb328666@gmail.com>
On 03/05/19 06:21 +0200, François Dumont wrote:
>Hi
>
>Â Â Â This is a patch I already proposed in another thread but I review
>it and moreover there is now a PR associated so I am submitting it as
>a brand new one.
>
>Â Â Â So working on PR 68303 I noticed that one of the performance issue
>of current implementation is that initial sizing of buckets is small.
>In tr1 implementation we were starting at 11 but now we go through 2,
>3, 5, 7 and eventually 11, a lot of intermediate reallocation/rehash.
>It can be considered as a fix for PR 90277 cause when initial bucket
>count is 11 there is no rehash anymore during those tests.
>
>Â Â Â Compared to initial submission this version has the refinement
>that if the user explicitly set initial bucket count we respect it and
>do not jump to 11.
>
>Â Â Â Additionally this patch extend the PR 87135 fix to the power of 2
>rehash policy alternative and it adopts the long double versions of
>builtin ceil/floor as advised in another message thread.
>
>Â Â Â Last I realized that _Hashtable<>::reserve could leverage on
>rehash policy _M_bkt_for_elements rather than trying to compute it
>itself, it brings more consistency in the container behavior.
>
>Â Â Â * include/bits/hashtable.h (_Hashtable<>::rehash): Review comment.
>Â Â Â * include/bits/hashtable_policy.h
>Â Â Â (_Prime_rehash_policy::_M_bkt_for_elements): Use __builtin_ceill.
>Â Â Â (_Power2_rehash_policy::_M_bkt_for_elements): Likewise.
>Â Â Â (_Power2_rehash_policy::_M_next_bkt): Enforce returning a result not
>Â Â Â smaller than input value rather than always greater. Preserve
>Â Â Â _M_next_resize if called with 0 input. Use __builtin_floorl.
>Â Â Â (_Power2_rehash_policy::_M_need_rehash): Rehash only if number of
>Â Â Â elements + number of insertions is greater than _M_next_resize. Start
>Â Â Â with 11 buckets if not told otherwise. Use __builtin_floorl.
>Â Â Â (_Rehash_base<>::reserve): Use rehash policy _M_bkt_for_elements.
>Â Â Â * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
>Â Â Â Preserve _M_next_resize if called with 0 input. Use __builtin_floorl.
>Â Â Â (_Prime_rehash_policy::_M_need_rehash): Start with 11 buckets if not
>Â Â Â told otherwise. Use __builtin_floorl.
>Â Â Â * testsuite/23_containers/unordered_set/hash_policy/71181.cc:
>Adapt test
>Â Â Â to also validate _Power2_rehash_policy.
>Â Â Â * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc:
>Â Â Â Adapt.
>
>Tested under Linux x86_64 normal and debug modes.
>
>Ok to commit ?
Yes, looks good - thanks!
prev parent reply other threads:[~2019-05-03 12:10 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <9adabe26-e373-c600-3963-291c806b69d1@gmail.com>
2019-05-03 4:21 ` François Dumont
2019-05-03 12:10 ` Jonathan Wakely [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20190503121016.GE2599@redhat.com \
--to=jwakely@redhat.com \
--cc=frs.dumont@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).