libstdc++/41975
Daniel Krügler
daniel.kruegler@googlemail.com
Tue Nov 22 20:57:00 GMT 2011
2011/11/22 François Dumont <frs.dumont@gmail.com>:
> Hi
>
> Here is my latest proposition to fix 41975 defect.
>
> Now all tests are passing under linux x86_64. There is no ICE anymore, I
> don't know where they were coming and I haven't been able to reproduce, a
> bad build perhaps.
>
> There is now the static_assert to check that hash code is cache or that the
> hash functor is noexcept qualified. The hash codes are cached only where the
> type is not an integral type and when the hash functor do not throw.
>
> Performance I pretty good:
>
> Without patch:
>
> unordered_set.cc unordered_set<int> copy 2624r 2322u
> 290s 0mem 0pf
> 41975.cc unordered_set<int> without cache: first
> insert 3r 1u 0s 8452192mem 0pf
> 41975.cc unordered_set<int> without cache: erase from
> iterator 2847r 2838u 2s -6400096mem 0pf
> 41975.cc unordered_set<int> without cache: second
> insert 1r 1u 0s 6400032mem 0pf
> 41975.cc unordered_set<int> without cache: erase from
> key 1r 1u 0s -6400032mem 0pf
> 41975.cc unordered_set<int> with cache: first insert
> 2r 2u 0s 11652192mem 0pf
> 41975.cc unordered_set<int> with cache: erase from
> iterator 2901r 2887u 8s -9600096mem 0pf
> 41975.cc unordered_set<int> with cache: second insert
> 1r 1u 0s 9600016mem 0pf
> 41975.cc unordered_set<int> with cache: erase from
> key 1r 1u 0s -9600016mem 0pf
> 41975.cc unordered_set<string> without cache: first
> insert 9r 9u 0s 8452192mem 0pf
> 41975.cc unordered_set<string> without cache: erase
> from iterator 3r 3u 0s -6400096mem 0pf
> 41975.cc unordered_set<string> without cache: second
> insert 4r 4u 0s 6400016mem 0pf
> 41975.cc unordered_set<string> without cache: erase
> from key 4r 5u 0s -6400016mem 0pf
> 41975.cc unordered_set<string> with cache: first
> insert 6r 5u 1s 11652176mem 0pf
> 41975.cc unordered_set<string> with cache: erase from
> iterator 3r 3u 0s -9600080mem 0pf
> 41975.cc unordered_set<string> with cache: second
> insert 3r 3u 0s 9600016mem 0pf
> 41975.cc unordered_set<string> with cache: erase from
> key 4r 4u 0s -9600016mem 0pf
>
> With the patch:
>
> unordered_set.cc unordered_set<int> copy 2780r 2480u
> 292s 0mem 0pf
> 41975.cc unordered_set<int> without cache: first
> insert 9r 7u 0s 8022160mem 0pf
> 41975.cc unordered_set<int> without cache: erase from
> iterator 2r 2u 0s -6400144mem 0pf
> 41975.cc unordered_set<int> without cache: second
> insert 100r 99u 1s 6400272mem 0pf
> 41975.cc unordered_set<int> without cache: erase from
> key 1r 1u 0s -6400272mem 0pf
> 41975.cc unordered_set<int> with cache: first insert
> 11r 10u 1s 11222224mem 0pf
> 41975.cc unordered_set<int> with cache: erase from
> iterator 2r 1u 0s -9600208mem 0pf
> 41975.cc unordered_set<int> with cache: second insert
> 104r 102u 0s 9600240mem 0pf
> 41975.cc unordered_set<int> with cache: erase from
> key 1r 1u 0s -9600240mem 0pf
> 41975.cc unordered_set<string> without cache: first
> insert 59r 57u 1s 8022160mem 0pf
> 41975.cc unordered_set<string> without cache: erase
> from iterator 8r 8u 0s -6400144mem 0pf
> 41975.cc unordered_set<string> without cache: second
> insert 59r 58u 1s 6400144mem 0pf
> 41975.cc unordered_set<string> without cache: erase
> from key 8r 7u 0s -6400144mem 0pf
> 41975.cc unordered_set<string> with cache: first
> insert 30r 28u 2s 11222176mem 0pf
> 41975.cc unordered_set<string> with cache: erase from
> iterator 5r 5u 0s -9600160mem 0pf
> 41975.cc unordered_set<string> with cache: second
> insert 28r 27u 0s 9600240mem 0pf
> 41975.cc unordered_set<string> with cache: erase from
> key 5r 5u 0s -9600240mem 0pf
>
> 2011-11-22 François Dumont <fdumont@gcc.gnu.org>
>
> PR libstdc++/41975
> * include/bits/hashtable.h (_Hashtable<>): Major data model
> modification to limit performance impact of empty buckets in
> erase(iterator) implementation.
> * include/bits/hashtable_policy.h (_Hashtable_iterator,
> _Hashtable_const_iterator): Remove not used anymore.
> * include/bits/hashtable_policy.h (_Prime_rehash_policy): Remove
> _M_grow_factor, just use natural evolution of prime numbers. Add
> _M_prev_size to know when the number of buckets can be reduced.
> * include/bits/unordered_set.h (__unordered_set<>,
> _unordered_multiset<>), unordered_map.h (__unordered_map<>,
> __unordered_multimap<>): Change default value of cache hash code
> template parameter, false for integral types with noexcept hash
> functor, true otherwise.
> * include/debug/unordered_map, unordered_set: Adapt transformation
> from iterator/const_iterator to respectively
> local_iterator/const_local_iterator.
> *
> testsuite/performance/23_containers/copy_construct/unordered_set.cc:
> New.
> * testsuite/23_containers/unordered_set/instantiation_neg.cc: New.
> * testsuite/23_containers/unordered_set/hash_policy/rehash.cc: New.
> * testsuite/23_containers/unordered_multiset/cons/copy.cc: New.
> * testsuite/23_containers/unordered_multiset/erase/1.cc,
> 24061-multiset.cc: Add checks on the number of bucket elements.
> *
> testsuite/23_containers/unordered_multiset/insert/multiset_range.cc,
> multiset_single.cc, multiset_single_move.cc: Likewise.
>
> Ok to commit in trunk ?
Regarding:
+ static_assert(__or_<integral_constant<bool, __cache_hash_code>,
+ integral_constant<bool,
+ noexcept(declval<const _H1&>()(declval<const _Key&>()))>
+ >::value,
+ "Cache the hash code or qualify your hash functor with noexcept");
I would recommend to wrap the expression test in a wrapper trait combined
to ensure lazy evaluation. As written, this test is always performed, regardless
of the value of __cache_hash_code.
- Daniel
More information about the Libstdc++
mailing list