4 ms·

Lock-Free Data Structures (2004)

55 points by jervisfm 13y ago

cmbaus 13y ago
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 13y ago
  > 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.
  - kevingadd 13y ago
    Very often your language runtime library lacks adequate lock-free datastructures. This was especially true in 2004.
  - kev009 13y ago
    http://concurrencykit.org/ http://concurrencykit.org/ is what you want.
- aardvark179 13y ago
  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.
- TacticalCoder 13y ago
  "...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.
gliese1337 13y ago
Here's the follow-up article: http://www.drdobbs.com/lock-free-data-structures-with-hazard-po/184401890 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.
taspeotis 13y ago
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%22+site%3Ablogs.msdn.com%2Fb%2Foldnewthing https://www.google.com.au/search?q=%22lock-free+algorithms%2...
infogulch 13y ago
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 13y ago
  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 13y ago
Also relevant and covers these topics in greater depth: http://queue.acm.org/detail.cfm?id=2492433 http://queue.acm.org/detail.cfm?id=2492433 http://queue.acm.org/detail.cfm?id=2488549 http://queue.acm.org/detail.cfm?id=2488549 http://queue.acm.org/detail.cfm?id=2490873 http://queue.acm.org/detail.cfm?id=2490873 and http://queue.acm.org/detail.cfm?id=2513575 http://queue.acm.org/detail.cfm?id=2513575

55 points by jervisfm 13y ago

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 13y ago
> 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.
- kevingadd 13y ago
  Very often your language runtime library lacks adequate lock-free datastructures. This was especially true in 2004.
- kev009 13y ago
  http://concurrencykit.org/ http://concurrencykit.org/ is what you want.
aardvark179 13y ago
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.
TacticalCoder 13y ago
"...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.

gliese1337 13y ago

Here's the follow-up article: http://www.drdobbs.com/lock-free-data-structures-with-hazard-po/184401890 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.

taspeotis 13y ago

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%22+site%3Ablogs.msdn.com%2Fb%2Foldnewthing https://www.google.com.au/search?q=%22lock-free+algorithms%2...

infogulch 13y ago

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 13y ago
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 13y ago

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