Bartosz Milewski's Programming Cafe

With the multicore explosion in the making, are we going to be running hundreds of thousands of threads in a single program? Erlang programmers would emphatically say, yes! C++ and Java programmers would probably say no.

Why this discrepancy?

Thread model based on heavy-duty OS threads and mutexes has its limitations. You can ask server writers, or Google for “thread per connection” to convince yourself. Servers use thread pools exactly because of that.

Thread pools are an admission of defeat for the thread model. Having to pool threads tells you that:

• Thread creation is not fast enough
• Threads’ consumption of resources is substantial, so it makes sense to keep their numbers down

Granted, these are technical problems that might be overcome in future by improvements in operating systems.

The more fundamental problem with threads has its root in memory sharing. It seems like sharing offers great advantage in terms of performance, but sharing requires locking. It’s a well known fact that locking doesn’t scale (or compose). Between races and deadlocks, it’s also extremely hard to get right.

Here’s what Erlang does

Erlang gives up on sharing!

Threads that don’t share memory are called processes. We tend to think of processes as heavyweight beasts implemented by operating systems. That’s because one needs the operating system to strictly enforce the no-sharing policy (the isolation of address spaces). Only the OS can manage separate address spaces and the passing of data between them.

But that’s not the only way. The isolation might instead be enforced by the language. Erlang is a functional language with strict copy semantics and with no pointers or references. Erlang processes communicate by message passing. Of course, behind the scenes, messages are passed through shared memory, thus avoiding a large performance hit of inter-process communication. But that’s invisible to the client.

Erlang rolls out its own threads!

Erlang interpreter provides lightweight processes (so lightweight that there’s a benchmark running 20 million Erlang processes).

And there is a bonus: Erlang code that uses lightweight processes will also work with heavyweight processes and in a distributed environment.

Why don’t we all switch to Erlang?

As far as I know there are two main reasons:

• It’s a weird language. Don’t get me wrong, I love functional programming for its mathematical beauty, terseness, and elegance. But I had to rewire my brain to be able to write pure functional programs. Functional paradigm is as alien to our everyday experience as quantum mechanics. (CS grad students: you’re not typical programmers.)
• Messages have to be copied. You can’t deep-copy a large data structure without some performance degradation, and not all copying can be optimized away (it requires behind-the-scenes alias analysis). This is why mainstream languages (and I will even include Scala in this category) don’t abandon sharing. Instead they rely on programmer’s discipline or try to control aliasing.

Conclusions

Native threads are expensive. Interpreted languages, like Erlang, can afford to implement their own lightweight threads and schedulers. I don’t see that happening in compiled languages. The hope is that  operating systems will improve their implementations of threads–I hear Linux’s NPTL already is a big improvement in this area. In the meanwhile, we have to rely on thread pools.

Shared memory concurrency model is the reason why multithreaded programming is so difficult and error-prone. Separating address spaces simplifies programming, but at a performance cost. I believe that some kind of compromise is possible. A message-passing or an actor model can work with sharing, as long as aliasing is under control.

Inspiration for this post

After my last post on thin lock implementation, I was asked the question, why I used such a small number, 1024, for the maximum number of threads. It was actually a number I’ve found in the D compiler runtime. A thin lock could easily work with a much larger number of threads. In fact I’m going to substantially increase the number of bits for thread ID at the expense of recursion count. But this question got me thinking about scalability of threading in general.

Fibers

Fibers (as well as Java’s green threads) are not an alternative to heavyweight threads. Fibers can’t run in parallel, so they have no way to use multiple processors. They are more of a flow-of-control construct, often used interchangeably with coroutines.

Interesting reading

• The Problem with Threads by Edward E. Lee.
• Kilim: Isolation-Typed Actors for Java by Sriram Srinivasan and Alan Mycroft.

Previously I have described a thin lock as a very efficient implementation of object monitor. It’s time to flesh out the design. Since most of the thin lock implementation is itself lock free, all kinds of multicore subtleties come into play. I did my best to analyze every step, but I’m only human. The code hasn’t yet been written in D, much less tested.

Object Layout

Every object (instance of a class) in the D programming language inherits from Object. Object contains a hidden header consisting of two fields:

• pointer to vtable
• pointer-sized thin lock

I’m not adding any new fields, just replacing an existing pointer field with the thin lock. The pointer used to point to a lazily evaluated Monitor object.

Thin lock is a union of a bit field and a pointer to a FatLock struct. The union is discriminated by the two lowest bits–if they are zero, it’s a pointer. A null pointer has special meaning–the object can never be shared (it was created as non-shared). See sharing and unsharing n D.

Here’s the thin lock bit-field layout (the low 32-bits; the whole field is either 32- or 64-bit wide, depending on native pointer size).

D runtime has a fixed-size global array of threads. An index into this array is used to identify a thread. This is different from the operating-system-defined thread ID.

Sharing policy

To share an object between threads, it must be created as shared (possibly allocated from a separate, shared heap). Any global object that is not declared shared is only accessible through thread-local handles.

A shared object’s thin lock (which hasn’t been inflated to a fat lock, see later) has the two lowest bits set. Sharing can be cast away, at which point the currently-shared bit is cleared, but the created-shared bit is still on. The object can then be cast back to shared; however, if the created-shared bit is not on, such a cast will throw an exception.

This guarantees that an object that was not created for sharing can never be cast to shared.

When sharing is cast away, the casting thread’s identifier is remembered in the thread index field. The object becomes exclusively owned by the current thread (essentially, locked by it). Any attempt by a different thread to lock such an object will result in an exception.

Locking a never-shared object

An object that was created as non-shared (the default) has zero in its thin lock. This state is permanent and not reachable from any other state.

Originally I thought that the comparison (thinlock == 0) didn’t require any synchronization. I totally spaced out on publication safety (thank you, Andrei, for a reality check!). In general, this test has to be preceded by a read fence. Fortunately, on an x86, publication safety is guaranteed without fencing, so at least on that platform, the check is lightning fast. Because the thin lock is co-located with the rest of the object–next to the vtable pointer–even the overhead of fetching it from main memory is rarely incurred.

Therefore the incentive for writing two versions of a class–one with synchronized, and the other with non-synchronized methods–is practically absent in D.

I mentioned before that the D compiler might be able to elide synchronization of non-shared objects altogether. If that happens, the testing of the two sharing bits in the thin lock would be redundant. There is however a code-size/performance trade-off between the two solutions.

Locking algorithm

– Test thin lock for zero (on an x86, without any synchronization, otherwise precede it with a read fence). If zero, return. This is the most common case: the object was not created for sharing and will never be accessed by another thread.

– Fetch current compact thread ID, which is conveniently stored in thread-local memory. Compact thread ID is pre-calculated for each thread using an 11-bit thread index (see above) shifted left by 21 and OR’ed with 3 (the lowest two bits are set). This is an optimization. Notice that an XOR with a compact thread ID flips the two lowest bits of the thin lock, which makes subsequent tests look logically inverted.

– XOR thin lock with this ID. If the result is 2 (remember the inversion), return. This is the case when the object was created shared, but was cast to non-shared by the current thread. This operation doesn’t require any synchronization, because only the current thread could cast the object back to shared.

if (thinlock ^ compactThreadId == 2)
  return;

– If we are past this point, we know that the object is shared, or we are attempting (incorrectly) to lock an object that is exclusive to (cast to non-shared by) another thread.

– Perform a CAS (atomic Compare And Swap operation) on thinlock. The value we are expecting is 3 (two lowest bits set and noting else), the replacement value is the compact thread ID of the current thread. This operation will succeed in the next most common case–the object is shared but is not currently locked. The resulting thin lock state has the thread index filled with a non-zero value, and the two lowest bits set (see the description of compact thread ID). This state is interpreted as “locked once by a given thread”.

– If the CAS fails (thinlock didn’t have the expected value and the swap did not occur), we know that the object is locked (or the thin lock has been inflated to a fat lock, see later).

– Try the next most common case–the object is locked by the current thread (recursive locking). First XOR the value of the thin lock with the current compact thread ID to isolate the count field. If the result is less that the maximum count shifted left by 2 and the two lowest bits are zero (meaning, they were set before the XOR), then increment the count. These operations don’t require any synchronization, because they only succeed when the lock is owned by the current thread.

uint tmp = thinlock ^ compactTID;
if (tmp < MAX_COUNT_MASK && (tmp & 3) == 0)
{
  thinlock += COUNT_INCREMENT;
  return;
}

– Check for the error of trying to lock an object that is owned exclusively by another thread.

if ((thinlock & 3) == 1)
  throw new ExclusiveLockViolation;

– Check if the lock has been inflated (the two lowest bits are zero). If so, interpret the thin lock as a pointer to FatLock and lock it. Fat lock is implemented using the operating system locking primitives and can deal with contention. Return.

– If we reach this point, we know that there is contention for the lock or the count has overflowed. In either case we have to inflate the lock. We have to preserve one invariant–the lock can only be modified by the thread that holds it, otherwise we are open to all kinds of races. Therefore we have to busy-wait for the lock to be released.

while (thinlock != 3 && (thinlock & 3) != 0)
  compiler_fence();

Notice that busy waiting requires that the compiler not optimize this loop–we need a “compiler fence”. However, no processor memory fences are required, because there is no ordering dependence. It’s enough that, when another thread modifies the lock, the new value eventually becomes visible to the spinning thread.

It’s possible to miss the unlocked state and spin longer than necessary. Starvation is theoretically possible if the other thread keeps unlocking and locking without discovering a contention; with the current thread repeatedly missing the unlocked state. (This part of the algorithm may be optimized further by introducing exponential backup.)

– The loop is exited if either the lock has been released (thinlock == 3) or another thread managed to inflate the lock (the two lowest bits are zero, signifying that the value stored is a pointer to FatLock).

– Try to acquire the lock using CAS (the arguments are the same as in the original attempt).

– If it succeeds, allocate the fat lock, lock it, and atomically store the pointer to it in the thin lock. Return. Once the lock has been inflated, it will remain so for the lifetime of the object.

– If we reach this point, we know that: either the lock has been inflated, another thread is in the process of inflating it, or another thread has acquired the lock without contention while we were busy waiting.

– Try again: go back to busy waiting.

Unlocking

When unlocking, we have the guarantee that the current thread owns the lock, so we don’t need any additional synchronization.

• If the thin locks is zero, return. The object was not created for sharing.
• XOR thin lock with the compact thread ID.
• If the result is 2, we own the object exclusively. Return.
• If the result is zero, we hit the next most common case–the lock has been taken once by the current thread. Store 3 in the thin lock and return.
• If the result of XOR is non-zero and its lowest two bits are clear, decrement the recursion count.
• Otherwise, the lock has been inflated. Unlock the fat lock.

FatLock must also contain a field exclusively-owned-by. This field is filled with a compact thread ID when sharing is cast away. When sharing is re-established, this field goes back to zero. Therefore, after locking the fat lock, additional checking is done: If the field is non-zero and the result of XOR with the current compact thread ID is also non-zero, an exception is thrown (attempt to lock an exclusively owned object).

I already mentioned the paper, SharC: Checking Data Sharing Strategies for Multithreaded C, by Anderson at al. The authors describe a strategy for checking multithreaded correctness of C programs. They were able to classify sharing modes into five categories:

• Private (to current thread)
• Read only
• Shared under a specific lock (the lock is part of the type)
• Racy (no checking)
• Dynamically checked (to be either read-only or private)

The programmer makes strategic annotations by adding sharing type qualifiers to declarations of shared data. The SharC tool then derives the rest, and flags inconsistencies. There is also a run-time component for checking dynamically shared data and allowing safe casting between sharing modes.

You might notice some similarities to the D sharing model. For one, SharC assumes that all unannotated sharing is unintended and treats it as an error. In D, if you don’t annotate something as shared, it will be allocated from thread-private pool and it will be invisible to other threads.

The annotation system of SharC was not designed to be very practical. The authors didn’t expect the programmer to precisely annotate all shared variables–it’s clearly too much work. Instead they fell back on global program analysis, which is quite expensive and requires access to all sources.

In D we’ll have to make a few compromises to get maximum benefit from the types system without over-burdening the programmer with tedious annotations. (Making the right trade-offs is the hardest part of language design. You know you got it right when half of the programmers hate you for making it too strict, and the other half for making it too relaxed.) D reduces sharing annotations to just two type qualifiers: shared and invariant. I talked about shared in one of my previous post. The invariant type modifier is already well defined and in use in D 2.0.

The most interesting part of any sharing scheme based on types is the transitions between modes. A common example where such transitions might be desirable is in the producer consumer queue. Objects may be passed between threads–through the queue–either by value or by reference. When they are passed by reference, they have to be shared–multiple threads may access them concurrently. However, once the consumer gets exclusive access to such an object, she might want to treat it as non-shared. Why? Because she might want to pass itto a library function, which was not designed to deal with shared objects.

For obvious reasons we don’t want conversions between shared and non-shared data to be implicit. That would pretty much defeat the whole scheme. So we are left with explicit casting. Here’s my current thinking (which hasn’t been peer-reviewed yet).

There are two types of casts, unchecked and checked. An unchecked cast always succeeds (assuming it compiles), a checked one might throw an exception. C++ dynamic_cast is checked. So is D cast when applied to class objects. There are unchecked casts for numeric types in D, but the standard library provides a checked template to (in the module std.conv), which checks for over- and underflows.

How can you check a cast that strips the shared modifier– i.e., privatizes the object? SharC offers one solution–reference counting.

You can be 100% sure that no other thread has access to your shared data when you can prove that you have the only reference to it. SharC’s run-time uses a very clever reference counting scheme borrowed from a garbage collector to accomplish just that. Could we do it in D? We probably could, if we committed to the reference-counting GC, but that’s rather unlikely.

What’s the next best thing? Locking the object! This will only work for class objects, which have a built-in monitor but, at least in the SafeD subset, we expect class objects to play a major role. Locking the object when privatizing it has several advantages.

• It will fail if the object is already locked by another thread
• If another thread still has shared access to it after privatization, and tries to lock it, it will fail
• The reverse operation, casting an object back to shared, can be checked.

Most of this can be easily accomplished by slightly modifying thin locks (see my previous post). I’ll provide more details later.

Now, let’s talk about casting back to shared (I’m using “back” deliberately, as we don’t want to share objects that were created as non-shared). This cast is much more tricky, since a lot of bad things might have happen while the object was unshared. We can check for some of them and trust the programmer not to do others.

We have to trust the programmer not to squirrel away non-shared aliases to a temporarily unshared object (or its internals). Such aliases become unprotected back doors to the object when it becomes shared again. Remember that, even if you call a synchronized method on an object that is not declared as shared, the synchronization is statically elided by the compiler (at least that’s the plan).

Another danger is that non-shared objects may be inserted into a temporarily unshared object. For that we could check during casting, if we used a different heap for allocating shared objects. We could ask the garbage collector if a given pointer points into the shared heap or not. For class objects, this check can be made much faster by testing a special bit in the thin lock.

Checked sharing casts in both directions have to be recursive, since the shared qualifier is transitive. When casting from shared to non-shared, each class object must have its thin lock put in the “exclusively owned by current thread” state. When casting back to shared, each class object must have its thin lock put back in the sharing state, and all pointers must be checked against the shared heap.

Conveniently enough, in D, such checked casts can be implemented in the library using unchecked casts and reflection.

Publication safety is the core issue in the famously non-intuitive Double-Checked Locking Pattern.

What’s publication? In a nutshell, one thread prepares data and publishes it–other threads check if the data has been published and use it. Common scenario is the creation of a shared object (this example is written in the D programming language, but it’s pretty self-explanatory).

shared Foo foo = new shared Foo();

When a thread creates an object, it first runs its constructor (Foo()) and then points the shared handle (foo) to it. Other threads check the handle for non-null and then happily access the object.

if (foo !is null) foo.doSomething();

Naturally, in our naivete, we tend to assume that if the second thread can see a non-null handle, the construction of the object must have completed. That belief is known as publication safety and, guess what!, it’s not guaranteed on modern multi-processors that use relaxed memory models.

To understand what’s happening, let’s simplify the problem even further and write it in pseudo assembly. Initially the globals x and ready are zero. R is a thread-local variable (register). Think of writing to x as part of the construction of an object and writing to ready as the publication (the initialization of a shared handle).

Can Thread 2 see ready == 1 and x == 0? Yes, for two separate reasons. On a relaxed-memory-model multiprocessor

1. writes to memory can be completed out of order and
2. reads from memory can be satisfied out of order.

Imagine processors sending e-mail messages to memory. Thread 1 sends a message instructing the memory to write 1 to x. Then it sends another message instructing it to write 1 to ready. It’s perfectly possible on modern processors that the first message gets delayed and the write to ready completes before the write to x.

The way to make sure this doesn’t happen is to separate the two writes by a memory barrier, or fence. Every relaxed-memory-model multiprocessor offers some ways to do it. The x86’s (x > 3) have such instructions (mfence, lfence, and sfence), even though they implement processor-order memory model.

But beware, even if the writes are ordered by a (write) fence, the reads in Thread 2 may still execute out of order. Imagine that Thread 2 sends two e-mail messages asking for the values of ready and x. The second message arrives first, before any writes by Thread 1 are done. The memory sends back an e-mail with the value 0 for x. Next, the two writes by Thread 1 are committed. Then the first read message (fetch ready) arrives, and the memory responds with the value 1. Thread 2 sees a non-zero value of ready, but a zero (uninitialized) value of x. We’re in trouble!

Notice that the read of x is speculative. The processor issues the read request just in case the branch ready == 1 were taken. If it’s not, it can always abandon the speculation.

Again, the way to ensure that the two reads are satisfied in program order is to put a fence between them. Here’s the pseudocode.

Both fences are necessary!

The write fence is easier to remember. In our publication example,  it makes sense to put it at the end of the constructor. It has the connotation of flushing all the writes performed during construction, before the public handle is initialized.

It’s the need for the read fence that is often overlooked. It’s not immediately obvious that every time you access a published shared variable you have to use a fence. It’s the “every time” part that seems excessive, especially if your code initializes the handle only once (as in the double-checked locking pattern). Sure, there are a few cases when a benign race is acceptable, but even the best of us get it wrong half of the time.

Why is this whole low-level discussion relevant? Very few programmers will be inserting (non-portable) fences into their code. Most programmer will use monitors and locks, which have appropriate fences (or their equivalents) built in. Java programmers will mark shared variables volatile, which will tell the compiler to issue memory fences on every access. C++ and D programmers will occasionally use atomics, which are implemented with all the fencing in place.

But look at it this way: This is a cautionary story for high-level programmers too. Do not elide synchronization even in the simplest, seemingly obvious cases! Don’t try to be clever! The processors (and the compilers) are out there to get you. The slightest slip and they will “optimize” your code in a way that is contrary to your intuitions.

Most modern multi-processors implement relaxed memory models. How much should you care about that?

When you program in a high-level language, you shouldn’t have to worry about your processor’s memory model, as long as you follow some simple rules.

In Java, for instance, you must make sure that access to shared variables (both for reading and writing) is protected by locks (e.g., synchronized sections). If you are adventurous, and want to share variables without locking, you must declare them as volatile. Finally, if you try to share non-volatile variables without locking, you are introducing data races and your program is considered incorrect (it might still work on some processors). This is what the Java memory model is about, in a nutshell.

C++ memory model proposal takes a similar approach, except that the use of volatile is replaced by the atomic library. Renegade Java programmers beware–C++ volatile has no multi-thread connotations (except in some vendor-specific extensions).

The D programming language tries to bridge the gap between safe and simple (Java-like), and unsafe and efficient (systems) programming. That almost requires two different memory models.

In the SafeD subset, we’d ideally want to ban all races and deadlocks. That could be accomplished only by eliminating lock-based programming. It seems like a drastic step until you consider that (a) you could still use certified libraries that internally use locking, and (b) you’d have futures, message passing, and STM (Software Transactional Memory) at your disposal. There are languages, like Erlang, that base all concurrency on message passing. And there’s a lot of code written in Erlang, despite its idiosyncratic syntax.

On the systems-programming end, D might as well follow the C++ memory model, down to “raw” atomics, which let you introduce low-level data races.

The volatile keyword is reserved in D, but it’s not clear what it should mean. We might simply get rid of it or change its definition. The problem is that volatile means many different things. In Java, it’s both a directive to the compiler to insert appropriate fences (memory barriers), as well as a directive to the optimizer not to perform code motion or caching. This is also how Microsoft implemented volatile in their C++ compiler. In principle, code motion and fencing are orthogonal issues. Hans Boehm’s implementation of atomics, for instance, uses a low level primitive AO_compiler_barrier, which prevents code movement without introducing memory fences (it’s implementation is very compiler-specific).

Of course, the D atomics library would not be certified for use in SafeD; but some lock-free data structures based on it, would.