I often speak of the need to develop programming models whereby developers write code in the most natural way possible, and it just so happens to be inherently parallel.  I don’t believe the lion’s share of developers want to rearchitect and rewrite their code with parallelism at the forefront of their development process.  They don’t want to think about shipping memory over to the GPU and launching a highly-specialized data parallel kernel of computation, nor do they want to have to add locks and transactions everywhere to make things safe.  But I do, however, believe the lion’s share of developers wouldn’t mind if their code ran faster as hardware got faster (via more cores).

(To be clear, there are certainly a lot of developers who will be happy to write specialized code if it means eking out every last bit of performance on their machine.  But that’s the minority.)

This viewpoint tends to get a lot of skeptical looks from people who quickly point out that this has been tried countless times before, and always leads to failure.  They, of course, are referring back to the 80’s and early 90’s where “dusty deck” parallelization was all the rage, mostly in the realm of vectorization and HPC.  To be fair, there were some mild successes in getting floating point loops parallelized, but there’s no wonder these attempts had little longevity.  No touch solutions are always inadequate.  Trying to make a fundamentally non-secure program secure, by way of, say, virtualization, may work in some constrained circumstances.  But the right solution is to develop models and practices that lead to security-by-construction.

Furthermore, languages were (and in most cases still are) lacking some major prerequisites for large-scale automatic parallelization:

1. Safety.  Unless a compiler can reason about the determinism of a program when run in parallel, one cannot prove that its results will remain correct when parallelism is added.  Compilers are therefore limited to parallelizing highly-specialized recognized patterns, like loops comprised solely of floating point additions of two arrays indexed by the loop iteration.
   
2. Performance.  Rampantly parallelizing a huge program wherever possible is dangerous, will drain performance, and make power consumption skyrocket.  Dynamic techniques like workstealing and static techniques like nested data parallelism and profile guided feedback need to work together to inform these decisions.  Machine-wide resource management needs to know about the memory topology, machine load and policy, and make informed decisions based on them.  Although there has been a lot of disparate research in these areas over the years, they have only recently been coming together.  Certainly in the 80’s, they were in their infancy.
   
3. Declarative patterns.  Most of the prior art was done in FORTRAN, a standard imperative language riddled with loops, effects, and assignments.  Programs need to be written with as few dependencies as possible in order to expose large amounts of parallelism, and the von Neumann inspired languages fall short of this aim.  Data comprehensions allow set-at-a-time computations to be expressed in a higher-order way, and newer languages like Fortress have language semantics that permit parallel evaluation in many more areas, like argument evaluation.  And application models that encourage isolation and loose state coupling allow coarse partitioning.

In addition to all of those three things, we must have realistic expectations.  Even if a program were fully safe to parallelize, as many Haskell kernels are, we would seldom see perfect scaling.  Buying a 128-core machine doesn’t necessarily give you a 128x speedup.  Why?  Because there are still portions of the code that will end up less parallel than other portions, and some parts may even continue to run sequentially.  There will always be I/O and waiting: these are real programs, after all, and real programs tend not to be 100% computation.  They need to do something useful with the real world.  Moreover, safety does not mean “dependence free.”  And data dependencies are ultimately what limit parallelism.

My stated goal would therefore be that parallelism in programs is solely limited by data dependence.  Safety issues are handled by construction.  Performance is (mostly) handled by the system, although as with all things, there will be some amount of measurement, hints, and tuning necessary.  But hopefully a huge part of tuning performance will be seeking out needless dependencies, or finding new algorithms that have different dependence characteristics.  And with that, we can focus our energy on raising the level of abstraction and pushing more declarative patterns that are broadly useful.  Over time as more and more programs are written in this fashion, they become more and more naturally parallel.

What do you think?  Am I crazy?  Perhaps.  But I still know we can do it.

Managed code generally is not hardened against asynchronous exceptions.

“Hardened” simply means “written to preserve state invariants in the face of unexpected failure.”  In other words, hardened code can tolerate an exception and continue being called subsequently without a process or machine restart.  Conversely, code that is not hardened may react sporadically if continued use is attempted: by corrupting state and subsequently behaving strangely and unpredictably.

Asynchronous exceptions are a foreign concept to native programmers, and arise because there is a runtime underneath all managed code that is silently injecting code on behalf of the original program.  The only truly asynchronous exception is ThreadAbortException, but any in the set { OutOfMemoryException, TypeInitializationException, ThreadInterruptedException, StackOverflowException } are often labeled as such.  While thread aborts can happen at any line of code outside a delay-abort regions, these other exceptions can be introduced by the CLR at surprising times; i.e., { memory allocations, static member access, blocking calls, any function call }.  The effect is that, unlike most exceptions, the points at which they may occur are not obvious.  OOMs, for instance, can happen at any method call (due to failure to allocate memory in which to JIT code), implicit boxing, etc.

(As of 2.0, StackOverflowException is no longer relevant because SO triggers a FailFast of the process instead.  So saying that managed code is not hardened against SO is an understatement.)

Also, because of the way COM reentrancy works, any blocking call can lead to any arbitrary code dispatched through STA pumping.  And that arbitrary code, much like an APC, can fail via any arbitrary exception.  These are a lot like asynchronous exceptions.  So in truth, code that isn’t written to respond to arbitrary exceptions at all blocking points is technically not hardened either.

.NET doesn’t provide checked exceptions, so the blunt reality is that very little managed code is hardened properly to synchronous exceptions either.  I think we do a better job in the framework of carefully engineering the code to resiliently tolerate failure, usually by being very careful about argument validation, but we aren’t perfect.  Some things slip through.

If you stop to think about why hardening isn’t done, it’s probably obvious.  It’s darn difficult.  Especially for asynchronous exceptions where nearly every line of code must be considered.  In Win32 programming, most failure points are indicated by return codes.  (Although C++ exceptions can sneak through the cracks at surprising times.  Like the fact that EnterCriticalSection can throw.)  While error codes are cumbersome to program against (since every call needs to be checked for a plethora of conditions, making it easy to miss something), at least the response to failure is explicit.  You can decide to propagate and leave state corrupt, fix up state and then propagate, rip the process, or ignore the failure, as appropriate.  This becomes part of the API contract.  In managed code, you need to know to wrap such calls in try/catch blocks.  Nobody does this.  It’s insane to even consider doing that.  And because nobody does, you can’t even catch exceptions coming out of a single API call and know that, when faced with an OOM (for example), that all code on the propagating callgraph has transitively handled the failure in a controlled manner.  The very fact that the lock{} statement auto-unlocks without rolling back corrupt state should be indication enough of the current state of affairs.

An instance of any of the aforementioned exceptions means the AppDomain is toast.

By toast, I mean that it’s soon going to be unusable, and hopefully actively being unloaded.  Code in the framework assumes this, and you should too.  All it does is try to get out of the way by not crashing or hanging the ensuing unload.  A small fraction of code that deals with process-wide state comprised of resources not under the purview of the CLR GC needs to worry about running and avoiding leaks.  This is where things like CERs, CriticalFinalizerObjects, and paired operations stuck in finally blocks come into play.  They ensure cross-process state is freed, and that asynchronous exceptions cannot occur in places that would crash or hang a clean unload.

Unfortunately, it’s not always the case that the AppDomain is unloading when such an exception occurs:

• Somebody can call Thread.Abort directly, without killing the AppDomain.  They can either call ResetAbort and keep it around, or let it return to the ThreadPool which catches and swallows aborts.  In fact, we tell people that synchronous aborts a la Thread.CurrentThread.Abort is “always safe”, whereas we tell people asynchronous aborts are dangerous and best avoided.
• Some framework infrastructure, most notably ASP.NET, even aborts individual threads routinely without unloading the domain.  They backstop the ThreadAbortExceptions, call ResetAbort on the thread and reuse it or return it to the CLR ThreadPool.  That means any code running in ASP.NET is apt to be corrupted when websites are recycled and AppDomain isolation is not being used.
• Assume AppDomain B is being unloaded.  If some thread has called from A to B to C, the thread will immediately suffer an abort.  The result is that C will see a thread unwinding with a ThreadAbortException, back into B, and then back to A, at which point the exception turns into a deniable AppDomainUnloadedException that can be caught.  But C has seen an in-flight abort and yet it is not being unloaded.  The result is that C’s state may be completely corrupt.  I believe this should be considered a bug in the CLR.
• We can’t differentiate between soft- and hard-OOMs today.  The former are caused by requests to allocate large blocks memory.  Often a failure here isn’t indicative of a disaster.  It may be due to a need to allocate 1GB of contiguous memory, and perhaps there is fragmentation.  Hard OOMs are often caused by running up against the edge of the machine where no pagefile space is available, and may indicate a failure to JIT some important method, among other things.  But because we don’t differentiate, any managed code can catch-and-ignore any kind of OOM, including hard ones.
• Thread interruptions are often used as a form of inter-thread communication.  For example, they can be used as a poor man’s cancellation.  (This is inappropriate, and cooperative techniques should always be used.  But it is widespread.)  But because they are used as a means of communication, they are almost always caught and handled in some controlled manner.  This is one place where we screwed up by not hardening the frameworks against interrupted blocking calls and reacting intelligently.  Checked exceptions would have saved us.

What does all of this mean?  Quite simply, the .NET Framework cannot be trusted when any of the aforementioned exceptions are thrown.  Ideally the process will come tumbling down shortly thereafter, but improperly written code can catch them and continue trying to limp along.  In fact, as I mentioned above, some wildly popular & successful application models do (notably, ASP.NET and WinForms).

This state of affairs is admittedly unfortunate.  We don’t properly separate out the truly fatal exceptions from those that we can gracefully recover from.  In an ideal world, I’d love to see us do that.  For example:

1. At some point, we really ought to consider FailFast instead of continuing to run code under failures we know are fatal and dangerous to attempt to recover from, much like we do with SO.  At least these failures should be undeniable like thread aborts are.  But this is a fairly Byzantine response and is not for the faint of heart.  Given that we still live in a world where WinForms wraps the top-most frame of the GUI thread in a catch-all, presents a dialog box, and allows a user to click “Ignore & Continue”, I seriously doubt we’ll get there anytime soon.
2. Never expose a ThreadAbortException to code in an AppDomain unless we can guarantee the AppDomain is being unloaded.  That means getting rid of the Abort API, and thus indirectly disallowing code from catching and calling ResetAbort.  It also means the A calls B calls C case would not allow B to unload until the thread voluntarily unwinds out of C.
3. Allow OOMs to be caught only when they are soft.  That means a call to ‘new’, and it means the catch much occur inside the same stack frame as the call to ‘new’.  Such exceptions can be tolerated if code is properly written, and we will tell developed to be mindful of them.  Once such an OOM propagates past the calling stack frame, they will escalate to hard.
4. All other OOMs are hard and fatal.  This includes failure to allocate memory to JIT code and failure to allocate 20 bytes to box an int.  Hard OOMs are thus undeniable.
5. Get rid of ThreadInterruptedExceptions.  We screwed this up from Day One, and it’s probably too late to fix this.  We added cooperative cancellation in .NET 4.0 for a reason.
6. TypeInitializationExceptions can probably stay, but we should allow rerunning the cctor upon subsequent accesses.  Today, once a class C throws from its cctor, the class can never be constructed.  So on the current plan, it only makes sense to FailFast.

I’m sure there are many other things we could do to improve things.  But these 6 general themes would be a great start.

I’m just spitballing here.  There are no concrete plans to do any of these 6 things as far as I know.  And at the end of the day, hardening only improves the statistics of the situation, so it tends to be very difficult to argue for one change over another, particularly if taking the change would make existing programs break.  But I really would like to see the base level of reliability in managed code improve with time.  Especially with the exciting work going on around contract-checking in the BCL in Visual Studio 10, I hope these topics become top-of-mind for folks again in the near future.

A developer from the Parallel Extensions team, Igor Ostrovsky, recently whipped together a really neat Silverlight game.  It's called RoboZZle, and he calls it a "social puzzle game":

"RoboZZle is an online puzzle game that challenges players to program a robot to pick up all stars on a game board. The game mechanics are simple, yet allow for a wide variety of challenges that call for very different solution approaches." (from the blog entry introducing it.)

The coolest feature of this game is that you win by programming.  And there's a whole community surrounding it, complete with forums, the ability to create your own games, a ranking system, its own blog and continuously updated news, etc.  Check it out.

Pop quiz: Can this code deadlock?

A few weeks back I recorded a discussion with the infamous Erik Meijer and Charles from Channel9.

Perspectives on Concurrent Programming and Parallelism
http://channel9.msdn.com/shows/Going+Deep/Joe-Duffy-Perspectives-on-Concurrent-Programming-and-Parallelism/

In it, I show my cards a bit more than intuition says I should.  I'm not good at poker.

To summarize:

• Mostly functional (purity + immutability) is a great default.
• Safe, determinstic mutability (a la runST) is a must-have for cognitive familiarity.
• Isolation is key to achieve the former; type systems can help (a lot).
• Actors, agents, forkIO, <what have you> is a good model, but not the only one.  Isolation is (far) more general.
• Transactions can help around the edges.

I'm working on a few papers for public consumption this year where I espouse these ideas.  Keep watching for more detail.

I was very harsh in my previous post about reader/writer locks.

The results are clearly very hardware-specific.  And one can certainly argue that better implementations are possible.  (In fact, I will show one momentarily.)  But no matter which way you slice-and-dice it, a lock implies mutable shared state which implies contention.  Herb argued this point quite well, and rather thoroughly, in his recent Dr. Dobb’s article.  Interference due to contention means more time spent resolving memory conflicts and less time doing useful work.  A reader/writer lock can be infinitely clever, but there is still a consensus protocol that must be established: and that implies a loss of scalability.  Pretty simple.

It’s very tricky to develop a consensus protocol that is sufficiently lossy so as to relieve memory contention while at the same time being sufficiently precise that the lock works right.  In the case of a spinning reader/writer lock (which is, for what it’s worth, overly naïve an approach for most circumstances), you need to ensure that a writer knows for sure when there are 0 readers, and that each reader knows for sure whether there is 0 or 1 writer.  (For blocking reader/writer locks, there’s a whole lot more.)  One promising thing to note is that the writer only needs to know whether there are 0 or N readers, but not the specific value N; there’s a fair bit of research on scalable counters (like this) which exploit problems of this nature.  Unfortunately, it’s not completely relevant here.  You need to know exactly when the transition from N to 0 readers happens in order to let the writer through in a timely fashion; and in order to account for that transition, a consensus among readers is needed.  That's hard to do.

More scalable solutions are possible than the simple lock I showed previously.  Although writers need to know whether readers are present, the readers themselves could care less about other readers.  As a result, we can make the lock slightly more expensive for the writer, because it needs to accumulate the count of readers, but this allows us to make it it slightly cheaper for the readers to enter and exit.  Where cheaper means less contention.

Here’s one possible algorithm.  We’ll keep an array of read flags and a single write flag:

private volatile int m_writer;

private ReadEntry[] m_readers = new ReadEntry[Environment.ProcessorCount * 16];

A few things are noteworthy about the read flags.

First, it’s an array of ReadEntry values.  These are just simple structs that wrap a volatile int, but we also pad the struct so that it’s 128 bytes in total size.  That avoids the situation where multiple read flags just happen to end up sharing the same cache line (which are usually either 64 or 128 bytes in size), which leads to false sharing in the memory system (destroying our aim to reduce contention).

[StructLayout(LayoutKind.Sequential, Size = 128)]

struct ReadEntry {

    internal volatile int m_taken;

}

Second, we size the array to be 16-times the number of processors.  We hash into it based on the calling thread’s unique identifier, so to reduce (but not eliminate) the chance of hashing collisions, we’ll use a few times more buckets than the total number of concurrent threads.  Hashing collisions are expensive: they incur some amount of memory contention, and also demand that we use an atomic CAS increment instead of an ordinary ++.  (While a super-duper-cheap TLS solution might seem more ideal, there isn’t any good per-object TLS solution to use.  The array hashing approach is actually quite fast.)

Notice that we’re using an awful lot of space for a single lock.  This means the techniques I show here wouldn’t be readily applicable to a system that uses lots of fine-grained locks, like transactional memory.  But similar ideas can be extrapolated, e.g., by using shared lock tables.

Lastly, some invariants among these fields are self-evident.  When the writer flag is 0, no writers are waiting; when it is 1, either a writer is actively in the critical section, or there is a writer waiting for readers to exit.  When at least one reader flag entry is non-0, there is a reader either inside the lock or attempting to enter it.  Thus, no new writer is permitted while there’s a non-0 reader entry, and no new reader is permitted while there’s a non-0 writer flag.  This is sufficient to ensure the reader/writer lock properties hold.

Now let’s look at how the EnterReadLock and ExitReadLock methods work.

When a reader arrives, it spins until the writer flag is non-0.  It then hashes into the read flag array using its unique thread identifier, and then atomically increments the read counter.  It then needs to recheck that a writer didn’t arrive in the meantime.  (The CAS increment means we can safely do this without worry for reordering bugs, like the read of the writer flag passing the write to the reader flag.)  If a writer hasn’t arrived, the read lock has been successfully acquired and we’re done; if a writer has arrived, however, the reader needs to back out the change (since the writer might be waiting for the read flag to become 0) and then go back to spinning.  It will retry again once the writer exits.

private int ReadLockIndex {

    get { return Thread.CurrentThread.ManagedThreadId % m_readers.Length; }

}

 

public void EnterReadLock() {

    SPW sw = new SPW();

    int tid = ReadLockIndex;

 

    // Wait until there are no writers.

    while (true) {

        while (m_writer == 1) sw.SpinOnce();

 

        // Try to take the read lock.

        Interlocked.Increment(ref m_readers[tid].m_taken);

        if (m_writer == 0) {

            // Success, no writer, proceed.

            break;

        }

 

        // Back off, to let the writer go through.

        Interlocked.Decrement(ref m_readers[tid].m_taken);

    }

}

(Note that SPW is a little type to encapsulate the spin-wait logic, including some amount of backoff to reduce contention.  An example implementation at the bottom of this essay, along with the full reader/writer lock code.  .NET 4.0 includes a SpinWait type that provides this same functionality.)

Exiting the read lock is pretty simple.  We just need to decrement our counter.

public void ExitReadLock() {

    // Just note that the current reader has left the lock.

    Interlocked.Decrement(ref m_readers[ReadLockIndex].m_taken);

}

The writer lock is pretty straightforward.  It works the same way most spin-based mutually exclusive locks work, but using a CAS on the writer flag, but has an extra step after successfully acquiring the lock: a writer must walk the list of read flags, and wait for each one to become 0.  (This is similar to Peterson's mutual exclusion algorithm for N-threads.)  Because the write flag is set first (using a CAS), and because new readers won’t enter if the flag is set, we can be assured this works correctly without hokey memory reordering problems cropping up.

public void EnterWriteLock() {

    SPW sw = new SPW();

    while (true) {

        if (m_writer == 0 && Interlocked.Exchange(ref m_writer, 1) == 0) {

            // We now hold the write lock, and prevent new readers.

            // But we must ensure no readers exist before proceeding.

            for (int i = 0; i < m_readers.Length; i++)

                while (m_readers[i].m_taken != 0) sw.SpinOnce();

 

            break;

        }

 

        // We failed to take the write lock; wait a bit and retry.

        sw.SpinOnce();

    }

}

And exiting the write lock is even simpler than exiting the read lock.  We just set the writer flag to 0.

public void ExitWriteLock() {

    // No need for a CAS.

    m_writer = 0;

}

Given all of that, you might wonder how well this bad boy performs.  Well, single-threaded performance is a bit worse than the previous spin reader/writer lock: about 1.55x the cost of a monitor acquisition for the read lock instead of 0.95x, and about 5.52x for the write lock instead of 0.85X.  This makes sense.  There’s simply a whole lot more work going on in this new lock compared to the old, simple one.

But scalability is vastly improved.  Our hard work has apparently paid off.  Here’s a table much like the one in the previous post: scaling over the equivalent mutually exclusive monitor code, for various percentages of writers and various amounts of "work" (counts of function calls) inside the lock region.  (I have left out the legacy .NET ReaderWriterLock type because it is embarassingly terrible.)  Remember: 1.0x means it scales the new lock is the same as monitor, 0.5x means twice as fast, and 2.0x means twice as slow.  0.25x is ideal speedup (4x) since I am running the tests on a four way machine.

0% writers:

              0 calls       10 calls      100 calls     1000 calls

RWLSlim (3.5) 2.11x         2.01x         0.96x         0.32x

SpinRWL(old)  9.63x         7.04x         1.02x         0.26x

SpinRWL(new)  0.39x         0.36x         0.28x         0.25x

 

5% writers:

              0 calls       10 calls      100 calls     1000 calls

RWLSlim (3.5) 2.29x         2.36x         1.18x         0.61x

SpinRWL(old)  5.69x         5.59x         1.43x         0.94x

SpinRWL(new)  1.01x         0.96x         0.45x         0.38x

 

10% writers:

              0 calls       10 calls      100 calls     1000 calls

RWLSlim (3.5) 2.26x         2.04x         1.15x         1.00x

SpinRWL(old)  6.87x         5.03x         1.42x         1.34x

SpinRWL(new)  1.60x         1.51x         0.63x         0.53x

 

25% writers:

              0 calls       10 calls      100 calls     1000 calls

RWLSlim (3.5) 2.09x         2.10x         1.14x         1.00x

SpinRWL(old)  4.70x         4.20x         1.43x         1.69x

SpinRWL(new)  2.81x         2.29x         1.27x         0.73x

 

50% writers:

              0 calls       10 calls      100 calls     1000 calls

RWLSlim (3.5) 2.18x         1.95x         1.15x         0.95x

SpinRWL(old)  3.23x         3.73x         1.54x         1.39x

SpinRWL(new)  3.16x         2.76x         1.73x         1.10x

 

100% writers:

              0 calls       10 calls      100 calls     1000 calls

RWLSlim (3.5) 2.18x         1.95x         1.04x         0.92x

SpinRWL(old)  2.63x         2.04x         1.06x         0.87x

SpinRWL(new)  6.79x         3.96x         1.62x         1.06x

You can see there are now several more cases where the new reader/writer lock beats out both the .NET 3.5 ReaderWriterLockSlim type in addition to our previous attempt.  In fact, we now have a few new scenarios that scale, like 5% or 10% writers where the amount of work being done is at least 100 function calls.  (Unfortunately, doing 100 or more function calls inside a lock that uses spin-waiting is dangerous and considered a very bad practice: you should be able to count the number of instructions on your fingers (and toes).  But that’s somewhat beside the point.)  In summary, so long as there is a fair amount of work going on and the percentage of writers remains very low, we might see a benefit.

So was I overly harsh on reader/writer locks in my last post?  Sure, maybe a little.  While I am still very disappointed in the current .NET reader/writer locks (and, I imagine, the Vista SRWLock), the results I was able to get here are a bit more promising.

But the point I was trying to get across is the same: sharing is sharing is sharing.  Avoid it like the plague.

(Thanks to Tim Harris for sending me private email about my previous posts.  The brief discussion inspired me to pick this back up.)

Here’s the full code for the reader/writer lock.

using System;

using System.Threading;

using System.Collections.Concurrent;

using System.Collections.Generic;

using System.Runtime.InteropServices;

// We use plenty of interlocked operations on volatile fields below.  Safe.

#pragma warning disable 0420

/// <summary>

/// A very lightweight reader/writer lock.  It uses a single word of memory, and

/// only spins when contention arises (no events are necessary).

/// </summary>

public class ReaderWriterSpinLockPerProc {

    private volatile int m_writer;

    private volatile ReadEntry[] m_readers = new ReadEntry[Environment.ProcessorCount * 16];

    [StructLayout(LayoutKind.Sequential, Size = 128)]

    struct ReadEntry {

        internal volatile int m_taken;

    }

    private int ReadLockIndex {

        get { return Thread.CurrentThread.ManagedThreadId % m_readers.Length; }

    }

    public void EnterReadLock() {

        SPW sw = new SPW();

        int tid = ReadLockIndex;

        // Wait until there are no writers.

        while (true) {

            while (m_writer == 1) sw.SpinOnce();

            // Try to take the read lock.

            Interlocked.Increment(ref m_readers[tid].m_taken);

            if (m_writer == 0) {

                // Success, no writer, proceed.

                break;

            }

            // Back off, to let the writer go through.

            Interlocked.Decrement(ref m_readers[tid].m_taken);

        }

    }

    public void EnterWriteLock() {

        SPW sw = new SPW();

        while (true) {

            if (m_writer == 0 && Interlocked.Exchange(ref m_writer, 1) == 0) {

                // We now hold the write lock, and prevent new readers.

                // But we must ensure no readers exist before proceeding.

                for (int i = 0; i < m_readers.Length; i++)

                    while (m_readers[i].m_taken != 0) sw.SpinOnce();

                break;

            }

            // We failed to take the write lock; wait a bit and retry.

            sw.SpinOnce();

        }

    }

    public void ExitReadLock() {

        // Just note that the current reader has left the lock.

        Interlocked.Decrement(ref m_readers[ReadLockIndex].m_taken);

    }

    public void ExitWriteLock() {

        // No need for a CAS.

        m_writer = 0;

    }

}

struct SPW {

    private int m_count;

    internal void SpinOnce() {

        if (m_count++ > 32) {

            Thread.Sleep(0);

        } else if (m_count > 12) {

            Thread.Yield();

        } else {

            Thread.SpinWait(2 << m_count);

        }

    }

}

A couple weeks ago, I illustrated a very simple reader/writer lock that was comprised of a single word and used spinning instead of blocking under contention.  The reason you might use a lock with a read (aka shared) mode is fairly well known: by allowing multiple readers to enter the lock simultaneously, concurrency is improved and therefore so does scalability.  Or so the textbook theory goes.

As a purely theoretical illustration, imagine we’re on a heavily loaded 8-CPU server where a new request arrives every 0.25ms and runs for 1ms.  In an ideal world, we could service requests coming in at a rate of 1ms / 8-CPUs = 0.125ms without falling behind.  But imagine these requests need to access some shared state, and so there is a bit of serialization required.  In fact, let’s imagine each does 0.5ms’ worth of its work inside a lock.  If you were to use a mutually exclusive lock, then you’d have an immediate lock convoy on your hands.  Even with 8-CPUs you won’t be able to keep up.  You’ll start off gradually building up a debt, and eventually come to a crawl.  Let’s examine the initial timeline:

Req#          Arrival       Acquire       Release       Wait Time

1             0.0ms         0.0ms         0.5ms         0.0ms

2             0.25ms        0.5ms         1.0ms         0.25ms

3             0.5ms         1.0ms         1.5ms         0.5ms

4             0.75ms        1.5ms         2.0ms         0.75ms

5             1.0ms         2.0ms         2.5ms         1.0ms

6             1.25ms        2.5ms         3.0ms         1.25ms

7             1.5ms         3.0ms         3.5ms         1.5ms

8             1.75ms        3.5ms         4.0ms         1.75ms

Oh jeez, after only the first 8 requests, we’ve fallen way behind.

Each new request adds 0.25ms onto the amount of time the request must wait for the lock.  And it’s not going to get any better:

9             2.0ms         4.0ms         4.5ms         2ms

10            2.25ms        4.5ms         5.0ms         2.25ms

11            2.5ms         5.0ms         5.5ms         2.5ms

12            2.75ms        5.5ms         6.0ms         2.75ms

 

... and so on ...

By request #9, requests have to wait for twice as long as they run.  Eventually something has to give, or the server will come tumbling down.

Now, imagine we used a reader/writer lock instead.  Threads would never wait for each other, and we wouldn’t end up with this never-ending buildup of wait times.  In other words, the “Wait Time” column above would always be 0.0ms.  And because the arrival rate is less than our theoretical limit of one request per 0.125ms, our lock convoy is gone.  Right?

Unfortunately, probably not; this mental model is overly naïve.

Even when a read lock is acquired, there is mutual exclusion going on:

• Some reader/writer locks actually use mutually exclusive locks to protect their own internal state, like the list of current readers!  This can come as a surprise, but it’s true of the .NET reader/writer locks.  Vance’s example even does and, although it uses a spin lock in an attempt to reduce the overhead, there’s still no denying that it’s mutual exclusion.
• And even if they don’t use mutually exclusive locks, like the simple spin-based one from my previous blog post, there are CAS instructions.  And a CAS instruction actually amounts to a form of mutual exclusion at the hardware level, because the cache coherency machinery needs to ensure that no two processors try to acquire and modify the same cache line exclusively.
• In addition to all of that overhead, the cost in CPU cycles of acquiring the read-lock is nowhere near zero.  Because of the use of locks and/or CAS internally, and the resulting cache contention and line evictions that this will cause, throughput will suffer.  If there is contention, threads may end up blocked (if real locks are being used), spinning (if spin locks are being used), or simply optimistically retrying CAS’s due to line ping ponging.

The result?

Read locks are just as bad as mutually exclusive locks when lock hold times are short.  In fact, they can be worse, because reader/writer locks are more complicated and therefore cost more than simple mutually exclusive locks: many need to keep track of read lists in order to disallow recursive acquires, maintain multiple event handles so certain kinds of waiters can be awakened over others, and store various kinds of counters and flags.  Even my super simple single-word, spin-based reader/writer lock needed to worry about blocking out readers when a writer was waiting, properly incrementing and decrementing the reader count when readers are racing with one another (leading to more complicated CAS on the exit path than ordinary write locks), and so on.

That said, a reader/writer lock would in fact probably work in the situation above.  A hold time of 0.5ms is huge, and with only 8 concurrent threads and the arrival rate we’re talking about, the overheads are apt to be quite small in relation to the work being done.  Another similar setting in which reader/writer locks commonly make a noticeable difference is in the execution of large database transactions.

But the sad truth is that we tell programmers to keep lock hold times short, and most locks I see are comprised of two dozen instructions or less.  So we’re in the microsecond range at the very most, which is certainly not large enough for read locks to pan out.

To illustrate this point, I wrote a little benchmark program that benchmarks the legacy .NET ReaderWriterLock, the 3.5 ReaderWriterLockSlim type, and my little spin reader/writer lock.  All it does is spawn 4 threads on my dual-socket, dual-core (4-CPU) machine, and then loop around so many times acquiring and releasing a certain kind of lock.  I’ve written the test so that the amount of work done inside the lock is parameterized as a certain number of non-inlined function calls.  I also parameterize the percentage of acquires that will be write-locks.  Then I’ve run this a bunch of times, and compared the total time taken with the equivalent code using a CLR Monitor for mutual exclusion instead.

Here are some results, where each column represents the number of function calls.  The entries are the cost relative to Monitor: 1.00x means they are the same, 0.5x means the alternative lock is twice as fast, and 2.0x means the alternative lock is twice as slow.  Remember, the ideal situation would be 0.25x: that is, by allowing four threads to run completely concurrently, we run four times faster.

0% writers:

                     0 calls       10 calls      100 calls     1000 calls

RWL (legacy)         9.23x         6.46x         0.90x         0.49x

RWLSlim (3.5)        2.11x         2.01x         0.96x         0.32x

SpinRWL              9.63x         7.04x         1.02x         0.26x

 

5% writers:

                     0 calls       10 calls      100 calls     1000 calls

RWL (legacy)         10.55x        8.23x         1.71x         0.63x

RWLSlim (3.5)        2.29x         2.36x         1.18x         0.61x

SpinRWL              5.69x         5.59x         1.43x         0.94x

 

10% writers:

                     0 calls       10 calls      100 calls     1000 calls

RWL (legacy)         20.31x        10.39x        2.34x         0.99x

RWLSlim (3.5)        2.26x         2.04x         1.15x         1.00x

SpinRWL              6.87x         5.03x         1.42x         1.34x

 

25% writers:

                     0 calls       10 calls      100 calls     1000 calls

RWL (legacy)         74.49x        49.59x        9.18x         2.15x

RWLSlim (3.5)        2.09x         2.10x         1.14x         1.00x

SpinRWL              4.70x         4.20x         1.43x         1.69x

 

50% writers:

                     0 calls       10 calls      100 calls     1000 calls

RWL (legacy)         148.34x       98.46x        20.46x        3.63x

RWLSlim (3.5)        2.18x         1.95x         1.15x         0.95x

SpinRWL              3.23x         3.73x         1.54x         1.39x

 

100% writers:

                     0 calls       10 calls      100 calls     1000 calls

RWL (legacy)         170.59x       123.66x       24.04x        4.29x

RWLSlim (3.5)        2.18x         1.95x         1.04x         0.92x

SpinRWL              2.63x         2.04x         1.06x         0.87x

Clearly there are a number of anomalies in these numbers.  Why the legacy ReaderWriterLock balloons to 170X the cost of Monitor when we have 100% writers is a very interesting question indeed.  Why my simple spin reader/writer lock is 9.63X when we have pure reads and 0 calls, and yet the ReaderWriterLockSlim type is only 2.11X is also interesting.  And so on.  The numbers are very specific to the version of .NET I am using, and indeed the precise machine configuration, including the number and layout of cores and caches.

But if we look more generally at the numbers, ignoring some of the surprising ones, we can make one interesting and safe conclusion: You need a really low percentage of writers, and a really long amount of time inside the lock, for any scalability wins to show up as a result of using a reader/writer lock.  Our best case was the spin reader/writer lock when we had 0% writers and 1000 calls.  But clearly if you have no writers, i.e., state is immutable, there’s little point in using any locks whatsoever!  This is an extreme result, where threads are hammering on the lock constantly in a tight loop, but if you stop to think about it: When else would a reader/writer lock make a difference?  If threads are just getting in and out of the lock very quickly, and arrivals are infrequent, then there is no benefit to allowing multiple threads in at once anyway.

The moral of the story?  Besides suggesting that you seriously question whether a reader/writer lock is actually going to buy you anything, it's the same as the conclusion in my previous post on the matter:

Sharing is evil, fundamentally limits scalability, and is best avoided.

I frequently get asked about the C# compiler's warning CS0420 about taking byrefs to volatile fields.  For example, given a program

class P {
    static volatile int x;

    static void Main() {
        f(ref x);
    }

    static void f(ref int y) {
        while (y == 0) ;
    }
}

the C# compiler will complain

xx.cs(8,15): warning CS0420: 'P.x': a reference to a volatile field will not be treated as volatile

because of the line containing 'ref x'.  (The same applies to 'out' parameters too.)  The natural question is, of course, whether to worry about it.

In general, the answer is yes, you must worry.  In the above example, the use of the 'y' parameter inside 'f' will not be treated as volatile, as the warning says.  What does that mean in practice?  For one, the read of 'y' in 'f's while loop could be considered loop invariant by the JIT compiler and hoisted, and you'd possibly loop forever.  It also means that on IA64 platforms, such reads will be emitted as ordinary loads instead of the special load-acquire variant that is emitted for volatile loads.  This can lead to reordering bugs.  In other words, you lose the volatile-ness of the field as soon as you cast it away as an ordinary byref.  And unlike C++ where you can have a volatile pointer, there's no way to mark a .NET byref as volatile.

(You can use the Thread.VolatileRead and VolatileWrite methods to use a byref in a volatile manner.  Unfortunately they are far more costly than ordinary volatile loads and stores.)

There is one particularly annoying case in which this warning is complete noise: when passing a byref to an API that internally performs volatile (or stronger) loads and stores.  I.e., the Interlocked.*, Thread.VolatileRead, and VolatileWrite methods.  Because these APIs internally use explicit memory barriers and atomic hardware instructions, the byref will effectively be treated as volatile regardless of whether it was taken from a volatile field or not.  And therefore it is safe.

For instance, the compiler will warn you about the following code

volatile int x;

static void f() {
    Interlocked.Exchange(ref x, 1);
}

even though there is no problem.  You can suppress the warning with a "#pragma warning disable" just before the call

volatile int x;

static void f() {
#pragma warning disable 0420
    Interlocked.Exchange(ref x, 1);
#pragma warning restore 0420
}

and then restore it immediately afterwards.  (It's a good idea to restore the warning so that you catch other possibly-problematic instances from being missed.)

This comes up a whole lot.  Why?  Because many times you'll mark a field volatile, even though it is updated exclusively with CAS operations, because it's also used in other contexts: e.g., sequences where loads mustn't reorder or erroneously be considered loop invariant.  I personally have a habit of always marking these variables as such, mostly as a carryover from Win32 whose InterlockedXX family of APIs demand volatile pointers (i.e., volatile * LONG).

I'm told that this annoying case might be fixed in the next C# compiler, by the way.  Until then, I figured I'd throw this up for reference purposes.

Reader/writer locks are commonly used when significantly more time is spent reading shared state than writing it (as is often the case), with the aim of improving scalability.  The theoretical scalability wins come because the lock can be acquired in a special read-mode, which permits multiple readers to enter at once.  A write-mode is also available which offers typical mutual exclusion with respect to all readers and writers.  The idea is simple: if many readers can read simultaneously, the theory goes, concurrency improves.

(I’ll be posting an analysis of reader/writer lock scalability in an upcoming post.  For a variety of reasons--most related to my recent CAS post--they seldom make a dramatic impact in practice.)

In addition to showing up in libraries--such as Vista’s new SRWLock, .NET’s ReaderWriterLock, and .NET 3.5’s ReaderWriterLockSlim--they are used pervasively in relational databases, distributed transactions, and software transactional memory.

Vance Morrison demonstrated a lightweight reader/writer lock on his blog a couple years back.  Although quite small, you can get smaller.  Much like the new SpinLock type being made available in .NET 4.0, we can build a ReaderWriterSpinLock that offers several advantages:

1. It’s a struct, and so there is no object allocation or space for an object header necessary.
2. It’s a single word in size (i.e., 4 bytes).
3. No kernel events are ever allocated; we will spin instead.

For cases in which reads are extraordinarily frequent, and writes are extraordinarily rare, this approach can actually be useful.  Unfortunately, because one common case in which reader/writer locks scale very well is when hold times are lengthy, as will be shown in my upcoming post, even moderately common writes will result in chewing up a whole lot of wasted CPU time due to (3).  If there’s interest, I will look into implementing a variant of this type that uses events for waiting.  Clearly this would sacrifice (2).

Some design decisions have been made in the name of keeping this thing lightweight:

1. No thread affinity will be used.
2. And therefore no recursive acquires will be allowed.

The full code is below, at the bottom of this post.  But let’s review the details one-by-one.

First, all state is packed into a single field, m_state.  We’ll use the 32nd bit to represent whether the write lock is held, and we’ll use the 31st bit to represent whether a writer is attempting to acquire the lock.  As with most reader/writer locks, we will give writers priority over readers because they are supposed to be very infrequent.  In other words, once a writer arrives, no more read lock acquires will be permitted.  The remaining 30 bits will be used to store the reader count.  Some masks make this convenient:

private volatile int m_state;
private const int MASK_WRITER_BIT = unchecked((int)0x80000000);
private const int MASK_WRITER_WAITING_BIT = unchecked((int)0x40000000);
private const int MASK_WRITER_BITS = unchecked((int)(MASK_WRITER_BIT | MASK_WRITER_WAITING_BIT));
private const int MASK_READER_BITS = unchecked((int)~MASK_WRITER_BITS);

Now we can write the four methods: EnterWriteLock, ExitWriteLock, EnterReadLock, ExitReadLock.

Entering the write lock merely entails setting m_state to MASK_WRITER_BIT, provided that we see it available.  If it’s not available, we’ll just go ahead and try to set the MASK_WRITER_WAITING_BIT to prevent subsequent read locks from being acquired until we get in.  We then go ahead and spin until the lock is available using the new type SpinWait in .NET 4.0, checking the m_state field over and over again.  The lock is available if m_state is 0 or MASK_WRITER_WAITING_BIT:

public void EnterWriteLock()
{
    SpinWait sw = new SpinWait();
    do
    {
        // If there are no readers currently, grab the write lock.
        int state = m_state;
        if ((state == 0 || state == MASK_WRITER_WAITING_BIT) &&
             Interlocked.CompareExchange(ref m_state, MASK_WRITER_BIT, state) == state)
           return;

        // Otherwise, if the writer waiting bit is unset, set it.  We don't
        // care if we fail -- we'll have to try again the next time around.
        if ((state & MASK_WRITER_WAITING_BIT) == 0)
            Interlocked.CompareExchange(ref m_state, state | MASK_WRITER_WAITING_BIT, state);

        sw.SpinOnce();
    }
    while (true);
}

Leaving the write lock is actually quite simple.  We just set the m_state field to 0, preserving the MASK_WRITER_WAITING_BIT just in case another writer has arrived since we acquired the lock.  We use an Interlocked.Exchange (XCHG) operation for this, although we technically could have just done an ordinary write, provided doing so wouldn’t cause memory model or availability problems:

public void ExitWriteLock()
{
    // Exiting the write lock is simple: just set the state to 0.  We
    // try to keep the writer waiting bit to prevent readers from getting
    // in -- but don't want to resort to a CAS, so we may lose one.
    Interlocked.Exchange(ref m_state, 0 | (m_state & MASK_WRITER_WAITING_BIT));
}

Entering the read lock is even more straightforward.  The lock is available for readers when m_state & MASK_WRITER_BITS is 0.  In other words, no writer holds the lock and no writer is waiting for the lock.  Once we see the lock in such a state, we merely try to add one to the state value and CAS it in.  In this way, m_state & MASK_READER_BITS will be equal to the number of concurrent readers in the lock:

public void EnterReadLock()
{
    SpinWait sw = new SpinWait();
    do
    {
        int state = m_state;
        if ((state & MASK_WRITER_BITS) == 0)
        {
            if (Interlocked.CompareExchange(ref m_state, state + 1, state) == state)
                return;
        }

        sw.SpinOnce();
    }
    while (true);
}

Lastly, exiting the read lock is the most complicated operation of all.  It needs to decrement the reader count, while at the same time preserving the MASK_WRITER_WAITING_BIT:

public void ExitReadLock()
{
    SpinWait sw = new SpinWait();
    do
    {
        // Validate we hold a read lock.
        int state = m_state;
        if ((state & MASK_READER_BITS) == 0)
            throw new Exception("Cannot exit read lock when there are no readers");

        // Try to exit the read lock, preserving the writer waiting bit (if any).
        if (Interlocked.CompareExchange(
                ref m_state, ((state & MASK_READER_BITS) - 1) | (state & MASK_WRITER_WAITING_BIT), state) == state)
            return;

        sw.SpinOnce();
    }
    while (true);
}

And that’s it.

Here are some single-threaded performance numbers, comparing the relative costs of several locks out there.  These are taken from a large number of acquire/release pairs, i.e., ‘for (int i = 0; i < N; i++) { lock.Enter(); lock.Exit(); }’, for a very large value of N:

Monitor                         0004487479
RWL read lock (legacy)          0023042785      5.13491x
RWL write lock (legacy)         0023118085      5.15169x
SlimRWL read lock (3.5)         0009423579      2.099976x
SlimRWL write lock (3.5)        0008680855      1.934465x
Vance read lock                 0004923609      1.097193x
Vance write lock                0004802136      1.070123x
SpinRWL read lock               0004298525      0.9579604x
SpinRWL write lock              0003819024      0.8510431x

The Nx ratios compare the lock in question to Monitor as our baseline.  Smaller is better.  As you can see, we seem to be on pretty solid ground to start with.  But clearly the most interesting part of this whole thing is the scaling numbers--in particular whether read-mode helps with throughput--both for the existing reader/writer locks and our new one.  The results may surprise you.  That’s coming in the next post...

(Here is the full listing.)

using System;

// We use plenty of interlocked operations on volatile fields below.  Safe.
#pragma warning disable 0420

namespace System.Threading
{
    /// <summary>
    /// A very lightweight reader/writer lock.  It uses a single word of memory, and
    /// only spins when contention arises (no events are necessary).
    /// </summary>
    public struct ReaderWriterSpinLock
    {
        private volatile int m_state;
        private const int MASK_WRITER_BIT = unchecked((int)0x80000000);
        private const int MASK_WRITER_WAITING_BIT = unchecked((int)0x40000000);
        private const int MASK_WRITER_BITS = unchecked((int)(MASK_WRITER_BIT | MASK_WRITER_WAITING_BIT));
        private const int MASK_READER_BITS = unchecked((int)~MASK_WRITER_BITS);

        public void EnterWriteLock()
        {
            SpinWait sw = new SpinWait();
            do
            {
                // If there are no readers currently, grab the write lock.
                int state = m_state;
                if ((state == 0 || state == MASK_WRITER_WAITING_BIT) &&
                    Interlocked.CompareExchange(ref m_state, MASK_WRITER_BIT, state) == state)
                    return;

                // Otherwise, if the writer waiting bit is unset, set it.  We don't
                // care if we fail -- we'll have to try again the next time around.
                if ((state & MASK_WRITER_WAITING_BIT) == 0)
                    Interlocked.CompareExchange(ref m_state, state | MASK_WRITER_WAITING_BIT, state);

                sw.SpinOnce();
            }
            while (true);
        }

        public void ExitWriteLock()
        {
            // Exiting the write lock is simple: just set the state to 0.  We
            // try to keep the writer waiting bit to prevent readers from getting
            // in -- but don't want to resort to a CAS, so we may lose one.
            Interlocked.Exchange(ref m_state, 0 | (m_state & MASK_WRITER_WAITING_BIT));
        }

        public void EnterReadLock()
        {
            SpinWait sw = new SpinWait();
            do
            {
                int state = m_state;
                if ((state & MASK_WRITER_BITS) == 0)
                {
                    if (Interlocked.CompareExchange(ref m_state, state + 1, state) == state)
                        return;
                }

                sw.SpinOnce();
            }
            while (true);
        }

        public void ExitReadLock()
        {
            SpinWait sw = new SpinWait();
            do
            {
                // Validate we hold a read lock.
                int state = m_state;
                if ((state & MASK_READER_BITS) == 0)
                    throw new Exception("Cannot exit read lock when there are no readers");

                // Try to exit the read lock, preserving the writer waiting bit (if any).
                if (Interlocked.CompareExchange(
                    ref m_state, ((state & MASK_READER_BITS) - 1) | (state & MASK_WRITER_WAITING_BIT), state) == state)
                    return;

                sw.SpinOnce();
            }
            while (true);
        }
    }
}

I just uploaded a free sample chapter for my Concurrent Programming on Windows book:

2
Synchronization and Time

STATE IS AN important part of any computer system. This point seems so obvious that it sounds silly to say it explicitly. But state within even a single computer program is seldom a simple thing, and, in fact, is often scattered throughout the program, involving complex interrelationships and different components responsible for managing state transitions, persistence, and so on. Some of this state may reside inside a process’s memory—whether that means memory allocated dynamically in the heap (e.g., objects) or on thread stacks—as well as files on-disk, data stored remotely in database systems, spread across one or more remote systems accessed over a network, and so on. The relationships between related parts may be protected by transactions, handcrafted semitransactional systems, or nothing at all.

The broad problems associated with state management, such as keeping all sources of state in-synch, and architecting consistency and recoverability plans all grow in complexity as the system itself grows and are all traditionally very tricky problems. If one part of the system fails, either state must have been protected so as to avoid corruption entirely (which is generally not possible) or some means of recovering from a known safe point must be put into place.

While state management is primarily outside of the scope of this book, state “in-the-small” is fundamental to building concurrent programs. Most Windows systems are built with a strong dependency on shared memory due to the way in which many threads inside a process share access to the same virtual memory address space. The introduction of concurrent access to such state introduces some tough challenges. With concurrency, many parts of the program may simultaneously try to read or write to the same shared memory locations, which, if left uncontrolled, will quickly wreak havoc. This is due to a fundamental concurrency problem called a data race or often just race condition. Because such things manifest only during certain interactions between concurrent parts of the system, it’s all too easy to be given a false sense of security—that the possibility of havoc does not exist.

In this chapter, we’ll take a look at state and synchronization at a fairly high level. We’ll review the three general approaches to managing state in a concurrent system:

1. Isolation, ensuring each concurrent part of the system has its own copy of state.
2. Immutability, meaning that shared state is read-only and never modified, and
3. Synchronization, which ensures multiple concurrent parts that wish to access the same shared state simultaneously cooperate to do so in a safe way.

We won’t explore the real mechanisms offered by Windows and the .NET Framework yet. The aim is to understand the fundamental principles first, leaving many important details for subsequent chapters, though pseudo-code will be used often for illustration.

We also will look at the relationship between state, control flow, and the impact on coordination among concurrent threads in this chapter. This brings about a different kind of synchronization that helps to coordinate state dependencies between threads. This usually requires some form of waiting and notification. We use the term control synchronization to differentiate this from the kind of synchronization described above, which we will term data synchronization.

Read more here...

Related, I was recently interviewed by DZone about the book.  You can read my responses here.  Enjoy.