Improve relocation

[Marc Glisse]

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 <***@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.

[Marc Glisse]

ping?

Post by Marc Glisse
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.
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.
Add parameter for meta-programming.
(__relocate_a_1, __relocate_a): Add noexcept specification.
* include/bits/stl_vector.h (__use_relocate): Test __relocate_a.

[Jonathan Wakely]

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.

[Marc Glisse]

Post by Jonathan Wakely

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 :-(

Post by Jonathan Wakely
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."

[Jonathan Wakely]

Post by Marc Glisse

Post by Jonathan Wakely

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 :-(

Post by Jonathan Wakely
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?

[Marc Glisse]

Post by Jonathan Wakely

"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.

Post by Jonathan Wakely
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.