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 :)

Donniedonnish

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

Restaurateur

Agreed on Click. I ported his algorithm to .NET (first as a relatively straight port, then a more thorough re-write with his basic idea but adapted to the different pros and cons on the CLR over the JVM) and it's great to know it's safely clear of patents. Have you tried adding it to your C library? There's a greater "distance" (particularly with Java and .NET both being non-reference-counting garbage collected which removes a bunch of concerns), but I'd be interested in hearing if anyone had found it worked out. – Remediable

@Jon: I'm currently adding a conventional lock-free hash (e.g. each element being a singly-linked list) because I want to have the next release out pronto since it is the basis for my next goal, a lock-free relational database (once you have the list, that type of hash is a doddle; and I need the list for the database). I will add his hash once that's done. A friend of mine implemented his hash in C; I don't know the details, but it seemed to go just fine. – Restaurateur

Oh, I'm sure a Click-style hash could be done in C, though my C and C++ is far too rusty for me to try. It is nice to have GC though despite it having its own costs - a lot of ABA issues just go away, unless you explicitly try to reuse objects. My .NET approach is described at github.com/hackcraft/Ariadne/wiki/… where the biggest win was definitely in considering the memoised hash to be a full part of the entry rather than just an optimisation, which I'm sure would be applicable to other languages and frameworks. – Remediable

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).

Colorless

Cool info, I hope in the near future somebody does c++ mutexed container vs C# concurrent containers performance comparison – Donniedonnish

ConcurrentDictionary isn't lock-free; it mixes lock-free, striped-locked and fully-locked approaches. Arguably this is better than lock-free for most uses (it beats my lock-free dictionary in most cases, but then that could just be that I could do better somewhere). – Remediable

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.

Sapowith

no offense to authors, but Im scared to use new untested lib. – Donniedonnish

This will set us back a bit: Errata: "Desktop 4th Generation Intel Core Processor Family...: Specification Update (Revision 014)" (PDF). Intel. June 2014. p. 46. Retrieved 2014-08-13. Under a complex set of internal timing conditions and system events, software using the Intel TSX (Transactional Synchronization Extensions) instructions may observe unpredictable system behavior. – Witenagemot

...A fix is on the horizon though. – Witenagemot

Answer 4

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

Cappadocia

I was thinking more about some ADA, C or C++ library...but +1, I didnt know Erlang is lock free – Donniedonnish

Erlang run time system is written mainly in C. It is also extremely simple to talk to C/C++ via NIF interface or talk to .so . – Encephalography

Answer 5

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.

Carolann