vector<bool> _M_start and 0 offset

vector<bool> _M_start and 0 offset

[Marc Glisse]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 871 bytes --]

Hello,

as explained in the PR, the implementation of vector<bool> is weirdly 
wasteful. Preserving the ABI prevents from changing much for now, but this 
small tweak can help the compiler remove quite a bit of dead code.

I think most other direct uses of _M_start are in constructors where the 
offset has just been initialized to 0, so the compiler should already know 
enough there, but I may have missed a few relevant places where the same 
idea could be used.

I used C++11 syntax because I find it nicer, and the compiler accepts it 
in C++98 mode with just a warning, suppressed in a standard header.

Bootstrap+regtest on powerpc64le-unknown-linux-gnu.

2018-09-15  Marc Glisse  <marc.glisse@inria.fr>

         PR libstdc++/87258
 	* include/bits/stl_bvector.h (vector::begin(), vector::cbegin()):
 	Rebuild _M_start with an explicit 0 offset.

-- 
Marc Glisse

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: TEXT/x-diff; name=vbool.patch, Size: 1692 bytes --]

Index: include/bits/stl_bvector.h
===================================================================
--- include/bits/stl_bvector.h	(revision 264178)
+++ include/bits/stl_bvector.h	(working copy)
@@ -802,25 +802,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
 
 #if __cplusplus >= 201103L
       void
       assign(initializer_list<bool> __l)
       { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); }
 #endif
 
       iterator
       begin() _GLIBCXX_NOEXCEPT
-      { return this->_M_impl._M_start; }
+      { return { this->_M_impl._M_start._M_p, 0 }; }
 
       const_iterator
       begin() const _GLIBCXX_NOEXCEPT
-      { return this->_M_impl._M_start; }
+      { return { this->_M_impl._M_start._M_p, 0 }; }
 
       iterator
       end() _GLIBCXX_NOEXCEPT
       { return this->_M_impl._M_finish; }
 
       const_iterator
       end() const _GLIBCXX_NOEXCEPT
       { return this->_M_impl._M_finish; }
 
       reverse_iterator
@@ -835,21 +835,21 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       rend() _GLIBCXX_NOEXCEPT
       { return reverse_iterator(begin()); }
 
       const_reverse_iterator
       rend() const _GLIBCXX_NOEXCEPT
       { return const_reverse_iterator(begin()); }
 
 #if __cplusplus >= 201103L
       const_iterator
       cbegin() const noexcept
-      { return this->_M_impl._M_start; }
+      { return { this->_M_impl._M_start._M_p, 0 }; }
 
       const_iterator
       cend() const noexcept
       { return this->_M_impl._M_finish; }
 
       const_reverse_iterator
       crbegin() const noexcept
       { return const_reverse_iterator(end()); }
 
       const_reverse_iterator

Re: vector<bool> _M_start and 0 offset

[Jonathan Wakely]

On 15/09/18 14:27 +0200, Marc Glisse wrote:
>Hello,
>
>as explained in the PR, the implementation of vector<bool> is weirdly 
>wasteful. Preserving the ABI prevents from changing much for now, but 
>this small tweak can help the compiler remove quite a bit of dead 
>code.
>
>I think most other direct uses of _M_start are in constructors where 
>the offset has just been initialized to 0, so the compiler should 
>already know enough there, but I may have missed a few relevant places 
>where the same idea could be used.
>
>I used C++11 syntax because I find it nicer, and the compiler accepts 
>it in C++98 mode with just a warning, suppressed in a standard header.
>
>Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
>
>2018-09-15  Marc Glisse  <marc.glisse@inria.fr>
>
>        PR libstdc++/87258
>	* include/bits/stl_bvector.h (vector::begin(), vector::cbegin()):
>	Rebuild _M_start with an explicit 0 offset.
>
>-- 
>Marc Glisse

>Index: include/bits/stl_bvector.h
>===================================================================
>--- include/bits/stl_bvector.h	(revision 264178)
>+++ include/bits/stl_bvector.h	(working copy)
>@@ -802,25 +802,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> #endif
> 
> #if __cplusplus >= 201103L
>       void
>       assign(initializer_list<bool> __l)
>       { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); }
> #endif
> 
>       iterator
>       begin() _GLIBCXX_NOEXCEPT
>-      { return this->_M_impl._M_start; }
>+      { return { this->_M_impl._M_start._M_p, 0 }; }
> 
>       const_iterator
>       begin() const _GLIBCXX_NOEXCEPT
>-      { return this->_M_impl._M_start; }
>+      { return { this->_M_impl._M_start._M_p, 0 }; }

Won't this fail to compile in C++98 mode?

Re: vector<bool> _M_start and 0 offset

[Marc Glisse]

On Mon, 17 Sep 2018, Jonathan Wakely wrote:

> On 15/09/18 14:27 +0200, Marc Glisse wrote:
>> Hello,
>> 
>> as explained in the PR, the implementation of vector<bool> is weirdly 
>> wasteful. Preserving the ABI prevents from changing much for now, but this 
>> small tweak can help the compiler remove quite a bit of dead code.
>> 
>> I think most other direct uses of _M_start are in constructors where the 
>> offset has just been initialized to 0, so the compiler should already know 
>> enough there, but I may have missed a few relevant places where the same 
>> idea could be used.
>> 
>> I used C++11 syntax because I find it nicer, and the compiler accepts it in 
>> C++98 mode with just a warning, suppressed in a standard header.

^^^^^^^^^^

>> Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
>> 
>> 2018-09-15  Marc Glisse  <marc.glisse@inria.fr>
>>
>>        PR libstdc++/87258
>> 	* include/bits/stl_bvector.h (vector::begin(), vector::cbegin()):
>> 	Rebuild _M_start with an explicit 0 offset.
>> 
>> -- 
>> Marc Glisse
>
>> Index: include/bits/stl_bvector.h
>> ===================================================================
>> --- include/bits/stl_bvector.h	(revision 264178)
>> +++ include/bits/stl_bvector.h	(working copy)
>> @@ -802,25 +802,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>> #endif
>> 
>> #if __cplusplus >= 201103L
>>       void
>>       assign(initializer_list<bool> __l)
>>       { _M_assign_aux(__l.begin(), __l.end(), 
>> random_access_iterator_tag()); }
>> #endif
>>
>>       iterator
>>       begin() _GLIBCXX_NOEXCEPT
>> -      { return this->_M_impl._M_start; }
>> +      { return { this->_M_impl._M_start._M_p, 0 }; }
>>
>>       const_iterator
>>       begin() const _GLIBCXX_NOEXCEPT
>> -      { return this->_M_impl._M_start; }
>> +      { return { this->_M_impl._M_start._M_p, 0 }; }
>
> Won't this fail to compile in C++98 mode?

"I used C++11 syntax because I find it nicer, and the compiler accepts it 
in C++98 mode with just a warning, suppressed in a standard header."

Even with -Wsystem-headers I don't get a warning, I have to precompile 
with -P -E then compile the result to get "warning: extended initializer 
lists only available with -std=c++11 or -std=gnu++11".

-- 
Marc Glisse

Re: vector<bool> _M_start and 0 offset

[Jonathan Wakely]

On 17/09/18 19:57 +0200, Marc Glisse wrote:
>On Mon, 17 Sep 2018, Jonathan Wakely wrote:
>
>>On 15/09/18 14:27 +0200, Marc Glisse wrote:
>>>Hello,
>>>
>>>as explained in the PR, the implementation of vector<bool> is 
>>>weirdly wasteful. Preserving the ABI prevents from changing much 
>>>for now, but this small tweak can help the compiler remove quite a 
>>>bit of dead code.
>>>
>>>I think most other direct uses of _M_start are in constructors 
>>>where the offset has just been initialized to 0, so the compiler 
>>>should already know enough there, but I may have missed a few 
>>>relevant places where the same idea could be used.
>>>
>>>I used C++11 syntax because I find it nicer, and the compiler 
>>>accepts it in C++98 mode with just a warning, suppressed in a 
>>>standard header.
>
>^^^^^^^^^^
>
>>>Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
>>>
>>>2018-09-15  Marc Glisse  <marc.glisse@inria.fr>
>>>
>>>       PR libstdc++/87258
>>>	* include/bits/stl_bvector.h (vector::begin(), vector::cbegin()):
>>>	Rebuild _M_start with an explicit 0 offset.
>>>
>>>-- 
>>>Marc Glisse
>>
>>>Index: include/bits/stl_bvector.h
>>>===================================================================
>>>--- include/bits/stl_bvector.h	(revision 264178)
>>>+++ include/bits/stl_bvector.h	(working copy)
>>>@@ -802,25 +802,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>>#endif
>>>
>>>#if __cplusplus >= 201103L
>>>      void
>>>      assign(initializer_list<bool> __l)
>>>      { _M_assign_aux(__l.begin(), __l.end(), 
>>>random_access_iterator_tag()); }
>>>#endif
>>>
>>>      iterator
>>>      begin() _GLIBCXX_NOEXCEPT
>>>-      { return this->_M_impl._M_start; }
>>>+      { return { this->_M_impl._M_start._M_p, 0 }; }
>>>
>>>      const_iterator
>>>      begin() const _GLIBCXX_NOEXCEPT
>>>-      { return this->_M_impl._M_start; }
>>>+      { return { this->_M_impl._M_start._M_p, 0 }; }
>>
>>Won't this fail to compile in C++98 mode?
>
>"I used C++11 syntax because I find it nicer, and the compiler accepts 
>it in C++98 mode with just a warning, suppressed in a standard 
>header."

Oh sorry, I just looked at the patch and replied without reading the
top bit.

>Even with -Wsystem-headers I don't get a warning, I have to precompile 
>with -P -E then compile the result to get "warning: extended 
>initializer lists only available with -std=c++11 or -std=gnu++11".

OK for trunk then.

Re: vector<bool> _M_start and 0 offset

[Ville Voutilainen]

On Mon, 17 Sep 2018 at 21:50, Jonathan Wakely <jwakely@redhat.com> wrote:
 >"I used C++11 syntax because I find it nicer, and the compiler accepts
> >it in C++98 mode with just a warning, suppressed in a standard
> >header."
>
> Oh sorry, I just looked at the patch and replied without reading the
> top bit.
>
> >Even with -Wsystem-headers I don't get a warning, I have to precompile
> >with -P -E then compile the result to get "warning: extended
> >initializer lists only available with -std=c++11 or -std=gnu++11".
>
> OK for trunk then.

Do other compilers besides gcc suppress the same way?

Re: vector<bool> _M_start and 0 offset

[Jonathan Wakely]

On 17/09/18 21:55 +0300, Ville Voutilainen wrote:
>On Mon, 17 Sep 2018 at 21:50, Jonathan Wakely <jwakely@redhat.com> wrote:
> >"I used C++11 syntax because I find it nicer, and the compiler accepts
>> >it in C++98 mode with just a warning, suppressed in a standard
>> >header."
>>
>> Oh sorry, I just looked at the patch and replied without reading the
>> top bit.
>>
>> >Even with -Wsystem-headers I don't get a warning, I have to precompile
>> >with -P -E then compile the result to get "warning: extended
>> >initializer lists only available with -std=c++11 or -std=gnu++11".
>>
>> OK for trunk then.
>
>Do other compilers besides gcc suppress the same way?

No, clang doesn't:

In file included from bv.cc:1:
In file included from /home/jwakely/gcc/latest/lib/gcc/x86_64-pc-linux-gnu/9.0.0/../../../../include/c++/9.0.0/vector:65:
/home/jwakely/gcc/latest/lib/gcc/x86_64-pc-linux-gnu/9.0.0/../../../../include/c++/9.0.0/bits/stl_bvector.h:812:16: error: non-aggregate type 'std::vector<bool, type-parameter-0-0>::iterator' (aka 'std::_Bit_iterator') cannot be initialized with an initializer list
      { return { this->_M_impl._M_start, 0 }; }
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bv.cc:6:5: note: in instantiation of member function 'std::vector<bool, std::allocator<bool> >::begin' requested here
  b.begin();
    ^
1 error generated.

So I do think we should stick to C++98 syntax.

Re: vector<bool> _M_start and 0 offset

[Jonathan Wakely]

On 17/09/18 20:10 +0100, Jonathan Wakely wrote:
>On 17/09/18 21:55 +0300, Ville Voutilainen wrote:
>>On Mon, 17 Sep 2018 at 21:50, Jonathan Wakely <jwakely@redhat.com> wrote:
>>>"I used C++11 syntax because I find it nicer, and the compiler accepts
>>>>it in C++98 mode with just a warning, suppressed in a standard
>>>>header."
>>>
>>>Oh sorry, I just looked at the patch and replied without reading the
>>>top bit.
>>>
>>>>Even with -Wsystem-headers I don't get a warning, I have to precompile
>>>>with -P -E then compile the result to get "warning: extended
>>>>initializer lists only available with -std=c++11 or -std=gnu++11".
>>>
>>>OK for trunk then.
>>
>>Do other compilers besides gcc suppress the same way?
>
>No, clang doesn't:
>
>In file included from bv.cc:1:
>In file included from /home/jwakely/gcc/latest/lib/gcc/x86_64-pc-linux-gnu/9.0.0/../../../../include/c++/9.0.0/vector:65:
>/home/jwakely/gcc/latest/lib/gcc/x86_64-pc-linux-gnu/9.0.0/../../../../include/c++/9.0.0/bits/stl_bvector.h:812:16: error: non-aggregate type 'std::vector<bool, type-parameter-0-0>::iterator' (aka 'std::_Bit_iterator') cannot be initialized with an initializer list
>     { return { this->_M_impl._M_start, 0 }; }

And for the avoidance of doubt, it's the same error if I make the
correct change to the header:

      { return { this->_M_impl._M_start._M_p, 0 }; }


>              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>bv.cc:6:5: note: in instantiation of member function 'std::vector<bool, std::allocator<bool> >::begin' requested here
> b.begin();
>   ^
>1 error generated.
>
>So I do think we should stick to C++98 syntax.
>

Re: vector<bool> _M_start and 0 offset

[Marc Glisse]

On Mon, 17 Sep 2018, Jonathan Wakely wrote:

>> Do other compilers besides gcc suppress the same way?
>
> No, clang doesn't:

What version is that? I didn't test on this exact patch, but clang 6 and
7 print, for similar code:

warning: generalized initializer lists are a C++11 extension
       [-Wc++11-extensions]

> So I do think we should stick to C++98 syntax.

What is the oldest version of clang we are supposed to support? I
thought historically we mostly supported whatever version of clang was
released *after* (i.e. clang does the support).

-- 
Marc Glisse

Re: vector<bool> _M_start and 0 offset

[Marc Glisse]

On Mon, 17 Sep 2018, Marc Glisse wrote:

> On Mon, 17 Sep 2018, Jonathan Wakely wrote:
>
>>> Do other compilers besides gcc suppress the same way?
>> 
>> No, clang doesn't:
>
> What version is that? I didn't test on this exact patch, but clang 6 and
> 7 print, for similar code:
>
> warning: generalized initializer lists are a C++11 extension
>      [-Wc++11-extensions]

Ah, with the exact code I do get an error indeed. I'll change the code :-(

>> So I do think we should stick to C++98 syntax.
>
> What is the oldest version of clang we are supposed to support? I
> thought historically we mostly supported whatever version of clang was
> released *after* (i.e. clang does the support).

-- 
Marc Glisse

Re: vector<bool> _M_start and 0 offset

[Jonathan Wakely]

On 17/09/18 21:24 +0200, Marc Glisse wrote:
>On Mon, 17 Sep 2018, Marc Glisse wrote:
>
>>On Mon, 17 Sep 2018, Jonathan Wakely wrote:
>>
>>>>Do other compilers besides gcc suppress the same way?
>>>
>>>No, clang doesn't:
>>
>>What version is that? I didn't test on this exact patch, but clang 6 and
>>7 print, for similar code:
>>
>>warning: generalized initializer lists are a C++11 extension
>>     [-Wc++11-extensions]
>
>Ah, with the exact code I do get an error indeed. I'll change the code :-(

Thanks. I feel your pain, but I think we'd need a better reason to
break it (the valid C++98 code is uglier but not too painful).

The cbegin() change can still use C++11 syntax.

>>>So I do think we should stick to C++98 syntax.
>>
>>What is the oldest version of clang we are supposed to support? I
>>thought historically we mostly supported whatever version of clang was
>>released *after* (i.e. clang does the support).
>
>-- 
>Marc Glisse

Re: vector<bool> _M_start and 0 offset

[Marc Glisse]

On Mon, 17 Sep 2018, Jonathan Wakely wrote:

> On 17/09/18 21:24 +0200, Marc Glisse wrote:
>> On Mon, 17 Sep 2018, Marc Glisse wrote:
>> 
>>> On Mon, 17 Sep 2018, Jonathan Wakely wrote:
>>> 
>>>>> Do other compilers besides gcc suppress the same way?
>>>> 
>>>> No, clang doesn't:
>>> 
>>> What version is that? I didn't test on this exact patch, but clang 6 and
>>> 7 print, for similar code:
>>> 
>>> warning: generalized initializer lists are a C++11 extension
>>>     [-Wc++11-extensions]
>> 
>> Ah, with the exact code I do get an error indeed. I'll change the code :-(
>
> Thanks. I feel your pain, but I think we'd need a better reason to
> break it (the valid C++98 code is uglier but not too painful).
>
> The cbegin() change can still use C++11 syntax.

I think I'd rather keep the 3 lines identical, or make cbegin() call
begin().

-- 
Marc Glisse

Re: vector<bool> _M_start and 0 offset

[Marc Glisse]

[-- Attachment #1: Type: text/plain, Size: 257 bytes --]

Hello,

here is a clang-friendly version of the patch (same changelog), tested a 
while ago. Is it ok or do you prefer something like the

+ if(this->_M_impl._M_start._M_offset != 0) __builtin_unreachable();

version suggested by François?

-- 
Marc Glisse

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: text/x-diff; NAME=vbool.patch, Size: 1722 bytes --]

Index: include/bits/stl_bvector.h
===================================================================
--- include/bits/stl_bvector.h	(revision 264371)
+++ include/bits/stl_bvector.h	(working copy)
@@ -802,25 +802,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
 
 #if __cplusplus >= 201103L
       void
       assign(initializer_list<bool> __l)
       { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); }
 #endif
 
       iterator
       begin() _GLIBCXX_NOEXCEPT
-      { return this->_M_impl._M_start; }
+      { return iterator(this->_M_impl._M_start._M_p, 0); }
 
       const_iterator
       begin() const _GLIBCXX_NOEXCEPT
-      { return this->_M_impl._M_start; }
+      { return const_iterator(this->_M_impl._M_start._M_p, 0); }
 
       iterator
       end() _GLIBCXX_NOEXCEPT
       { return this->_M_impl._M_finish; }
 
       const_iterator
       end() const _GLIBCXX_NOEXCEPT
       { return this->_M_impl._M_finish; }
 
       reverse_iterator
@@ -835,21 +835,21 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       rend() _GLIBCXX_NOEXCEPT
       { return reverse_iterator(begin()); }
 
       const_reverse_iterator
       rend() const _GLIBCXX_NOEXCEPT
       { return const_reverse_iterator(begin()); }
 
 #if __cplusplus >= 201103L
       const_iterator
       cbegin() const noexcept
-      { return this->_M_impl._M_start; }
+      { return const_iterator(this->_M_impl._M_start._M_p, 0); }
 
       const_iterator
       cend() const noexcept
       { return this->_M_impl._M_finish; }
 
       const_reverse_iterator
       crbegin() const noexcept
       { return const_reverse_iterator(end()); }
 
       const_reverse_iterator

Re: vector<bool> _M_start and 0 offset

[Jonathan Wakely]

On 29/09/18 10:56 +0200, Marc Glisse wrote:
>Hello,
>
>here is a clang-friendly version of the patch (same changelog), tested 
>a while ago. Is it ok or do you prefer something like the
>
>+ if(this->_M_impl._M_start._M_offset != 0) __builtin_unreachable();
>
>version suggested by François?

I don't think __builtin_unreachable would improve the clarity of the code.

The patch is OK for trunk, thanks.

Re: vector<bool> _M_start and 0 offset

[Jonathan Wakely]

On 17/09/18 21:18 +0200, Marc Glisse wrote:
>On Mon, 17 Sep 2018, Jonathan Wakely wrote:
>
>>>Do other compilers besides gcc suppress the same way?
>>
>>No, clang doesn't:
>
>What version is that? I didn't test on this exact patch, but clang 6 and
>7 print, for similar code:
>
>warning: generalized initializer lists are a C++11 extension
>      [-Wc++11-extensions]

A 5 month old build from the source repo:

clang version 7.0.0 (https://git.llvm.org/git/clang.git 1a4f56e161a5ab24aa022f7e8a754e71fa5347a1) (https://git.llvm.org/git/llvm.git afb8c1fed21eb4848d86f2d28e9cb3afcfbb2656)

With -Wsystem-headers it gives the -Wc++11-extensions warning, but if
the begin() member function is actually called then it gives the
error, even without -Wsystem-headers.


>>So I do think we should stick to C++98 syntax.
>
>What is the oldest version of clang we are supposed to support? I
>thought historically we mostly supported whatever version of clang was
>released *after* (i.e. clang does the support).

There's no precise policy. I generally try to keep the most recent one
or two releases working though.

But usually when we introduce something that needs a recent Clang it's
bleeding edge stuff like new C++17 or C++2a support. In that case, I
think it's fine to require a new Clang to use new libstdc++ headers.
For std::vector<bool> in C++98 mode it would be unfortunate to require
the latest and greatest version.