[libc++] Use std::move in numeric algorithms (P0616R0).

This patch updates algorithms in <numeric> to use std::move
based on p0616r0. Moving values instead of copying them
creates huge speed improvements (see the paper for details).

Differential Revision: https://reviews.llvm.org/D61170

6 files changed, 265 insertions, 15 deletions

diff --git a/libcxx/docs/Cxx2aStatusPaperStatus.csv b/libcxx/docs/Cxx2aStatusPaperStatus.csv
index cf476c87a130..456ac647b7a3 100644
--- a/libcxx/docs/Cxx2aStatusPaperStatus.csv
+++ b/libcxx/docs/Cxx2aStatusPaperStatus.csv
@@ -10,7 +10,7 @@
 "`P0457R2 <https://wg21.link/P0457R2>`__","LWG","String Prefix and Suffix Checking","Albuquerque","|Complete|","6.0"
 "`P0550R2 <https://wg21.link/P0550R2>`__","LWG","Transformation Trait ``remove_cvref``\ ","Albuquerque","|Complete|","6.0"
 "`P0600R1 <https://wg21.link/P0600R1>`__","LWG","nodiscard in the Library","Albuquerque","|In Progress| [#note-P0600]_","7.0"
-"`P0616R0 <https://wg21.link/P0616R0>`__","LWG","de-pessimize legacy <numeric> algorithms with std::move","Albuquerque","",""
+"`P0616R0 <https://wg21.link/P0616R0>`__","LWG","de-pessimize legacy <numeric> algorithms with std::move","Albuquerque","|Complete|","12.0"
 "`P0653R2 <https://wg21.link/P0653R2>`__","LWG","Utility to convert a pointer to a raw pointer","Albuquerque","|Complete|","6.0"
 "`P0718R2 <https://wg21.link/P0718R2>`__","LWG","Atomic shared_ptr","Albuquerque","",""
 "`P0767R1 <https://wg21.link/P0767R1>`__","CWG","Deprecate POD","Albuquerque","|Complete|","7.0"
diff --git a/libcxx/include/numeric b/libcxx/include/numeric
index 50070ded8fed..088bd7438d2b 100644
--- a/libcxx/include/numeric
+++ b/libcxx/include/numeric
@@ -163,7 +163,11 @@ _Tp
 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
 {
     for (; __first != __last; ++__first)
+#if _LIBCPP_STD_VER > 17
+        __init = _VSTD::move(__init) + *__first;
+#else
         __init = __init + *__first;
+#endif
     return __init;
 }
 
@@ -173,7 +177,11 @@ _Tp
 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOperation __binary_op)
 {
     for (; __first != __last; ++__first)
+#if _LIBCPP_STD_VER > 17
+        __init = __binary_op(_VSTD::move(__init), *__first);
+#else
         __init = __binary_op(__init, *__first);
+#endif
     return __init;
 }
 
@@ -212,7 +220,11 @@ _Tp
 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init)
 {
     for (; __first1 != __last1; ++__first1, (void) ++__first2)
+#if _LIBCPP_STD_VER > 17
+        __init = _VSTD::move(__init) + *__first1 * *__first2;
+#else
         __init = __init + *__first1 * *__first2;
+#endif
     return __init;
 }
 
@@ -223,7 +235,11 @@ inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2
               _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2)
 {
     for (; __first1 != __last1; ++__first1, (void) ++__first2)
+#if _LIBCPP_STD_VER > 17
+        __init = __binary_op1(_VSTD::move(__init), __binary_op2(*__first1, *__first2));
+#else
         __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
+#endif
     return __init;
 }
 
@@ -273,7 +289,11 @@ partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __res
         *__result = __t;
         for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)
         {
+#if _LIBCPP_STD_VER > 17
+            __t = _VSTD::move(__t) + *__first;
+#else
             __t = __t + *__first;
+#endif
             *__result = __t;
         }
     }
@@ -292,7 +312,11 @@ partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __res
         *__result = __t;
         for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)
         {
+#if _LIBCPP_STD_VER > 17
+            __t = __binary_op(_VSTD::move(__t), *__first);
+#else
             __t = __binary_op(__t, *__first);
+#endif
             *__result = __t;
         }
     }
@@ -417,13 +441,17 @@ adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterat
 {
     if (__first != __last)
     {
-        typename iterator_traits<_InputIterator>::value_type __t1(*__first);
-        *__result = __t1;
+        typename iterator_traits<_InputIterator>::value_type __acc(*__first);
+        *__result = __acc;
         for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)
         {
-            typename iterator_traits<_InputIterator>::value_type __t2(*__first);
-            *__result = __t2 - __t1;
-            __t1 = _VSTD::move(__t2);
+            typename iterator_traits<_InputIterator>::value_type __val(*__first);
+#if _LIBCPP_STD_VER > 17
+            *__result = __val - _VSTD::move(__acc);
+#else
+            *__result = __val - __acc;
+#endif
+            __acc = _VSTD::move(__val);
         }
     }
     return __result;
@@ -437,13 +465,17 @@ adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterat
 {
     if (__first != __last)
     {
-        typename iterator_traits<_InputIterator>::value_type __t1(*__first);
-        *__result = __t1;
+        typename iterator_traits<_InputIterator>::value_type __acc(*__first);
+        *__result = __acc;
         for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)
         {
-            typename iterator_traits<_InputIterator>::value_type __t2(*__first);
-            *__result = __binary_op(__t2, __t1);
-            __t1 = _VSTD::move(__t2);
+            typename iterator_traits<_InputIterator>::value_type __val(*__first);
+#if _LIBCPP_STD_VER > 17
+            *__result = __binary_op(__val, _VSTD::move(__acc));
+#else
+            *__result = __binary_op(__val, __acc);
+#endif
+            __acc = _VSTD::move(__val);
         }
     }
     return __result;
diff --git a/libcxx/test/std/numerics/numeric.ops/accumulate/accumulate_op.pass.cpp b/libcxx/test/std/numerics/numeric.ops/accumulate/accumulate_op.pass.cpp
index f2e3a6bc26c3..c2a430f370f7 100644
--- a/libcxx/test/std/numerics/numeric.ops/accumulate/accumulate_op.pass.cpp
+++ b/libcxx/test/std/numerics/numeric.ops/accumulate/accumulate_op.pass.cpp
@@ -17,11 +17,55 @@
 
 #include <numeric>
 #include <functional>
+#include <string>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
+#if TEST_STD_VER > 17
+struct rvalue_addable
+{
+    bool correctOperatorUsed = false;
+
+    // make sure the predicate is passed an rvalue and an lvalue (so check that the first argument was moved)
+    rvalue_addable operator()(rvalue_addable&& r, rvalue_addable const&) {
+        r.correctOperatorUsed = true;
+        return std::move(r);
+    }
+};
+
+rvalue_addable operator+(rvalue_addable& lhs, rvalue_addable const&)
+{
+    lhs.correctOperatorUsed = false;
+        return lhs;
+}
+
+rvalue_addable operator+(rvalue_addable&& lhs, rvalue_addable const&)
+{
+    lhs.correctOperatorUsed = true;
+    return std::move(lhs);
+}
+
+void
+test_use_move()
+{
+    rvalue_addable arr[100];
+    auto res1 = std::accumulate(arr, arr + 100, rvalue_addable());
+    auto res2 = std::accumulate(arr, arr + 100, rvalue_addable(), /*predicate=*/rvalue_addable());
+    assert(res1.correctOperatorUsed);
+    assert(res2.correctOperatorUsed);
+}
+#endif // TEST_STD_VER > 17
+
+void
+test_string()
+{
+    std::string sa[] = {"a", "b", "c"};
+    assert(std::accumulate(sa, sa + 3, std::string()) == "abc");
+    assert(std::accumulate(sa, sa + 3, std::string(), std::plus<std::string>()) == "abc");
+}
+
 template <class Iter, class T>
 void
 test(Iter first, Iter last, T init, T x)
@@ -53,5 +97,10 @@ int main(int, char**)
     test<random_access_iterator<const int*> >();
     test<const int*>();
 
-  return 0;
+#if TEST_STD_VER > 17
+    test_use_move();
+#endif // TEST_STD_VER > 17
+    test_string();
+
+    return 0;
 }
diff --git a/libcxx/test/std/numerics/numeric.ops/adjacent.difference/adjacent_difference_op.pass.cpp b/libcxx/test/std/numerics/numeric.ops/adjacent.difference/adjacent_difference_op.pass.cpp
index 9a10105d0490..f8c12abd9e2b 100644
--- a/libcxx/test/std/numerics/numeric.ops/adjacent.difference/adjacent_difference_op.pass.cpp
+++ b/libcxx/test/std/numerics/numeric.ops/adjacent.difference/adjacent_difference_op.pass.cpp
@@ -20,11 +20,61 @@
 
 #include <numeric>
 #include <functional>
+#include <string>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
+#if TEST_STD_VER > 17
+struct rvalue_subtractable
+{
+    bool correctOperatorUsed = false;
+
+    // make sure the predicate is passed an rvalue and an lvalue (so check that the first argument was moved)
+    rvalue_subtractable operator()(rvalue_subtractable const&, rvalue_subtractable&& r) {
+        r.correctOperatorUsed = true;
+        return std::move(r);
+    }
+};
+
+rvalue_subtractable operator-(rvalue_subtractable const&, rvalue_subtractable& rhs)
+{
+    rhs.correctOperatorUsed = false;
+    return rhs;
+}
+
+rvalue_subtractable operator-(rvalue_subtractable const&, rvalue_subtractable&& rhs)
+{
+    rhs.correctOperatorUsed = true;
+    return std::move(rhs);
+}
+
+void
+test_use_move()
+{
+    const std::size_t size = 100;
+    rvalue_subtractable arr[size];
+    rvalue_subtractable res1[size];
+    rvalue_subtractable res2[size];
+    std::adjacent_difference(arr, arr + size, res1);
+    std::adjacent_difference(arr, arr + size, res2, /*predicate=*/rvalue_subtractable());
+    // start at 1 because the first element is not moved
+    for (unsigned i = 1; i < size; ++i) assert(res1[i].correctOperatorUsed);
+    for (unsigned i = 1; i < size; ++i) assert(res2[i].correctOperatorUsed);
+}
+#endif // TEST_STD_VER > 17
+
+void
+test_string()
+{
+    std::string sa[] = {"a", "b", "c"};
+    std::string sr[] = {"a", "ba", "cb"};
+    std::string output[3];
+    std::adjacent_difference(sa, sa + 3, output, std::plus<std::string>());
+    for (unsigned i = 0; i < 3; ++i) assert(output[i] == sr[i]);
+}
+
 template <class InIter, class OutIter>
 void
 test()
@@ -116,5 +166,10 @@ int main(int, char**)
     std::adjacent_difference(x, x+3, y, std::minus<X>());
 #endif
 
-  return 0;
+#if TEST_STD_VER > 17
+    test_use_move();
+#endif // TEST_STD_VER > 17
+    test_string();
+
+    return 0;
 }
diff --git a/libcxx/test/std/numerics/numeric.ops/inner.product/inner_product_comp.pass.cpp b/libcxx/test/std/numerics/numeric.ops/inner.product/inner_product_comp.pass.cpp
index 3f9ed7ee8951..be325b65ec29 100644
--- a/libcxx/test/std/numerics/numeric.ops/inner.product/inner_product_comp.pass.cpp
+++ b/libcxx/test/std/numerics/numeric.ops/inner.product/inner_product_comp.pass.cpp
@@ -21,11 +21,65 @@
 
 #include <numeric>
 #include <functional>
+#include <string>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
+#if TEST_STD_VER > 17
+struct do_nothing_op
+{
+    template<class T>
+    T operator()(T a, T)
+    { return a; }
+};
+
+struct rvalue_addable
+{
+    bool correctOperatorUsed = false;
+
+    rvalue_addable operator*(rvalue_addable const&) { return *this; }
+
+    // make sure the predicate is passed an rvalue and an lvalue (so check that the first argument was moved)
+    rvalue_addable operator()(rvalue_addable&& r, rvalue_addable const&) {
+        r.correctOperatorUsed = true;
+        return std::move(r);
+    }
+};
+
+rvalue_addable operator+(rvalue_addable& lhs, rvalue_addable const&)
+{
+    lhs.correctOperatorUsed = false;
+    return lhs;
+}
+
+rvalue_addable operator+(rvalue_addable&& lhs, rvalue_addable const&)
+{
+    lhs.correctOperatorUsed = true;
+    return std::move(lhs);
+}
+
+void
+test_use_move()
+{
+    rvalue_addable arr[100];
+    auto res1 = std::inner_product(arr, arr + 100, arr, rvalue_addable());
+    auto res2 = std::inner_product(arr, arr + 100, arr, rvalue_addable(), /*predicate=*/rvalue_addable(), do_nothing_op());
+
+    assert(res1.correctOperatorUsed);
+    assert(res2.correctOperatorUsed);
+}
+#endif // TEST_STD_VER > 17
+
+void
+test_string()
+{
+    std::string sa[] = {"a", "b", "c"};
+    assert(std::accumulate(sa, sa + 3, std::string()) == "abc");
+    assert(std::accumulate(sa, sa + 3, std::string(), std::plus<std::string>()) == "abc");
+}
+
 template <class Iter1, class Iter2, class T>
 void
 test(Iter1 first1, Iter1 last1, Iter2 first2, T init, T x)
@@ -83,5 +137,10 @@ int main(int, char**)
     test<const int*, random_access_iterator<const int*> >();
     test<const int*, const int*>();
 
-  return 0;
+#if TEST_STD_VER > 17
+    test_use_move();
+#endif // TEST_STD_VER > 17
+    test_string();
+
+    return 0;
 }
diff --git a/libcxx/test/std/numerics/numeric.ops/partial.sum/partial_sum_op.pass.cpp b/libcxx/test/std/numerics/numeric.ops/partial.sum/partial_sum_op.pass.cpp
index 9bc79fdcae74..133edd73b2b7 100644
--- a/libcxx/test/std/numerics/numeric.ops/partial.sum/partial_sum_op.pass.cpp
+++ b/libcxx/test/std/numerics/numeric.ops/partial.sum/partial_sum_op.pass.cpp
@@ -19,11 +19,61 @@
 
 #include <numeric>
 #include <functional>
+#include <string>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
+#if TEST_STD_VER > 17
+struct rvalue_addable
+{
+    bool correctOperatorUsed = false;
+
+    // make sure the predicate is passed an rvalue and an lvalue (so check that the first argument was moved)
+    rvalue_addable operator()(rvalue_addable&& r, rvalue_addable const&) {
+        r.correctOperatorUsed = true;
+        return std::move(r);
+    }
+};
+
+rvalue_addable operator+(rvalue_addable& lhs, rvalue_addable const&)
+{
+    lhs.correctOperatorUsed = false;
+    return lhs;
+}
+
+rvalue_addable operator+(rvalue_addable&& lhs, rvalue_addable const&)
+{
+    lhs.correctOperatorUsed = true;
+    return std::move(lhs);
+}
+
+void
+test_use_move()
+{
+    const std::size_t size = 100;
+    rvalue_addable arr[size];
+    rvalue_addable res1[size];
+    rvalue_addable res2[size];
+    std::partial_sum(arr, arr + size, res1);
+    std::partial_sum(arr, arr + size, res2, /*predicate=*/rvalue_addable());
+    // start at 1 because the first element is not moved
+    for (unsigned i = 1; i < size; ++i) assert(res1[i].correctOperatorUsed);
+    for (unsigned i = 1; i < size; ++i) assert(res2[i].correctOperatorUsed);
+}
+#endif // TEST_STD_VER > 17
+
+void
+test_string()
+{
+    std::string sa[] = {"a", "b", "c"};
+    std::string sr[] = {"a", "ba", "cb"};
+    std::string output[3];
+    std::adjacent_difference(sa, sa + 3, output, std::plus<std::string>());
+    for (unsigned i = 0; i < 3; ++i) assert(output[i] == sr[i]);
+}
+
 template <class InIter, class OutIter>
 void
 test()
@@ -70,5 +120,10 @@ int main(int, char**)
     test<const int*, random_access_iterator<int*> >();
     test<const int*, int*>();
 
-  return 0;
+#if TEST_STD_VER > 17
+    test_use_move();
+#endif // TEST_STD_VER > 17
+    test_string();
+
+    return 0;
 }