{"id":10993,"date":"2011-04-08T07:00:00","date_gmt":"2011-04-08T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2011\/04\/08\/lock-free-algorithms-the-singleton-constructor-answer-to-exercises\/"},"modified":"2011-04-08T07:00:00","modified_gmt":"2011-04-08T07:00:00","slug":"lock-free-algorithms-the-singleton-constructor-answer-to-exercises","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20110408-00\/?p=10993","title":{"rendered":"Lock-free algorithms: The singleton constructor (answer to exercises)"},"content":{"rendered":"

\n\nA few days ago<\/a>,\nI asked you to make an existing class multithread-safe.\nThe class caches objects called SINGLETON­INFO<\/code>\nwhich are indexed by a 32-bit ID.\nThe cache is implemented as an array that dynamically resizes as\nmore items are added to it.\nA naïve multithreaded version might use a slim reader-writer lock\nwith shared access on reads, exclusive access on writes,\nand mixed access on the treacherous\n“create if it doesn’t already exist” path.\n<\/p>\n

\nLet’s see.\nFirst of all, the function doesn’t allocate the memory for the cache\nuntil somebody actually tries to look something up.\nBut duh, that’s the whole point of the class: To look up things!\nThe only time this lazy-initialization actually provides a benefit is\nif somebody creates a Singleton­Manager<\/code>,\ncalls no methods on it<\/i>,\nand then destroys it.\n<\/p>\n

\nThis doesn’t happen in practice, and even if it did,\nit’s certainly not a scenario we’re going to optimize for.\nGet rid of the lazy-initialization of the cache; it makes multithreading\nunnecessarily complicated.\n<\/p>\n

\nSecond, since the only way an ITEM­CONTROLLER<\/code> can\nget into the cache is via the SINGLETON­INFO<\/code>,\nif a Singleton­Manager<\/code> is told,\n“Here are 30 item IDs and their corresponding controller creation\nfunctions,”\nthen the cache can never hold more than 30 items.\nIf you only know how to create 30 items, and you never create\nmore than one copy of each item, then you’re never going to create\nmore than 30 items.\n<\/p>\n

\nTherefore, instead of managing a dynamically-growing array,\nwe can allocate a fixed-size array at construction\nof length equal to the number of SINGLETON­INFO<\/code> elements.\nThis avoids having to lock around the code that reallocates the array.\nSince the array length is in the range 30–50, we don’t have\nthe problem of allocating megabytes of memory to track just a few objects.\nIn the worst case, we allocate a 50-element cache.\n<\/p>\n

\nNext, we can store each ITEM­CONTROLLER<\/code> in the same\nposition in the cache array as it exists in the SINGLETON­INFO<\/code>\narray.\n<\/p>\n

\nWith these simplifications, we see that we don’t need to do any\nlocking or complicated duplicate-detection.\nAfter locating the ID in the SINGLETON­INFO<\/code> array,\nlook at the corresponding entry in the cache array\nand perform a singleton initialization there.\n<\/p>\n

\nstruct ITEMCONTROLLER;\nstruct SINGLETONINFO {\n DWORD dwId;\n ITEMCONTROLLER *(*pfnCreateController)();\n};\nclass SingletonManager {\npublic:\n \/\/ rgsi is an array that describes how to create the objects.\n \/\/ It's a static array, with csi in the range 20 to 50.\n SingletonManager(const SINGLETONINFO *rgsi, UINT csi)\n               : m_rgsi(rgsi), m_csi(csi),\n                 m_rgpic(new ITEMCONTROLLER*[csi]) { }\n ~SingletonManager() { ... }\n ITEMCONTROLLER *Lookup(DWORD dwId);\nprivate:\n const SINGLETONINFO *m_rgsi;\n int m_csi;\n \/\/ Array that describes objects we've created\n \/\/ runs parallel to m_rgsi\n ITEMCONTROLLER *m_pic;\n};\nITEMCONTROLLER *SingletonManager::Lookup(DWORD dwId)\n{\n int i;\n \/\/ Convert ID to index\n for (i = 0; i = m_csi) return NULL; \/\/ not something we know about\n \/\/ Singleton constructor pattern\n if (!m_rgpic[i]) {\n  ITEMCONTROLLER *pic = m_rgsi[i].pfnCreateController();\n  if (!pic) return NULL;\n  if (InterlockedCompareExchangePointerRelease(\n          &reinterpret_cast<PVOID&>(m_rgpic[i]),\n          pic, NULL) != 0) {\n   delete pic; \/\/ lost the race - destroy the redundant copy\n  }\n }\n MemoryBarrier();\n return m_rgpic[i];\n}\n<\/pre>\n
\nComments on proposed solutions<\/b>:\n\nGabe pointed out<\/a>\nthat the reallocation was a sticking point\nwhich made a lock-free implementation difficult if not impossible.\nCredit to him for recognizing the problem.\n<\/p>\n
\n\nThorsten proposed using a linked list instead of an array<\/a>\nto avoid the reallocation problem.\n<\/p>\n
\n\nRay Trent reminded us of the C++ function-local static technique<\/a>,\nwhich works if it’s what you need, but it has its own problems,\nsuch as lack of thread-safety (up until perhaps two weeks ago),\nand the fact that it doesn’t generalize to a solution\nto the exercise.\nThe not-thread-safe-ness of C++ static initialization was called out\nas a feature<\/i> in early versions of the C++ language specification\n(to permit recursive initialization).\nThis was revised in the ISO version of C++, which declared\nthat if control enters a function which is in the middle of\ninitializing its statics,\nthe behavior is undefined<\/i>.\nI don’t know what C++0x has to say about the subject,\nbut seeing as the standard\n\nwas approved only two weeks ago<\/a>\nand hasn’t even been formally published yet,\nit seems premature to expect all compilers to conform to any\nnew multi-threading semantics.\n<\/p>\n
\nNote that the function-local static technique works only if you want a\nprocess-wide singleton.\nIf you need a singleton with a tighter scope (say, “one object per thread”\nor “one object per transaction”), then the function-local static technique will\nnot work.\nWhich after all was the point of the SingletonManager class:\nTo manage singletons relative to its own scope, not globally.\nIf you had wanted global singletons, then you wouldn’t need a singleton\nmanager; you would just have each object manage its own singleton.\n<\/p>\n
\nTo elaborate:\nSuppose you have an object with a bunch of components.\nMost clients don’t use all the components, so you want to lazy-create\nthose components.\nSay, each Transaction<\/code> can have an error log file,\nbut you don’t want\nto create the error log file until an error occurs.\nOn the other hand, you want all the errors for a single transaction\nto go into the same log file.\n<\/p>\n
\nclass LogFile : public ITEMCONTROLLER\n{\npublic:\n  static ITEMCONTROLLER *Create() { return new LogFile(); }\n};\nconst SINGLETONINFO c_rgsiTransactions[] = {\n  { LOGFILE_ID, LogFile::Create };\n};\nclass Transaction\n{\npublic:\n  Transaction()\n    : m_singletons(c_rgsiTransactions,\n                   ARRAYSIZE(c_rgsiTransactions))\n  { }\n  void LogError(blah blah)\n  {\n    LogFile *plog = static_cast<LogFile*>\n                        (m_singletons.Lookup(LOGFILE_ID));\n    if (plog) plog->Log(blah blah);\n  }\nprivate:\n  SingletonManager m_singletons;\n};\n<\/pre>\n
\nThe singleton manager makes sure that each transaction has at most one\nlog file.\nBut we can’t use the function-local static technique in\nLogFile::Create<\/code>,\nbecause we want multiple log files in general, just a singleton log file\nper transaction.\nIf we had used the function-local static technique in\nLogFile::Create<\/code>, then all errors would have been logged\ninto a giant log file instead of a separate log file per transaction.\n<\/p>\n
\n\nScott tried to update the singleton atomically<\/a>\nbut forgot about the thread safety of the reallocation,\nand the solution had its own holes too.\n\nAlex Grigoriev’s solution is the classic back-off-and-retry algorithm<\/a>\nmodulo forgetting to protect against reallocation.\n<\/p>\n
\n\nnksingh was the first to observe that the reallocation could be removed<\/a>,\nand effectively came up with the solution presented here.\n(But missed the further optimization that the dwId<\/code> member\nwas redundant.)\nHe also recommended using the InitOnce functions,\nwhich is something I too recommend.\nWe’ll look at the InitOnce functions\n\nin a separate article<\/a>\nsince this one is getting kind of long.<\/p>\n","protected":false},"excerpt":{"rendered":"
A few days ago, I asked you to make an existing class multithread-safe. The class caches objects called SINGLETON­INFO which are indexed by a 32-bit ID. The cache is implemented as an array that dynamically resizes as more items are added to it. A naïve multithreaded version might use a slim reader-writer lock with shared […]<\/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-10993","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
A few days ago, I asked you to make an existing class multithread-safe. The class caches objects called SINGLETON­INFO which are indexed by a 32-bit ID. The cache is implemented as an array that dynamically resizes as more items are added to it. A naïve multithreaded version might use a slim reader-writer lock with shared […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/10993","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=10993"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/10993\/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=10993"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=10993"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=10993"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}