std::vector<bool> fix & enhancements

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

std::vector<bool> fix & enhancements

François Dumont-2
Following Marc Glisse change to ignore _M_start offset I wanted to go a
little step further and just remove it in _GLIBCXX_INLINE_VERSION mode.

I also fix a regression we already fixed on mainstream std::vector
regarding noexcept qualification of move constructor with allocator.

And I implemented the same optimizations than in std::vector for
allocators always comparing equals and for the std::swap operation.

I also avoid re-implementing in vector::operator[] the same code already
implemented in iterator::operator[] but this one should perhaps go in a
different commit.


     * include/bits/stl_bvector.h
     [_GLIBCXX_INLINE_VERSION](_Bvector_impl_data::_M_start): Define as
     _Bit_type*.
     (_Bvector_impl_data(const _Bvector_impl_data&)): New.
     (_Bvector_impl_data(_Bvector_impl_data&&)): Delegate to latter.
     (_Bvector_impl_data::operator=(const _Bvector_impl_data&)): New.
(_Bvector_impl_data::_M_move_data(_Bvector_impl_data&&)): Use latter.
     (_Bvector_impl_data::_M_reset()): Likewise.
     (_Bvector_impl_data::_M_begin()): New.
     (_Bvector_impl_data::_M_cbegin()): New.
     (_Bvector_impl_data::_M_start_p()): New.
     (_Bvector_impl_data::_M_set_start(_Bit_type*)): New.
     (_Bvector_impl_data::_M_swap_data): New.
     (_Bvector_impl::_Bvector_impl(_Bvector_impl&&)): Implement explicitely.
     (_Bvector_impl::_Bvector_impl(_Bit_alloc_type&&, _Bvector_impl&&)):
New.
     (_Bvector_base::_Bvector_base(_Bvector_base&&, const allocator_type&)):
     New.
     (_Bvector_base::_M_deallocate()): Adapt.
     (vector::vector(const vector&, const allocator_type&)): Adapt.
     (vector::vector(vector&&, const allocator_type&, true_type)): New.
     (vector::vector(vector&&, const allocator_type&, false_type)): New.
     (vector::vector(vector&&, const allocator_type&)): Use latters.
     (vector::vector(const vector&, const allocator_type&)): Adapt.
     (vector::begin()): Adapt.
     (vector::cbegin()): Adapt.
     (vector::operator[](size_type)): Use iterator operator[].
     (vector::swap(vector&)): Adapt.
     (vector::flip()): Adapt.
     (vector::_M_initialize(size_type)): Adapt.
     (vector::_M_initialize_value(bool)): Adapt.
     * include/bits/vector.tcc:
     (vector<bool>::_M_reallocate(size_type)): Adapt.
     (vector<bool>::_M_fill_insert(iterator, size_type, bool)): Adapt.
     (vector<bool>::_M_insert_range<_FwdIter>(iterator, _FwdIter, _FwdIter
     std::forward_iterator_tag)): Adapt.
     (vector<bool>::_M_insert_aux(iterator, bool)): Adapt.
     (std::hash<std::vector<bool>>::operator()): Adapt.
     * testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc:
     Add check.

Tested under Linux x86_64.

Ok to commit ?

François


bvector.patch (12K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: std::vector<bool> fix & enhancements

François Dumont-2
Running tests in C++98 mode show that I had forgotten a 'return *this;'
in _Bvector_impl_data::operator=.

So here is the patch again.

On 10/30/18 7:28 AM, François Dumont wrote:

> Following Marc Glisse change to ignore _M_start offset I wanted to go
> a little step further and just remove it in _GLIBCXX_INLINE_VERSION mode.
>
> I also fix a regression we already fixed on mainstream std::vector
> regarding noexcept qualification of move constructor with allocator.
>
> And I implemented the same optimizations than in std::vector for
> allocators always comparing equals and for the std::swap operation.
>
> I also avoid re-implementing in vector::operator[] the same code
> already implemented in iterator::operator[] but this one should
> perhaps go in a different commit.
>
>
>     * include/bits/stl_bvector.h
>     [_GLIBCXX_INLINE_VERSION](_Bvector_impl_data::_M_start): Define as
>     _Bit_type*.
>     (_Bvector_impl_data(const _Bvector_impl_data&)): New.
>     (_Bvector_impl_data(_Bvector_impl_data&&)): Delegate to latter.
>     (_Bvector_impl_data::operator=(const _Bvector_impl_data&)): New.
> (_Bvector_impl_data::_M_move_data(_Bvector_impl_data&&)): Use latter.
>     (_Bvector_impl_data::_M_reset()): Likewise.
>     (_Bvector_impl_data::_M_begin()): New.
>     (_Bvector_impl_data::_M_cbegin()): New.
>     (_Bvector_impl_data::_M_start_p()): New.
>     (_Bvector_impl_data::_M_set_start(_Bit_type*)): New.
>     (_Bvector_impl_data::_M_swap_data): New.
>     (_Bvector_impl::_Bvector_impl(_Bvector_impl&&)): Implement
> explicitely.
>     (_Bvector_impl::_Bvector_impl(_Bit_alloc_type&&,
> _Bvector_impl&&)): New.
>     (_Bvector_base::_Bvector_base(_Bvector_base&&, const
> allocator_type&)):
>     New.
>     (_Bvector_base::_M_deallocate()): Adapt.
>     (vector::vector(const vector&, const allocator_type&)): Adapt.
>     (vector::vector(vector&&, const allocator_type&, true_type)): New.
>     (vector::vector(vector&&, const allocator_type&, false_type)): New.
>     (vector::vector(vector&&, const allocator_type&)): Use latters.
>     (vector::vector(const vector&, const allocator_type&)): Adapt.
>     (vector::begin()): Adapt.
>     (vector::cbegin()): Adapt.
>     (vector::operator[](size_type)): Use iterator operator[].
>     (vector::swap(vector&)): Adapt.
>     (vector::flip()): Adapt.
>     (vector::_M_initialize(size_type)): Adapt.
>     (vector::_M_initialize_value(bool)): Adapt.
>     * include/bits/vector.tcc:
>     (vector<bool>::_M_reallocate(size_type)): Adapt.
>     (vector<bool>::_M_fill_insert(iterator, size_type, bool)): Adapt.
>     (vector<bool>::_M_insert_range<_FwdIter>(iterator, _FwdIter, _FwdIter
>     std::forward_iterator_tag)): Adapt.
>     (vector<bool>::_M_insert_aux(iterator, bool)): Adapt.
>     (std::hash<std::vector<bool>>::operator()): Adapt.
>     *
> testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc:
>     Add check.
>
> Tested under Linux x86_64.
>
> Ok to commit ?
>
> François
>


bvector.patch (12K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: std::vector<bool> fix & enhancements

François Dumont-2
In reply to this post by François Dumont-2
Here is the updated patch.

I forgot that pre-C+11 we already had the default copy constructor and
assignment operators. And with the trick on definition of _M_start the
patch is much smaller.

     * include/bits/stl_bvector.h
     [_GLIBCXX_INLINE_VERSION](_Bvector_impl_data::_M_start): Define as
     _Bit_type*.
     (_Bvector_impl_data(const _Bvector_impl_data&)): Default.
     (_Bvector_impl_data(_Bvector_impl_data&&)): Delegate to latter.
     (_Bvector_impl_data::operator=(const _Bvector_impl_data&)): Default.
(_Bvector_impl_data::_M_move_data(_Bvector_impl_data&&)): Use latter.
     (_Bvector_impl_data::_M_reset()): Likewise.
     (_Bvector_impl_data::_M_swap_data): New.
     (_Bvector_impl::_Bvector_impl(_Bvector_impl&&)): Implement explicitely.
     (_Bvector_impl::_Bvector_impl(_Bit_alloc_type&&, _Bvector_impl&&)):
New.
     (_Bvector_base::_Bvector_base(_Bvector_base&&, const allocator_type&)):
     New, use latter.
     (vector::vector(vector&&, const allocator_type&, true_type)): New, use
     latter.
     (vector::vector(vector&&, const allocator_type&, false_type)): New.
     (vector::vector(vector&&, const allocator_type&)): Use latters.
     (vector::vector(const vector&, const allocator_type&)): Adapt.
     (vector::operator[](size_type)): Use iterator operator[].
     (vector::operator[](size_type) const): Use const_iterator operator[].
     (vector::swap(vector&)): Adapt.
     (vector::_M_initialize(size_type)): Adapt.
     * testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc:
     Add check.

Tested under Linux x86_64 w/o versioned namespace, w/o C++98 mode.

Ok to commit ?

François


On 10/30/18 10:59 PM, Jonathan Wakely wrote:

> On 30/10/18 07:28 +0100, François Dumont wrote:
>> Following Marc Glisse change to ignore _M_start offset I wanted to go
>> a little step further and just remove it in _GLIBCXX_INLINE_VERSION
>> mode.
>>
>> I also fix a regression we already fixed on mainstream std::vector
>> regarding noexcept qualification of move constructor with allocator.
>>
>> And I implemented the same optimizations than in std::vector for
>> allocators always comparing equals and for the std::swap operation.
>>
>> I also avoid re-implementing in vector::operator[] the same code
>> already implemented in iterator::operator[] but this one should
>> perhaps go in a different commit.
>>
>>
>>     * include/bits/stl_bvector.h
>>     [_GLIBCXX_INLINE_VERSION](_Bvector_impl_data::_M_start): Define as
>>     _Bit_type*.
>>     (_Bvector_impl_data(const _Bvector_impl_data&)): New.
>>     (_Bvector_impl_data(_Bvector_impl_data&&)): Delegate to latter.
>>     (_Bvector_impl_data::operator=(const _Bvector_impl_data&)): New.
>> (_Bvector_impl_data::_M_move_data(_Bvector_impl_data&&)): Use latter.
>>     (_Bvector_impl_data::_M_reset()): Likewise.
>>     (_Bvector_impl_data::_M_begin()): New.
>>     (_Bvector_impl_data::_M_cbegin()): New.
>>     (_Bvector_impl_data::_M_start_p()): New.
>>     (_Bvector_impl_data::_M_set_start(_Bit_type*)): New.
>>     (_Bvector_impl_data::_M_swap_data): New.
>>     (_Bvector_impl::_Bvector_impl(_Bvector_impl&&)): Implement
>> explicitely.
>>     (_Bvector_impl::_Bvector_impl(_Bit_alloc_type&&,
>> _Bvector_impl&&)): New.
>>     (_Bvector_base::_Bvector_base(_Bvector_base&&, const
>> allocator_type&)):
>>     New.
>>     (_Bvector_base::_M_deallocate()): Adapt.
>>     (vector::vector(const vector&, const allocator_type&)): Adapt.
>>     (vector::vector(vector&&, const allocator_type&, true_type)): New.
>>     (vector::vector(vector&&, const allocator_type&, false_type)): New.
>>     (vector::vector(vector&&, const allocator_type&)): Use latters.
>>     (vector::vector(const vector&, const allocator_type&)): Adapt.
>>     (vector::begin()): Adapt.
>>     (vector::cbegin()): Adapt.
>>     (vector::operator[](size_type)): Use iterator operator[].
>>     (vector::swap(vector&)): Adapt.
>>     (vector::flip()): Adapt.
>>     (vector::_M_initialize(size_type)): Adapt.
>>     (vector::_M_initialize_value(bool)): Adapt.
>>     * include/bits/vector.tcc:
>>     (vector<bool>::_M_reallocate(size_type)): Adapt.
>>     (vector<bool>::_M_fill_insert(iterator, size_type, bool)): Adapt.
>> (vector<bool>::_M_insert_range<_FwdIter>(iterator, _FwdIter, _FwdIter
>>     std::forward_iterator_tag)): Adapt.
>>     (vector<bool>::_M_insert_aux(iterator, bool)): Adapt.
>>     (std::hash<std::vector<bool>>::operator()): Adapt.
>>     *
>> testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc:
>>     Add check.
>>
>> Tested under Linux x86_64.
>>
>> Ok to commit ?
>>
>> François
>>
>
>> diff --git a/libstdc++-v3/include/bits/stl_bvector.h
>> b/libstdc++-v3/include/bits/stl_bvector.h
>> index 8fbef7a1a3a..81b4a75236d 100644
>> --- a/libstdc++-v3/include/bits/stl_bvector.h
>> +++ b/libstdc++-v3/include/bits/stl_bvector.h
>> @@ -437,7 +437,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>
>>       struct _Bvector_impl_data
>>       {
>> +#if !_GLIBCXX_INLINE_VERSION
>>     _Bit_iterator    _M_start;
>> +#else
>> +    _Bit_type*    _M_start;
>> +#endif
>
> An alternative that would require fewer changes elsewhere in the file
> would be:
>
> #if !_GLIBCXX_INLINE_VERSION
>     _Bit_iterator    _M_start;
> #else
>        // We don't need the offset field for the start pointer,
>        // it's always zero.
>        struct {
>          _Bit_type* _M_p;
>          // Allow assignment from iterators (assume offset is zero):
>          void operator=(_Bit_iterator __it) { _M_p = __it._M_p; }
>        } _M_start;
> #endif
>
> Now the rest of the file doesn't need any checks for
> _GLIBCXX_INLINE_VERSION (which I'd prefer to avoid, because it
> clutters the code up with extra conditionals for a mode that
> **nobody** uses in practice).
>
>
>>     _Bit_iterator    _M_finish;
>>     _Bit_pointer    _M_end_of_storage;
>>
>> @@ -447,32 +451,74 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>
>> #if __cplusplus >= 201103L
>>     _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept
>> -    : _M_start(__x._M_start), _M_finish(__x._M_finish)
>> -    , _M_end_of_storage(__x._M_end_of_storage)
>> +    : _Bvector_impl_data(__x)
>>     { __x._M_reset(); }
>>
>> +    _Bvector_impl_data(const _Bvector_impl_data&) = default;
>> +    _Bvector_impl_data&
>> +    operator=(const _Bvector_impl_data&) = default;
>>     void
>>     _M_move_data(_Bvector_impl_data&& __x) noexcept
>>     {
>> -      this->_M_start = __x._M_start;
>> -      this->_M_finish = __x._M_finish;
>> -      this->_M_end_of_storage = __x._M_end_of_storage;
>> +      *this = __x;
>>       __x._M_reset();
>>     }
>> +#else
>> +    _Bvector_impl_data(const _Bvector_impl_data& __x)
>> +      : _M_start(__x._M_start), _M_finish(__x._M_finish)
>> +      , _M_end_of_storage(__x._M_end_of_storage)
>> +    { }
>
> Do we need this definition? Won't the compiler generate the same thing
> for us anyway?
>
>> +    _Bvector_impl_data&
>> +    operator=(const _Bvector_impl_data& __x)
>> +    {
>> +      _M_start = __x._M_start;
>> +      _M_finish = __x._M_finish;
>> +      _M_end_of_storage = __x._M_end_of_storage;
>> +    }
>
> Same here.
>
>> +#endif
>> +
>> +    _Bit_iterator
>> +    _M_begin() const _GLIBCXX_NOEXCEPT
>> +    { return _Bit_iterator(_M_start_p(), 0); }
>> +
>> +    _Bit_const_iterator
>> +    _M_cbegin() const _GLIBCXX_NOEXCEPT
>> +    { return _Bit_const_iterator(_M_start_p(), 0); }
>> +
>> +    _Bit_type*
>> +    _M_start_p() const _GLIBCXX_NOEXCEPT
>
> We already have _M_end_addr() so would _M_begin_addr be a better name
> for this new function?
>
>> +#if !_GLIBCXX_INLINE_VERSION
>> +    { return _M_start._M_p; }
>> +#else
>> +    { return _M_start; }
>> +#endif
>
> Using the suggestion above you wouldn't need #if because return
> _M_start._M_p would always be right. But you wouldn't even need this
> function at all, the code that uses _M_start._M_p would Just Work™.
>
>
>> +    void
>> +    _M_set_start(_Bit_type* __p) _GLIBCXX_NOEXCEPT
>> +#if !_GLIBCXX_INLINE_VERSION
>> +    { _M_start._M_p = __p; }
>> +#else
>> +    { _M_start = __p; }
>> #endif
>
> You wouldn't need this function.
>
> etc. etc.
>
>
>>
>>     void
>>     _M_reset() _GLIBCXX_NOEXCEPT
>> +    { *this = _Bvector_impl_data(); }
>> +
>> +    void
>> +    _M_swap_data(_Bvector_impl_data& __x) _GLIBCXX_NOEXCEPT
>>     {
>> -      _M_start = _M_finish = _Bit_iterator();
>> -      _M_end_of_storage = _Bit_pointer();
>> +      // Do not use std::swap(_M_start, __x._M_start), etc as it loses
>> +      // information used by TBAA.
>> +      std::swap(*this, __x);
>>     }
>>       };
>>
>>       struct _Bvector_impl
>>     : public _Bit_alloc_type, public _Bvector_impl_data
>>       {
>> -    public:
>>     _Bvector_impl()
>>       _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type()) )
>
> You'll need to rebase the patch, because I just fixed a bug in this
> exception specification (r265626).
>
>>     : _Bit_alloc_type()
>


bvector.patch (7K) Download Attachment