Via DBox and TBray, I stumbled upon Will Continuations Continue?, a great essay about why continuation support in modern VMs is not a good idea after all:

"By far he most compelling use case for continuations are continuation-based web servers. ... Rather than relying on the server’s stack to keep track of what location we’re looking at, the [UI] will be a view on a model ... When you pressed “Buy”, it would pass all the information necessary to complete the transaction onto the server. Consequently, we’ll have no more of a pressing need for continuations than traditional applications have today."

I couldn't agree more, although I arrive at the conclusion via a different line of thought.

Just over a year ago now, I was working on continuations for my Scheme interpreter and compiler, Sencha. I managed to create something that "worked" -- in the sense that the stack could be captured, passed around, and restored; and it even still reported locals as roots to the GC -- but there are so many facets of a modern runtime to consider that true product support would be a massive undertaking. I thought continuations were a good idea. Why? To be honest, the main reason was my simple goal of having a full-fidelity Scheme runtime. But I also admired their power.

In retrospect, I now realize something important: the stack is evil. It's a horrible representation of state, especially for web applications.

The stack is unnecessarily bound to an OS thread, and munges control flow with the "state" of the program. The fact that return addresses for function calls lives on it has been the source of many security problems and counter-measures (/GS). When a thread blocks, the entire stack is wasted, even if there is logical work on it that could progress if it weren't for the arbitrary physical association. There's so much crap on it that to summarize the state of your entire program often requires pausing threads and walking their stacks. How dirty and impolite! Freak-of-nature abominations have twisted what the stack was meant for, e.g. COM and GUI reentrancy and APCs, completely disassociating logical and physical representations. You have to reserve a contiguous chunk of the thing per thread (often 1MB), wasting virtual memory space, because Windows doesn't support linked stack regions (not as big a deal on 64-bit as on 32-bit, sure), which also leads to the CLR ripping the process if you ever exceed it (overflow).

So many problems we encounter with parallel programming (among other domains) would go away with a more structured representation of the program as a state machine.

Dharma and the rest of the WF team are delivering just that (in the large). C# 2.0's iterator feature supplies a similar capability (in the small). The Concurrency and Coordination Runtime (CCR) eschews stack in favor of orchestration and message passing. We'll converge at some point. And it won't be around serializing stacks, it will be around getting rid of the damned things.

It's been a while since I last posted a "recent reads" list.

Show-Stopper! The Breakneck Race to Create Windows NT and the Next Generation at Microsoft -- G. Pascal Zachary

10 of 10. I read this book in nearly one sitting. I couldn't put it down. This book details the story of the conception, design, and implementation of the Windows NT OS. It's a great "from the trenches" report of what it must have been like to work on the project, and stars many familiar faces, not the least of which is Dave Cutler. Some DevDiv familiar show up, such as David Treadwell (was dev on WinSock, now VP for the .NET Framework) and S. Somasegar (was tester, now VP for DevDiv), among many Windows core architects who are still at the company today. It's out of print, but I found a like-new copy for a few bucks (yaay).

The Calculi of Lambda Conversion (AM-6, Annals of Mathematics Studies) -- Alonzo Church

10 of 10. λ! Who am I to rate such a classic book? This is the seminal work for all modern functional languages (LISP is modern, yes?). I had to read it twice... carefully... to follow everything. (Perhaps I'm slow?) But it's only 77 pages. The text covers α conversion, β reduction, and η conversion, in addition to normal and head normal forms. And the best part of all? It's very concise, not very wordy, and follows a nice, natural progression.

Chances Are...: Adventures in Probability -- Michael Kaplan, Ellen Kaplan

8 of 10. This book is fun. It's a bit lighter on the math than I'd prefer, but nevertheless offers a great historical insight into the evolution of probability. It begins in the 1600s, and details its origins in mathematics and science, and -- surprise! -- its practical use as a tool for gamblers. Eventually it discusses impacts to more interesting parts of society, such as the development of an insurance industry, evaluation of new drugs, and combat and war. A welcome break from my typical computer nerd books.

Dr. Euler's Fabulous Formula: Cures Many Mathematical Ills -- Paul J. Nahin

8 of 10. Ahhh, a book after my heart. A quote from the opening says it all: I used to think math was no fun 'Cause I couldn't see how it was done Now Euler's my hero For I now see why zero Equals eπi + 1 The book details the historical development and importance of Euler's formula. Throughout, there is quite a bit of description-by-example by way of complex number mathematics, in addition to great historical accounts.

Why Most Things Fail: Evolution, Extinction, and Economics -- Paul Ormerod

7 of 10. First, let me admit: I was a little disappointed by the broad title and relative narrow focus of the text. While some correlation is drawn between evolution, extinction, and economics, most of the book is spent describing why uncertainty in business--and the aparrent disregard for such uncertainty in commonplace naive business theory--leads to failure. He also uses examples from game theory on other related topics to draw such conclusions. The book should have been much longer, as I found myself at the end wondering, did I miss some big pieces? With that said, much of it is unique content backed by real research, so I'm sure developing the ideas took quite a bit of time.

The New Turing Omnibus: Sixty-Six Excursions in Computer Science -- A. K. Dewdney

6 of 10. I don't think I learned a whole lot from this particular book, but it was at least entertaining to read. I brought it along with me on a trip, and liked the format: Short, concise, often under 5-page essays on some topic in computer science. While I was traveling, this enabled me to pick it up and read an entire essay when I had only a brief period of time. The topics do range quite dramatically, and the content is a little "dumbed down," but it is a great coffee table addition.

The Devil's Cup: A History of the World According to Coffee -- Stewart Lee Allen

8 of 10. OK, this is definitely the odd book out. But I read it in about a day and a half, last weekend, and couldn't put it down. The book really isn't as much about coffee as it is about the author's crazy travels from Africa to Yemen to Europe and back to the US, in search of the "local brews." Quite a bit of historical insight is given, and it's a fun ride. I enjoyed it, and it was a much needed break from the techno babble and funny symbols. :)

The use of parallel spreadsheet calculations in Excel 12 is a great example of how software vendors can use multi-core CPUs to vastly improve the user experience.

There is some great stuff here: Intelligent parallel execution based on dependency analysis; near-linear speedup for spreadsheets with minimal dependencies; an extension model, where user-defined functions can be written either thread-safe or thread-unsafe, and be treated accordingly by the engine; user-defined thread-counts for functions that perform blocking operations; among others.

One of the challenges when designing reusable software that employs hidden parallelism -- such as a BCL API that parallelizes sorts, for-all style data parallel loops, and so forth -- is deciding, without a whole lot of context, whether to run in parallel or not. A leaf level function call running on a heavily loaded ASP.NET server, for example, probably should not suddenly take over all 16 already-busy CPUs to search an array of 1,000 elements. But if there's 16 idle CPUs and one request to process, doing so could reduce the response latency and make for a happier user. Especially for a search of an array of 1,000,000+ elements, for example. In most cases, before such a function "goes parallel," it has to ask: Is it worth it?

Answering this question is surprisingly tough. Running parallel at a high level might be more profitable, such as enabling multiple incoming ASP.NET requests to be processed, but often fine-grained parallelism can lead to better results. And just as often, a combination of the two works best. Consider an extreme case: Imagine that most ASP.NET web requests for a particular site ultimately acquire a mutual exclusive lock on a resource, essentially serializing a portion of all web requests. Of course, this is a design that's going to kill scalability eventually. But regardless, it could be present to a lesser degree, and might actually be an architectural requirement of the system. Executing some finer-grained operations in parallel might lead to better throughput in this case, especially those performed while the lock is held.

And clearly, the act of parallelizing an algorithm is not just based on the static properties of the system itself, but also dynamic capabilities and utilization of the machine. There are some APIs that allow dynamic querying of the machine state, which can aid in this process, e.g.:

• System.Environment.ProcessorCount: This property (new in 2.0) tells you how many hardware threads are on the system. Note that the number includes hyper-threads on Intel architectures, which really shouldn't be counted as a full parallel unit when deciding whether to parallelize your code. GetSystemInfo can give you richer information, albeit with some P/Invoke nonsense. We should give a better interface into this data for the next version of the Framework.
• Processor:% Processor Time performance counter: This gives you the % utilization of a specific processor and allows asynchronous querying. Using it, you could query each processor on the system to figure out what the overall system utilization is, and specifically how many sub-parts to break your problem into. The CLR thread-pool uses this today to decide when to inject or retire threads. You can use it too to determine whether introducing parallelism is a wise thing to do. Although your code may not have a lot of "context," this is often a good heuristic that even leaf level algorithms can use.
• System:Processor Queue Length performance counter: For more sophisticated situations, you can not only key off of the processor utilization, but also off the queue length of processes waiting to be scheduled. For a really deep queue (say, more than 2x the number of processors), introducing additional work is likely to lead to unnecessary waiting.

Using these are apt to lead to statistically good decisions. But clearly this is a heuristic, and as such the state of the system could change dramatically immediately after obtaining the values, perhaps making your deicision look naive and ill-conceived in retrospect. The worst case could be bad, but perhaps not terrible. The worst aspect of this is that performance characteristics could vary dramatically, and your users might respect predictable execution over sometimes-fast execution. The good news is that each of these functions are fairly cheap to call, amounting to less than 0.5ms total in some quick-and-dirty tests I wrote that read from all three.

But spending any time answering the question is tricky business. Assuming the software dynamically executes some code to decide if, and to what degree, we should run in parallel, and assuming these calculations are not done in parallel themselves ;), all of this work amounts to a fixed overhead on some part of the overall system, reducing overall parallel speedup (due to Amdahl's Law). We hope that in the future we can hide a lot of this messy work in the guts of the runtime and WinFX stack, but for now it's mostly up to you to decide.

Databases have utilized parallelism for a long time now to effectively scale-up and scale-out with continuously improving chip and cluster technologies. Consider a few high-level examples:

Parallel query execution is employed by all sophisticated modern databases, including SQL Server and Oracle. This comes in two flavors: (1) execution of multiple queries simultaneously which potentially access intersecting resources, and (2) implicit parallelization of individual queries, to acheive speed-ups even when a large quantity of incoming work is not present (e.g. high-cost queries, lots of data, etc.). Often a combination of both is used dynamically in a production system. I won't say much more, other than to refer to an interesting new query technology on the horizon.

Transactions are used as a simple model for concurrency control, enabling high scalability due to dynamic fine-grained locking techniques and policies, while supplying conveniences such as intelligent contention management and deadlock detection. And of course reliability is improved, because of the all-or-nothing semantics of transactions. Even in the face of asynchronous thread aborts, a transaction can ensure inconsistent state isn't left behind to corrupt a process, greatly improving the reliability of software at a surprisingly low cost. Software transactional memory (STM) borrows directly from the field, and applies it to general purpose parallel programming.

Invariants about data in databases are often modeled as integrity checks and foreign key constraints, which help to maintain reliable and consistent execution even in the face of concurrency. This, coupled with transactions, helps to ensure invariants aren't broken at transaction boundaries, and recent work done by MSR explores how this might be applied to general programming. STM combined with a rich system like Spec# could facilitate highly reliable and consistent systems that don't expose latent race conditions in the face of parallel execution.

Assuming you have (1) a lot of data to process, (2) complex computations to perform, and/or (3) simply a lot of individual tasks to accomodate, this model of parallel programming stretches quite far. With many cores per CPU, TB disks, and 100+-GB memories on desktops just around the corner; an order of magnitude more network bandwith available to consumers; and a continuing explosion of the amount of information humans generate and have to make some sense of, similar approaches could enable the next era of computer applications. I will also observe that surprisingly similar models of computation are precisely what fuel technologies like Google's MapReduce, albeit at a coarser granularity.

Raymond's recent post talks about queueing user-mode APCs in Win32.

When you block in managed code, the CLR is responsible for figuring out the correct style of wait. This ends up in a CoWaitForMultipleHandles (on Win2k+) or MsgWaitForMultipleObjectsEx if you're executing in an STA; else, this ends up in a non-pumping wait, such as WaitForSingleObjectEx/WaitForMultipleObjectsEx. In any case, the wait is alertable, meaning that user-mode APCs will have a chance to run. There are various blocking calls hidden in Win32 and the CLR itself, so it's not guaranteed that all waits are alertable; but any that originate from managed code are, which we hope is a significant percentage.

This code illustrates a simple user-mode APC reentering as we do an alertable wait (via Thread.CurrentThread.Join(0)):

using System;
using System.Runtime.InteropServices;
using System.Threading;

static class Program {

    static void Main() {
        QueueUserAPC(
            delegate { Console.WriteLine("APC fired"); },
            GetCurrentThread(),
            UIntPtr.Zero);

        Console.WriteLine("Doing join");
        Thread.CurrentThread.Join(0);
        Console.WriteLine("Finishing join");
    }

    delegate void APCProc(UIntPtr dwParam);

    [DllImport("kernel32.dll")]
    static extern uint QueueUserAPC(APCProc pfnAPC,
        IntPtr hThread, UIntPtr dwData);

    [DllImport("kernel32.dll")]
    static extern IntPtr GetCurrentThread();

}

While this technique seems like an effective way to reuse a thread while it is blocked -- for example, you might contemplate doing this for thread-pool threads -- a little problem called thread affinity tends to arise. I wrote about this in terms of COM reentrancy before. An APC reentering doesn't perform a context transition, so even if we used a logical context to store such state, the problem would still exist. The simple fact is that user-mode APCs are good for system bookkeeping, but not for running general purpose code that modifies arbitrary program state.

I don't know what's publicly available about our future ship schedules. But regardless, we begin M1 -- our first real coding milestone for the next version of the CLR -- on Monday. There's been some work going on in the meantime, of course, limited mostly to prototyping, design, and prioritization, but it's finally time to get serious, write real product code, and start hitting dates.

One fairly large item on our schedule is revamping our thread-pool. Our primary aim there is to enable fine-grained parallelism, and to supply new scheduling features that many people have asked for in the past. Today, coarse-grained parallelism is more attractive due to the costs associated with scheduling and dispatching work items, but we are going to change that.

This includes these tentative high level items:

• Low performance overhead of queueing and dispatching work
• Deadlock avoidance (surging) due to 100% blocking
• Queue partitioning and isolation
• Prioritization of work items
• Cancellation of work items, possibly with support for Vista IO Cancellation
• NUMA awareness such as CPU affinitization and/or user-hinted node affinitization
• And, of course, enhanced debugging and diagnostics

We'd love any feedback on any of these, including which sound more or less important to you. And if you have an interesting problem or scenario we might not have considered, please, please, please let me know.

A colleague of mine recently referred me to the Cilk work at MIT. This paper supplies a good overview. We've been slowly arriving at a similar design, so it's great to have prior art from which to draw. The idea most important with respect to the thread-pool is how multiple queues can be backed by a single physical thread store, and further the way in which queues are dynamically load balanced via thread leases and work stealing.

By now you’ve probably read things like Herb Sutter’s free lunch paper. And if you follow my blog at all, you’ll know that I do a bit of writing and thinking about how Microsoft can make our platform better suited for the multi-core era that stands in front of us.

Most people, when considering the topic of parallelism vis-à-vis multi-core, start by jumping straight to the bottom of the stack. I’ll admit that I sure did. They think about threads, locks, and the associated headaches. Some even think about the chip architecture and memory hierarchy. They take it for granted that the work exists. But these same people seldom stop to think—or when they do think often hit the same wall—about what workloads will actually substantially benefit from massive amounts of parallelism. This is a difficult topic.

Scientific computing of course has this nailed pretty good already. But how much of the code do you write that actually resembles scientific problems, like n-bodies, heat transfer, fluid dynamics, and the like? My guess is that, for most of Microsoft’s customers, the answer is: Not much. That’s especially true on the client, where data-intensive operations are often shipped to a high-end server for processing, leaving what amounts to quasi-workflow orchestration initiated by UI events, for example. I’m not going to refute the massive gains in CPU scalability we’ve seen over the past 10 years due to superscalar execution, via techniques like pipelining and branch prediction, and the effect that has had on client and server programs alike. But for most application code today, the network and disk are the limiting factors, not the CPU.

Of course, to the extent that there is work the CPU must perform for any problem—even for IO-bound ones—code needs to be architected to separate logical tasks, ensuring that a bunch of otherwise ready-to-run work doesn’t get backed up behind a blocking call unnecessarily. And of course, separating logical work is important for other reasons, like avoiding a hung UI thread. Unfortunately, we don’t make this overly easy today. Win32 and WinFX APIs (nor the associated documentation or tool support) are not overly helpful when it comes to figuring out the performance characteristics of the code they invoke, including latency and blocking. This makes it tricky to architect things as I suggest. New programming models like the CCR provide the infrastructure that could facilitate such a shift, but it will take hard work to get to a reasonable place.

Back to workloads. Consider server applications for a moment. The model of concurrency there is actually quite simple. And in fact I believe the majority of server programs will be equipped to exploit multi-core right away. Each incoming request is considered a logical task and is assigned to an available thread of work, often using the CLR’s thread-pool. Sharing between concurrent requests is (hopefully) minimal, meaning that the one-thread-per-request model leads to naturally good scaling. This works up to a point. Once the average number of available CPUs surpasses the average number of incoming workers, the need to assign multiple CPUs to a single request becomes more important. This is obviously very workload dependent. Databases already do this with individual queries. Their use a single-thread-per-request model, but often use individual query parallelization to get better utilization. SQL Server added support for this in 7.0. I’ve been working quite a bit over the past year on similar techniques for LINQ. I’m almost to the point where I can disclose more information publicly, in the form of a paper.

Search is clearly a workload of recent importance that, whether on the client or server, benefits tremendously from parallel execution. This applies not only to the act of searching, but also to the act of indexing the data in preparation for search. MSN and Google’s current desktop search products are cognizant not to interrupt your primary work by doing indexing while your computer is idle. But given a bunch more cores, they needn’t wait. Further, parallelizing search is a well researched topic. You still need to solve some tough problems like ensuring parallel tasks aren’t contending heavily for the disk (becoming IO bound), but it’s very possible.

There are of course other workloads. Graphics processing on modern computers is extremely parallel, currently handled by the GPU. But I am going to wrap up, and summarize all of this by saying: It remains to be seen whether most mainstream Windows programs can become highly parallel, and if they can, how profitable it will be. We'll also find out over time whether reaching that stage will require radically new programming models and a gradual shift over time. I am optimistic, and confident that parallel execution is the direction we ultimately need to go down. Surely the workloads are there, seemingly obscured by the traditional sequential approach to software.

I'm writing an article for an upcoming MSDN Magazine CLR Inside Out column. And I am looking for topic suggestions.

Of course, my expertise is around concurrency, but I'm also a CLR internals-kinda geek. So, what do you want to read about?

I have some ideas. But I'll post them after I hear yours.

I wrote about torn reads previously, in which, because loads from and stores to > 32-bit data types are not actually "atomic" on a 32-bit CPU, obscure magic values are seen in the program from time to time. This isn't as scary as "out of thin air" values, but can be troublesome nonetheless. I noted that, by using a lock, you can serialize access to the location to ensure safety.

You can of course write such thread-safe code that avoids taking a lock, usually motivated by performance. Vance has a pretty detailed write-up of this on MSDN. Most of the time, you shouldn't try to be so clever, as it will get you in trouble sooner or later, and is even worse to debug than a typical race. But for really hot code-paths, it can make a measurable difference. (Note the key word: measurable. If you've measured a problem, you might consider such techniques... but otherwise, stay far, far away. (Have I made enough qualifications and disclaimers yet?))

If you access individual pointer-sized byte segments of the data structure, such as 32-bit aligned segments (e.g. volatile or __declspec(align(x)) in VC++, all values on the CLR), you can load and store in a known order. Furthermore, you need to use the appropriate types of loads and stores with fences in the appropriate places; load/acquire and store/release are usually adequate. You can then use the intrinsic properties of this order to make statements about the correctness of your algorithm.

For example, imagine you have some code that increments a 64-bit counter on a 32-bit system. Aside from overflow, the value always increases. If you always increment the low 32-bits, followed by the high, and if you always read the high, followed by the low, you'll be guaranteed that, should you read a torn value, it will be too low rather than too high (not counting for overflow, of course). Sometimes it can be really low, such as when the low 32-bits wrap back to 0, in which case the higher 32-bit increment needs to carry one. Depending on your situation, this might be precisely what you are looking for. (I wrote some code last week that needed exactly this.)

For example, your typical code might read and write under a lock, in VC++/Win32:

ULONGLONG ReadCounter_Lock(
    volatile ULONGLONG * pTarget, CRITICAL_SECTION * pCs)
{
    ULONGLONG val;

    EnterCriticalSection(pCs);
    val = *pTarget;
    LeaveCriticalSection(pCs);

    return val;
}

ULONGLONG IncrCounter_Lock(
    volatile ULONGLONG * pTarget, CRITICAL_SECTION * pCs)
{
    ULONGLONG val;

    EnterCriticalSection(pCs);
    val = *pTarget;
    *pTarget = val + 1;
    LeaveCriticalSection(pCs);

    return val;
}

But, using the load/store order described above, it can become lock free:

#define LO_LONG(x) (reinterpret_cast<volatile LONG *>((x)))
#define HI_LONG(x) (reinterpret_cast<volatile LONG *>((x)) + 1)

ULONGLONG ReadCounter_NoLock(volatile ULONGLONG * pTarget)
{
    ULONGLONG val;

#ifdef _Win64

    val = *pTarget;

#else

    // Read high 32-bits first, then low:
    *HI_LONG(&val) = *HI_LONG(pTarget);
    *LO_LONG(&val) = *LO_LONG(pTarget);

#endif

    return val;
}

ULONGLONG IncrCounter_NoLock(
    volatile ULONGLONG * pTarget)
{
    ULONGLONG oldVal;

#ifdef _Win64

    oldVal = static_cast<LONGLONG>(
        InterlockedIncrement64(static_cast<LONGLONG *>(pTarget)));

#else

    // Increment the low 32-bits first, then high:
    if ((*LO_LONG(&oldVal) =
        InterlockedIncrement(LO_LONG(pTarget))) == 0)
    {
        *HI_LONG(&oldVal) = InterlockedIncrement(HI_LONG(pTarget));
    }
    else
    {
        *HI_LONG(&oldVal) = *HI_LONG(pTarget);
    }

#endif

    return oldVal;
}

It's obvious which is simpler to code, understand, and maintain. But the latter technique can come in handy when you're in a pinch.

For information on other similar techniques, including multi-word CAS and object-based STM, Tim Harris's recent "Concurrent programming with locks" paper is an excellent read. Most of it isn't built and ready for you to use today, but the details of the algorithms are in there if you'd like to play around a little. And there's a lot of literature out there about creating lock-free data structures. Interestingly, you can end up worse off than if you'd used a lock in the first place. Many such lock free algorithms are optimistic meaning that they do a bunch of work hoping not to run into contention; when they do, they have to throw away work, rinse, and repeat. Your mileage can vary dramatically based on workload.