{"id":108412,"date":"2023-07-12T07:00:00","date_gmt":"2023-07-12T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=108412"},"modified":"2023-06-19T08:36:29","modified_gmt":"2023-06-19T15:36:29","slug":"20230712-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20230712-00\/?p=108412\/","title":{"rendered":"How to clone a Windows Runtime vector in the face of possible concurrent modification, part 1"},"content":{"rendered":"<p>Some time ago, we looked at <a title=\"How do I make a clone of a Windows Runtime vector in C++\/WinRT?\" href=\"https:\/\/devblogs.microsoft.com\/oldnewthing\/20191122-00\/?p=103123\"> making a clone of a Windows Runtime vector in C++\/WinRT<\/a>. We ended up with<\/p>\n<pre>IVector&lt;Thing&gt; original = GetTheThings();\r\nstd::vector&lt;Thing&gt; temp(original.Size(), <a title=\"Producing an empty Windows Runtime type in C++\/WinRT\" href=\"https:\/\/devblogs.microsoft.com\/oldnewthing\/20220504-00\/?p=106569\">winrt_empty_value<\/a>&lt;Thing&gt;());\r\noriginal.GetMany(0, temp);\r\nIVector&lt;Thing&gt; clone = multi_threaded_vector(std::move(temp));\r\n<\/pre>\n<p>I made two changes to the code:<\/p>\n<ul>\n<li>I used <code>winrt_<wbr \/>empty_<wbr \/>value<\/code> to fill the vector with emptiness instead of default-constructed <code>Thing<\/code>s.<\/li>\n<li>I upgraded the code we had last time from <code>single_<wbr \/>threaded_<wbr \/>vector<\/code> to <code>multi_<wbr \/>threaded_<wbr \/>vector<\/code>.<\/li>\n<\/ul>\n<p>I noted at the time that this code assumes that the vector is not being mutated concurrently. If the vector size changes between the time we check the <code>Size()<\/code> and the time we call <code>GetMany()<\/code>, then we will either read too many or too few items.<\/p>\n<p>I had left dealing with concurrency as an exercise. Let&#8217;s solve the exercise.<\/p>\n<p>To deal with the case that the vector shrinks unexpectedly, you can check how many items <code>GetMany<\/code> actually retrieved:<\/p>\n<pre>IVector&lt;Thing&gt; original = GetTheThings();\r\nstd::vector&lt;Thing&gt; temp(original.Size(), winrt_empty_value&lt;Thing&gt;());\r\n<span style=\"border: solid 1px currentcolor;\">temp.erase(temp.begin() + original.GetMany(0, temp), temp.end());<\/span>\r\nIVector&lt;Thing&gt; clone = multi_threaded_vector(std::move(temp));\r\n<\/pre>\n<p>The <code>GetMany()<\/code> method returns the actual number of elements retrieved. If the vector shrinks unexpectedly, then it will return the new smaller size of the vector, and we erase the extra elements. (We saw last time <a title=\"Why does the compiler complain about a missing constructor when I'm just resizing my std::vector to a smaller size?\" href=\"https:\/\/devblogs.microsoft.com\/oldnewthing\/20230711-00\/?p=108408\"> why we are using <code>erase<\/code> instead of <code>resize<\/code><\/a>.)<\/p>\n<p>The trickier part is detecting whether the vector grew. In that case, the call to <code>GetMany()<\/code> will return, &#8220;Yup, I got all the elements you requested,&#8221; but it has no way of telling you, &#8220;But there are still more to go.&#8221; We&#8217;ll have to figure out some other way to get this information.<\/p>\n<p>One thing that might occur to you is to recheck the size after the <code>GetMany()<\/code> call.<\/p>\n<pre>IVector&lt;Thing&gt; original = GetTheThings();\r\nstd::vector&lt;Thing&gt; temp{ original.Size() };\r\n<span style=\"border: solid 1px currentcolor;\">do {<\/span>\r\n    temp.erase(temp.begin() + original.GetMany(0, temp), temp.end());\r\n<span style=\"border: solid 1px currentcolor;\">} while (temp.size() != original.Size());<\/span>\r\nIVector&lt;Thing&gt; clone = multi_threaded_vector(std::move(temp));\r\n<\/pre>\n<p>However, this doesn&#8217;t work because it fails to detect the case where the vector changes size <i>twice<\/i>.<\/p>\n<p>\ncontents = <code>{ 3, 2 }<\/code> (size = 2)<code>temp.size() == original.Size()<\/code> (2 == 2)<\/p>\n<table class=\"cp3\" style=\"border-collapse: collapse;\" border=\"1\" cellspacing=\"0\" cellpadding=\"3\">\n<tbody>\n<tr>\n<th>Thread 1<\/th>\n<th>Thread 2<\/th>\n<\/tr>\n<tr>\n<td colspan=\"2\" align=\"center\">contents = <code>{ 1, 2 }<\/code> (size = 2)<\/td>\n<\/tr>\n<tr>\n<td><code>temp{ original.size() }; \/\/ 2<\/code><\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>&nbsp;<\/td>\n<td>contents = <code>{ 3, 1, 2 }<\/code> (size = 3)<\/td>\n<\/tr>\n<tr>\n<td><code>temp.resize(original.GetMany(0, temp))<\/code><br \/>\n<code>\/\/ temp = { 3, 1 }<\/code><\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>When we re-check the size, we see that the size is still 2, and we think that means that we got all of the items. However, the values in <code>temp<\/code> are <code>{ 3, 1 }<\/code> which was never the contents of the original vector at any point.<\/p>\n<p>The trick is to over-allocate the buffer by one element, and then ask for one too many elements. If we get more elements than we expected, then the vector grew by at least one (but possibly more), so we loop back and try again. Otherwise, we know that we got all the elements, and we can resize the vector to match the actual number.<\/p>\n<p>The important thing is that we get the elements in a single <code>GetMany()<\/code> call, which is atomic.<\/p>\n<pre>IVector&lt;Thing&gt; original = GetTheThings();\r\n<span style=\"border: solid 1px currentcolor; border-bottom: none;\">std::vector&lt;Thing&gt; temp;                                  <\/span>\r\n<span style=\"border: 1px currentcolor; border-style: none solid;\">uint32_t expected;                                        <\/span>\r\n<span style=\"border: 1px currentcolor; border-style: none solid;\">uint32_t actual;                                          <\/span>\r\n<span style=\"border: 1px currentcolor; border-style: none solid;\">do {                                                      <\/span>\r\n<span style=\"border: 1px currentcolor; border-style: none solid;\">    expected = original.Size();                           <\/span>\r\n<span style=\"border: 1px currentcolor; border-style: none solid;\">    temp.resize(expected + 1, winrt_empty_value&lt;Thing&gt;());<\/span>\r\n<span style=\"border: 1px currentcolor; border-style: none solid;\">    actual = original.GetMany(0, temp);                   <\/span>\r\n<span style=\"border: 1px currentcolor; border-style: none solid;\">} while (actual &gt; expected);                              <\/span>\r\n<span style=\"border: solid 1px currentcolor; border-top: none;\">temp.resize(actual, winrt_empty_value&lt;Thing&gt;());          <\/span>\r\nIVector&lt;Thing&gt; clone = multi_threaded_vector(std::move(temp));\r\n<\/pre>\n<p>Next time, we will try to encapsulate this pattern into a function.<\/p>\n<p><b>Bonus chatter<\/b>: You might decide to simply abandon the operation in the face of concurrent modification, the theory being that if somebody else is modifying the vector concurrently, we will just report the problem to the caller and let them decide how to proceed.<\/p>\n<pre>IVector&lt;Thing&gt; original = GetTheThings();\r\nstd::vector&lt;Thing&gt; temp;\r\nauto expected = original.Size();\r\ntemp.resize(expected + 1, winrt_empty_value&lt;Thing&gt;());\r\nauto actual = original.GetMany(0, temp);\r\n<span style=\"border: solid 1px currentcolor; border-bottom: none;\">if (actual &gt; expected) {                 <\/span>\r\n<span style=\"border: 1px currentcolor; border-style: none solid;\">    throw winrt::hresult_changed_state();<\/span>\r\n<span style=\"border: solid 1px currentcolor; border-top: none;\">}                                        <\/span>\r\ntemp.erase(temp.begin() + actual, temp.end());\r\nIVector&lt;Thing&gt; clone = multi_threaded_vector(std::move(temp));\r\n<\/pre>\n<p>There&#8217;s an interesting question here: What should happen if we detect a concurrent modification that nevertheless did not prevent us from making an atomic clone of the vector? That would be the case if <code>actual &lt; expected<\/code>.<\/p>\n<p>One argument is that we should throw a state change exception, just like we do for a concurrent modification that we cannot recover from. The theory here is that we should report concurrent modifications consistently, especially if concurrent modification is not something the caller was expecting. In that case, we would throw when <code>actual != expected<\/code>. It would however fail to detect the case where the concurrent modification did not have a net change to the size of the vector.<\/p>\n<p>Another school of thought is that we should report problems only if we can&#8217;t fix them. In that case, we throw only if <code>actual &gt; expected<\/code>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Backing off and retrying, but the detection is the tricky part.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-108412","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"<p>Backing off and retrying, but the detection is the tricky part.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/108412","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=108412"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/108412\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=108412"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=108412"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=108412"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}