Improve relocation

Hello,

here are some tweaks so that I can usefully mark deque as trivially 
relocatable. It includes more noexcept(auto) madness. For __relocate_a_1, 
I should also test if copying, ++ and != are noexcept, but I wanted to ask 
first because there might be restrictions on what iterators are allowed to 
do, even if I didn't see them. Also, the current code already ignores 
those, so it may as well be fixed in another patch.

Allocators are complicated. I specialized only for the default allocator, 
because that's by far the one that is used the most, and I have much less 
risk of getting it wrong. Some allocator expert is welcome to make a 
better test. I do not know in details how deque is implemented. A quick 
look seemed to show that trivial relocation should be fine, but I would 
appreciate a confirmation.

The extra parameter for __is_trivially_relocatable is not used, but I 
expect it will be as soon as the specializations of 
__is_trivially_relocatable become more advanced.

If I use or specialize __is_trivially_relocatable in many places, this 
forces to #include bits/stl_uninitialized.h in many places. I wonder if I 
should move some of that stuff. Since I may use it in std::swap, 
bits/move.h looks like a sensible place for the core pieces 
(__is_trivially_relocatable, and __relocate_object if I ever create that). 
That or type_traits.

Regtested on gcc112. I manually checked that there was a speed-up for 
operations on vector<deque<int>>, although doing any kind of benchmarking 
on gcc112 is hard, I'll test locally next time.

2018-10-26  Marc Glisse  <marc.glisse@inria.fr>

 	PR libstdc++/87106
 	* include/bits/stl_algobase.h: Include <type_traits>.
 	(__niter_base): Add noexcept specification.
 	* include/bits/stl_deque.h: Include <bits/stl_uninitialized.h>.
 	(__is_trivially_relocatable): Specialize for deque.
 	* include/bits/stl_iterator.h: Include <type_traits>.
 	(__niter_base): Add noexcept specification.
 	* include/bits/stl_uninitialized.h (__is_trivially_relocatable):
 	Add parameter for meta-programming.
 	(__relocate_a_1, __relocate_a): Add noexcept specification.
 	* include/bits/stl_vector.h (__use_relocate): Test __relocate_a.

ping?

On Fri, 26 Oct 2018, Marc Glisse wrote:

> Hello,
>
> here are some tweaks so that I can usefully mark deque as trivially 
> relocatable. It includes more noexcept(auto) madness. For __relocate_a_1, I 
> should also test if copying, ++ and != are noexcept, but I wanted to ask 
> first because there might be restrictions on what iterators are allowed to 
> do, even if I didn't see them. Also, the current code already ignores those, 
> so it may as well be fixed in another patch.
>
> Allocators are complicated. I specialized only for the default allocator, 
> because that's by far the one that is used the most, and I have much less 
> risk of getting it wrong. Some allocator expert is welcome to make a better 
> test. I do not know in details how deque is implemented. A quick look seemed 
> to show that trivial relocation should be fine, but I would appreciate a 
> confirmation.
>
> The extra parameter for __is_trivially_relocatable is not used, but I expect 
> it will be as soon as the specializations of __is_trivially_relocatable 
> become more advanced.
>
> If I use or specialize __is_trivially_relocatable in many places, this forces 
> to #include bits/stl_uninitialized.h in many places. I wonder if I should 
> move some of that stuff. Since I may use it in std::swap, bits/move.h looks 
> like a sensible place for the core pieces (__is_trivially_relocatable, and 
> __relocate_object if I ever create that). That or type_traits.
>
> Regtested on gcc112. I manually checked that there was a speed-up for 
> operations on vector<deque<int>>, although doing any kind of benchmarking on 
> gcc112 is hard, I'll test locally next time.
>
> 2018-10-26  Marc Glisse  <marc.glisse@inria.fr>
>
> 	PR libstdc++/87106
> 	* include/bits/stl_algobase.h: Include <type_traits>.
> 	(__niter_base): Add noexcept specification.
> 	* include/bits/stl_deque.h: Include <bits/stl_uninitialized.h>.
> 	(__is_trivially_relocatable): Specialize for deque.
> 	* include/bits/stl_iterator.h: Include <type_traits>.
> 	(__niter_base): Add noexcept specification.
> 	* include/bits/stl_uninitialized.h (__is_trivially_relocatable):
> 	Add parameter for meta-programming.
> 	(__relocate_a_1, __relocate_a): Add noexcept specification.
> 	* include/bits/stl_vector.h (__use_relocate): Test __relocate_a.

On 26/10/18 14:02 +0200, Marc Glisse wrote:
>Index: libstdc++-v3/include/bits/stl_iterator.h
>===================================================================
>--- libstdc++-v3/include/bits/stl_iterator.h	(revision 265522)
>+++ libstdc++-v3/include/bits/stl_iterator.h	(working copy)
>@@ -59,20 +59,24 @@
> 
> #ifndef _STL_ITERATOR_H
> #define _STL_ITERATOR_H 1
> 
> #include <bits/cpp_type_traits.h>
> #include <ext/type_traits.h>
> #include <bits/move.h>
> #include <bits/ptr_traits.h>
> 
> #if __cplusplus > 201402L

I think this should be >= 201103L, no?

OK for trunk (with that #if changed, if appropriate).

Thanks.

On Thu, 22 Nov 2018, Jonathan Wakely wrote:

> On 26/10/18 14:02 +0200, Marc Glisse wrote:
>> Index: libstdc++-v3/include/bits/stl_iterator.h
>> ===================================================================
>> --- libstdc++-v3/include/bits/stl_iterator.h	(revision 265522)
>> +++ libstdc++-v3/include/bits/stl_iterator.h	(working copy)
>> @@ -59,20 +59,24 @@
>> 
>> #ifndef _STL_ITERATOR_H
>> #define _STL_ITERATOR_H 1
>> 
>> #include <bits/cpp_type_traits.h>
>> #include <ext/type_traits.h>
>> #include <bits/move.h>
>> #include <bits/ptr_traits.h>
>> 
>> #if __cplusplus > 201402L
>
> I think this should be >= 201103L, no?

Ah, yes, I guess I started from a copy-paste and got interrupted before 
updating it :-(

> OK for trunk (with that #if changed, if appropriate).

Thanks. Re-tested and committed. Do you have an opinion on the following 
item, which may be a bug in the current code?

"For __relocate_a_1, I should also test if copying, ++ and != are 
noexcept, but I wanted to ask first because there might be restrictions on 
what iterators are allowed to do, even if I didn't see them."

On 22/11/18 19:10 +0100, Marc Glisse wrote:
>On Thu, 22 Nov 2018, Jonathan Wakely wrote:
>
>>On 26/10/18 14:02 +0200, Marc Glisse wrote:
>>>Index: libstdc++-v3/include/bits/stl_iterator.h
>>>===================================================================
>>>--- libstdc++-v3/include/bits/stl_iterator.h	(revision 265522)
>>>+++ libstdc++-v3/include/bits/stl_iterator.h	(working copy)
>>>@@ -59,20 +59,24 @@
>>>
>>>#ifndef _STL_ITERATOR_H
>>>#define _STL_ITERATOR_H 1
>>>
>>>#include <bits/cpp_type_traits.h>
>>>#include <ext/type_traits.h>
>>>#include <bits/move.h>
>>>#include <bits/ptr_traits.h>
>>>
>>>#if __cplusplus > 201402L
>>
>>I think this should be >= 201103L, no?
>
>Ah, yes, I guess I started from a copy-paste and got interrupted 
>before updating it :-(
>
>>OK for trunk (with that #if changed, if appropriate).
>
>Thanks. Re-tested and committed. Do you have an opinion on the 
>following item, which may be a bug in the current code?
>
>"For __relocate_a_1, I should also test if copying, ++ and != are 
>noexcept, but I wanted to ask first because there might be 
>restrictions on what iterators are allowed to do, even if I didn't see 
>them."

I decided to postpone thinking about that :-)

In general iterators can throw on those operations. But for container
iterators copy construction of "a returned iterator" never throws. I
think that means that copying a singular iterator is allowed to throw,
but no container member functions ever return singular iterators.

Increment and decrement could throw, but for our implementation they
don't (and so far __relocate_a_1 is only used with pointers, or vector
or deque iterators, right?) Since we know we're using valid iterator
ranges (because we choose the begin and end iterators of the ranges
being relocated) it should also be safe to assume we never increment a
past-the-end iterator or anything else that might give an iterator a
reasom to throw.

Is that good enough, or do you want to make __relocate_a_1 general
enough to work with arbitrary iterators?

On Thu, 22 Nov 2018, Jonathan Wakely wrote:

>> "For __relocate_a_1, I should also test if copying, ++ and != are noexcept, 
>> but I wanted to ask first because there might be restrictions on what 
>> iterators are allowed to do, even if I didn't see them."
>
> I decided to postpone thinking about that :-)
>
> In general iterators can throw on those operations. But for container
> iterators copy construction of "a returned iterator" never throws. I
> think that means that copying a singular iterator is allowed to throw,
> but no container member functions ever return singular iterators.
>
> Increment and decrement could throw, but for our implementation they
> don't (and so far __relocate_a_1 is only used with pointers, or vector
> or deque iterators, right?) Since we know we're using valid iterator
> ranges (because we choose the begin and end iterators of the ranges
> being relocated) it should also be safe to assume we never increment a
> past-the-end iterator or anything else that might give an iterator a
> reasom to throw.

Indeed, I think currently we only use relocate with vector iterators, so 
it is not urgent to fix this.

> Is that good enough, or do you want to make __relocate_a_1 general
> enough to work with arbitrary iterators?

Eventually yes, but now that I think about it, as long as relocation is a 
private implementation detail, all uses are likely to be with standard 
iterators that we control, so it may not matter.

So now I agree with the "postpone" decision, thanks.