Re: [patch] No allocation for empty unordered containers
On 14/08/14 21:22 +0200, François Dumont wrote:
I am preparing a patch for profile mode so I will submit modification
for this mode with this big patch.
btw, François, for profile mode I think we should just do something
like this patch.
I feel quite strongly that if using Debug Mode or Profile Mode makes
your program run out of memory where it wouldn't usually fail, then
terminating is reasonable. The point of Profile Mode is not to test
abnormal execution of your program because that won't give you useful
profile information for the normal case.
It's more important for the noexcept specification to be consistent
across normal/debug/profile modes than for profile mode to fail
gracefully via bad_alloc in out-of-memory scenarios.
diff --git a/libstdc++-v3/include/profile/unordered_base.h
b/libstdc++-v3/include/profile/unordered_base.h
index 283f87c..cd9db7e 100644
--- a/libstdc++-v3/include/profile/unordered_base.h
+++ b/libstdc++-v3/include/profile/unordered_base.h
@@ -154,7 +154,7 @@ namespace __profile
using __unique_keys = std::integral_constantbool, _Unique_keys;
protected:
- _Unordered_profile()
+ _Unordered_profile() noexcept
{
auto __uc = _M_conjure();
__profcxx_hashtable_construct(__uc, __uc.bucket_count());
@@ -162,10 +162,10 @@ namespace __profile
}
_Unordered_profile(const _Unordered_profile)
: _Unordered_profile() { }
- _Unordered_profile(_Unordered_profile)
+ _Unordered_profile(_Unordered_profile) noexcept
: _Unordered_profile() { }
- ~_Unordered_profile() noexcept
+ ~_Unordered_profile()
{
auto __uc = _M_conjure();
__profcxx_hashtable_destruct(__uc, __uc.bucket_count(), __uc.size());
Re: [patch] No allocation for empty unordered containers
On 09/09/2014 19:29, Jonathan Wakely wrote: On 14/08/14 21:22 +0200, François Dumont wrote: I am preparing a patch for profile mode so I will submit modification for this mode with this big patch. btw, François, for profile mode I think we should just do something like this patch. I feel quite strongly that if using Debug Mode or Profile Mode makes your program run out of memory where it wouldn't usually fail, then terminating is reasonable. The point of Profile Mode is not to test abnormal execution of your program because that won't give you useful profile information for the normal case. It's more important for the noexcept specification to be consistent across normal/debug/profile modes than for profile mode to fail gracefully via bad_alloc in out-of-memory scenarios. Sure, no problem. In the patch I am preparing for profile mode failure in allocation will just mean that the involved container won't be profiled so that I can add noexcept wherever it is needed for consistency with normal mode. I hope to be able to submit this patch in a week or two. François
Re: [patch] No allocation for empty unordered containers
On 09/09/14 23:03 +0200, François Dumont wrote: On 09/09/2014 19:29, Jonathan Wakely wrote: On 14/08/14 21:22 +0200, François Dumont wrote: I am preparing a patch for profile mode so I will submit modification for this mode with this big patch. btw, François, for profile mode I think we should just do something like this patch. I feel quite strongly that if using Debug Mode or Profile Mode makes your program run out of memory where it wouldn't usually fail, then terminating is reasonable. The point of Profile Mode is not to test abnormal execution of your program because that won't give you useful profile information for the normal case. It's more important for the noexcept specification to be consistent across normal/debug/profile modes than for profile mode to fail gracefully via bad_alloc in out-of-memory scenarios. Sure, no problem. In the patch I am preparing for profile mode failure in allocation will just mean that the involved container won't be profiled so that I can add noexcept wherever it is needed for consistency with normal mode. I hope to be able to submit this patch in a week or two. Great - thanks for working on it.
Re: [patch] No allocation for empty unordered containers
On 14/08/14 21:22 +0200, François Dumont wrote: Then here is the patch to introduce default constructor with compiler computed noexcept qualification. Note that I also made allocator aware default constructor allocation free however noexcept qualification has to be manually written which I find quite a burden. Do you think we shall do so now ? I don't really care about that constructor, no need to do it now. The patch is OK to commit, thanks.
Re: [patch] No allocation for empty unordered containers
On 30/08/14 20:03 +0200, François Dumont wrote: Any news for my patch proposals ? Regarding documentation of default minimum number of buckets, I don't know where it has been documented but why do we need to document it separately ? Could it be taken care by Doxygen ? Can't it get the default value from the code itself ? If not we could document it ourself next to the code rather than in a distinct file. It's OK to document it with a Doxygen comment, although I think it would be better in doc/xml/manual/containers.xml. I'm reviewing the rest of the patch today, thanks for you patience.
Re: [patch] No allocation for empty unordered containers
Any news for my patch proposals ? Regarding documentation of default minimum number of buckets, I don't know where it has been documented but why do we need to document it separately ? Could it be taken care by Doxygen ? Can't it get the default value from the code itself ? If not we could document it ourself next to the code rather than in a distinct file. François On 14/08/2014 21:22, François Dumont wrote: On 13/08/2014 11:50, Jonathan Wakely wrote: Yes you can, it's conforming to replace a (non-virtual) member function with default arguments by two or more member functions. We do it all the time. See 17.6.5.5 [member.functions] p2. You should have told it sooner ! But of course no-one is supposed to ignore the Standard :-). Then here is the patch to introduce default constructor with compiler computed noexcept qualification. Note that I also made allocator aware default constructor allocation free however noexcept qualification has to be manually written which I find quite a burden. Do you think we shall do so now ? 2014-08-14 François Dumont fdum...@gcc.gnu.org * include/bits/hashtable_policy.h (_Prime_rehash_policy): Qualify constructor noexcept. (_Hash_code_base): All specialization default constructible if possible. (_Hashtable_base): Likewise. * include/bits/hashtable.h (_Hashtable()): Implementation defaulted. * include/bits/unordered_map.h (unordered_map::unordered_map()): New, implementation defaulted. (unordered_multimap::unordered_multimap()): Likewise. * include/bits/unordered_set.h (unordered_set::unordered_set()): Likewise. (unordered_multiset::unordered_multiset()): Likewise. * include/debug/unordered_map: Likewise. * include/debug/unordered_set: Likewise. * testsuite/23_containers/unordered_map/allocator/noexcept.cc (test04()): New. * testsuite/23_containers/unordered_multimap/allocator/noexcept.cc (test04()): New. * testsuite/23_containers/unordered_set/allocator/noexcept.cc (test04()): New. * testsuite/23_containers/unordered_multiset/allocator/noexcept.cc (test04()): New. I am preparing a patch for profile mode so I will submit modification for this mode with this big patch. Tested under Linux x86_64. Ok to commit ? François
Re: [patch] No allocation for empty unordered containers
On 13/08/2014 11:50, Jonathan Wakely wrote:
Yes you can, it's conforming to replace a (non-virtual) member function
with default arguments by two or more member functions. We do it all
the time.
See 17.6.5.5 [member.functions] p2.
You should have told it sooner ! But of course no-one is supposed
to ignore the Standard :-).
Then here is the patch to introduce default constructor with
compiler computed noexcept qualification. Note that I also made
allocator aware default constructor allocation free however noexcept
qualification has to be manually written which I find quite a burden. Do
you think we shall do so now ?
2014-08-14 François Dumont fdum...@gcc.gnu.org
* include/bits/hashtable_policy.h (_Prime_rehash_policy): Qualify
constructor
noexcept.
(_Hash_code_base): All specialization default constructible if
possible.
(_Hashtable_base): Likewise.
* include/bits/hashtable.h (_Hashtable()): Implementation defaulted.
* include/bits/unordered_map.h (unordered_map::unordered_map()): New,
implementation defaulted.
(unordered_multimap::unordered_multimap()): Likewise.
* include/bits/unordered_set.h
(unordered_set::unordered_set()): Likewise.
(unordered_multiset::unordered_multiset()): Likewise.
* include/debug/unordered_map: Likewise.
* include/debug/unordered_set: Likewise.
* testsuite/23_containers/unordered_map/allocator/noexcept.cc
(test04()): New.
* testsuite/23_containers/unordered_multimap/allocator/noexcept.cc
(test04()): New.
* testsuite/23_containers/unordered_set/allocator/noexcept.cc
(test04()): New.
* testsuite/23_containers/unordered_multiset/allocator/noexcept.cc
(test04()): New.
I am preparing a patch for profile mode so I will submit modification
for this mode with this big patch.
Tested under Linux x86_64.
Ok to commit ?
François
Index: include/bits/hashtable_policy.h
===
--- include/bits/hashtable_policy.h (revision 213780)
+++ include/bits/hashtable_policy.h (working copy)
@@ -460,7 +460,7 @@
/// smallest prime that keeps the load factor small enough.
struct _Prime_rehash_policy
{
-_Prime_rehash_policy(float __z = 1.0)
+_Prime_rehash_policy(float __z = 1.0) noexcept
: _M_max_load_factor(__z), _M_next_resize(0) { }
float
@@ -1071,7 +1071,8 @@
typedef void* __hash_code;
typedef _Hash_node_Value, false __node_type;
- // We need the default constructor for the local iterators.
+ // We need the default constructor for the local iterators and _Hashtable
+ // default constructor.
_Hash_code_base() = default;
_Hash_code_base(const _ExtractKey __ex, const _H1, const _H2,
@@ -1161,7 +1162,8 @@
typedef std::size_t __hash_code;
typedef _Hash_node_Value, false __node_type;
- // We need the default constructor for the local iterators.
+ // We need the default constructor for the local iterators and _Hashtable
+ // default constructor.
_Hash_code_base() = default;
_Hash_code_base(const _ExtractKey __ex,
@@ -1250,6 +1252,8 @@
typedef std::size_t __hash_code;
typedef _Hash_node_Value, true __node_type;
+ // We need the default constructor for _Hashtable default constructor.
+ _Hash_code_base() = default;
_Hash_code_base(const _ExtractKey __ex,
const _H1 __h1, const _H2 __h2,
const _Default_ranged_hash)
@@ -1694,6 +1698,7 @@
__hash_code, __hash_cached::value;
protected:
+_Hashtable_base() = default;
_Hashtable_base(const _ExtractKey __ex, const _H1 __h1, const _H2 __h2,
const _Hash __hash, const _Equal __eq)
: __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
@@ -1906,6 +1911,7 @@
__alloc_rebind__node_alloc_type, __bucket_type;
using __bucket_alloc_traits = std::allocator_traits__bucket_alloc_type;
+ _Hashtable_alloc() = default;
_Hashtable_alloc(const _Hashtable_alloc) = default;
_Hashtable_alloc(_Hashtable_alloc) = default;
Index: include/bits/hashtable.h
===
--- include/bits/hashtable.h (revision 213780)
+++ include/bits/hashtable.h (working copy)
@@ -310,10 +310,10 @@
const_local_iterator;
private:
- __bucket_type* _M_buckets;
- size_type _M_bucket_count;
+ __bucket_type* _M_buckets = _M_single_bucket;
+ size_type _M_bucket_count = 1;
__node_base _M_before_begin;
- size_type _M_element_count;
+ size_type _M_element_count = 0;
_RehashPolicy _M_rehash_policy;
// A single bucket used when only need for 1 bucket. Especially
@@ -322,7 +322,7 @@
// qualified.
// Note that we can't leave hashtable with 0 bucket without adding
// numerous checks in the code to avoid 0 modulus.
- __bucket_type
Re: [patch] No allocation for empty unordered containers
On 12/08/14 21:53 +0200, François Dumont wrote: On 12/08/2014 21:39, Marc Glisse wrote: On Tue, 12 Aug 2014, François Dumont wrote: Based on your feedbacks I think we should stay with just targeting good QoI by not allocating on default construction. As I said the noexcept qualification would need to not conform strictly to the Standard. The standard explicitly says that you may add noexcept wherever you like. It is constexpr that we can only add in GNU mode. That's not what I meant. For unordered containers there is no real default constructor. it is in fact a constructor with parameters which have all default values. This is why you can only say that it won't throw at runtime and so you can't qualify it noexcept. Yes you can, it's conforming to replace a (non-virtual) member function with default arguments by two or more member functions. We do it all the time. See 17.6.5.5 [member.functions] p2.
Re: [patch] No allocation for empty unordered containers
On 05/08/2014 22:23, Paolo Carlini wrote:
Hi,
On 08/05/2014 10:10 PM, Jonathan Wakely wrote:
It doesn't have to be noexcept, but IMHO there is no point changing
the containers to avoid allocation unless that allows us to mark it
noexcept. If it can throw anyway, we might as well allocate the
initial buckets.
I have been following this discussion on and off. In general, I must
say that AFAIK a default constructor which doesn't allocate memory is
normally considered superior from the QoI point of view, even if isn't
noexcept. As probably I have already mentioned, a well known C++
library implementer used to repeat it all the time and used also to
say that our std::list implementation was very good exactly because of
that feature, *well* before the invention of noexcept. That said,
marking the constructor noexcept is of course the obvious next step, I
don't have much to say about the general development plans we have got
here.
Paolo.
Hi
Based on your feedbacks I think we should stay with just targeting
good QoI by not allocating on default construction. As I said the
noexcept qualification would need to not conform strictly to the Standard.
So here is the patch again even if a little bit simplified.
Regarding the doc I try to put information in Doxygen comments this way
we do not need to maintain another page for that.
2014-08-12 François Dumont fdum...@gcc.gnu.org
* include/bits/hashtable.h: Make use of the internal single bucket to
limit allocation as long as container remains empty.
* include/bits/unordered_map.h: Set default bucket hint to 0 in
constructors to avoid allocation.
* include/bits/unordered_set.h: Likewise.
* include/debug/unordered_map: Likewise.
* include/debug/unordered_set: Likewise.
* src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
Returns 1 for hint 0.
* testsuite/23_containers/unordered_map/allocator/
empty_instantiation.cc:New.
* testsuite/23_containers/unordered_multimap/allocator/
empty_instantiation.cc:New.
* testsuite/23_containers/unordered_set/allocator/
empty_instantiation.cc: New.
* testsuite/23_containers/unordered_multiset/allocator/
empty_instantiation.cc: New.
Tested under Linux x86_64.
François
Index: include/bits/hashtable.h
===
--- include/bits/hashtable.h (revision 213780)
+++ include/bits/hashtable.h (working copy)
@@ -382,6 +382,17 @@
void
_M_reset() noexcept;
+ _Hashtable(const _H1 __h1, const _H2 __h2, const _Hash __h,
+ const _Equal __eq, const _ExtractKey __exk,
+ const allocator_type __a)
+ : __hashtable_base(__exk, __h1, __h2, __h, __eq),
+ __hashtable_alloc(__node_alloc_type(__a)),
+ _M_buckets(_M_single_bucket),
+ _M_bucket_count(1),
+ _M_element_count(0),
+ _M_single_bucket(nullptr)
+ { }
+
public:
// Constructor, destructor, assignment, swap
_Hashtable(size_type __bucket_hint,
@@ -407,12 +418,12 @@
// Use delegating constructors.
explicit
_Hashtable(const allocator_type __a)
- : _Hashtable(10, _H1(), _H2(), _Hash(), key_equal(),
+ : _Hashtable(_H1(), _H2(), _Hash(), key_equal(),
__key_extract(), __a)
{ }
explicit
- _Hashtable(size_type __n = 10,
+ _Hashtable(size_type __n = 0,
const _H1 __hf = _H1(),
const key_equal __eql = key_equal(),
const allocator_type __a = allocator_type())
@@ -791,15 +802,14 @@
const _H1 __h1, const _H2 __h2, const _Hash __h,
const _Equal __eq, const _ExtractKey __exk,
const allocator_type __a)
-: __hashtable_base(__exk, __h1, __h2, __h, __eq),
- __map_base(),
- __rehash_base(),
- __hashtable_alloc(__node_alloc_type(__a)),
- _M_element_count(0),
- _M_rehash_policy()
+ : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
{
- _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ auto __bkt = _M_rehash_policy._M_next_bkt(__bucket_hint);
+ if (__bkt _M_bucket_count)
+ {
+ _M_buckets = _M_allocate_buckets(__bkt);
+ _M_bucket_count = __bkt;
+ }
}
templatetypename _Key, typename _Value,
@@ -814,20 +824,20 @@
const _H1 __h1, const _H2 __h2, const _Hash __h,
const _Equal __eq, const _ExtractKey __exk,
const allocator_type __a)
- : __hashtable_base(__exk, __h1, __h2, __h, __eq),
- __map_base(),
- __rehash_base(),
- __hashtable_alloc(__node_alloc_type(__a)),
- _M_element_count(0),
- _M_rehash_policy()
+ : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
{
auto __nb_elems = __detail::__distance_fw(__f, __l);
- _M_bucket_count =
+ auto __bkt_count =
_M_rehash_policy._M_next_bkt(
std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
__bucket_hint));
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ if
Re: [patch] No allocation for empty unordered containers
On Tue, 12 Aug 2014, François Dumont wrote: Based on your feedbacks I think we should stay with just targeting good QoI by not allocating on default construction. As I said the noexcept qualification would need to not conform strictly to the Standard. The standard explicitly says that you may add noexcept wherever you like. It is constexpr that we can only add in GNU mode. -- Marc Glisse
Re: [patch] No allocation for empty unordered containers
On 12/08/2014 21:39, Marc Glisse wrote: On Tue, 12 Aug 2014, François Dumont wrote: Based on your feedbacks I think we should stay with just targeting good QoI by not allocating on default construction. As I said the noexcept qualification would need to not conform strictly to the Standard. The standard explicitly says that you may add noexcept wherever you like. It is constexpr that we can only add in GNU mode. That's not what I meant. For unordered containers there is no real default constructor. it is in fact a constructor with parameters which have all default values. This is why you can only say that it won't throw at runtime and so you can't qualify it noexcept. François
Re: [patch] No allocation for empty unordered containers
On 25/07/14 22:53 +0200, François Dumont wrote:
Hi
I think I never get feedback regarding this patch proposal. Note
I've been trying to weigh up the pros and cons and am unsure what's
best, but I think my preference is to have a noexcept default
constructor. Unless you hear any objections in the next 48 hours
please go ahead and commit this to trunk, thanks
that if accepted the doc will have to be updated regarding the default
hint value.
Good point.
Thanks
On 03/06/2014 22:44, François Dumont wrote:
Hi
Thanks to the single bucket introduced to make move semantic
noexcept we can also avoid some over allocations. Here is a patch to
avoid any allocation on default instantiation, on range constructor
when range is empty and on construction from an initialization list
when this list is empty too. I had to make all default hint value to
0 so that if this value is used the rehash policy next bucket
returns 1 bucket.
I don't know if you had in mind to noexcept qualify the default
constructor but it would mean to have a real default constructor and
another to deal with the hint which wouldn't match the Standard so
no noexcept qualification at the moment.
Tested under Linux x86_64.normal debug and profile modes.
2014-06-03 François Dumont fdum...@gcc.gnu.org
* include/bits/hashtable.h: Make use of the internal single bucket to
limit allocation as long as container remains empty.
* include/bits/unordered_map.h: Set default bucket hint to 0 in
constructors to avoid allocation.
* include/bits/unordered_set.h: Likewise.
* include/debug/unordered_map: Likewise.
* include/debug/unordered_set: Likewise.
* include/profile/unordered_map: Likewise.
* include/profile/unordered_set: Likewise.
* src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
Returns 1 for hint 0.
* testsuite/23_containers/unordered_map/allocator/
empty_instantiation.cc:New.
* testsuite/23_containers/unordered_multimap/allocator/
empty_instantiation.cc:New.
* testsuite/23_containers/unordered_set/allocator/
empty_instantiation.cc: New.
* testsuite/23_containers/unordered_multiset/allocator/
empty_instantiation.cc: New.
Ok to commit ?
François
Index: include/bits/hashtable.h
===
--- include/bits/hashtable.h(revision 211144)
+++ include/bits/hashtable.h(working copy)
@@ -407,12 +407,12 @@
// Use delegating constructors.
explicit
_Hashtable(const allocator_type __a)
- : _Hashtable(10, _H1(), _H2(), _Hash(), key_equal(),
+ : _Hashtable(0, _H1(), _H2(), _Hash(), key_equal(),
__key_extract(), __a)
{ }
explicit
- _Hashtable(size_type __n = 10,
+ _Hashtable(size_type __n = 0,
const _H1 __hf = _H1(),
const key_equal __eql = key_equal(),
const allocator_type __a = allocator_type())
@@ -792,14 +792,18 @@
const _Equal __eq, const _ExtractKey __exk,
const allocator_type __a)
: __hashtable_base(__exk, __h1, __h2, __h, __eq),
- __map_base(),
- __rehash_base(),
__hashtable_alloc(__node_alloc_type(__a)),
+ _M_buckets(_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(0),
- _M_rehash_policy()
+ _M_single_bucket(nullptr)
{
- _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ auto __bkt_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
+ if (_M_bucket_count != __bkt_count)
+ {
+ _M_bucket_count = __bkt_count;
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ }
}
templatetypename _Key, typename _Value,
@@ -815,19 +819,24 @@
const _Equal __eq, const _ExtractKey __exk,
const allocator_type __a)
: __hashtable_base(__exk, __h1, __h2, __h, __eq),
- __map_base(),
- __rehash_base(),
__hashtable_alloc(__node_alloc_type(__a)),
+ _M_buckets(_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(0),
- _M_rehash_policy()
+ _M_single_bucket(nullptr)
{
auto __nb_elems = __detail::__distance_fw(__f, __l);
- _M_bucket_count =
+ auto __bkt_count =
_M_rehash_policy._M_next_bkt(
std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
__bucket_hint));
+
+ if (_M_bucket_count != __bkt_count)
+ {
+ _M_bucket_count = __bkt_count;
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ }
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
for (; __f != __l; ++__f)
@@ -864,14 +873,15 @@
{
// Replacement allocator cannot free existing storage.
this-_M_deallocate_nodes(_M_begin());
-
Re: [patch] No allocation for empty unordered containers
On 04/08/14 12:49 +0100, Jonathan Wakely wrote: On 25/07/14 22:53 +0200, François Dumont wrote: Hi I think I never get feedback regarding this patch proposal. Note I've been trying to weigh up the pros and cons and am unsure what's best, but I think my preference is to have a noexcept default constructor. Unless you hear any objections in the next 48 hours please go ahead and commit this to trunk, thanks I hit send too soon, I meant to say that I think this change is also needed: I don't know if you had in mind to noexcept qualify the default constructor but it would mean to have a real default constructor and another to deal with the hint which wouldn't match the Standard so no noexcept qualification at the moment. If we don't make it noexcept then I see no point in avoiding allocation. (And if the functors and allocator can throw then the noexcept might have to be condition.) So please make sure we get that change as well during stage 1.
Re: [patch] No allocation for empty unordered containers
Hi
I think I never get feedback regarding this patch proposal. Note
that if accepted the doc will have to be updated regarding the default
hint value.
Thanks
On 03/06/2014 22:44, François Dumont wrote:
Hi
Thanks to the single bucket introduced to make move semantic
noexcept we can also avoid some over allocations. Here is a patch to
avoid any allocation on default instantiation, on range constructor
when range is empty and on construction from an initialization list
when this list is empty too. I had to make all default hint value to 0
so that if this value is used the rehash policy next bucket returns 1
bucket.
I don't know if you had in mind to noexcept qualify the default
constructor but it would mean to have a real default constructor and
another to deal with the hint which wouldn't match the Standard so no
noexcept qualification at the moment.
Tested under Linux x86_64.normal debug and profile modes.
2014-06-03 François Dumont fdum...@gcc.gnu.org
* include/bits/hashtable.h: Make use of the internal single bucket to
limit allocation as long as container remains empty.
* include/bits/unordered_map.h: Set default bucket hint to 0 in
constructors to avoid allocation.
* include/bits/unordered_set.h: Likewise.
* include/debug/unordered_map: Likewise.
* include/debug/unordered_set: Likewise.
* include/profile/unordered_map: Likewise.
* include/profile/unordered_set: Likewise.
* src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
Returns 1 for hint 0.
* testsuite/23_containers/unordered_map/allocator/
empty_instantiation.cc:New.
* testsuite/23_containers/unordered_multimap/allocator/
empty_instantiation.cc:New.
* testsuite/23_containers/unordered_set/allocator/
empty_instantiation.cc: New.
* testsuite/23_containers/unordered_multiset/allocator/
empty_instantiation.cc: New.
Ok to commit ?
François
Index: include/bits/hashtable.h
===
--- include/bits/hashtable.h (revision 211144)
+++ include/bits/hashtable.h (working copy)
@@ -407,12 +407,12 @@
// Use delegating constructors.
explicit
_Hashtable(const allocator_type __a)
- : _Hashtable(10, _H1(), _H2(), _Hash(), key_equal(),
+ : _Hashtable(0, _H1(), _H2(), _Hash(), key_equal(),
__key_extract(), __a)
{ }
explicit
- _Hashtable(size_type __n = 10,
+ _Hashtable(size_type __n = 0,
const _H1 __hf = _H1(),
const key_equal __eql = key_equal(),
const allocator_type __a = allocator_type())
@@ -792,14 +792,18 @@
const _Equal __eq, const _ExtractKey __exk,
const allocator_type __a)
: __hashtable_base(__exk, __h1, __h2, __h, __eq),
- __map_base(),
- __rehash_base(),
__hashtable_alloc(__node_alloc_type(__a)),
+ _M_buckets(_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(0),
- _M_rehash_policy()
+ _M_single_bucket(nullptr)
{
- _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ auto __bkt_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
+ if (_M_bucket_count != __bkt_count)
+ {
+ _M_bucket_count = __bkt_count;
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ }
}
templatetypename _Key, typename _Value,
@@ -815,19 +819,24 @@
const _Equal __eq, const _ExtractKey __exk,
const allocator_type __a)
: __hashtable_base(__exk, __h1, __h2, __h, __eq),
- __map_base(),
- __rehash_base(),
__hashtable_alloc(__node_alloc_type(__a)),
+ _M_buckets(_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(0),
- _M_rehash_policy()
+ _M_single_bucket(nullptr)
{
auto __nb_elems = __detail::__distance_fw(__f, __l);
- _M_bucket_count =
+ auto __bkt_count =
_M_rehash_policy._M_next_bkt(
std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
__bucket_hint));
+
+ if (_M_bucket_count != __bkt_count)
+ {
+ _M_bucket_count = __bkt_count;
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ }
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
for (; __f != __l; ++__f)
@@ -864,14 +873,15 @@
{
// Replacement allocator cannot free existing storage.
this-_M_deallocate_nodes(_M_begin());
- _M_before_begin._M_nxt = nullptr;
_M_deallocate_buckets();
- _M_buckets = nullptr;
+ __hashtable_base::operator=(__ht);
std::__alloc_on_copy(__this_alloc, __that_alloc);
- __hashtable_base::operator=(__ht);
- _M_bucket_count = __ht._M_bucket_count;
+ _M_buckets = _M_single_bucket;
+ _M_bucket_count = 1;
+ _M_before_begin._M_nxt = nullptr;
_M_element_count = __ht._M_element_count;
_M_rehash_policy = __ht._M_rehash_policy;
+ _M_single_bucket = nullptr;
__try
{
_M_assign(__ht,
@@ -946,8 +956,14 @@
_M_assign(const
[patch] No allocation for empty unordered containers
Hi
Thanks to the single bucket introduced to make move semantic
noexcept we can also avoid some over allocations. Here is a patch to
avoid any allocation on default instantiation, on range constructor when
range is empty and on construction from an initialization list when this
list is empty too. I had to make all default hint value to 0 so that if
this value is used the rehash policy next bucket returns 1 bucket.
I don't know if you had in mind to noexcept qualify the default
constructor but it would mean to have a real default constructor and
another to deal with the hint which wouldn't match the Standard so no
noexcept qualification at the moment.
Tested under Linux x86_64.normal debug and profile modes.
2014-06-03 François Dumont fdum...@gcc.gnu.org
* include/bits/hashtable.h: Make use of the internal single bucket to
limit allocation as long as container remains empty.
* include/bits/unordered_map.h: Set default bucket hint to 0 in
constructors to avoid allocation.
* include/bits/unordered_set.h: Likewise.
* include/debug/unordered_map: Likewise.
* include/debug/unordered_set: Likewise.
* include/profile/unordered_map: Likewise.
* include/profile/unordered_set: Likewise.
* src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
Returns 1 for hint 0.
* testsuite/23_containers/unordered_map/allocator/
empty_instantiation.cc:New.
* testsuite/23_containers/unordered_multimap/allocator/
empty_instantiation.cc:New.
* testsuite/23_containers/unordered_set/allocator/
empty_instantiation.cc: New.
* testsuite/23_containers/unordered_multiset/allocator/
empty_instantiation.cc: New.
Ok to commit ?
François
Index: include/bits/hashtable.h
===
--- include/bits/hashtable.h (revision 211144)
+++ include/bits/hashtable.h (working copy)
@@ -407,12 +407,12 @@
// Use delegating constructors.
explicit
_Hashtable(const allocator_type __a)
- : _Hashtable(10, _H1(), _H2(), _Hash(), key_equal(),
+ : _Hashtable(0, _H1(), _H2(), _Hash(), key_equal(),
__key_extract(), __a)
{ }
explicit
- _Hashtable(size_type __n = 10,
+ _Hashtable(size_type __n = 0,
const _H1 __hf = _H1(),
const key_equal __eql = key_equal(),
const allocator_type __a = allocator_type())
@@ -792,14 +792,18 @@
const _Equal __eq, const _ExtractKey __exk,
const allocator_type __a)
: __hashtable_base(__exk, __h1, __h2, __h, __eq),
- __map_base(),
- __rehash_base(),
__hashtable_alloc(__node_alloc_type(__a)),
+ _M_buckets(_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(0),
- _M_rehash_policy()
+ _M_single_bucket(nullptr)
{
- _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ auto __bkt_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
+ if (_M_bucket_count != __bkt_count)
+ {
+ _M_bucket_count = __bkt_count;
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ }
}
templatetypename _Key, typename _Value,
@@ -815,19 +819,24 @@
const _Equal __eq, const _ExtractKey __exk,
const allocator_type __a)
: __hashtable_base(__exk, __h1, __h2, __h, __eq),
- __map_base(),
- __rehash_base(),
__hashtable_alloc(__node_alloc_type(__a)),
+ _M_buckets(_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(0),
- _M_rehash_policy()
+ _M_single_bucket(nullptr)
{
auto __nb_elems = __detail::__distance_fw(__f, __l);
- _M_bucket_count =
+ auto __bkt_count =
_M_rehash_policy._M_next_bkt(
std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
__bucket_hint));
+
+ if (_M_bucket_count != __bkt_count)
+ {
+ _M_bucket_count = __bkt_count;
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ }
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
for (; __f != __l; ++__f)
@@ -864,14 +873,15 @@
{
// Replacement allocator cannot free existing storage.
this-_M_deallocate_nodes(_M_begin());
- _M_before_begin._M_nxt = nullptr;
_M_deallocate_buckets();
- _M_buckets = nullptr;
+ __hashtable_base::operator=(__ht);
std::__alloc_on_copy(__this_alloc, __that_alloc);
- __hashtable_base::operator=(__ht);
- _M_bucket_count = __ht._M_bucket_count;
+ _M_buckets = _M_single_bucket;
+ _M_bucket_count = 1;
+ _M_before_begin._M_nxt = nullptr;
_M_element_count = __ht._M_element_count;
_M_rehash_policy = __ht._M_rehash_policy;
+ _M_single_bucket = nullptr;
__try
{
_M_assign(__ht,
@@ -946,8 +956,14 @@
_M_assign(const _Hashtable __ht, const _NodeGenerator __node_gen)
{
__bucket_type* __buckets = nullptr;
- if (!_M_buckets)
- _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
+ if (_M_bucket_count !=
