[PATCH] Optimize std::advance for single increments

[Jonathan Wakely]

LWG 2931 suggests a new overload of std::next for the default n==1
case, because it can be simpler for some random access iterators to do
++i than i += 1, e.g. for std::deque::iterator.

I've suggested we close that issue as NAD, because we don't need a new
overload to do that, and here's the proof. This performs the same
optimisation when the argument to __advance<RandomAccessIterator> is
known at compile-time to be +1 or -1, as is the case when called from
std::next(i) or std::prev(i).

This makes the generated assembly for
std::next<std::deque<T,A>::iterator>(i) quite a lot shorter.

In practice we probably don't need the optimisation in std::advance,
only in std::next and std::prev, because it would be very unusual to
call std::advance(i, 1) or std::advance(i, -1) when you could just do
++i or --i. But doing it here means we handle the std::next/std::prev
cases, and std::advance, and any unusual cases like std::next(i, -1).

	* include/bits/stl_iterator_base_funcs.h
	(__advance<_RandomAccessIterator, _Distance>): Optimize for next/prev
	cases where incrementing or decrementing a single step.

Tested powerpc64le-linux, committed to trunk.

-------------- next part --------------
commit 95e8802ccde0fe86462b28897c78e57c1c0866cc
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Mon Jun 5 11:13:31 2017 +0100

    Optimize std::advance for single increments
    
    	* include/bits/stl_iterator_base_funcs.h
    	(__advance<_RandomAccessIterator, _Distance>): Optimize for next/prev
    	cases where incrementing or decrementing a single step.

diff --git a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
index ce6c3d2..e14a22c 100644
--- a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
+++ b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
@@ -177,7 +177,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // concept requirements
       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 				  _RandomAccessIterator>)
-      __i += __n;
+      if (__builtin_constant_p(__n) && __n == 1)
+	++__i;
+      else if (__builtin_constant_p(__n) && __n == -1)
+	--__i;
+      else
+	__i += __n;
     }
 
   /**