Transform-reduce is a pattern in which a set of data is first modified by applying a transformation on each of the elements and then it is reduced to a single value. In C++, this can be implemented straightforwardly with std::transform<\/tt> and std::accumulate<\/tt>. In C++17, an alternative for std::accumulate<\/tt> is available; std::reduce<\/tt> sums a range of elements just like std::accumulate<\/tt>, except that it does so out of order. That means you cannot use it with operators that are not communicative or associative (including overloads of operator+<\/tt> that don’t exhibit these properties). On the other hand, there is yet another algorithm called std::transform_reduce<\/tt> that applies a functor to all the elements of a range and then reduces them, all in an out of order manner. And then, there are also parallel versions of these algorithms. In this post, I will try to compare the performance of these possible alternatives for implementing transform-reduce.<\/p>\n
Let’s start with a problem: we have a list of order prices on which we need to apply a discount; if the order price is greater then 100, then a 20% discount applies. We need to compute the total sum of all orders after discounts have been applied.<\/p>\n
For convenience, we will use the following function to apply a discount on an order price:<\/p>\n
inline double apply_discount(double const value)\r\n{\r\n return value > 100 ? 0.8 * value : value;\r\n}<\/pre>\nThe traditional way to solve this problem is to first use std::transform<\/tt> to modify the elements of the range by applying the discount (with apply_discount<\/tt>) and then summing all the resulted values with std::accumulate<\/tt>. That should look like the following:<\/p>\ntemplate <typename C>\r\nlong double transform_and_accummulate(C&& c)\r\n{\r\n std::transform(std::begin(c), std::end(c),\r\n std::begin(c),\r\n apply_discount);\r\n\r\n return std::accumulate(std::cbegin(c), std::cend(c), 0.0L);\r\n}<\/pre>\nIn C++17, we can replace std::accumulate<\/tt> with std::reduce<\/tt>, since summing the elements of the prices range can be done in any order; the result would be the same. std::reduce<\/tt> has various overloads<\/a> but for this problem we need one that takes the range bound iterators and an initial value (and implicitly uses std::plus<><\/tt> to sum the elements).<\/p>\ntemplate <typename C>\r\nlong double transform_and_reduce(C&& c)\r\n{\r\n std::transform(std::begin(c), std::end(c),\r\n std::begin(c),\r\n apply_discount);\r\n\r\n return std::reduce(std::cbegin(c), std::cend(c), 0.0L);\r\n}<\/pre>\nC++17 also provides a parallel version of tens of algorithms, including std::transform<\/tt> and std::reduce<\/tt> but not for std::accumulate<\/tt>. The algorithms that do have parallel versions have overloads that take an execution policy<\/a>. This can be one of:<\/p>\n\n- std::execution::seq<\/tt>: execution of the algorithm is sequential;<\/li>\n
- std::execution::par<\/tt>: execution of the algorithm may be parallelized on the calling thread or on another thread;<\/li>\n
- std::execution::par_unseq<\/tt>: execution of the algorithm may be parallelized, vectorized, or migrated across threads.<\/li>\n<\/ul>\n
When using std::execution::seq<\/tt>, the execution is the same as when using an overload without an execution policy. On the other hand, std::execution::par<\/tt> and std::execution::par_unseq<\/tt> may execute the algorithm in parallel. par_unseq<\/tt> requires stronger quarantees than par<\/tt>; the function calls are unsequenced with respect for each other. Because of that, it is not possible to perform vectorization unsafe operations, such as allocate or deallocate memory, acquire mutexes, use non-lockfree std::atomic<\/tt> specializations, when using this policy.<\/p>\n
With this in mind, we can rewrite the transform_and_reduce<\/tt> function to also specify an execution policy, as follows:<\/p>\ntemplate <typename C, class ExecutionPolicy>\r\nlong double transform_and_reduce(C&& c, ExecutionPolicy&& policy)\r\n{\r\n std::transform(std::forward<ExecutionPolicy>(policy),\r\n std::begin(c), std::end(c),\r\n std::begin(c),\r\n apply_discount);\r\n\r\n return std::reduce(std::forward<ExecutionPolicy>(policy),\r\n std::cbegin(c), std::cend(c), 0.0L);\r\n}<\/pre>\nThis can be, however, replaced with the C++17 new standard algorithm std::transform_reduce<\/tt>. This again has multiple overloads<\/a> to support different scenarios and needs but the one we are interested in takes a policy, range bound iterators, an initial value, a binary functor to reduce the values (we can use std::plus<><\/tt>) and a unary functor to transform the range elements.<\/p>\ntemplate <typename C, class ExecutionPolicy>\r\nlong double transform_reduce(C&& c, ExecutionPolicy&& policy)\r\n{\r\n return std::transform_reduce(\r\n std::forward<ExecutionPolicy>(policy),\r\n std::begin(c), std::end(c),\r\n 0.0L,\r\n std::plus<>(),\r\n apply_discount);\r\n}<\/pre>\nThe question is, how do these perform compared to each other for various range sizes. To check that, I have written the following testing program. It generates vectors of random values, from 100 to 100 million elements, calls all these functions, will all the three possible execution policies, and prints the results.<\/p>\n
\r\ninline void assert_are_equal(long double const d1, long double const d2, long double diff = 0.001)\r\n{\r\n if (std::abs(d1 - d2) > diff)\r\n std::terminate();\r\n}\r\n\r\nint main()\r\n{\r\n std::random_device rd;\r\n auto seed_data = std::array<int, std::mt19937::state_size> {};\r\n std::generate(std::begin(seed_data), std::end(seed_data), std::ref(rd));\r\n std::seed_seq seq(std::begin(seed_data), std::end(seed_data));\r\n auto eng = std::mt19937{ seq };\r\n auto dist = std::uniform_real_distribution<>{ 1, 250 };\r\n\r\n std::cout\r\n << std::left << std::setw(15) << \"size\"\r\n << std::left << std::setw(10) << \"t+a\/seq\"\r\n << std::left << std::setw(10) << \"t+r\/seq\"\r\n << std::left << std::setw(10) << \"t+r\/par\"\r\n << std::left << std::setw(10) << \"t+r\/vec\"\r\n << std::left << std::setw(10) << \"t_r\/sec\"\r\n << std::left << std::setw(10) << \"t_r\/par\"\r\n << std::left << std::setw(10) << \"t_r\/vec\"\r\n << '\\n';\r\n\r\n size_t size = 100;\r\n for (size_t i = 0; i < 13; ++i)\r\n {\r\n std::vector<double> v(size);\r\n std::generate_n(v.data(), size, [&eng, &dist]() {return dist(eng); });\r\n\r\n auto v1 = v;\r\n auto s1 = std::chrono::high_resolution_clock::now();\r\n auto r1 = transform_and_accummulate(v1);\r\n auto e1 = std::chrono::high_resolution_clock::now();\r\n\r\n auto v2 = v;\r\n auto s2 = std::chrono::high_resolution_clock::now();\r\n auto r2 = transform_and_reduce(v2, std::execution::seq);\r\n auto e2 = std::chrono::high_resolution_clock::now();\r\n\r\n auto v3 = v;\r\n auto s3 = std::chrono::high_resolution_clock::now();\r\n auto r3 = transform_and_reduce(v3, std::execution::par);\r\n auto e3 = std::chrono::high_resolution_clock::now();\r\n\r\n auto v4 = v;\r\n auto s4 = std::chrono::high_resolution_clock::now();\r\n auto r4 = transform_and_reduce(v4, std::execution::par_unseq);\r\n auto e4 = std::chrono::high_resolution_clock::now();\r\n\r\n auto v5 = v;\r\n auto s5 = std::chrono::high_resolution_clock::now();\r\n auto r5 = transform_reduce(v5, std::execution::seq);\r\n auto e5 = std::chrono::high_resolution_clock::now();\r\n\r\n auto v6 = v;\r\n auto s6 = std::chrono::high_resolution_clock::now();\r\n auto r6 = transform_reduce(v6, std::execution::par);\r\n auto e6 = std::chrono::high_resolution_clock::now();\r\n\r\n auto v7 = v;\r\n auto s7 = std::chrono::high_resolution_clock::now();\r\n auto r7 = transform_reduce(v7, std::execution::par_unseq);\r\n auto e7 = std::chrono::high_resolution_clock::now();\r\n\r\n auto t1 = std::chrono::duration_cast<std::chrono::microseconds>(e1 - s1);\r\n auto t2 = std::chrono::duration_cast<std::chrono::microseconds>(e2 - s2);\r\n auto t3 = std::chrono::duration_cast<std::chrono::microseconds>(e3 - s3);\r\n auto t4 = std::chrono::duration_cast<std::chrono::microseconds>(e4 - s4);\r\n auto t5 = std::chrono::duration_cast<std::chrono::microseconds>(e5 - s5);\r\n auto t6 = std::chrono::duration_cast<std::chrono::microseconds>(e6 - s6);\r\n auto t7 = std::chrono::duration_cast<std::chrono::microseconds>(e7 - s7);\r\n\r\n assert_are_equal(r1, r2);\r\n assert_are_equal(r1, r3);\r\n assert_are_equal(r1, r4);\r\n assert_are_equal(r1, r5);\r\n assert_are_equal(r1, r6);\r\n assert_are_equal(r1, r7);\r\n\r\n std::cout\r\n << std::left << std::setw(15) << size\r\n << std::left << std::setw(10) << t1.count()\r\n << std::left << std::setw(10) << t2.count()\r\n << std::left << std::setw(10) << t3.count()\r\n << std::left << std::setw(10) << t4.count()\r\n << std::left << std::setw(10) << t5.count()\r\n << std::left << std::setw(10) << t6.count()\r\n << std::left << std::setw(10) << t7.count()\r\n << '\\n';\r\n\r\n size *= (i % 2 == 0 ? 5 : 2);\r\n }\r\n}<\/pre>\nHere is an output example (Visual Studio 2017 15.6, release built for x64):<\/p>\n
\r\nsize t+a\/seq t+r\/seq t+r\/par t+r\/vec t_r\/sec t_r\/par t_r\/vec\r\n100 0 0 89 6 0 3 2\r\n500 2 1 37 20 1 7 6\r\n1000 4 4 37 21 4 14 20\r\n5000 22 23 52 64 22 32 36\r\n10000 47 46 76 90 45 47 49\r\n50000 229 238 170 177 220 132 136\r\n100000 456 473 296 300 491 194 188\r\n500000 2250 2688 922 890 2922 829 977\r\n1000000 5200 5117 1618 1662 4604 1457 1461\r\n5000000 24074 27139 9195 12550 24576 7296 7768\r\n10000000 46948 52491 17609 26444 46819 23617 15381\r\n50000000 237774 260770 92045 91120 234912 86378 101222\r\n100000000 475621 526457 205715 184198 475033 180723 208145\r\n<\/pre>\nWhat I can see from here is that:<\/p>\n
\n- until 50,000 elements std::transform<\/tt> + std::accumulate<\/tt>, sequential std::transform<\/tt> + std::reduce<\/tt> and std::transform_reduce<\/tt> have similar times<\/li>\n
- after 50,000 elements the parallel version of std::transform_reduce<\/tt> is performing the best, with parallel std::transform<\/tt> + std::reduce<\/tt> comming close<\/li>\n
- the par_unseq<\/tt> version of std::transform<\/tt> + std::reduce<\/tt> is slightly better than the par<\/tt> version after more than 10 million elements; that is not the case for std::transform_reduce<\/tt>, whose vectorized version is only better at around 10 million elements.<\/li>\n<\/ul>\n
Of course, you could argue that the call to std::transform<\/tt> is not actually needed here and the discount can be applied while computing the sum. Although this has different semantics, these functions could be simply rewritten as follows:<\/p>\n\r\ntemplate <typename C>\r\nlong double transform_and_accummulate(C&& c)\r\n{\r\n return std::accumulate(\r\n std::cbegin(c), std::cend(c),\r\n 0.0L,\r\n [](auto const sum, auto const price) {\r\n return sum + apply_discount(price); });\r\n}\r\n\r\ntemplate <typename C, class ExecutionPolicy>\r\nlong double transform_and_reduce(C&& c, ExecutionPolicy&& policy)\r\n{\r\n return std::reduce(\r\n std::forward<ExecutionPolicy>(policy),\r\n std::cbegin(c), std::cend(c),\r\n 0.0L,\r\n [](auto const sum, auto const price) {\r\n return sum + apply_discount(price); });\r\n}<\/pre>\nIn this case, however, you can not execute transform_and_reduce<\/tt> with the par<\/tt> or par_unseq<\/tt> policies because they would not yield correct results.<\/p>\n\r\nsize t+a\/seq t+r\/seq\r\n100 0 0 \r\n500 2 2 \r\n1000 4 4 \r\n5000 21 21 \r\n10000 43 42 \r\n50000 223 226 \r\n100000 433 449 \r\n500000 2455 2264 \r\n1000000 4774 4605 \r\n5000000 23687 23554 \r\n10000000 45510 45672 \r\n50000000 229429 229375 \r\n100000000 459254 460425 <\/pre>\nLet us complicate the problem a bit and consider a list of orders, each order having a quantity and price per item. We should again calculate the total orders price, by summing individual order prices (quantity * price) after applying a discount the same way we did earlier. We could use the following order structure:<\/p>\n
struct order\r\n{\r\n int quantity;\r\n double price;\r\n};<\/pre>\nThe implementation using std::transform<\/tt> + std::accumulate<\/tt> could look as follows:<\/p>\ntemplate <typename C>\r\nlong double transform_and_accumulate(C&& c)\r\n{\r\n std::transform(\r\n std::begin(c), std::end(c),\r\n std::begin(c),\r\n [](order const & o) {\r\n return order{ o.quantity, apply_discount(o.price) }; });\r\n\r\n return std::accumulate(\r\n std::cbegin(c), std::cend(c),\r\n 0.0L,\r\n [](auto const & sum, auto const & o) {\r\n return sum + (o.quantity * o.price); });\r\n}<\/pre>\nThe alternative with std::transform<\/tt> + std::reduce<\/tt> is not as straight forward as it may seem. First of all, std::reduce<\/tt> cannot use the same binary functor as std::accumulate<\/tt> because of some key requirements:<\/p>\n\n- T<\/tt>, the type of the initial value, must meet the requirements of MoveConstructible<\/a>, and<\/li>\n
- binary_op(init, *first)<\/tt>, binary_op(*first, init)<\/tt>, binary_op(init, init)<\/tt>, and binary_op(*first, *first)<\/tt> must be convertible to T<\/tt>.<\/li>\n<\/ul>\n
That means we must perform a certain trick to make std::reduce<\/tt> work:<\/p>\n\n- the type of the initial value should be order<\/tt> and not long double<\/tt>, and<\/li>\n
- the return type of the binary operation should also be order<\/tt>; this functor would actually return a new order<\/tt> value with the quantity being irrelevant (and set to zero) and the price being the accumulated total price.<\/li>\n<\/ul>\n
However, this no longer makes it possible for std::reduce<\/tt> to execute in parallel and yield correct results. Therefore, the implementation in this case could be as follows:<\/p>\ntemplate <typename C, class ExecutionPolicy>\r\nlong double transform_and_reduce(C&& c, ExecutionPolicy&& policy)\r\n{\r\n std::transform(\r\n std::forward<ExecutionPolicy>(policy),\r\n std::begin(c), std::end(c),\r\n std::begin(c),\r\n [](order const & o) {\r\n return order{ o.quantity, apply_discount(o.price) }; });\r\n\r\n return std::reduce( \r\n std::cbegin(c), std::cend(c),\r\n order{ 0, 0.0L },\r\n [](order const & sum, order const & o) {\r\n return order{ 0, sum.price + (o.quantity * o.price) }; }).price;\r\n}<\/pre>\nThis does not look great and it’s exactly where std::transform_reduce<\/tt> comes to the rescue. This standard algorithm allows us to supply a unary operation to transform each element of the input range; we can use a lambda that returns quantity * discount(price)<\/tt>. Then, we can use the binary functor std::plus<><\/tt> to sum the results of the unary operation on an initial value. And this can all be done in parallel or even parallel unsequenced.<\/p>\ntemplate <typename C, class ExecutionPolicy>\r\nlong double transform_reduce(C&& c, ExecutionPolicy&& policy)\r\n{\r\n return std::transform_reduce(\r\n std::forward<ExecutionPolicy>(policy),\r\n std::cbegin(c), std::cend(c),\r\n 0.0L,\r\n std::plus<>(),\r\n [](order const & o) {\r\n return o.quantity * apply_discount(o.price); });\r\n}<\/pre>\nThe results in this case look like the following:<\/p>\n
\r\nsize t+a\/seq t+r\/seq t+r\/par t+r\/vec t_r\/sec t_r\/par t_r\/vec\r\n100 0 1 66 8 0 3 2\r\n500 2 6 14 20 2 11 11\r\n1000 5 12 54 27 4 20 18\r\n5000 29 60 80 86 22 37 26\r\n10000 60 128 135 205 45 56 51\r\n50000 392 612 495 552 227 114 107\r\n100000 590 1214 1786 1238 478 193 186\r\n500000 3155 6279 4706 4187 2526 813 704\r\n1000000 6709 12746 9185 9654 5522 1750 1374\r\n5000000 31477 63989 42310 41512 26201 8015 7190\r\n10000000 62533 128311 92530 81102 51302 16070 14188\r\n50000000 313559 643133 427432 485140 270360 101922 81585\r\n100000000 632420 1282368 877781 941224 599787 244742 284056\r\n<\/pre>\nWhat we can see from here is that:<\/p>\n
\n- std::transform<\/tt> + std::accumulate<\/tt> performs much better than std::transform<\/tt> + std::reduce<\/tt><\/li>\n
- std::transform_reduce<\/tt> performs better than any of the two, regardless it is sequential or parallel, after about 10000 elements<\/li>\n
- the parallel unsequenced version is better or much better comparing to sequential and parallel runs when the size of the input range is between 50,000 elements.<\/li>\n<\/ul>\n
Conclusion<\/h3>\n
In C++17, there are various alternatives for implementing the transform-reduce pattern, sequentially, in parallel or even parallel and vectorized. These can accommodate different needs, but the performance may differ depending on the actual problem you are solving and the size of the input datasets. Therefore, you should use the one that fits your needs the best.<\/p>\n
See also<\/h3>\n\n- std::accumulate vs. std::reduce<\/a><\/li>\n
- C++17: std::transform_reduce()<\/a><\/li>\n
- Parallel Algorithms of the Standard Template Library<\/a><\/li>\n
- C++17 in details: Parallel Algorithms<\/a><\/li>\n
- Transform Reduce, an Additional Algorithm for C++ Extensions for Parallelism<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
Transform-reduce is a pattern in which a set of data is first modified by applying a transformation on each of the elements and then it is reduced to a single value. In C++, this can be implemented straightforwardly with std::transform<\/tt> and std::accumulate<\/tt>. In C++17, an alternative for std::accumulate<\/tt> is available; std::reduce<\/tt> sums a range of elements just like std::accumulate<\/tt>, except that it does so out of order. That means you cannot use it with operators that are not communicative or associative (including overloads of operator+<\/tt> that don’t exhibit these properties). On the other hand, there is yet another algorithm called std::transform_reduce<\/tt> that applies a functor to all the elements of a range and then reduces them, all in an out of order manner. And then, there are also parallel versions of these algorithms. In this post, I will try to compare the performance of these possible alternatives for implementing transform-reduce.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","advgb_blocks_editor_width":"","advgb_blocks_columns_visual_guide":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[7],"tags":[557,451,475,559,558,487],"class_list":["post-2951","post","type-post","status-publish","format-standard","hentry","category-c","tag-algorithms","tag-c","tag-c17","tag-perf","tag-reduce","tag-transform"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t