{"id":8587,"date":"2023-11-06T08:27:00","date_gmt":"2023-11-06T08:27:00","guid":{"rendered":"https:\/\/www.modernescpp.com\/?p=8587"},"modified":"2023-11-06T08:27:01","modified_gmt":"2023-11-06T08:27:01","slug":"the-ranges-library-in-c20-more-design-choices","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/the-ranges-library-in-c20-more-design-choices\/","title":{"rendered":"The Ranges Library in C++20: More Design Choices"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">The ranges library in C++20 made due to performance reasons a few unique design choices. These choices have consequences: cache issues and constness issues.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"979\" height=\"373\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/10\/TimelineCpp20Ranges.png\" alt=\"\" class=\"wp-image-8543\" srcset=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/10\/TimelineCpp20Ranges.png 979w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/10\/TimelineCpp20Ranges-300x114.png 300w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/10\/TimelineCpp20Ranges-768x293.png 768w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/10\/TimelineCpp20Ranges-705x269.png 705w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/10\/TimelineCpp20Ranges-845x321.png 845w\" sizes=\"auto, (max-width: 979px) 100vw, 979px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Here is a short reminder. In my last post, &#8220;<a href=\"https:\/\/www.modernescpp.com\/index.php\/the-ranges-library-in-c20-design-choices\/\" data-type=\"link\" data-id=\"https:\/\/www.modernescpp.com\/index.php\/the-ranges-library-in-c20-design-choices\/\">The Ranges Libray in C++20: Design Choices<\/a>&#8220;, I presented this possible implementation of <code>std::ranges::filter_view<\/code>:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"> <\/p>\n\n\n\n<!-- HTML generated using hilite.me --><div style=\"background: #f0f3f3; overflow:auto;width:auto;gray;border-width:.1em .1em .1em .8em\"><pre style=\"margin: 0; line-height: 125%\"><span style=\"color: #006699; font-weight: bold\">if<\/span> constexpr (<span style=\"color: #555555\">!<\/span>ranges<span style=\"color: #555555\">::<\/span>forward_range<span style=\"color: #555555\">&lt;<\/span>V<span style=\"color: #555555\">&gt;<\/span>)\n    <span style=\"color: #006699; font-weight: bold\">return<\/span> <span style=\"color: #0099FF; font-style: italic\">\/* iterator *\/<\/span>{<span style=\"color: #555555\">*<\/span><span style=\"color: #006699; font-weight: bold\">this<\/span>, ranges<span style=\"color: #555555\">::<\/span>find_if(base_, std<span style=\"color: #555555\">::<\/span>ref(<span style=\"color: #555555\">*<\/span>pred_))};\n<span style=\"color: #006699; font-weight: bold\">else<\/span>\n{\n    <span style=\"color: #006699; font-weight: bold\">if<\/span> (<span style=\"color: #555555\">!<\/span>begin_.has_value())\n        begin_ <span style=\"color: #555555\">=<\/span> ranges<span style=\"color: #555555\">::<\/span>find_if(base_, std<span style=\"color: #555555\">::<\/span>ref(<span style=\"color: #555555\">*<\/span>pred_)); <span style=\"color: #0099FF; font-style: italic\">\/\/ caching<\/span>\n    <span style=\"color: #006699; font-weight: bold\">return<\/span> <span style=\"color: #0099FF; font-style: italic\">\/* iterator *\/<\/span>{<span style=\"color: #555555\">*<\/span><span style=\"color: #006699; font-weight: bold\">this<\/span>, begin_.value())};\n}\n<\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">The key observation is that the <code>begin <\/code>iterator is cached for subsequent calls. This caching has two interesting consequences: <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Don\u2019t use a view on modified ranges.<\/li>\n\n\n\n<li>Don\u2019t copy a view.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Or, to put it positively: <strong>Use views directly after you have defined them.<\/strong> <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">There are more design choices you must know.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Constness<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">The member function of a view may cache the position. This implicates the following:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A function taking an arbitrary view should take its view by universal reference.<\/li>\n\n\n\n<li>Reading two views concurrently may be a data race.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Let&#8217;s discuss the first consequence.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Take Arbitrary Views by Universal <strong>Reference<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">The function <code>printElements<\/code> takes its view by universal reference.<\/p>\n\n\n\n<!-- HTML generated using hilite.me --><div style=\"background: #f0f3f3; overflow:auto;width:auto;gray;border-width:.1em .1em .1em .8em\"><pre style=\"margin: 0; line-height: 125%\"><span style=\"color: #007788; font-weight: bold\">void<\/span> <span style=\"color: #CC00FF\">printElements<\/span>(std<span style=\"color: #555555\">::<\/span>ranges<span style=\"color: #555555\">::<\/span>input_range <span style=\"color: #006699; font-weight: bold\">auto<\/span><span style=\"color: #555555\">&amp;&amp;<\/span> rang) {\n    <span style=\"color: #006699; font-weight: bold\">for<\/span> (<span style=\"color: #007788; font-weight: bold\">int<\/span> i<span style=\"color: #555555\">:<\/span> rang) {\n        std<span style=\"color: #555555\">::<\/span>cout <span style=\"color: #555555\">&lt;&lt;<\/span> i <span style=\"color: #555555\">&lt;&lt;<\/span> <span style=\"color: #CC3300\">&quot; &quot;<\/span>;  \n    }\n    std<span style=\"color: #555555\">::<\/span>cout <span style=\"color: #555555\">&lt;&lt;<\/span> <span style=\"color: #CC3300\">&#39;\\n&#39;<\/span>;\n}\n<\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\"><code>printElements <\/code>takes its argument by universal reference. Taking it by lvalue reference or by value is, in general, no option.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Taking the argument by <code>const <\/code>lvalue reference may not work because the implicit <code>begin <\/code>call on the view could modify it. On the contrary, a non-<code>const <\/code>lvalue reference cannot handle rvalues.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Taking the argument by value may invalidate the cache.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Concurrent Reading of Views may be a Data Ra<strong>ce<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">The following program exemplifies the concurrency issue with views:<\/p>\n\n\n\n<!-- HTML generated using hilite.me --><div style=\"background: #f0f3f3; overflow:auto;width:auto;gray;border-width:.1em .1em .1em .8em\"><pre style=\"margin: 0; line-height: 125%\"><span style=\"color: #0099FF; font-style: italic\">\/\/ dataRaceRanges.cpp<\/span>\n\n<span style=\"color: #009999\">#include &lt;numeric&gt;<\/span>\n<span style=\"color: #009999\">#include &lt;iostream&gt;<\/span>\n<span style=\"color: #009999\">#include &lt;ranges&gt;<\/span>\n<span style=\"color: #009999\">#include &lt;thread&gt;<\/span>\n<span style=\"color: #009999\">#include &lt;vector&gt;<\/span>\n \n<span style=\"color: #007788; font-weight: bold\">int<\/span> <span style=\"color: #CC00FF\">main<\/span>() {\n\n    std<span style=\"color: #555555\">::<\/span>vector<span style=\"color: #555555\">&lt;<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span><span style=\"color: #555555\">&gt;<\/span> vec(<span style=\"color: #FF6600\">1<\/span><span style=\"color: #AA0000; background-color: #FFAAAA\">&#39;<\/span><span style=\"color: #FF6600\">000<\/span>);\n    std<span style=\"color: #555555\">::<\/span>iota(vec.begin(), vec.end(), <span style=\"color: #FF6600\">0<\/span>);\n\n    <span style=\"color: #006699; font-weight: bold\">auto<\/span> first5Vector <span style=\"color: #555555\">=<\/span> vec <span style=\"color: #555555\">|<\/span> std<span style=\"color: #555555\">::<\/span>views<span style=\"color: #555555\">::<\/span>filter([](<span style=\"color: #006699; font-weight: bold\">auto<\/span> v) { <span style=\"color: #006699; font-weight: bold\">return<\/span> v <span style=\"color: #555555\">&gt;<\/span> <span style=\"color: #FF6600\">0<\/span>; }) \n                            <span style=\"color: #555555\">|<\/span> std<span style=\"color: #555555\">::<\/span>views<span style=\"color: #555555\">::<\/span>take(<span style=\"color: #FF6600\">5<\/span>);\n\n    std<span style=\"color: #555555\">::<\/span>jthread thr1([<span style=\"color: #555555\">&amp;<\/span>first5Vector]{\n        <span style=\"color: #006699; font-weight: bold\">for<\/span> (<span style=\"color: #007788; font-weight: bold\">int<\/span> i<span style=\"color: #555555\">:<\/span> first5Vector) {\n            std<span style=\"color: #555555\">::<\/span>cout <span style=\"color: #555555\">&lt;&lt;<\/span> i <span style=\"color: #555555\">&lt;&lt;<\/span> <span style=\"color: #CC3300\">&quot; &quot;<\/span>;  \n        }\n    });\n\n\n    <span style=\"color: #006699; font-weight: bold\">for<\/span> (<span style=\"color: #007788; font-weight: bold\">int<\/span> i<span style=\"color: #555555\">:<\/span> first5Vector) {\n        std<span style=\"color: #555555\">::<\/span>cout <span style=\"color: #555555\">&lt;&lt;<\/span> i <span style=\"color: #555555\">&lt;&lt;<\/span> <span style=\"color: #CC3300\">&quot; &quot;<\/span>;  \n    }\n\n    std<span style=\"color: #555555\">::<\/span>cout <span style=\"color: #555555\">&lt;&lt;<\/span> <span style=\"color: #CC3300\">&quot;<\/span><span style=\"color: #CC3300; font-weight: bold\">\\n\\n<\/span><span style=\"color: #CC3300\">&quot;<\/span>;\n    \n}\n<\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">I iterate in the program <code>dataRaceRanges.cpp<\/code> concurrently two times through a view in a non-modifying way. First, I iterate in the <code>std::jthread thr1<\/code> and second in the main function. This is a data race because both iterations implicitly use the member function <code>begin<\/code>, which may cache the position. <a href=\"http:\/\/(https:\/\/clang.llvm.org\/docs\/ThreadSanitizer.html\" data-type=\"link\" data-id=\"(https:\/\/clang.llvm.org\/docs\/ThreadSanitizer.html\">ThreadSanitizer<\/a> visualizes this data race and complains about a previous write on line 24:<code> std::cout &lt;&lt; i &lt;&lt; \" \";<\/code><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1030\" height=\"385\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/11\/dataRaceRanges-1030x385.png\" alt=\"\" class=\"wp-image-8592\" srcset=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/11\/dataRaceRanges-1030x385.png 1030w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/11\/dataRaceRanges-300x112.png 300w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/11\/dataRaceRanges-768x287.png 768w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/11\/dataRaceRanges-1536x574.png 1536w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/11\/dataRaceRanges-1500x561.png 1500w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/11\/dataRaceRanges-705x264.png 705w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/11\/dataRaceRanges.png 1960w\" sizes=\"auto, (max-width: 1030px) 100vw, 1030px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">On the contrary, iterating through a classical container such as<code> std::vector <\/code>is thread-safe. There is an additional difference between classical container and views.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Propagation of Constness<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Classical container model deep constness. They propagate their constness to their elements. This means that modifying elements of a constant container is impossible.<\/p>\n\n\n\n<!-- HTML generated using hilite.me --><div style=\"background: #f0f3f3; overflow:auto;width:auto;gray;border-width:.1em .1em .1em .8em\"><pre style=\"margin: 0; line-height: 125%\"><span style=\"color: #0099FF; font-style: italic\">\/\/ constPropagationContainer.cpp<\/span>\n\n<span style=\"color: #009999\">#include &lt;iostream&gt;<\/span>\n<span style=\"color: #009999\">#include &lt;vector&gt;<\/span>\n\n<span style=\"color: #006699; font-weight: bold\">template<\/span> <span style=\"color: #555555\">&lt;<\/span><span style=\"color: #006699; font-weight: bold\">typename<\/span> T<span style=\"color: #555555\">&gt;<\/span>\n<span style=\"color: #007788; font-weight: bold\">void<\/span> modifyConstRange(<span style=\"color: #006699; font-weight: bold\">const<\/span> T<span style=\"color: #555555\">&amp;<\/span> cont) {\n    cont[<span style=\"color: #FF6600\">0<\/span>] <span style=\"color: #555555\">=<\/span> <span style=\"color: #FF6600\">5<\/span>;\n}\n \n<span style=\"color: #007788; font-weight: bold\">int<\/span> main() {\n\n    std<span style=\"color: #555555\">::<\/span>vector myVec{<span style=\"color: #FF6600\">1<\/span>, <span style=\"color: #FF6600\">2<\/span>, <span style=\"color: #FF6600\">3<\/span>, <span style=\"color: #FF6600\">4<\/span>, <span style=\"color: #FF6600\">5<\/span>};\n    modifyConstRange(myVec);         <span style=\"color: #0099FF; font-style: italic\">\/\/ ERROR<\/span>\n\n} \n<\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">The call <code>modifyConstRange(myVec)<\/code> causes a compile-time error.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">On the contrary, views model shallow constness. They do not propagate the constness to their elements. The elements can still be modified.<\/p>\n\n\n\n<!-- HTML generated using hilite.me --><div style=\"background: #f0f3f3; overflow:auto;width:auto;gray;border-width:.1em .1em .1em .8em\"><pre style=\"margin: 0; line-height: 125%\"><span style=\"color: #0099FF; font-style: italic\">\/\/ constPropagationViews.cpp<\/span>\n\n<span style=\"color: #009999\">#include &lt;iostream&gt;<\/span>\n<span style=\"color: #009999\">#include &lt;ranges&gt;<\/span>\n<span style=\"color: #009999\">#include &lt;vector&gt;<\/span>\n\n<span style=\"color: #006699; font-weight: bold\">template<\/span> <span style=\"color: #555555\">&lt;<\/span><span style=\"color: #006699; font-weight: bold\">typename<\/span> T<span style=\"color: #555555\">&gt;<\/span>\n<span style=\"color: #007788; font-weight: bold\">void<\/span> modifyConstRange(<span style=\"color: #006699; font-weight: bold\">const<\/span> T<span style=\"color: #555555\">&amp;<\/span> cont) {\n    cont[<span style=\"color: #FF6600\">0<\/span>] <span style=\"color: #555555\">=<\/span> <span style=\"color: #FF6600\">5<\/span>;\n}\n \n<span style=\"color: #007788; font-weight: bold\">int<\/span> main() {\n\n    std<span style=\"color: #555555\">::<\/span>vector myVec{<span style=\"color: #FF6600\">1<\/span>, <span style=\"color: #FF6600\">2<\/span>, <span style=\"color: #FF6600\">3<\/span>, <span style=\"color: #FF6600\">4<\/span>, <span style=\"color: #FF6600\">5<\/span>};\n\n    modifyConstRange(std<span style=\"color: #555555\">::<\/span>views<span style=\"color: #555555\">::<\/span>all(myVec));   <span style=\"color: #0099FF; font-style: italic\">\/\/ OK<\/span>\n\n}   \n<\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">The call <code>modifyConstRange(std::views::all(myVec))<\/code> is fine.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">What&#8217;s Next?<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Coroutines are probably the most challenging part of C++20. My next post presents a guest post from Dian-Lun Lin. He will give a concise introduction to coroutines and exemplify his idea with a straightforward scheduler managing tasks.  <\/p>\n","protected":false},"excerpt":{"rendered":"<p>The ranges library in C++20 made due to performance reasons a few unique design choices. These choices have consequences: cache issues and constness issues. Here is a short reminder. In my last post, &#8220;The Ranges Libray in C++20: Design Choices&#8220;, I presented this possible implementation of std::ranges::filter_view: if constexpr (!ranges::forward_range&lt;V&gt;) return \/* iterator *\/{*this, ranges::find_if(base_, [&hellip;]<\/p>\n","protected":false},"author":21,"featured_media":8543,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[375],"tags":[413],"class_list":["post-8587","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c-20","tag-ranges"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/8587","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=8587"}],"version-history":[{"count":13,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/8587\/revisions"}],"predecessor-version":[{"id":8603,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/8587\/revisions\/8603"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/8543"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=8587"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=8587"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=8587"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}