{"id":32015,"date":"2023-04-13T14:55:40","date_gmt":"2023-04-13T14:55:40","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/cppblog\/?p=32015"},"modified":"2023-04-14T15:53:25","modified_gmt":"2023-04-14T15:53:25","slug":"cpp23s-new-fold-algorithms","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/cppblog\/cpp23s-new-fold-algorithms\/","title":{"rendered":"C++23’s New Fold Algorithms"},"content":{"rendered":"

C++20 added new versions of the standard library algorithms which take ranges as their first argument rather than iterator pairs, alongside other improvements. However, key algorithms like std::accumulate<\/code> were not updated. This has been done in C++23, with the new std::ranges::fold_*<\/code> family of algorithms. The standards paper for this is P2322<\/a> and was written by Barry Revzin. It been implemented in Visual Studio 2022 version 17.5<\/a>. In this post I\u2019ll explain the benefits of the new \u201crangified\u201d algorithms, talk you through the new C++23 additions, and explore some of the design space for fold algorithms in C++.<\/p>\n

Background: Rangified Algorithms<\/h2>\n

C++20\u2019s algorithms make several improvements to the old iterator-based ones. The most obvious is that they now can take a range instead of requiring you to pass iterator pairs. But they also allow passing a \u201cprojection function\u201d to be called on elements of the range before being processed, and the use of C++20 concepts for constraining their interfaces more strictly defines what valid uses of these algorithms are. These changes allow you to make refactors like:<\/p>\n

\/\/ C++17 algorithm\r\ncat find_kitten(const std::vector<cat>& cats) {\r\n    return *std::find_if(cats.begin(), cats.end(), \r\n        [](cat const& c) { return c.age == 0; });\r\n}\r\n\r\n\/\/ C++20 algorithm\r\ncat find_kitten(std::span<cat> cats) {\r\n    return *std::ranges::find(cats, 0, &cat::age);\r\n}<\/code><\/pre>\n
The differences here are:<\/p>\n
    \n
  1. Instead of having to pass cats.begin()<\/code> and cats.end()<\/code>, we just pass cats<\/code> itself.<\/li>\n
  2. Since we are comparing a member variable of the cat<\/code> to 0<\/code>, in C++17 we need to use std::find_if<\/code> and pass a closure which accesses that member and does the comparison. Since the rangified algorithms support projections, in C++20 we can use std::ranges::find<\/code> and pass &cat::age<\/code> as a projection, getting rid of the need for the lambda completely.<\/li>\n<\/ol>\n
    These improvements can greatly clean up code which makes heavy use of the standard library algorithms.<\/p>\n
    Unfortunately, alongside the algorithms which reside in the <algorithm><\/code> header, there are also several important ones in the <numeric><\/code> header, and these were not rangified in C++201<\/sup><\/a>. In this post we\u2019re particularly interested in std::accumulate<\/code> and std::reduce<\/code>.<\/p>\n
    accumulate<\/code> and reduce<\/code><\/h2>\n
    std::accumulate<\/code> and std::reduce<\/code> are both fold<\/a> operations. They “fold” or “reduce” or “combine” multiple values into a single value. Both take two iterators, an initial value, and a binary operator (which defaults to +<\/code>). They then run the given operator over the range of values given by the iterators, collecting a result as they go. For instance, given std::array<int,3> arr = {1,2,3}<\/code>, std::accumulate(begin(arr), end(arr), 0, std::plus())<\/code> will run (((0 + 1) + 2) + 3)<\/code>. Or std::accumulate(begin(arr), end(arr), 0, f)<\/code> will run f(f(f(0, 1), 2), 3)<\/code>.<\/p>\n
    These functions are both what are called left folds<\/em> because they run from left to right. There’s also right folds<\/em>, which as you may guess, run from right to left. For the last example a right fold would look like f(1, f(2, f(3, 0)))<\/code>. For some operations, like +<\/code>, these would give the same result, but for operations which are not associative<\/a> (like -<\/code>), it could make a difference.<\/p>\n
    So why do we have both std::accumulate<\/code> and std::reduce<\/code>? std::reduce<\/code> was added in C++17 as one of the many parallel algorithms<\/a> which let you take advantage of parallel execution for improved performance. The reason it has a different name than std::accumulate<\/code> is because it has different constraints on what types and operations you can use: namely the operation used must be both associative and commutative<\/a>.<\/p>\n
    To understand why, consider the following code:<\/p>\n
    std::array<int,8> a {0,1,2,3,4,5,6,7};\r\nauto result = std::reduce(std::execution::par, \/\/execute in parallel \r\n    begin(a), end(a), 0, f);<\/code><\/pre>\n
    If f<\/code> is associative, then std::reduce<\/code> could reduce the first half of a<\/code> on one CPU core, reduce the second half of a<\/code> on another core, then call f<\/code> on the result. However, if f<\/code> is not<\/em> associative, this could result in a different answer than carrying out a pure left fold. As such, requiring associativity lets std::reduce<\/code> distribute the reduction across multiple units of execution.<\/p>\n
    Requiring commutativity likewise enables some potential optimizations. One is that the implementation is free to reorder operations as it likes. If, for example, some calls to f<\/code> take longer than others, reduce<\/code> could use whichever intermediate results are available without having to wait around for the “right” result. Commutativity also enables vectorization when using the std::execution::par_unseq<\/code> policy. For example, if f<\/code> is addition, the first half of a<\/code> could be loaded into one vector register, the second half loaded into another, and a vector addition executed on them. This would result in (0 + 4) + (1 + 5) + (2 + 6) + (3 + 7)<\/code>. Notice that the operands have been interleaved: this requires commutativity.<\/p>\n
    std::ranges::fold_*<\/code><\/h2>\n
    C++23 comes with six fold functions which fulfil different important use cases. The one you’ll reach for most is std::ranges::fold_left<\/code>.<\/p>\n
    fold_left<\/code><\/h3>\n
    You can use fold_left<\/code> in place of calls to std::accumulate<\/code>. For instance, I have three cats, and when I brush them, I collect all the loose fur as I go so I can throw it away:<\/p>\n
    fur brush(fur existing_fur, cat& c);\r\nstd::vector<cat> cats = get_cats(); \r\n\r\n\/\/ C++20\r\nauto loose_fur = std::accumulate(begin(cats), end(cats), fur{}, brush);\r\n\/\/ C++23\r\nauto loose_fur = std::ranges::fold_left(cats, fur{}, brush);\r\n\r\nthrow_away(loose_fur);<\/code><\/pre>\n
    std::accumulate<\/code> is really a generic left fold, but its name suggests summation, and the defaulting of the binary operator to addition further contributes to this. This makes uses of accumulate<\/code> for non-summation purposes look a little clunky. This is why the new version is instead called fold_left<\/code>, and does not have a default operator.<\/p>\n
    fold_right<\/code><\/h3>\n
    As you can probably guess, since there’s a fold_left<\/code> function, there’s also a fold_right<\/code> function. For associative operations like brush<\/code>, there’s no real difference in behaviour. But say we have a function which takes some amount of food and feeds half of it to a cat, returning the leftovers:<\/p>\n
    food feed_half(cat& c, food f) {\r\n    auto to_feed = f \/ 2;\r\n    c.eaten += to_feed;\r\n    return f - to_feed;\r\n}<\/code><\/pre>\n
    This operation is not associative, therefore using fold_left<\/code> or fold_right<\/code> would result in feeding different cats different amounts of food. We could call fold_right<\/code> like this:<\/p>\n
    std::vector<cat> cats = get_cats();\r\n\/\/feed cats from right to left, starting with 100 food\r\nauto leftovers = std::ranges::fold_right(cats, 100, feed_half); <\/code><\/pre>\n
    Note that for fold_right<\/code>, the order of arguments to the operator are flipped from fold_left<\/code>: the accumulator is on the right rather than the left.<\/p>\n
    In these examples we’ve been able to pick a reasonable initial value for our folds (fur{}<\/code> in the first, 100<\/code> in the second). But how do we pick our initial element? What if there is no good initial value to pick?<\/p>\n
    Aside on initial element<\/h3>\n
    std::reduce<\/code> allows omitting the initial element for the fold, in which case it uses a value-initialized object of the given iterator’s value type (e.g. 0<\/code> for int<\/code>). This can be handy in some cases, such as summing integers, but doesn’t work so well in others, such as taking the product of integers. Usually what we want for the initial element is some identity element<\/em> for the value type of the range with respect to the given binary operator. Given any object x<\/code> of type T<\/code> and operation f<\/code>, the identity element id<\/code> is one for which f(id,x) == x<\/code>. For example, the identity element for the pair int, operator+<\/code> is 0<\/code>. For int, operator*<\/code> it’s 1<\/code>. For std::string, operator+<\/code> it’s \"\"<\/code>.<\/p>\n
    These pairs of types and associative binary operators which have an identity element turn out to be surprisingly common in programming, they’re called monoids<\/a>. Ben Deane has several great talks on monoids in C++, I’d highly recommend watching this one<\/a>.<\/p>\n
    We don’t have a way to easily get at the identity element of a given monoid in C++. You could imagine implementing some monoid_traits<\/code> class template which could be specialised by users to support custom types. This could let fold_left<\/code> be implemented something like (omitting constraints for brevity):<\/p>\n
    template <class Rng, class F, class T = std::ranges::range_value_t<Rng>>\r\nconstexpr T fold_left (Rng&& rng, F&& op, T init = monoid_traits<std::ranges::range_value_t<Rng>, F>::identity_element());<\/code><\/pre>\n
    Maybe you think that’s horrifying and too much work. I might agree for many cases. I do think it’s an interesting design area though, and I know GraphBLAS<\/a> does something like this; there’s a CppCon talk<\/a> which shows the kinds of things they do with monoid traits. P1813<\/a> explored a similar idea for a concepts design for numeric algorithms.<\/p>\n
    I think the C++23 design makes the right decision in simply not defaulting the initial element at all. This forces you to think about it and not accidentally supply a value-initialized value in cases where it’s not correct.<\/p>\n
    fold_left_first<\/code> and fold_right_last<\/code><\/h3>\n
    But what if you don’t have an identity element for your type? Then you need to pull out the first element by-hand, which is quite unwieldly and a bit tricky to get right for input iterators<\/a>:<\/p>\n
    auto b = std::ranges::begin(rng);\r\nauto e = std::ranges::end(rng);\r\nauto init = *b;\r\nfold_left(std::ranges::next(b), e, std::move(init), f);<\/code><\/pre>\n
    As such, many languages provide an alternative fold<\/code> function which uses the first element of the range as the initial element (thus additionally requiring the range to be non-empty).<\/p>\n
    The version we have in C++23 has this too, it calls them fold_left_first<\/code> and fold_right_last<\/code>. This lets you simply write:<\/p>\n
    std::ranges::fold_left_first(rng, f);<\/code><\/pre>\n
    Much better.<\/p>\n
    fold_left_with_iter<\/code> and fold_left_first_with_iter<\/code><\/h3>\n
    The final two versions of fold<\/code> which are in C++23 are ones which expose an additional result computed by the fold: the end iterator. Recall that for some ranges, the type returned by std::ranges::end<\/code> is not an iterator, but a sentinel<\/em>: some rule for when to finish iteration. For some ranges, computing the iterator for the range which is equal to what std::ranges::end<\/code> returns may actually be quite expensive. Since carrying out the fold necessarily requires computing this iterator, C++23 provides functions which return this iterator alongside the value computed.<\/p>\n
    For example, say we have a collection of cats sorted by age, and we have some food which is specially formulated for younger cats. We could split the food between the younger cats like so:<\/p>\n
    std::vector<cat> cats = get_sorted_cats();\r\nauto young_cats = cats | std::views::take_while([](auto c) { return c.age < 7; });\r\nauto leftover_food = std::ranges::fold_left(young_cats, food_for_young_cats, feed_half);<\/code><\/pre>\n
    However, now if we want to give some other food to the older cats, we need to recompute the point in cats<\/code> where the young cats stop and the older cats begin:<\/p>\n
    auto first_old_cat = std::ranges::find_if(cats, [](auto c) { return c.age >= 7; });\r\ngive_some_other_food(first_old_cat, std::ranges::end(cats));<\/code><\/pre>\n
    fold_left_with_iter<\/code> lets you avoid the recomputation:<\/p>\n
    std::vector<cat> cats = get_sorted_cats();\r\nauto young_cats = cats | std::views::take_while([](auto c) { return c.age < 7; });\r\nauto [first_old_cat, leftover_food] = std::ranges::fold_left_with_iter(young_cats, food_for_young_cats, feed_half);\r\n\r\ngive_some_other_food(first_old_cat, std::ranges::end(cats));<\/code><\/pre>\n
    What about reduce<\/code>?<\/h2>\n
    The fold<\/code> family of functions extend and replace std::accumulate<\/code>. But what about std::reduce<\/code>? std::ranges::reduce<\/code> is planned, but no one has written the necessary standards proposal for it yet. It wouldn’t be that<\/em> different from std::ranges::fold_*<\/code>, but there’s some subtle design points, like different constraints on the binary operator to allow op(*it, acc)<\/code>, op(acc, *it)<\/code>, and op(*it, *it)<\/code>.<\/p>\n
    What about projections?<\/h2>\n
    I said at the start that the rangified algorithms have 3 main benefits:<\/p>\n
      \n
    1. Can pass a range rather than iterator pair<\/li>\n
    2. Are constrained by concepts<\/li>\n
    3. Support projection functions<\/li>\n<\/ol>\n
      Only the first two apply for fold_*<\/code>, however: projection functions aren’t supported for a rather subtle reason. You can see P2322r6<\/a> for all the details, but essentially, for the fold_left_first*<\/code> and fold_right_last*<\/code> overloads, allowing projections would incur an extra copy even in cases where it shouldn’t be required. As such, projections were removed from those overloads, and then from the remaining three for consistency.<\/p>\n
      If you want to use a projection function with fold_left<\/code>, you could do something like:<\/p>\n
      auto res = fold_left(rng | std::views::transform(projection), init, f);<\/code><\/pre>\n
      Feedback<\/h2>\n
      You can try out the feature in Visual Studio 2022 version 17.5<\/a>. If you have any questions, comments, or issues with the feature, you can comment below, or reach us via email at visualcpp@microsoft.com<\/a> or via Twitter at @VisualC<\/a>.<\/p>\n
      Acknowledgements<\/h2>\n
      Thanks to Christopher Di Bella, Barry Revzin, and Stephan T. Lavavej for feedback and information. Thanks to Jakub Mazurkiewicz for implementing this feature in our standard library.<\/span><\/p>\n
      \n
      <\/a>1<\/sup>Why? Quoting Casey Carter: “Every time someone asks why we didn\u2019t cover <numeric><\/code> and <memory><\/code> algorithms: We thought 187 pages of Technical Specification was enough.”<\/p>\n","protected":false},"excerpt":{"rendered":"
      New fold algorithms in C++23, what they do, how to use them.<\/p>\n","protected":false},"author":706,"featured_media":35994,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-32015","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cplusplus"],"acf":[],"blog_post_summary":"
      New fold algorithms in C++23, what they do, how to use them.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/32015","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/users\/706"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/comments?post=32015"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/32015\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media\/35994"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media?parent=32015"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/categories?post=32015"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/tags?post=32015"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}