What's the difference between std::partial_sum and std::inclusive_scan?

Question

While reading about std::inclusive_scan, there does not appear to be any examples.
It strikes me as very similar to std::partial_sum.

partial_sum:

template< class InputIt, class OutputIt > OutputIt partial_sum( InputIt first,                       InputIt last, OutputIt d_first ); 

inclusive_scan:

template< class InputIt, class OutputIt > OutputIt inclusive_scan( InputIt first,                          InputIt last, OutputIt d_first ); 

---

Can someone elaborate on their differences? When would I choose one over the other?

Answer 1

Documentation of std::inclusive_scan states:

In other words, the summation operations may be performed in arbitrary order. The behavior is nondeterministic if binary_op is not associative.

Documentation of std::partial_sum states without any reservation that:

*(d_first+k) = *first + *(first+1) + ... + *(first+k); 

Thus, std::inclusive_scan is equivalent to std::partial_sum only if binary_op is associative, i.e. when (aopb)opc = aop(bopc).

In case of non-associative binary_op, std::partial_sum will produce a deterministic result, whereas you don't know what to expect from std::inclusive_scan.

Answer 2

std::inclusive_scan was added in C++17 as part of the parallel STD, while std::partial_sum existed before. Both functions are overloaded. If you do not specify the operator, the operator defaults to std::plus:

template< class InputIt, class OutputIt > OutputIt partial_sum( InputIt first,                       InputIt last, OutputIt d_first ); 

For many types like integers, where std::plus is associative, partial_sum and inclusive_scan will be identical. The algorithm behind is the same, in fact, "inclusive scan", "partial sum", etc. are all synonyms for the same type of computation (Wikipedia calls it prefix sum).

There is a difference though in the other overloads that take a user-specified operator:

template< class InputIt, class OutputIt, class BinaryOperation > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first,                       BinaryOperation op ); 

partial_sum has weaker constraints as inclusive_scan. It only requires that op must not invalidate any iterators, or modify any elements of the range involved.

The problem for parallelization is that it does not require op to be associative. As partial_sum demands sequential execution the way it is specified, this was not needed so far. The downside is that it prevents parallel execution, as you cannot reorder computations.

In inclusive_scan, op is explicitly required to be an associative operation. Otherwise, you get undefined behavior. However, the advantage is that is now possible to change your code to support parallel execution by specifying the execution policy:

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,           class BinaryOperation > ForwardIt2 inclusive_scan( ExecutionPolicy&& policy,                            ForwardIt1 first, ForwardIt1 last,                            ForwardIt2 d_first, BinaryOperation binary_op ); 

When would I choose one over the other?

• If your operator is associative, I would recommend to always use inclusive_scan. Even if you will always use sequential execution, it can serve as some form of documentation.

• If you know that your operator is not associative, you have to use partial_sum, otherwise, it will be undefined behavior.

If no user-specified operator is given, can I always replace partial_sum with inclusive_scan? In other words, is it safe to change partial_sum(first, last, out) to inclusive_scan(first, last, out)?

Typically, std::plus is associative (i.e., x + (y + z) == (x + y) + z will hold). In that case, it will be safe to change it.

There are exceptions though. Some weird user-defined classes could overload std::plus in an unexpected way. But a more interesting case are floating point operations, which are not associative in a strict sense:

0.1 + (0.2 + 0.3) != (0.1 + 0.2) + 0.3 // could be identical on some architectures, but fails on my machine (x86-64, AMD FX-8370) 

If your computation needs to be completely reproducible, you have to keep that in mind when changing partial_sum to inclusive_scan (in combination with a non-sequential execution policy).

Still, in practice, floating point operations are close enough to be considered associative. The accuracy can even be improved if the order of the operations is not fixed. That means, the straightforward sequential algorithm is not perfect anyway.