C++ Logo

SG20

Advanced search

Subject: Re: [isocpp-lib-ext] Reducing the number of numeric algorithms in namespace ranges
From: Arthur O'Dwyer (arthur.j.odwyer_at_[hidden])
Date: 2019-06-25 11:45:20


Chris,

If you're doing design work on <numeric>, then I EXTREMELY strongly
recommend watching Conor Hoekstra's talk "Algorithm Intuition"
<https://www.youtube.com/watch?v=48gV1SNm3WA> (from this year's C++Now)
first. Some design takeaways:

- Having "default" functors causes more confusion than help. The fact that
some numeric algorithms default to std::plus (std::reduce) and others to
std::minus (std::adjacent_difference) adds to the difficulty in developing
intuition about these algorithms.
- The historical naming of these algorithms is asymmetric and inconsistent
(just like their placement outside of <algorithm>). New "modern" versions
should go in <algorithm> so that learners of algorithms don't have to worry
about numerics.
- As pointed out in the Q&A, <numeric> is a misnomer for these abstract
algorithms anyway. For example,`std::inner_product` over doubles does not
compute a mathematically precise answer; "transform-reduce with std::plus
and std::times" is an unrealistically naïve way to compute "inner product."
The name of the algorithm should reflect its purpose, and the placement of
the algorithm should reflect its level of numeric sophistication.
- Having a 1-range version of `transform` and a 2-range version of
`transform`, sharing the same overload set, is a source of confusion.
Having 1- and 2-range versions but no 3- or 4-range versions (that is: the
original `std::transform` pre-dates variadic templates) is also a source of
confusion for programmers used to variadic `zip`.

Procedural issue: Your original message would have been clearer if you
could list not only the 7 algorithms you did, but also the (N??) algorithms
that are on your list of "all of the numeric algorithms."

HTH,
Arthur

On Tue, Jun 25, 2019 at 10:46 AM Christopher Di Bella <cjdb.ns_at_[hidden]>
wrote:

> I'm researching what is necessary to bring the numeric algorithms into
> namespace std::ranges (for those wondering why it's non-trivial: they
> require close study like those in <algorithm> got from N3351 + ranges
> work). Part of this research involves me consistently scratching my head
> over whether or not all of the numeric algorithms should be imported into
> std::ranges, or if it's possible to get away with just reduce,
> transform_reduce, exclusive_scan, inclusive_scan, transform_exclusive_scan,
> transform_inclusive_scan, and adjacent_difference. iota is deliberately
> not in that list, but that's also not relevant to the discussion I'm
> wanting to have.
>
> Note that I'm only considering the overloads without an ExecutionPolicy.
>
> 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
> }
> ```
>
> If either question can be answered with "yes", then forgetting accumulate
> is a non-starter, and I'll work on nailing down all of the numeric
> algorithms. I suspect this is the case, but lack the experience to answer
> them myself, and am yet to find a proposal or minutes detailing this
> discussion.
>
> If there aren't advantages for this overload of reduce, et al. to
> co-exist with their C++98 counterparts, then I'm inclined to propose that
> only the C++17 names be ported (plus adjacent_difference), because:
>
> 1. It seems redundant for us to have two algorithms that are specified
> differently, but produce equivalent results.
> 1. The ExecutionPolicy numeric algorithms can still have formal
> requirements for associativity and commutativity.
> 2. I've had a teacher pass on a question to me from a student
> asking if they should be using accumulate or reduce, so I have
> teachability concerns.
> 1. It's likely that there are more than two people in the situation
> of 'Curious Student Reading the C++ Reference' and 'Hesitant Teacher'.
> 2. If there's only one name in namespace std::ranges, then advice
> boils down to "prefer what's in namespace std::ranges; the rest are
> historical".
>
> Cheers,
>
> Chris
>
>



SG20 list run by herb.sutter at gmail.com

Older Archives on Google Groups