C++ Logo

sg20

Advanced search

Re: [SG20] Reducing the number of numeric algorithms in namespace ranges

From: Bryan St. Amour <bryan_at_[hidden]>
Date: Tue, 25 Jun 2019 11:59:24 -0400
... I'm just going to help myself to some more coffee and pretend that
parse error on my part didn't happen.

On 6/25/2019 11:54 AM, Yehezkel Bernat wrote:
> The issue isn't with implementing reduce as accumulate, of course.
> The issue is with adding parallelism in the NDEBUG case.
>
> On Tue, Jun 25, 2019 at 6:51 PM Bryan St. Amour via SG20
> <sg20_at_[hidden] <mailto:sg20_at_[hidden]>> wrote:
>
> That implementation of reduce looks fine to me. Since the order of
> applications of bop is unspecified, it should be fine to implement
> in terms of accumulate. Going the opposite way is where you would
> get trouble.
>
> On 6/25/2019 11:47 AM, Yehezkel Bernat via SG20 wrote:
>>
>>
>> On Tue, Jun 25, 2019 at 5:49 PM Christopher Di Bella via SG20
>> <sg20_at_[hidden] <mailto:sg20_at_[hidden]>> wrote:
>>
>> Are there any practical reasons for reduce(begin(v),
>> end(v), 0, plus{}) to permit out-of-order computation?
>> For example, is this allowed as an implementation?
>>
>> ```
>> template<class InputIterator, class T, class BOp>
>> T reduce(InputIterator first, InputIterator last, T init,
>> BOp bop)
>> {
>> #if NDEBUG
>> return reduce(execution::par_unseq, first, last,
>> init, bop);
>> #else
>> return accumulate(first, last, init, bop);
>> #endif // NDEBUG
>> }
>> ```
>>
>>
>> My understanding is that it isn't allowed.
>> What the standard mentions explicitly is:
>>
>> [ Note <http://eel.is/c++draft/reduce#8.note-1>
>> :
>> The difference between reduce and accumulate is that
>> reduce applies binary_­op in an unspecified order, which yields a
>> nondeterministic result for non-associative or non-commutative
>> binary_­op such as floating-point addition.
>> <http://eel.is/c++draft/reduce#8.sentence-1>
>> — /end note/
>> ]
>> http://eel.is/c++draft/reduce#8
>>
>> So this is equivalent to passing `std::execution::seq`, which
>> allows invocations that are "indeterminately sequenced". This is
>> different than `accumulate`, which is guaranteed to perform a
>> left fold.
>>
>> If either question can be answered with "yes", then
>> forgetting accumulate is a non-starter,
>>
>>
>> I'd think the question should go the opposite direction:
>> What are the reasons to *forbid* out-of-order computation (which
>> is the only reason to keep having accumulate around)?
>> The numerical algorithms are intended for numerical usages.
>> Maybe using a numerical type that isn't associative or isn't
>> commutative is a task that shouldn't be done by a generic
>> algorithm anyway?
>> Using other types (e.g. `std::string`; its operator+ isn't
>> commutative of course) is not what the algorithm was designed for
>> (this is why it is in `numeric` instead of `algorithm`) so maybe
>> we are fine with disallowing such a usage going forward.
>>
>>
> --
> SG20 mailing list
> SG20_at_[hidden] <mailto:SG20_at_[hidden]>
> http://lists.isocpp.org/mailman/listinfo.cgi/sg20
>

Received on 2019-06-25 11:01:36