Lock-free algorithms: The singleton constructor (answer to exercises)

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 access on reads, exclusive access on writes, and mixed access on the treacherous "create if it doesn't already exist" path.

Let's see. First of all, the function doesn't allocate the memory for the cache until somebody actually tries to look something up. But duh, that's the whole point of the class: To look up things! The only time this lazy-initialization actually provides a benefit is if somebody creates a Singleton­Manager, calls no methods on it, and then destroys it.

This doesn't happen in practice, and even if it did, it's certainly not a scenario we're going to optimize for. Get rid of the lazy-initialization of the cache; it makes multithreading unnecessarily complicated.

Second, since the only way an ITEM­CONTROLLER can get into the cache is via the SINGLETON­INFO, if a Singleton­Manager is told, "Here are 30 item IDs and their corresponding controller creation functions," then the cache can never hold more than 30 items. If you only know how to create 30 items, and you never create more than one copy of each item, then you're never going to create more than 30 items.

Therefore, instead of managing a dynamically-growing array, we can allocate a fixed-size array at construction of length equal to the number of SINGLETON­INFO elements. This avoids having to lock around the code that reallocates the array. Since the array length is in the range 30–50, we don't have the problem of allocating megabytes of memory to track just a few objects. In the worst case, we allocate a 50-element cache.

Next, we can store each ITEM­CONTROLLER in the same position in the cache array as it exists in the SINGLETON­INFO array.

With these simplifications, we see that we don't need to do any locking or complicated duplicate-detection. After locating the ID in the SINGLETON­INFO array, look at the corresponding entry in the cache array and perform a singleton initialization there.

struct ITEMCONTROLLER;

struct SINGLETONINFO {

 DWORD dwId;

 ITEMCONTROLLER *(*pfnCreateController)();

};

class SingletonManager {

public:

 // rgsi is an array that describes how to create the objects.

 // It's a static array, with csi in the range 20 to 50.

 SingletonManager(const SINGLETONINFO *rgsi, UINT csi)

               : m_rgsi(rgsi), m_csi(csi),

                 m_rgpic(new ITEMCONTROLLER*[csi]) { }

 ~SingletonManager() { ... }

 ITEMCONTROLLER *Lookup(DWORD dwId);

private:

 const SINGLETONINFO *m_rgsi;

 int m_csi;

 // Array that describes objects we've created

 // runs parallel to m_rgsi

 ITEMCONTROLLER *m_pic;

};

ITEMCONTROLLER *SingletonManager::Lookup(DWORD dwId)

{

 int i;

 // Convert ID to index

 for (i = 0; i < m_csi; i++) {

  if (m_rgsi[i].dwId == dwId)

   break;

 }

 if (i >= m_csi) return NULL; // not something we know about

 // Singleton constructor pattern

 if (!m_rgpic[i]) {

  ITEMCONTROLLER *pic = m_rgsi[i].pfnCreateController();

  if (!pic) return NULL;

  if (InterlockedCompareExchangePointerRelease(

          &reinterpret_cast<PVOID&>(m_rgpic[i]),

          pic, NULL) != 0) {

Read more: The old new thing

Posted via email from Jasper-net