[PATCH] D33997: Implement the non-execution policy versions of `reduce` and `transform_reduce` for C++17
mclow.lists marked 7 inline comments as done.
mclow.lists added inline comments.
Comment at: include/numeric:154
+return reduce(__first, __last,
+ typename iterator_traits<_InputIterator>::value_type{},
_VSTD::plus<>());
+}
wash wrote:
> In the spec, this overload of `reduce` is described as equivalent to `return
> reduce(std::forward(exec), first, last, typename
> iterator_traits::value_type{});`. The overload that it
> calls (the three argument version that omits a binary operation) just
> forwards to the four-argument reduce, adding the `plus<>()` argument.
>
> Is there a reason you wanted to avoid the extra layer of function call
> indirection (it should be inlined and optimized away, right)? What you have
> seems perfectly fine, I'm just curious though.
Nah. Just eager on the copy/paste.
Comment at:
test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_init_bop_uop.pass.cpp:36
+_NOEXCEPT_(noexcept(_VSTD::forward<_Tp>(__x)))
+-> decltype(_VSTD::forward<_Tp>(__x))
+{ return_VSTD::forward<_Tp>(__x); }
rsmith wrote:
> Maybe use `decltype(auto)` here?
I copied this formulation from `` where we use it all over the
place ;-)
(but that's because we support old standards)
https://reviews.llvm.org/D33997
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D33997: Implement the non-execution policy versions of `reduce` and `transform_reduce` for C++17
mclow.lists updated this revision to Diff 102125.
mclow.lists added a comment.
Rebased now that https://reviews.llvm.org/D34038 has landed; address Richard
and Bryce's comments
https://reviews.llvm.org/D33997
Files:
include/numeric
test/std/numerics/numeric.ops/reduce/reduce_iter_iter.pass.cpp
test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T.pass.cpp
test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T_op.pass.cpp
test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_init_bop_uop.pass.cpp
test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init.pass.cpp
test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp
Index: test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp
===
--- test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp
+++ test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp
@@ -0,0 +1,97 @@
+//===--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===--===//
+
+//
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// template
+//T transform_reduce(InputIterator1 first1, InputIterator1 last1,
+// InputIterator2 first2, T init,
+// BinaryOperation1 binary_op1, BinaryOperation2 binary_op2);
+//
+
+#include
+#include
+
+#include "test_iterators.h"
+
+template
+void
+test(Iter1 first1, Iter1 last1, Iter2 first2, T init, Op1 op1, Op2 op2, T x)
+{
+static_assert( std::is_same_v );
+assert(std::transform_reduce(first1, last1, first2, init, op1, op2) == x);
+}
+
+template
+void
+test()
+{
+int ia[] = {1, 2, 3, 4, 5, 6};
+unsigned int ua[] = {2, 4, 6, 8, 10,12};
+unsigned sa = sizeof(ia) / sizeof(ia[0]);
+assert(sa == sizeof(ua) / sizeof(ua[0])); // just to be sure
+
+test(SIter(ia), SIter(ia),UIter(ua), 0, std::plus<>(), std::multiplies<>(), 0);
+test(UIter(ua), UIter(ua),SIter(ia), 1, std::multiplies<>(), std::plus<>(), 1);
+test(SIter(ia), SIter(ia+1), UIter(ua), 0, std::multiplies<>(), std::plus<>(), 0);
+test(UIter(ua), UIter(ua+1), SIter(ia), 2, std::plus<>(), std::multiplies<>(), 4);
+test(SIter(ia), SIter(ia+2), UIter(ua), 0, std::plus<>(), std::multiplies<>(), 10);
+test(UIter(ua), UIter(ua+2), SIter(ia), 3, std::multiplies<>(), std::plus<>(), 54);
+test(SIter(ia), SIter(ia+sa), UIter(ua), 4, std::multiplies<>(), std::plus<>(), 2099520);
+test(UIter(ua), UIter(ua+sa), SIter(ia), 4, std::plus<>(), std::multiplies<>(), 186);
+}
+
+template
+void test_return_type()
+{
+T *p = nullptr;
+static_assert( std::is_same_v(), std::multiplies<>()))> );
+}
+
+int main()
+{
+test_return_type();
+test_return_type();
+test_return_type();
+test_return_type();
+test_return_type();
+test_return_type();
+test_return_type();
+
+// All the iterator categories
+test, input_iterator >();
+test, forward_iterator >();
+test, bidirectional_iterator >();
+test, random_access_iterator >();
+
+test, input_iterator >();
+test, forward_iterator >();
+test, bidirectional_iterator >();
+test, random_access_iterator >();
+
+test();
+test();
+test();
+test();
+
+test();
+test();
+test();
+test();
+
+// just plain pointers (const vs. non-const, too)
+test();
+test();
+test< int*, const unsigned int *>();
+test< int*, unsigned int *>();
+}
Index: test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init.pass.cpp
===
--- test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init.pass.cpp
+++
[PATCH] D33997: Implement the non-execution policy versions of `reduce` and `transform_reduce` for C++17
mclow.lists added a comment. > Should the non-parallel implementation of reduce static_assert or SFINAE away > when these requirements are not met? That may be desirable, but that's not what the standard says. There's nothing there about "shall not participate in overload resolution". //Requires:// in the standard is a requirement on the caller. Failure to satisfy those requirements is UB - and it can compile, not compile, explode at runtime, give the right answer, whatever. (Look at `copy`, say) https://reviews.llvm.org/D33997 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D33997: Implement the non-execution policy versions of `reduce` and `transform_reduce` for C++17
wash added a comment.
I think we need a test case like this for all of the `transform_*`s
struct A {};
struct B {};
struct C {};
B unary_op(C);
B unary_op(A) { assert(false); /* unary op applied to init value! */ }
A binary_op(A, A);
A binary_op(A, B);
A binary_op(B, A);
A binary_op(B, B);
std::vector v;
std::tranform_reduce(v.begin(), v.end(), A{}, binary_op, unary_op);
The "inner" transform operation should **never** be applied to the `init`
parameter.
Comment at: include/numeric:209
+{
+ return transform_reduce(__first1, __last1, __first2, __init,
_VSTD::plus<>(), _VSTD::multiplies<>());
+}
rsmith wrote:
> Missing _VSTD::
In the patch I downloaded from here, the spacing before the return is tabs, not
spaces.
Comment at:
test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_init_bop_uop.pass.cpp:44
+{
+ constexpr const _Tp operator()(const _Tp& __x) const noexcept { return
2 * __x; }
+};
In the patch I downloaded from here, there is a tab right before `constexpr`.
https://reviews.llvm.org/D33997
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D33997: Implement the non-execution policy versions of `reduce` and `transform_reduce` for C++17
wash added a comment.
For all the `transform_` variants, the spec allows the "inner" operation (the
transformation)'s return type is not constrained. We should have a test for
this.
For example, consider the binary-unary `transform_reduce` implementation:
template
inline _LIBCPP_INLINE_VISIBILITY
_Tp
transform_reduce(_InputIterator __first, _InputIterator __last,
_Tp __init, _BinaryOp __b, _UnaryOp __u)
{
for (; __first != __last; ++__first)
__init = __b(__init, __u(*__first));
return __init;
}
The standard says the algorithm requires all of the following expressions be
convertible to `_Tp`:
- `__b(__init, __init)`
- `__b(__init, __u(*__first))`
- `__b(__u(*__first), __init)`
- `__b(__u(*__first), __u(*__first))`
So, the following code should be allowed:
struct A {};
struct B {};
struct C {};
B unary_op(C);
A binary_op(A, A);
A binary_op(A, B);
A binary_op(B, A);
A binary_op(B, B);
std::vector v;
std::tranform_reduce(v.begin(), v.end(), A{}, binary_op, unary_op);
Similar cases can be constructed for all the other `transform_` overloads.
I'll try to find time later to put together a concrete test for this.
https://reviews.llvm.org/D33997
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D33997: Implement the non-execution policy versions of `reduce` and `transform_reduce` for C++17
rsmith added inline comments.
Comment at: include/numeric:145
+{
+return reduce(__first, __last, __init, _VSTD::plus<>());
+}
Missing _VSTD::
Comment at: include/numeric:153
+{
+return reduce(__first, __last,
+ typename iterator_traits<_InputIterator>::value_type{},
_VSTD::plus<>());
Missing _VSTD::
Comment at: include/numeric:209
+{
+ return transform_reduce(__first1, __last1, __first2, __init,
_VSTD::plus<>(), _VSTD::multiplies<>());
+}
Missing _VSTD::
Comment at: test/std/numerics/numeric.ops/reduce/reduce_iter_iter.pass.cpp:26
+{
+static_assert( std::is_same::value_type,
+decltype(std::reduce(first, last))>::value, ""
);
Maybe use _v trait?
Comment at: test/std/numerics/numeric.ops/reduce/reduce_iter_iter.pass.cpp:27
+static_assert( std::is_same::value_type,
+decltype(std::reduce(first, last))>::value, ""
);
+assert(std::reduce(first, last) == x);
May as well drop the `, ""` since this test requires C++17 anyway.
Comment at: test/std/numerics/numeric.ops/reduce/reduce_iter_iter.pass.cpp:37
+unsigned sa = sizeof(ia) / sizeof(ia[0]);
+test(Iter(ia), Iter(ia), 0);
+test(Iter(ia), Iter(ia+1), 1);
wash wrote:
> Just to confirm, this should be 0 because the "default" init value is
> `iterator_traits<_InputIterator>::value_type{}`, and `int{}` gives you a
> determinate result (as opposed to `int()` which would not), correct?
`int()` also gives a determinate result.
Comment at:
test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_init_bop_uop.pass.cpp:36
+_NOEXCEPT_(noexcept(_VSTD::forward<_Tp>(__x)))
+-> decltype(_VSTD::forward<_Tp>(__x))
+{ return_VSTD::forward<_Tp>(__x); }
Maybe use `decltype(auto)` here?
Comment at:
test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp:41
+unsigned sa = sizeof(ia) / sizeof(ia[0]);
+assert(sa == sizeof(ua) / sizeof(ua[0])); // just to be sure
+
You could static_assert this if you make sa const.
https://reviews.llvm.org/D33997
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D33997: Implement the non-execution policy versions of `reduce` and `transform_reduce` for C++17
wash added a comment.
I think the test `reduce_iter_iter_T.pass.cpp` can be improved a little bit.
Right now, it:
- Tests that the three argument overload (iterators + init) work correctly when
the iterator value type is the same as the init type.
- Tests that the return type of the three argument overload is correct in cases
where the iterator value type differs from the init type.
It does not, however, test whether the result is correct when the iterator
value type differs from the init type.
I'd suggest:
void
test_different_init_type()
{
char ca[] = {CHAR_MAX, CHAR_MAX, CHAR_MAX, CHAR_MAX};
unsigned sa = sizeof(ca) / sizeof(ca[0]);
test(ca, ca, int{0}, int{0});
test(ca, ca+1, int{0}, int{CHAR_MAX});
test(ca, ca+2, int{0}, int{2*CHAR_MAX});
test(ca, ca+sa, int{0}, int{4*CHAR_MAX});
}
https://reviews.llvm.org/D33997
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D33997: Implement the non-execution policy versions of `reduce` and `transform_reduce` for C++17
wash added a comment.
Suppose you have:
struct A {};
struct B {};
A operator+(A, B);
std::vector v;
std::reduce(v.begin(), v.end(), A{});
The implementation in this patch works fine for the above case - as would
`accumulate`, which it is equivalent to. However, `reduce` requires that "All
of `binary_op(init, *first)`, `binary_op(*first, init)`, `binary_op(init,
init)`, and `binary_op(*first, *first)` shall be convertible to T.", as all
those operations may be needed for the parallel execution-policy overload of
`reduce` (the requirement applies to the non-execution-policy overload as well).
E.g. in the above example, these operations are also required by `reduce`, even
though the non-parallel implementation does not need them:
A operator+(B, A);
A operator+(A, A);
A operator+(B, B);
Should the non-parallel implementation of `reduce` static_assert or SFINAE away
when these requirements are not met? I think it might be desirable to ensure
that if this won't compile:
std::reduce(std::par, v.begin(), v.end(), A{});
Then this will also not compile:
std::reduce(v.begin(), v.end(), A{});
(And the spec seems to suggest this too).
Comment at: include/numeric:154
+return reduce(__first, __last,
+ typename iterator_traits<_InputIterator>::value_type{},
_VSTD::plus<>());
+}
In the spec, this overload of `reduce` is described as equivalent to `return
reduce(std::forward(exec), first, last, typename
iterator_traits::value_type{});`. The overload that it calls
(the three argument version that omits a binary operation) just forwards to the
four-argument reduce, adding the `plus<>()` argument.
Is there a reason you wanted to avoid the extra layer of function call
indirection (it should be inlined and optimized away, right)? What you have
seems perfectly fine, I'm just curious though.
Comment at: test/std/numerics/numeric.ops/reduce/reduce_iter_iter.pass.cpp:37
+unsigned sa = sizeof(ia) / sizeof(ia[0]);
+test(Iter(ia), Iter(ia), 0);
+test(Iter(ia), Iter(ia+1), 1);
Just to confirm, this should be 0 because the "default" init value is
`iterator_traits<_InputIterator>::value_type{}`, and `int{}` gives you a
determinate result (as opposed to `int()` which would not), correct?
https://reviews.llvm.org/D33997
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D33997: Implement the non-execution policy versions of `reduce` and `transform_reduce` for C++17
mclow.lists added inline comments. Comment at: include/numeric:98 #include // for numeric_limits +#include I don't like adding this dependency; but the standard requires the use of `std::plus` and `std::multiplies` https://reviews.llvm.org/D33997 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D33997: Implement the non-execution policy versions of `reduce` and `transform_reduce` for C++17
mclow.lists created this revision.
There are versions of `reduce` and `transform_reduce` that take an execution
policy, and those that do not.
This implements the ones that do not.
https://reviews.llvm.org/D33997
Files:
include/numeric
test/std/numerics/numeric.ops/reduce/reduce_iter_iter.pass.cpp
test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T.pass.cpp
test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T_op.pass.cpp
test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_init_bop_uop.pass.cpp
test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init.pass.cpp
test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp
Index: test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp
===
--- test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp
+++ test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp
@@ -0,0 +1,97 @@
+//===--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===--===//
+
+//
+// UNSUPPORTED: c++98, c++03, c++11, C++14
+
+// template
+//T transform_reduce(InputIterator1 first1, InputIterator1 last1,
+// InputIterator2 first2, T init,
+// BinaryOperation1 binary_op1, BinaryOperation2 binary_op2);
+//
+
+#include
+#include
+
+#include "test_iterators.h"
+
+template
+void
+test(Iter1 first1, Iter1 last1, Iter2 first2, T init, Op1 op1, Op2 op2, T x)
+{
+static_assert( std::is_same::value, "" );
+assert(std::transform_reduce(first1, last1, first2, init, op1, op2) == x);
+}
+
+template
+void
+test()
+{
+int ia[] = {1, 2, 3, 4, 5, 6};
+unsigned int ua[] = {2, 4, 6, 8, 10,12};
+unsigned sa = sizeof(ia) / sizeof(ia[0]);
+assert(sa == sizeof(ua) / sizeof(ua[0])); // just to be sure
+
+test(SIter(ia), SIter(ia),UIter(ua), 0, std::plus<>(), std::multiplies<>(), 0);
+test(UIter(ua), UIter(ua),SIter(ia), 1, std::multiplies<>(), std::plus<>(), 1);
+test(SIter(ia), SIter(ia+1), UIter(ua), 0, std::multiplies<>(), std::plus<>(), 0);
+test(UIter(ua), UIter(ua+1), SIter(ia), 2, std::plus<>(), std::multiplies<>(), 4);
+test(SIter(ia), SIter(ia+2), UIter(ua), 0, std::plus<>(), std::multiplies<>(), 10);
+test(UIter(ua), UIter(ua+2), SIter(ia), 3, std::multiplies<>(), std::plus<>(), 54);
+test(SIter(ia), SIter(ia+sa), UIter(ua), 4, std::multiplies<>(), std::plus<>(), 2099520);
+test(UIter(ua), UIter(ua+sa), SIter(ia), 4, std::plus<>(), std::multiplies<>(), 186);
+}
+
+template
+void test_return_type()
+{
+T *p = nullptr;
+static_assert( std::is_same(), std::multiplies<>()))>::value, "" );
+}
+
+int main()
+{
+test_return_type();
+test_return_type();
+test_return_type();
+test_return_type();
+test_return_type();
+test_return_type();
+test_return_type();
+
+// All the iterator categories
+test, input_iterator >();
+test, forward_iterator >();
+test, bidirectional_iterator >();
+test, random_access_iterator >();
+
+test, input_iterator >();
+test, forward_iterator >();
+test, bidirectional_iterator >();
+test, random_access_iterator >();
+
+test();
+test();
+test();
+test();
+
+test();
+test();
+test();
+test();
+
+// just plain pointers (const vs. non-const, too)
+test();
+test();
+test< int*, const unsigned int *>();
+test< int*, unsigned int *>();
+}
Index: test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init.pass.cpp
===
--- test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init.pass.cpp
+++
