What is the reason why high level abstractions that use lock free programming deep down aren't popular?

Question

From what I gathered on the lock free programming, it is incredibly hard to do right... and I agree. Just thinking about some problems makes my head hurt. But what I wonder is, why isn't there a widespread use of high-level wrappers around (e.g. lock free queue and similar stuff)? For example boost has no lock free library, although one was suggested as far as I know. I mean I guess that there is a lot of applications where you cant avoid the fact that the critical section is the big part of the load. So what are the reasons? Is it...

1. Patents - I heard that some stuff related to lock-free programming is patented.
2. Performance.
3. Google, and Microsoft have internal libraries like that but none of them are public...
4. Something else?

So my question is: Why are high level abstractions that use lock free programming deep down not very popular, while at the same time "regular" multi-threaded programming is "in"?

EDIT: boost got a lockfree lib :)

Answer 1

There are few people who are familiar enough with the field to implement easy-to-use lock-free libraries. Of those few, even fewer publish work for free and of those almost none do the vital additional work to make the library useable - e.g. publish full API docs, etc. They tend to just release a zip file with code in, which is almost useless. Then of course you also need to find a library which is written in the language you want to use, compiles on the platform you're using and finally, word of the library has to get out, so people know it exists.

Patents are an issue, in that they limit what can be offered. There is, for example, to my knowledge no unpatented singly-linked list. All the skip list stuff is heavily patented, too.

A hero in this field is Cliff Click, who came up with a lock-free hash, which he has more-or-less placed in the public domain.

You can find my lock-free library here;

http://www.liblfds.org

Another is Samy Bahra's Concurrency Kit;

http://www.concurrencykit.org

Answer 2

FYI Microsoft's .Net framework gained some lock free classes in .Net 4.0. Namely container classes in the System.Collections.Concurrent namespace, which are:

ConcurrentDictionary
ConcurrentQueue
ConcurrentStack

I've looked into their implementation and they are relatively fiddly/complex under the hood therefore they do represent a significant amount of effort in designing and testing (threading issues are of course notoriously difficult to test to a high standard).

Answer 3

You can take a look at libcds C++ library. It is collection of lock-free containers (stacks, queues, sets and maps) and safe memory reclamation algorithms.

IMHO regarding C++ (I'm not advanced in other languages). New C++ standard has just been released and the compiler developers need a time to implement its requirements. Today, all compilers do not support C++11 memory model entirely since it requires significant changes in compiler’s optimization rules. Recently, Microsoft announces support of the atomic operations that is the base of lock-free programming in VC++ 11 Developer Preview. It is good news for us. As I know, GCC is going to support it in 4.8 (or above).

Second problem is patents. Many interesting lock-free container algorithms are patented that is a barrier to include them to vendor’s libraries.

Third, the main part of lock-free containers is garbage collecting (safe memory reclamation). C++ is free from any GC (fortunately). There are a few GC algos (Hazard Pointer, Pass-the-Buck, epoch-based and so on) but most of them are patented too.

Fourth, not enough instruments to prove the correctness of memory fences applied in your lock-free implementation. Now I known only one – relacy(http://www.1024cores.net/home/relacy-race-detector).

I think after 2-3 years we’ll see many production-ready multiplatform C++ libraries of lock-free containers and algorithms. These libraries are being developed by vendors and enthusiasts.

However, in my opinion, our future is the hardware transaction memory (HTM). Today AMD, Sun (sorry, Oracle), Intel (?) are investigating HTM with very interesting results. Let’s wait.

Answer 4

One major problem is that unless one uses an excessive number of memory barriers, it's hard to be certain that one has enough; if one does use an excessive number of memory barriers, performance is likely to be inferior to what one would have gotten using locks.

The biggest problem with locks is not performance, but robustness. If a thread gets waylaid while it holds a lock, the system dies. By contrast, if a thread which is accessing a lock-free data structure gets waylaid, it won't affect other threads' use thereof. In some situations, a lock-free data structure may be preferable to one using locks, even if performance is inferior, because one must protect the system from being brought down by a malfunctioning thread (for example, even if one was prepared to kill off a thread which hit a StackOverflowException without taking down the process, how would one protect against a thread putting a lot of stuff on its stack before calling a method to access a lock-protected data structure that the method, such that the lock-guarded method hit a stack overflow?) If one uses lock-free data structures, such risks aren't a problem.

Answer 5

There is at least one "lock free” framework that is somewhat popular: Erlang.