C++ Logo

SG20

Advanced search

Subject: Re: Reducing the number of numeric algorithms in namespace ranges
From: Bryan St. Amour (bryan_at_[hidden])
Date: 2019-06-25 10:51:01


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 list run by herb.sutter at gmail.com

Older Archives on Google Groups