Raymond Chen had an interesting series on lock-free algorithms a while back [1].<p>[1] <a href="https://www.google.com.au/search?q=%22lock-free+algorithms%22+site%3Ablogs.msdn.com%2Fb%2Foldnewthing" rel="nofollow">https://www.google.com.au/search?q=%22lock-free+algorithms%2...</a>
I remember the article quite well, as it was passed around our office when it was first published. The author gave multiple presentations on the topic around that time.<p>There is a lot of genius in the article and references, but I will say from experience it is very easy to implement these approaches incorrectly, so unless an application requires the performance benefits provided, it is probably still a better bet to use standard locking mechanisms.
Why couldn't the last reader delete the old map?<p>I guess the problem with this implementation is it requires <i>a</i> last reader for every write. If there are always readers, the second Update will block.<p><pre><code> // infogulch's lock-free implementation of WRRMMap
template <class K, class V>
class WRRMMap {
Map<K, V>* pMap_, * pGC_;
unsigned readers;
public:
V Lookup (const K& k) {
unsigned r
while (r = readers, !CAS(&readers, r, r+1)); // increment readers
V ret = (*pMap_) [k];
while (r = readers, !CAS(&readers, r, r-1)); // decrement
if (r == 1 && pGC_) { // last reader. garbage collect
delete pGC_;
pGC_ = 0;
}
return ret;
}
void Update(const K& k,
const V& v) {
Map<K, V>* pNew = 0, * pOld;
do {
pOld = pMap_;
delete pNew;
pNew = new Map<K, V>(*pOld);
(*pNew) [k] = v;
} while (!CAS(&pMap_, pOld, pNew));
// DON'T delete pMap_;
// wait for the GC spot to be open, set it
while (!CAS(&pGC_, 0, pOld));
}
};
</code></pre>
(Meta question: ok to put this much code here?)
Also relevant and covers these topics in greater depth: <a href="http://queue.acm.org/detail.cfm?id=2492433" rel="nofollow">http://queue.acm.org/detail.cfm?id=2492433</a> <a href="http://queue.acm.org/detail.cfm?id=2488549" rel="nofollow">http://queue.acm.org/detail.cfm?id=2488549</a> <a href="http://queue.acm.org/detail.cfm?id=2490873" rel="nofollow">http://queue.acm.org/detail.cfm?id=2490873</a> and <a href="http://queue.acm.org/detail.cfm?id=2513575" rel="nofollow">http://queue.acm.org/detail.cfm?id=2513575</a>