{"id":11013,"date":"2011-04-06T07:00:01","date_gmt":"2011-04-06T07:00:01","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2011\/04\/06\/lock-free-algorithms-choosing-a-unique-value-solutions\/"},"modified":"2011-04-06T07:00:01","modified_gmt":"2011-04-06T07:00:01","slug":"lock-free-algorithms-choosing-a-unique-value-solutions","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20110406-01\/?p=11013\/","title":{"rendered":"Lock-free algorithms: Choosing a unique value (solutions)"},"content":{"rendered":"

\nLast time, I left a\n\nwarm-up exercise<\/a>\nconsisting of a code fragment which tries to compute a unique\nprocess-wide value.\nHere it is again:\n<\/p>\n

\n
\ndwUniqueId = InterlockedCompareExchange(&g_dwUniqueId,\n                                        g_dwUniqueId+1,\n                                        g_dwUniqueId);\n<\/pre>\n<\/blockquote>\n
\nIt may be easier to enumerate what the function does right<\/i>\nrather than what it does wrong.\n<\/p>\n
\nUm, the words are correctly-spelled.\n<\/p>\n
\nThat’s about it.\n<\/p>\n
\nDamien was the first to note that\n\nthe author basically reimplemented Interlocked­Increment<\/code>.\nPoorly<\/a>.\n<\/p>\n
\nAs we saw earlier, the algorithm for performing complex calculations with\ninterlocked functions is\n\n(capture, compute, compare-exchange, retry)<\/a>.\nBut the above code didn’t do any of these things.\n<\/p>\n
\nBy failing to capture the values, the code is vulnerable to another\nthread modifying the g_dwUniqueId<\/code> value simultaneously.\nThis means that the computation step can fail,\nbecause the inconsistent reads of g_dwUniqueId<\/code>\nresult in who-knows-what getting passed to the\nInterlocked­Compare­Exchange<\/code> function.\n<\/p>\n
\nOkay, they managed to spell\nInterlocked­Compare­Exchange<\/code> correctly.\n<\/p>\n
\nAnd then they forgot to retry the operation if the compare-exchange\nfailed,\nwhich means that they will just proceed with whatever value the\ng_dwUniqueId<\/code>\nvariable held at the time of the\nInterlocked­Compare­Exchange<\/code> call.\nIf it just got incremented by another thread, then this thread\nand the other thread will be using the same “unique” value.\n<\/p>\n
\nJoshua points out that\n\ncompiler optimization can prevent the capture from being a true capture<\/a>.\nThough I would put the volatile<\/code> keyword on\ng_dwUniqueId<\/code> rather than scv<\/code>,\nbecause the volatile object is the global variable, not the local.\nMarking the local as volatile forces all accesses to the local to be\nexecuted as written, but the compiler can still optimize the access\nto g_dwUniqueId<\/code>.\n(It might, for example, propagate the value in from a previous read\nearlier in the function.)\n<\/p>\n
\nAnd do take into consideration\n\nLeo Davidson’s warning<\/a>:\nThis series of articles is a peek behind the scenes<\/i> series,\nnot a here’s how you should do it<\/i> series.\nWe’re taking apart a bunch of toasters to see how they work.\nWhen possible, take advantage of code written by people smarter\nthan you.<\/p>\n","protected":false},"excerpt":{"rendered":"
Last time, I left a warm-up exercise consisting of a code fragment which tries to compute a unique process-wide value. Here it is again: dwUniqueId = InterlockedCompareExchange(&g_dwUniqueId, g_dwUniqueId+1, g_dwUniqueId); It may be easier to enumerate what the function does right rather than what it does wrong. Um, the words are correctly-spelled. That’s about it. Damien […]<\/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-11013","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Last time, I left a warm-up exercise consisting of a code fragment which tries to compute a unique process-wide value. Here it is again: dwUniqueId = InterlockedCompareExchange(&g_dwUniqueId, g_dwUniqueId+1, g_dwUniqueId); It may be easier to enumerate what the function does right rather than what it does wrong. Um, the words are correctly-spelled. That’s about it. Damien […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/11013","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=11013"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/11013\/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=11013"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=11013"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=11013"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}