{"id":10863,"date":"2011-04-21T07:00:00","date_gmt":"2011-04-21T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2011\/04\/21\/the-performance-improvements-of-a-lock-free-algorithm-is-often-not-in-the-locking\/"},"modified":"2011-04-21T07:00:00","modified_gmt":"2011-04-21T07:00:00","slug":"the-performance-improvements-of-a-lock-free-algorithm-is-often-not-in-the-locking","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20110421-00\/?p=10863","title":{"rendered":"The performance improvements of a lock-free algorithm is often not in the locking"},"content":{"rendered":"

\n\nGWO\nwonders what the conditions are under which the lock-free version\nsignificantly outpeforms a simple critical section<\/a>.\n<\/p>\n

\nRemember that switching to a lock-free algorithm should be guided\nby performance measurements.\nSwitching from a simple algorithm to a complex one shouldn’t be done\nunless you know that the simple algorithm is having trouble.\n<\/p>\n

\nThat said, here are some non-obvious advantages of a lock-free algorithm\nover one that uses a simple lock.\n(Later, we’ll see how you can take advantage of\nthese techniques without actually going lock-free.)\n<\/p>\n

\nConsider a program that uses a simple critical section to perform\nsomething like the singleton constructor.\nInstead of a fancy lock-free algorithm, we use the much simpler\nversion:\n<\/p>\n

\nCRITICAL_SECTION g_csSingletonX;\nX *g_px = NULL;\nX *GetSingletonX()\n{\n    EnterCriticalSection(&g_csSingletonX);\n    if (g_px == NULL)\n    {\n        g_px = new(nothrow) X();\n    }\n    LeaveCriticalSection(&g_csSingletonX);\n    return g_px;\n}\n<\/pre>\n
\nThis simple code\ncan run into trouble if the constructor function itself requires\nsome locks,\nbecause now you have to impose a\n\nlock hierarchy<\/a>\nin order to avoid a deadlock.\n(And this becomes impossible if the constructor function\n\nbelongs to code outside your control<\/a>.)\n<\/p>\n
\nWhen working out what your lock hierarchy should be,\nyou may discover that you need to consolidate some locks.\nThis avoids the inversion problem,\nbut it also reduces your lock granularity.\nYou might decide to use a single lock to cover all singletons,\nand then you later discover that you also have to extend the lock\nthat protects X’s constructor to cover other operations on X.\n<\/p>\n
\nCRITICAL_SECTION g_csCommon;\n\/\/ (updated to remove double-check lock because that just raises\n\/\/ more questions that distract from the point of the article)\nX *GetSingletonX()\n{\n    EnterCriticalSection(&g_csCommon);\n    if (g_px == NULL)\n    {\n        g_px = new(nothrow) X();\n    }\n    LeaveCriticalSection(&g_csCommon);\n    return g_px;\n}\nY *GetSingletonY()\n{\n    EnterCriticalSection(&g_csCommon);\n    if (g_py == NULL)\n    {\n        g_py = new(nothrow) Y();\n    }\n    LeaveCriticalSection(&g_csCommon);\n    return g_py;\n}\nvoid X::DoSomething()\n{\n    EnterCriticalSection(&g_csCommon);\n    .. something ..\n    LeaveCriticalSection(&g_csCommon);\n}\n<\/pre>\n
\nOver time, your quiet little singleton lock has turned\ninto a high-contention lock in your system.\n<\/p>\n
\nOne nice thing about a lock-free algorithm is that since there\nis no lock, it can’t create inversion in a lock hierarchy.\n(Of course, you have to be careful not to use the interlocked operations\n\nto build a private lock<\/a>, because that puts you back where\nyou started.)\n<\/p>\n
\nAnother nice consequence of a lock-free algorithm is that,\nsince there is no lock, you don’t have to handle the\n\nWAIT_ABANDONED<\/code><\/a> case.\nThe data structure is never inconsistent; it passes atomically\nfrom one consistent state to another.\nTherefore, there’s no need to write code to clean up leftover\ninconsistency.\nThis came in handy in\n\na case we looked at earlier<\/a>,\nso that an application which crashes at an inopportune time will not\ncorrupt the shared data and require a server reboot.<\/p>\n","protected":false},"excerpt":{"rendered":"
GWO wonders what the conditions are under which the lock-free version significantly outpeforms a simple critical section. Remember that switching to a lock-free algorithm should be guided by performance measurements. Switching from a simple algorithm to a complex one shouldn’t be done unless you know that the simple algorithm is having trouble. That said, here […]<\/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-10863","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
GWO wonders what the conditions are under which the lock-free version significantly outpeforms a simple critical section. Remember that switching to a lock-free algorithm should be guided by performance measurements. Switching from a simple algorithm to a complex one shouldn’t be done unless you know that the simple algorithm is having trouble. That said, here […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/10863","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=10863"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/10863\/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=10863"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=10863"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=10863"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}