[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
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.
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] D34007: Implement inclusive_scan and transform_inclusive_scan
wash added a comment. Minor note: there's a mix of tabs and spaces in this diff. https://reviews.llvm.org/D34007 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D34007: Implement inclusive_scan and transform_inclusive_scan
wash added a comment. So, `inclusive_scan` should be equivalent to `partial_sum` for the non-parallel version. https://reviews.llvm.org/D34007 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D34007: Implement inclusive_scan and transform_inclusive_scan
wash added a comment.
Here's `partial_sum`:
template
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator
__result,
_BinaryOperation __binary_op)
{
if (__first != __last)
{
typename iterator_traits<_InputIterator>::value_type __t(*__first);
*__result = __t;
for (++__first, (void) ++__result; __first != __last; ++__first,
(void) ++__result)
{
__t = __binary_op(__t, *__first);
*__result = __t;
}
}
return __result;
}
And here's the `inclusive_scan` that should be equivalent to that `partial_sum`:
template
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
inclusive_scan(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, _BinaryOp __b)
{
if (__first != __last) {
typename iterator_traits<_InputIterator>::value_type __init =
*__first++;
return inclusive_scan(__first, __last, __result, __b, __init);
}
return __result;
}
The `inclusive_scan` that it forwards to is:
template
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
inclusive_scan(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, _BinaryOp __b, _Tp __init)
{
*__result++ = __init;
for (; __first != __last; ++__first) {
__init = __b(__init, *__first);
*__result++ = __init;
}
return __result;
}
Inlining it, we get:
template
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
inclusive_scan(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, _BinaryOp __b)
{
if (__first != __last) {
typename iterator_traits<_InputIterator>::value_type __init =
*__first++;
*__result++ = __init;
for (; __first != __last; ++__first) {
__init = __b(__init, *__first);
*__result++ = __init;
}
}
return __result;
}
That looks equivalent to the `partial_sum` implementation above, so I think it
is correct.
https://reviews.llvm.org/D34007
___
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] D34038: Implement the non-parallel versions of exclusive_scan and transform_exclusive_scan
wash added inline comments.
Comment at: include/numeric:182
+{
+ _Tp __saved = __init;
+ for (; __first != __last; ++__first, (void) ++__result) {
If `__first == __last`, this initialization is unnecessary; I'd refactor this
so that we check for `__first != __last` first.
Comment at: include/numeric:208
+{
+ _Tp __saved = __init;
+ for (; __first != __last; ++__first, (void) ++__result) {
If `__first == __last`, this initialization is unnecessary; I'd refactor this
so that we check for `__first != __last` first.
https://reviews.llvm.org/D34038
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D34038: Implement the non-parallel versions of exclusive_scan and transform_exclusive_scan
wash added a comment. https://gist.github.com/brycelelbach/137f1e45b737d615134e228ec0c84f3a <- some crude tests I wrote based on slides/notes of mine. https://reviews.llvm.org/D34038 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D34038: Implement the non-parallel versions of exclusive_scan and transform_exclusive_scan
wash added a comment. This implementation works, but performs unnecessary operations. https://gist.github.com/brycelelbach/907ac3b8a74603cc189897ab789a65a9 The "next" result is calculated in each iteration; this means one unnecessary application of the binary op (the "next" result on the final iteration). https://reviews.llvm.org/D34038 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D34038: Implement the non-parallel versions of exclusive_scan and transform_exclusive_scan
wash added a comment. The init typedef test looks good to me. This all looks good to go. https://reviews.llvm.org/D34038 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
