\nSuppose profiling reveals that a specific calculation is responsible\nfor a significant portion of your CPU time,\nand instrumentation says that most of the time, it’s just being\nasked to calculate the same thing over and over.\nA simple one-level cache would do the trick here.\n<\/p>\n
\nBOOL IsPrime(int n)\n{\n static int nLast = 1;\n static BOOL fLastIsPrime = FALSE<\/a>;\n \/\/ if it's the same value as last time, then\n \/\/ use the answer we cached from last time\n if (n == nLast) return fLastIsPrime;\n \/\/ calculate and cache the new result\n nLast = n;\n fLastIsPrime = slow_IsPrime(n);\n return fLastIsPrime;\n}\n<\/pre>\n\nOf course, this isn’t thread-safe, because if one thread\nis pre-empted inside the call to slow_IsPrime<\/code>,\nthen another thread will see\nvalues for nLast<\/code> and fLastIsPrime<\/code>\nthat do not correspond to each other.\n<\/p>\n\nOne solution would be to put a critical section around this code,\nbut this introduces an artificial bottleneck:\nIf the most recent cached result is nLast = 5<\/code>,\nfLastIsPrime = TRUE<\/code>,\nand if two threads both try to see whether 5 is prime,\nyou don’t want those two threads to serialize against each other.\n<\/p>\n\nAnother solution is to use\n\nslim reader-writer locks<\/a> and acquire in shared mode when\nchecking the cache and in exclusive mode when updating the cache.\nBut let’s try a lock-free solution.\n<\/p>\n\nWe’re going to combine two different techniques.\nFirst, we use the change counter technique\nwe saw last time when\n\nwe investigated try\/commit\/(try again)<\/a>,\nbut we also combine it with a lock that is manipulated\nwith a try\/commit\/abandon pattern.\n<\/p>\n\n#define IsLocked(l) ((l) & 1)\nBOOL IsPrime(int n)\n{\n static int nLast = 1;\n static BOOL fLastIsPrime = FALSE;\n static LONG lCounter = 0;\n \/\/ see if we can get it from the cache\n LONG lCounterStart = InterlockedReadAcquire(&lCounter, -1);\n if (!IsLocked(lCounterStart) && n == nLast) {\n BOOL fResult = fLastIsPrime;\n if (InterlockedReadRelease(&lCounter, -1) == lCounterStart)\n return fResult;\n }\n \/\/ calculate it the slow way\n BOOL fIsPrime = slow_IsPrime(n);\n \/\/ update the cache if we can\n lCounterStart = lCounter;\n if (!IsLocked(lCounterStart) &&\n InterlockedCompareExchangeAcquire(&lCounter,\n lCounterStart+1, lCounterStart) == lCounterStart) {\n nLast = n;\n fLastIsPrime = fIsPrime;\n InterlockedCompareExchangeRelease(&lCounter,\n lCounterStart+2, lCounterStart+1);\n }\n return fIsPrime;\n}\n<\/pre>\n\nThe lCounter<\/code> consists of\na LOCK bit as the bottom bit\nand a change counter in the remaining bits.\n(Choosing the bottom bit as the LOCK bit makes the operations\nof clearing the lock and incrementing the counter very simple.)\n<\/p>\n\nThere are two parts to this function, the part that reads the\ncache and the part that updates the cache.\n<\/p>\n
\nTo read the cache, we first read the counter with acquire semantics,\nso that the reads of nLast<\/code> and\nfLastIsPrime<\/code> will not take place until after we\nget the counter.\nIf the counter says that the cache is not locked, then we go\nahead and fetch the last value and the last result.\nIf the last value in the cache matches the value we’re calculating,\nthen we go ahead and use the last result.\nBut as a final check, we make sure that the counter hasn’t changed\nwhile we were busy looking at the protected variables.\nIf it has, then it means that we may have read inconsistent values\nand cannot trust the cached result.\n<\/p>\n\nIf we have a cache miss or we couldn’t access the cache,\nwe go ahead and calculate the result the slow way.\n<\/p>\n
\nNext, we try to update the cache.\nThis time, instead of just looking to see whether the cache\nis locked, we try to lock it ourselves by setting the bottom bit.\n(If the lock fails, then we skip the cache update and just return\nthe value we calculated.)\nOnce the lock is taken, we update the protected variables,\nthen atomically\nrelease the lock and increment the counter.\n(This is where putting the lock in the bottom bit comes in handy:\nYou can increment the counter by adding 2 and not worry about\na carry out of the counter bits turning into an accidental lock bit.)\nWe use Release semantics so that the\nvalues of the protected values are committed to memory before\nlock bit clears.\n<\/p>\n
\nNote that in both halves of the function, if the cache is locked,\nwe just proceed as if there were no cache at all.\nThe theory here is that it’s better just to say\n“Oh, the heck with it, I’ll just do it myself”\nthan to line up and wait to access the cache.\nContinuing instead of waiting avoids problems like priority inversion,\nbut it also means that you get some spurious cache misses.\nFortunately, since it’s just a cache, an occasional spurious miss\nis not the end of the world.\n<\/p>\n
\nYou could do something similar with the\nTryEnterCriticalSection<\/code> function\n\nprovided you’re running Windows NT 4.0 or higher<\/a>:\n<\/p>\n\nBOOL IsPrime(int n)\n{\n static int nLast = 1;\n static BOOL fLastIsPrime = FALSE;\n BOOL fHaveAnswer = FALSE;\n BOOL fIsPrime;\n \/\/ see if we can get it from the cache\n if (TryEnterCriticalSection(&g_cs)) {\n if (n == nLast) {\n fHaveAnswer = TRUE;\n fIsPrime = fLastIsPrime;\n }\n LeaveCriticalSection(&g_cs);\n }\n if (fHaveAnswer) return fIsPrime;\n \/\/ calculate it the slow way\n fIsPrime = slow_IsPrime(n);\n \/\/ update the cache if we can\n if (TryEnterCriticalSection(&g_cs)) {\n nLast = n;\n fLastIsPrime = fIsPrime;\n LeaveCriticalSection(&g_cs);\n }\n return fIsPrime;\n}\n<\/pre>\n