This is the mail archive of the
mailing list for the GCC project.
Re: hashtable optimization
- From: François Dumont <frs dot dumont at gmail dot com>
- To: Jonathan Wakely <jwakely at redhat dot com>
- 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, 22 Feb 2015 19:30:10 +0100
- Subject: Re: hashtable optimization
- Authentication-results: sourceware.org; auth=none
- References: <54E45CF9 dot 4000103 at gmail dot com> <20150220132242 dot GR3360 at redhat dot com>
On 20/02/2015 14:22, Jonathan Wakely wrote:
Ok, I understand, lets keep it for later then. I am also still
looking for the best implementation, maybe me or someone else will come
with the perfect one having tr1 performances for insert/lookup and std
performances for iteration/erase.
On 18/02/15 10:35 +0100, François Dumont wrote:
I am still studying hashtable performances and especially how to
reduce overhead compared to tr1 implementation. Most of the overhead
is coming from the additional modulo operations required with the new
data model. Having a closer look at PR 57885 bench I realized that we
can quite easily avoid an important modulo operation in
_M_insert_bucket_begin thanks to an additional std::size_t in the
The patch is quite straightforward, it optimizes insertion of a
node in an empty bucket which is the most important kind of insertion
as long as hash functor is doing a good job as per default we should
have at most 1 element per buckets:
Insertion: 1106 671 634 634 635 min=634 max=1106
Insertion: 885 491 487 490 511 min=487 max=885
Insertion: 1099 581 583 584 592 min=581 max=1099
Insertion: 889 491 519 492 493 min=491 max=889
I prefer to propose it now because it impacts ABI.
2015-02-19 François Dumont <firstname.lastname@example.org>
* include/bits/hashtable.h (_Hashtable<>::_M_bbegin_bkt): New, bucket
pointing to _M_before_begin.
(_Hashtable<>): Maintain and use later.
Tested under Linux x86_64.
I'm nervous about this kind of change at this stage. The patch looks
right, but are you sure you've covered *every* case where the cached
value needs to be updated?
Since this only affects performance, not correctness, it might be hard
to convince the release managers it is necessary during stage 4, and
I'm not entirely convinced myself either.