[patch] libstdc++/61143 make unordered containers usable after move

[François Dumont]

On 15/05/2014 22:52, Jonathan Wakely wrote:
> On 15/05/14 22:20 +0200, François Dumont wrote:
>> Hi
>>
>>    Here is a proposal to fix PR 61143. As explained in the PR I 
>> finally prefer to leave the container in a valid state that is to say 
>> with a non zero number of bucket, that is to say 1, after a move. 
>> This bucket is stored directly in the container so not allocated to 
>> leave the move operations noexcept qualified.
>
> Thanks for fixing this, I like the direction very much. I have a few
> comments below ...
>
>> With this evolution we could even make the default constructor 
>> noexcept but I don't think it has any interest.
>
> I tend to agree with Paolo that a noexcept default constructor might
> be useful, but let's fix the bug first and consider that later.

     ok, we will have to review the hint values but it should be easy.

>
>> Index: include/bits/hashtable.h
>> ===================================================================
>> --- include/bits/hashtable.h    (revision 210479)
>> +++ include/bits/hashtable.h    (working copy)
>> @@ -316,14 +316,37 @@
>>       size_type            _M_element_count;
>>       _RehashPolicy        _M_rehash_policy;
>>
>> +      // A single bucket used when only need 1 bucket. After move 
>> the hashtable
>> +      // is left with only 1 bucket which is not allocated so that 
>> we can have a
>> +      // noexcept move constructor.
>> +      // Note that we can't leave hashtable with 0 bucket without 
>> adding
>> +      // numerous checks in the code to avoid 0 modulus.
>> +      __bucket_type        _M_single_bucket;
>
> Does this get initialized in the constructors?
> Would it make sense to give it an initializer?
>
>      __bucket_type        _M_single_bucket = nullptr;

     This bucket is replacing those normally allocated and when they are 
allocated they are 0 initialised. So, you were right, there were one 
place where this initialization was missing which is fixed in this new 
patch. So I don't think this additional initialization is necessary.

>
>> @@ -980,12 +999,16 @@
>>     _M_move_assign(_Hashtable&& __ht, std::true_type)
>>     {
>>       this->_M_deallocate_nodes(_M_begin());
>> -      if (__builtin_expect(_M_bucket_count != 0, true))
>> -    _M_deallocate_buckets();
>> -
>> +      _M_deallocate_buckets();
>>       __hashtable_base::operator=(std::move(__ht));
>>       _M_rehash_policy = __ht._M_rehash_policy;
>> -      _M_buckets = __ht._M_buckets;
>> +      if (__builtin_expect(__ht._M_buckets != 
>> &__ht._M_single_bucket, true))
>> +    _M_buckets = __ht._M_buckets;
>
> What is the value of this->_M_single_bucket now?
>
> Should it be set to nullptr, if only to help debugging?

We are not resetting buckets to null when rehashing so unless I add more 
checks I won't be able to reset it each time.

>
>> +      if (__builtin_expect(__ht._M_buckets == 
>> &__ht._M_single_bucket, false))
>
> This check appears in a few places, I wonder if it is worth creating a
> private member function to hide the details:
>
>  bool _M_moved_from() const noexcept
>  {
>    return __builtin_expect(_M_buckets == &_M_single_bucket, false);
>  }
>
> Then just test if (__ht._M_moved_from())
>
> Usually I would think the __builtin_expect should not be inside the
> member function, so the caller decides what the expected result is,
> but I think in all cases the result is expected to be false. That
> matches how move semantics are designed: the object that gets moved
> from is expected to be going out of scope, and so will be reused in a
> minority of cases.
>
>> @@ -1139,7 +1170,14 @@
>>     {
>>       if (__ht._M_node_allocator() == this->_M_node_allocator())
>>     {
>> -      _M_buckets = __ht._M_buckets;
>> +      if (__builtin_expect(__ht._M_buckets == 
>> &__ht._M_single_bucket, false))
>
> This could be if (__ht._M_moved_from())

I hesitated in doing so and finally do so. I only prefer 
_M_use_single_bucket as we might not limit its usage to moved instances.

>
>> @@ -1193,11 +1231,21 @@
>>       std::swap(_M_bucket_count, __x._M_bucket_count);
>>       std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
>>       std::swap(_M_element_count, __x._M_element_count);
>> +      std::swap(_M_single_bucket, __x._M_single_bucket);
>>
>> +      // Fix buckets if any is pointing to its single bucket that 
>> can't be
>> +      // swapped.
>> +      if (_M_buckets == &__x._M_single_bucket)
>> +    _M_buckets = &_M_single_bucket;
>> +
>> +      if (__x._M_buckets == &_M_single_bucket)
>> +    __x._M_buckets = &__x._M_single_bucket;
>> +
>
> Does this do more work than necessary, swapping the _M_buckets
> members, then updating them again?
>
> How about removing the std::swap(_M_buckets, __x._M_buckets) above and
> doing (untested):
>
>  if (this->_M_moved_from())
>    {
>      if (__x._M_moved_from())
>        _M_buckets = &_M_single_bucket;
>      else
>        _M_buckets = __x._M_buckets;
>      __x._M_buckets = &__x._M_single_bucket;
>    }
>  else if (__x._M_moved_from())
>    {
>      __x._M_buckets = _M_buckets;
>      _M_buckets = &_M_single_bucket;
>    }
>  else
>    std::swap(_M_buckets, __x._M_buckets);
>
> Is that worth it?  I'm not sure.

Yes, with the newly introduced _M_use_single_bucket it worth it I think 
and is what I have done.

Here is the new patch limited to what I really want to commit this time.

2014-05-20  François Dumont  <fdumont@gcc.gnu.org>

     PR libstdc++/61143
     * include/bits/hashtable.h: Fix move semantic to leave hashtable in a
     usable state.
     * testsuite/23_containers/unordered_set/61143.cc: New.
     * testsuite/23_containers/unordered_set/modifiers/swap.cc: New.

Tested under Linux x86_64, ok to commit ?

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable.patch
Type: text/x-patch
Size: 14247 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20140519/2836d68c/attachment.bin>