Page MenuHomePhabricator

Implement the non-execution policy versions of `reduce` and `transform_reduce` for C++17
Needs ReviewPublic

Authored by mclow.lists on Jun 7 2017, 9:27 AM.

Details

Reviewers
EricWF
wash
Summary

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.

Diff Detail

Event Timeline

mclow.lists created this revision.Jun 7 2017, 9:27 AM
mclow.lists added inline comments.
include/numeric
98

I don't like adding this dependency; but the standard requires the use of std::plus and std::multiplies

wash edited edge metadata.Jun 8 2017, 12:36 PM

Suppose you have:

struct A {};
struct B {};

A operator+(A, B);

std::vector<B> 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).

include/numeric
154

In the spec, this overload of reduce is described as equivalent to return reduce(std::forward<ExecutionPolicy>(exec), first, last, typename iterator_traits<ForwardIterator>::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.

test/std/numerics/numeric.ops/reduce/reduce_iter_iter.pass.cpp
38

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?

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});
}
rsmith added a subscriber: rsmith.Jun 8 2017, 2:24 PM
rsmith added inline comments.
include/numeric
145

Missing _VSTD::

153

Missing _VSTD::

209

Missing _VSTD::

test/std/numerics/numeric.ops/reduce/reduce_iter_iter.pass.cpp
27

Maybe use _v trait?

28

May as well drop the , "" since this test requires C++17 anyway.

38

int() also gives a determinate result.

test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_init_bop_uop.pass.cpp
37

Maybe use decltype(auto) here?

test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp
42

You could static_assert this if you make sa const.

wash added a comment.EditedJun 8 2017, 3:06 PM

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 <class _InputIterator, class _Tp, class _BinaryOp, class _UnaryOp>
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<C> 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.

EDIT: Note that for transform_ algorithms, the "inner"operation (e.g. the transform) is never applied to the init value. So it is not necessary for unary_op in the above example to be callable with As.

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

include/numeric
209

In the patch I downloaded from here, the spacing before the return is tabs, not spaces.

test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_init_bop_uop.pass.cpp
45

In the patch I downloaded from here, there is a tab right before constexpr.

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)

Rebased now that D34038 has landed; address Richard and Bryce's comments

mclow.lists marked 7 inline comments as done.Jun 10 2017, 1:52 PM
mclow.lists added inline comments.
include/numeric
154

Nah. Just eager on the copy/paste.

test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_init_bop_uop.pass.cpp
37

I copied this formulation from <functional> where we use it all over the place ;-)
(but that's because we support old standards)