Default std::vector<bool> default and move constructor

Hi

     Following what I have started on RbTree here is a patch to default 
implementation of default and move constructors on std::vector<bool>.

     As in _Rb_tree_impl the default allocator is not value initialized 
anymore. We could add a small helper type arround the allocator to do 
this value initialization per default. Should I do so ?

     I also added some optimizations. Especially replacement of 
std::fill with calls to __builtin_memset. Has anyone ever proposed to 
optimize std::fill in such a way ? It would require a test on the value 
used to fill the range but it might worth this additional runtime check, 
no ?

     * include/bits/stl_bvector.h (_Bvector_impl_data): New.
     (_Bvector_impl): Inherits from latter.
     (_Bvector_impl(_Bit_alloc_type&&)): Delete.
     (_Bvector_impl(_Bvector_impl&&)): New, default.
     (_Bvector_base()): Default.
     (_Bvector_base(_Bvector_base&&)): Default.
     (_Bvector_base::_M_move_data(_Bvector_base&&)): New.
     (vector(vector&&, const allocator_type&)): Use latter.
     (vector<bool>::operator=(vector&&)): Likewise.
     (vector<bool>::vector()): Default.
     (vector<bool>::assign(_InputIterator, _InputIterator)): Use
     _M_assign_aux.
     (vector<bool>::assign(initializer_list<bool>)): Likewise.
     (vector<bool>::_M_initialize_value(bool)): New.
     (vector<bool>(size_type, const bool&, const allocator_type&)): Use
     latter.
     (vector<bool>::_M_initialize_dispatch(_Integer, _Integer, 
__true_type)):
     Likewise.
     (vector<bool>::_M_fill_assign(size_t, bool)): Likewise.

     Tested under Linux x86_64 normal mode, with and without versioned 
namespace.

Ok to commit ?

François

On Mon, 15 May 2017, François Dumont wrote:

>    I also added some optimizations. Especially replacement of std::fill with 
> calls to __builtin_memset. Has anyone ever proposed to optimize std::fill in 
> such a way ? It would require a test on the value used to fill the range but 
> it might worth this additional runtime check, no ?

Note that with -O3, gcc recognizes the pattern in std::fill and generates 
a call to memset (there is a bit too much extra code around the memset, 
but a couple match.pd transformations should fix that). That doesn't mean 
we can't save it the work. If you want to save the runtime check, there is 
always __builtin_constant_p...

The __fill_bvector part of the fill overload for vector<bool> could do 
with some improvements as well. Looping is unnecessary, one just needs to 
produce the right mask and and or or with it, that shouldn't take more 
than 4 instructions or so.

There was a time when I suggested overloading std::count and std::find in 
order to use __builtin_popcount, etc. But from what I've seen of committee 
discussions, I expect that there will be specialized algorithms (possibly 
member functions) eventually, making the overload less useful.

On 15/05/2017 21:31, Marc Glisse wrote:
> On Mon, 15 May 2017, François Dumont wrote:
>
>>    I also added some optimizations. Especially replacement of 
>> std::fill with calls to __builtin_memset. Has anyone ever proposed to 
>> optimize std::fill in such a way ? It would require a test on the 
>> value used to fill the range but it might worth this additional 
>> runtime check, no ?
>
> Note that with -O3, gcc recognizes the pattern in std::fill and 
> generates a call to memset (there is a bit too much extra code around 
> the memset, but a couple match.pd transformations should fix that).

Good to know, at least g++ will be able to spend more time on other 
optimizations :-) What is match.pd ?

> That doesn't mean we can't save it the work. If you want to save the 
> runtime check, there is always __builtin_constant_p...

Good point, I will give it a try.

>
> The __fill_bvector part of the fill overload for vector<bool> could do 
> with some improvements as well. Looping is unnecessary, one just needs 
> to produce the right mask and and or or with it, that shouldn't take 
> more than 4 instructions or so.
Yes, good idear, I'll submit another patch after this one.
>
> There was a time when I suggested overloading std::count and std::find 
> in order to use __builtin_popcount, etc. But from what I've seen of 
> committee discussions, I expect that there will be specialized 
> algorithms (possibly member functions) eventually, making the overload 
> less useful.
>
ok, thanks for those feedbacks.

François

On Tue, 16 May 2017, François Dumont wrote:

> What is match.pd ?

It is a file in gcc where we describe simple pattern-matching 
optimizations. In this case, IIRC, the missing transformations were
* ptr + n == ptr + 1 --> n == 1 (we already do it if 1 is replaced by a 
variable or 0)
* ((n/8)+1)*8 --> n+8 when the division is known to be exact

On 15/05/17 19:57 +0200, François Dumont wrote:
>Hi
>
>    Following what I have started on RbTree here is a patch to default 
>implementation of default and move constructors on std::vector<bool>.
>
>    As in _Rb_tree_impl the default allocator is not value initialized 
>anymore. We could add a small helper type arround the allocator to do 
>this value initialization per default. Should I do so ?

It's required to be value-initialized, so if your patch changes that
then it's a problem.

Did we decide it's OK to do that for RB-trees? Did we actually discuss
that part of the r243379 changes?

N.B. defining these members as defaulted makes diagnostics worse, see
PR 80858, but I think we need to fix that in the compiler anyway.

On 25/05/2017 18:28, Jonathan Wakely wrote:
> On 15/05/17 19:57 +0200, François Dumont wrote:
>> Hi
>>
>>    Following what I have started on RbTree here is a patch to default 
>> implementation of default and move constructors on std::vector<bool>.
>>
>>    As in _Rb_tree_impl the default allocator is not value initialized 
>> anymore. We could add a small helper type arround the allocator to do 
>> this value initialization per default. Should I do so ?
>
> It's required to be value-initialized, so if your patch changes that
> then it's a problem.
>
> Did we decide it's OK to do that for RB-trees? Did we actually discuss
> that part of the r243379 changes?

I remember a message pointing this issue but after the commit AFAIR. I 
thought it was from Tim but I can't find it on the archive.

What is the rational of this requirement ? I started working on a type 
to do the allocator value initialization if there is no default 
constructor but it seems quite complicated to do so. It is quite sad 
that we can't fully benefit from this nice C++11 feature just because of 
this requirement. If there is any initialization needed it doesn't sound 
complicated to provide a default constructor.

>
>
> N.B. defining these members as defaulted makes diagnostics worse, see
> PR 80858, but I think we need to fix that in the compiler anyway.
>
>
Ok, I hope compiler will be able to improve this situtation.

François

On 26/05/17 23:13 +0200, François Dumont wrote:
>On 25/05/2017 18:28, Jonathan Wakely wrote:
>>On 15/05/17 19:57 +0200, François Dumont wrote:
>>>Hi
>>>
>>>   Following what I have started on RbTree here is a patch to 
>>>default implementation of default and move constructors on 
>>>std::vector<bool>.
>>>
>>>   As in _Rb_tree_impl the default allocator is not value 
>>>initialized anymore. We could add a small helper type arround the 
>>>allocator to do this value initialization per default. Should I do 
>>>so ?
>>
>>It's required to be value-initialized, so if your patch changes that
>>then it's a problem.
>>
>>Did we decide it's OK to do that for RB-trees? Did we actually discuss
>>that part of the r243379 changes?
>
>I remember a message pointing this issue but after the commit AFAIR. I 
>thought it was from Tim but I can't find it on the archive.
>
>What is the rational of this requirement ? I started working on a type 
>to do the allocator value initialization if there is no default 
>constructor but it seems quite complicated to do so. It is quite sad 
>that we can't fully benefit from this nice C++11 feature just because 
>of this requirement. If there is any initialization needed it doesn't 
>sound complicated to provide a default constructor.

The standard says that the default constructor is:

  vector() : vector(Allocator()) { }

That value-initializes the allocator. If the allocator type behaves
differently for value-init and default-init (e.g. it has data members
that are left uninitialized by default-init) then the difference
matters. If you change the code so it only does default-init of the
allocator then you will introduce an observable difference.

I don't see any requirement that a DefaultConstructible allocator
cannot leave members uninitialized, so that means the standard
requires default construction of vector<bool> to value-init the
allocator. Not default-init.

Here's an allocator that behaves differently if value-initialized or
default-initialized:

template<typename T>
struct Alloc {
  using value_type = T;
  Alloc() = default;
  template<typename U>
    Alloc(const Alloc<U>& a) : mem(a.mem) { }
  T* allocate(std::size_t n) {
    if (mem)
      throw 1;
    return std::allocator<T>().allocate(n);
  }
  void deallocate(T* p, std::size_t n) {
    std::allocator<T>().deallocate(p, n);
  }

  int mem;
};

template<typename T, typename U>
bool operator==(const Alloc<T>& t, const Alloc<U>& u)
{ return t.mem == u.mem; }

template<typename T, typename U>
bool operator!=(const Alloc<T>& t, const Alloc<U>& u)
{ return !(t == u); }