{"id":10386,"date":"2024-12-02T10:30:52","date_gmt":"2024-12-02T10:30:52","guid":{"rendered":"https:\/\/www.modernescpp.com\/?p=10386"},"modified":"2025-07-04T15:46:41","modified_gmt":"2025-07-04T15:46:41","slug":"stdexecution-inclusive-scan","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/stdexecution-inclusive-scan\/","title":{"rendered":"std::execution: Inclusive Scan"},"content":{"rendered":"\n

Inclusive scan solves problems related to range queries, such as calculating the sum of a range of elements in an array. It is also used in range minimum queries and various other algorithms.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Before I present the asynchronous inclusive scan, I introduce the inclusive scan, aka prefix sum.<\/p>\n\n\n\n

Prefix Sum<\/h2>\n\n\n\n

In computer science<\/a>, the prefix sum<\/strong>, cumulative sum<\/strong>, inclusive scan<\/strong>, or simply scan<\/strong> of a sequence of numbers x<\/em>0<\/sub>, x<\/em>1<\/sub>, x<\/em>2<\/sub>, … is a second sequence of numbers y<\/em>0<\/sub>, y<\/em>1<\/sub>, y<\/em>2<\/sub>, …, the sums<\/a> of prefixes<\/a> (running totals<\/a>) of the input sequence:<\/p>\n\n\n\n

    y0 =<\/span> x0\n    y1 =<\/span> x0 +<\/span> x1\n    y2 =<\/span> x0 +<\/span> x1+<\/span> x2\n    ...\n<\/pre><\/div>\n\n\n\n
(https:\/\/en.wikipedia.org\/wiki\/Prefix_sum<\/a>)<\/p>\n\n\n\n
Proposal P2300R10<\/a> has an asynchronous implementation of inclusive scan.<\/p>\n\n\n\n
Asynchronous Inclusive Scan<\/h2>\n\n\n\n
using<\/span> namespace<\/span> std::<\/span>execution;\n\nsender auto<\/span> async_inclusive_scan<\/span>(scheduler auto<\/span> sch,                          \/\/ 2<\/span>\n                                 std::<\/span>span<<\/span>const<\/span> double<\/span>><\/span> input,               \/\/ 1<\/span>\n                                 std::<\/span>span<<\/span>double<\/span>><\/span> output,                    \/\/ 1<\/span>\n                                 double<\/span> init,                                 \/\/ 1<\/span>\n                                 std::<\/span>size_t<\/span> tile_count)                      \/\/ 3<\/span>\n{\n  std::<\/span>size_t<\/span> const<\/span> tile_size =<\/span> (input.size() +<\/span> tile_count -<\/span> 1<\/span>) \/<\/span> tile_count;\n\n  std::<\/span>vector<<\/span>double<\/span>><\/span> partials(tile_count +<\/span> 1<\/span>);                               \/\/ 4<\/span>\n  partials[0<\/span>] =<\/span> init;                                                         \/\/ 4<\/span>\n\n  return<\/span> just(std::<\/span>move(partials))                                            \/\/ 5<\/span>\n       |<\/span> continues_on(sch)\n       |<\/span> bulk(tile_count,                                                     \/\/ 6<\/span>\n           [ =<\/span> ](std::<\/span>size_t<\/span> i, std::<\/span>vector<<\/span>double<\/span>>&<\/span> partials) {              \/\/ 7<\/span>\n             auto<\/span> start =<\/span> i *<\/span> tile_size;                                      \/\/ 8<\/span>\n             auto<\/span> end   =<\/span> std::<\/span>min(input.size(), (i +<\/span> 1<\/span>) *<\/span> tile_size);        \/\/ 8<\/span>\n             partials[i +<\/span> 1<\/span>] =<\/span> *--<\/span>std::<\/span>inclusive_scan(begin(input) +<\/span> start,   \/\/ 9<\/span>\n                                                      begin(input) +<\/span> end,     \/\/ 9<\/span>\n                                                      begin(output) +<\/span> start); \/\/ 9<\/span>\n           })                                                                 \/\/ 10<\/span>\n       |<\/span> then(                                                                \/\/ 11<\/span>\n           [](std::<\/span>vector<<\/span>double<\/span>>&&<\/span> partials) {\n             std::<\/span>inclusive_scan(begin(partials), end(partials),              \/\/ 12<\/span>\n                                 begin(partials));                            \/\/ 12<\/span>\n             return<\/span> std::<\/span>move(partials);                                      \/\/ 13<\/span>\n           })\n       |<\/span> bulk(tile_count,                                                     \/\/ 14<\/span>\n           [ =<\/span> ](std::<\/span>size_t<\/span> i, std::<\/span>vector<<\/span>double<\/span>>&<\/span> partials) {              \/\/ 14<\/span>\n             auto<\/span> start =<\/span> i *<\/span> tile_size;                                      \/\/ 14<\/span>\n             auto<\/span> end   =<\/span> std::<\/span>min(input.size(), (i +<\/span> 1<\/span>) *<\/span> tile_size);        \/\/ 14<\/span>\n             std::<\/span>for_each(begin(output) +<\/span> start, begin(output) +<\/span> end,        \/\/ 14<\/span>\n               [&<\/span>] (double<\/span>&<\/span> e) { e =<\/span> partials[i] +<\/span> e; }                       \/\/ 14<\/span>\n             );\n           })\n       |<\/span> then(                                                                \/\/ 15<\/span>\n           [ =<\/span> ](std::<\/span>vector<<\/span>double<\/span>>&&<\/span> partials) {                            \/\/ 15<\/span>\n             return<\/span> output;                                                   \/\/ 15<\/span>\n           });                                                                \/\/ 15<\/span>\n}\n<\/pre><\/div>\n\n\n\n
 Here’s the explanation from the proposal P2300R10<\/a>:<\/p>\n\n\n\n
    \n
  1. It scans a sequence of double<\/code>s (represented as the std::span<const double><\/code> input<\/code>) and stores the result in another sequence of double<\/code>s (represented as std::span<double><\/code> output<\/code>).<\/li>\n\n\n\n
  2. It takes a scheduler, which specifies what execution resource the scan should be launched on.<\/li>\n\n\n\n
  3. It also takes a tile_count<\/code> parameter that controls the number of execution agents that will be spawned.<\/li>\n\n\n\n
  4. First we need to allocate temporary storage needed for the algorithm, which we\u2019ll do with a std::vector<\/code>, partials<\/code>. We need one double<\/code> of temporary storage for each execution agent we create.<\/li>\n\n\n\n
  5. Next we\u2019ll create our initial sender with execution::just <\/code>and execution::continues_on<\/code>. These senders will send the temporary storage, which we\u2019ve moved into the sender. The sender has a completion scheduler of sch<\/code>, which means the next item in the chain will use sch<\/code>.<\/li>\n\n\n\n
  6. Senders and sender adaptors support composition via operator|<\/code>, similar to C++ ranges. We\u2019ll use operator|<\/code> to attach the next piece of work, which will spawn tile_count<\/code> execution agents using execution::bulk<\/code>s.<\/li>\n\n\n\n
  7. Each agent will call a std::invocable<\/code>, passing it two arguments. The first is the agent\u2019s index (i<\/code>) in the execution::bulk operation, in this case a unique integer in [0, tile_count)<\/code>. The second argument is what the input sender sent – the temporary storage.<\/li>\n\n\n\n
  8. We start by computing the start and end of the range of input and output elements that this agent is responsible for, based on our agent index.<\/li>\n\n\n\n
  9. Then we do a sequential std::inclusive_scan<\/code> over our elements. We store the scan result for our last element, which is the sum of all of our elements, in our temporary storage partials<\/code>.<\/li>\n\n\n\n
  10. After all computation in that initial bulk <\/code>pass has completed, every one of the spawned execution agents will have written the sum of its elements into its slot in partials<\/code>.<\/li>\n\n\n\n
  11. Now we need to scan all of the values in partials<\/code>. We\u2019ll do that with a single execution agent which will execute after the <\/a>execution::bulk<\/code> completes. We create that execution agent with execution::then<\/code>.<\/li>\n\n\n\n
  12. execution::then<\/code> takes an input sender and an std::invocable<\/code> and calls the std::invocable<\/code> with the value sent by the input sender. Inside our std::invocable<\/code>, we call std::inclusive_scan<\/code> on partials<\/code>, which the input senders will send to us.<\/li>\n\n\n\n
  13. Then we return partials<\/code>, which the next phase will need.<\/li>\n\n\n\n
  14. Finally we do another execution::bulk <\/code>of the same shape as before. In this execution::bulk,<\/code> we will use the scanned values in partials<\/code> to integrate the sums from other tiles into our elements, completing the inclusive scan.<\/li>\n\n\n\n
  15. async_inclusive_scan<\/code> returns a sender that sends the output std::span<double><\/code>. A consumer of the algorithm can chain additional work that uses the scan result. At the point at which async_inclusive_scan<\/code> returns, the computation may not have completed. In fact, it may not have even started.<\/li>\n<\/ol>\n\n\n\n
    Sender<\/p>\n\n\n\n