Thursday, July 24, 2014

C11 on Windows with gcc 4.9.1

For those of you with a Windows machine and interested in C11, and feeling adventurous, there are builds of MinGW64 with gcc 4.9.1 on sourceforge that you can use to build C11 code.
It's easy to install (just uncompress the .7z file and add the <mingw>\bin\ folder to your %PATH%) and you can try to build some of the C11 locks we've put on github, or use our Rosetta Stone to translate your code from some other language to C11 atomics.

If you're more into Linux, there's always Arch, that comes with the latest gcc builds.

More on C11 at DrDobbs or wikipedia

Friday, July 18, 2014

Lock-Free is not Starvation-Free

Still on the topic of Progress Conditions, there is a very good paper (or essay?) by Maurice Herlihy and Nir Shavit

Figure 1 is particularly enlightening, showing a kind of periodic table of progress conditions:

There is a bit of an insight I would like to cover on this post, and the insight is this:
Lock-Free is, by definition, starvable.

Or maybe put in another way, a method that is (just) Lock-Free, never has the guarantee of being free from starvation. If it has this guarantee, then it must be Wait-Free.

I know, it's tricky, but lets dig a bit more.

For Blocking methods, there is a property named Starvation-Free which guarantees that the method will complete if the other threads are able to finish. This means that as long as the thread-scheduler is fair, this method will not starve, i.e. its execution will not be stopped by other methods.
A nice example of a Starvation-Free method is a mutual exclusion lock (mutex) based on the CLH algorithm that we talked about a few posts ago. It uses a queue with wait-free properties for enqueuing and blocking for dequeuing.
Lock-Free doesn't give such a guarantee.
Imagine for example a CAS loop to increment a counter. It can happen that one thread fails indefinitely because other threads win the CAS, and although there is a non-zero probability to succeed in the CAS, there is no guarantee of how many attempts are needed to succeed, i.e. there is no theoretical maximum number of steps for the CAS to be successful.
The only way to guarantee that it would not be starved, would be to have a bound on the number of steps, and if such a bound existed, then the method in question would be (by definition) Wait-Free instead of Lock-Free.

I'm not completely sure, but there seem to be two consequences to this train of thought:

First, the only way to achieve starvation-freedom is to use mechanisms that are wait-free by themselves. Starvation-freedom is a Blocking property, which means that we're putting together wait-free mechanisms to make something that in the end is Blocking, so why not use Lock-Free instead?
Well, because if we use Lock-Free mechanisms we can not achieve starvation-freedom. For example, you can't make a starvation-free lock by using a lock-free queue.

Second, if starvation-freedom has a bound on the number of steps to complete and lock-freedom does not, then we can conclude (theoretically) that the maximum latency may actually be better, assuming a fair thread-scheduler and other ideal conditions.
So, although Lock-Free should usually have a better latency distribution (closer to the left side) than Starvation-Free, Lock-Free can never guarantee a maximum cut-off in terms of number of operations, which means that it might be preferable to use it if your latency needs are more about the tail than about the bulk.

As an aside to all of this, a bit of "Statistics" is in order: what people usually call "performance" is actually the "mean of the latency distribution".
If an operation takes on average 10 micro-seconds (us) to complete, this is usually written as your algorithm being able to perform 100000 (one hundred thousand) operations per second, but this is just "a number". This number alone won't tell you if most of the operations took 1us to complete and then some of them took a few seconds, or, if all of them took between 9us and 11us to complete.  To understand this you have to look at a distribution of the latency with enough samples.

Why should we care about starvation-free?
Partially, for the same reason that we care about Wait-Free: to have a strong bound on max latency, at least a theoretical bound.

We'll have to talk more about Latency one of these days, but the takeaway of all this blahblah is this:
All Lock-Free methods can be starved, but some Blocking methods will not starve (and we name those Starvation-Free).

Wednesday, July 16, 2014

Lock-Free definitions galore

We've talked before about the definition of Lock-Free, but there is a lot of confusion around its definition and the other definitions of Progress Conditions, so lets take a closer look at it.

If you google a bit for the definition of Lock-Free, you'll see that there are several:
"An algorithm is lock-free if it satisfies that when the program threads are run sufficiently long at least one of the threads makes progress (for some sensible definition of progress)."
"Lock-freedom means that a system as a whole moves forward regardless of anything. Forward progress for each individual thread is not guaranteed (that is, individual threads can starve)."

CS Course at Carnegie Mellon:
"On a system using a lock-free algorithm, it is guaranteed that some thread is making progress. This means that the overall system is making progress toward the end goal. However, there still might be starved threads, as lock-free algorithms only guarantee that at least one thread is making progress at any given time."

Blog posts:
"An algorithm is lock-free if at all times at least one thread is guaranteed to be making progress."

The Art of Multiprocessor Programming, page 99:
"A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number of steps."

The Wikipedia definition is the easiest to understand, unfortunately, it is also the most ambiguous because it relies in the definition of "progress", whatever that means. I like it as a way to explain the concept of lock-free to someone that is new to the field, so it is appropriate as a wikipedia page, but too "fluffy" to be taken seriously.

The following three definitions are very similar to each other. They also rely on the ambiguous "progress", but at least the second and third ones explicitly mention something I find very important: that you can have starvation in a lock-free algorithm (or method).

The definition from "The Art of Multiprocessor Programming" by Maurice Herlihy and Nir Shavit is the best definition. It may not seem so at first, but I'm pretty sure that a lot of work and long hours of discussion went into this one sentence, and the end result is this short statement that is able to synthesize such a powerful concept. It has an almost haiku beauty.  :)

First, the definition by Herlihy is done in terms of number of steps, which is a concept better defined than progress, after all, Lock-Free is a type of Progress Condition, so in a certain sense, we could argue that on the first four definitions we are trying to use the concept of progress to define progress conditions, which sounds unproductive.

Second, it talks about methods and not algorithms, which is appropriate because as we have seen before, an algorithm can have methods with different progress conditions. For example:
- A data structure using the Double Instance Locking technique is Blocking for write-modify operations and Lock-Free for read-only operations;
- A data structure using the Left-Right Pattern is Blocking for write-modify operations and Wait-Free Population Oblivious for read-only operations (when using a WFPO readIndicator);
- Harris' linked-list can be made Wait-Free Bounded (by the size of the key) for lookups, and Lock-Free for insertions and removals.

Third, the part about "infinitely often" is very important because it covers non-deterministic scenarios.
Imagine the case where multiple threads attempt an operation and they all fail, but this failure is non-deterministic, with a non-zero probability that at least one of the threads will succeed. This means that all threads may fail for a finite number of consecutive attempts, but eventually one of them will succeed.
Under the other definitions, this scenario would not be Lock-Free, while under the definition by Herlihy it would be Lock-Free. Which one is best can be disputed, but if you use one of the other definitions, then what will the scenario I've described be? Blocking? Something else?
The different definitions of Blocking, Obstruction-Free, Lock-Free, Wait-Free are all inter-related, in the context that they only make sense when defined together, so that no scenario "escapes through the cracks". Whatever definitions of Blocking, Lock-Free and Wait-Free we use, they should make it as unambiguously as possible which progress condition we are talking about when faced with a particular method... this stuff is hard enough as it is, so lets not make it any harder by making definitions that are incoherent with each other, or ambiguous  ;)

I'm secretly hoping that Herb Sutter will be covering this in depth at the next CppCon, because he has a talk devoted solely to Lock-Free algorithms named Lock-Free Programming (or, Juggling Razor Blades). The title alone is worth the registration fee!

In summary, the best definition of Lock-Free I've seen so far is the one from "The Art of Multiprocessor Programming":
"A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number of steps."

Saturday, July 12, 2014

Martin Thompson on Top-10 performance myths

Here is a nice presentation on performance by Martin Thompson, covering hardware and software,

I particularly liked the part about Immutable (Persistent) data structures and magic ponies  :)
And what he said about "know your data structures".

(...) I think we're in an interesting era where people who just recall facts are almost redundant, because you can just google for them (the facts).
What's really useful is people who can reason. People who are aware of "I need to know what that is, given the characteristics of what I'm doing, and I can lookup it up."
It's that curiosity and ability to reason that I would search for during an interview process

As always, good stuff from Martin.
For more, check out his blog.