Lock-Free Data Structures (2004)

[jervisfm]

http://www.drdobbs.com/lock-free-data-structures/184401865

[taspeotis]

Raymond Chen had an interesting series on lock-free algorithms a while back [1].

[1] https://www.google.com.au/search?q=%22lock-free+algorithms%2...

[gliese1337]

Here's the follow-up article: http://www.drdobbs.com/lock-free-data-structures-with-hazard... Which deals with ensuring deterministic destruction (and thus bounded memory use) with lock-free structures.

[cmbaus]

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.

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.

[derefr → cmbaus]

> 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

I find the entire concept of implementing novel container data-structures specifically for your application kind of ridiculous. This sort of thing should be implemented exactly once--in the language runtime library.

[kev009 → derefr]

http://concurrencykit.org/ is what you want.

[kevingadd → derefr]

Very often your language runtime library lacks adequate lock-free datastructures. This was especially true in 2004.

[TacticalCoder → cmbaus]

"...so unless an application requires the performance benefits provided, it is probably still a better bet to use standard locking mechanisms."

Or simply use battle-hardened APIs which are known to be fast and correct and which, themselves, have been implemented by using lock-free algorithms?

For example if I'm not mistaken throughout time the Java concurrency APIs did evolve to use more and more facilities using lock-free CAS operations under the hood.

You can also use 3rd party APIs, like the incredibly fast LMAX disruptor pattern (which also makes great use of CAS operations IIRC).

All this without being forced to come up yourself with the low-level stuff.

Then you can also use a recent language where concurrency has been built in from day 1: like Clojure which is pretty much deadlock free because it doesn't even give you access to locks.

I guess my point is: you don't have to implement yourself these advanced techniques to greatly benefit from them.

[aardvark179 → cmbaus]

It is not always performance that is the main consideration. If you are developing a library and so do not have control of how threads might be used with it then it may be vital to ensure a lock can never be held by a thread which could be suspended.

I agree though that the use should normally be contained to a small area and the details carefully abstracted away from the rest of the code because it takes real care to get the details right.

[infogulch]

Why couldn't the last reader delete the old map?

I guess the problem with this implementation is it requires a last reader for every write. If there are always readers, the second Update will block.

  // 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));
     }
  };

(Meta question: ok to put this much code here?)

[optimusclimb → infogulch]

Sample set of one answer to your meta question: You could always just use a public gist, however I hope to never see the day where people have a problem on HN with a bunch of interesting code being posted.

[sbahra]

Also relevant and covers these topics in greater depth: http://queue.acm.org/detail.cfm?id=2492433 http://queue.acm.org/detail.cfm?id=2488549 http://queue.acm.org/detail.cfm?id=2490873 and http://queue.acm.org/detail.cfm?id=2513575