Jim Johnson started a series back in January that I’m dying to see continued. It's about writing resource managers in System.Transactions, which surprisingly turns out to be incredibly straightforward. Provided you are able to implement the correct ACI[D] transactional qualities for the resource in question, that is. Juval Lowy’s December 2005 MSDN Magazine article on volatile resource managers described how to build what turns out to be essentially mini-transactional memory, without much of the syntax, implicit and transitive qualities, and robustness.

As an example of where you might use a resource manager, imagine that you wanted to ensure that any memory allocations and deallocations inside a transaction scope participate with the System.Transactions ambient transaction. Maybe you'd like your allocations to be in sync with the database server or web service to which you’re also transacting access. I’ll walk through an example of how straightforward writing such a resource manager can be.

First, our starting class is quite simple. It just allocates and frees memory. Sans transactions, it looks like this:

using System.Runtime.InteropServices;

public static class Mm {
    public static IntPtr Malloc(long bytes) {
        return Marshal.AllocHGlobal(new IntPtr(bytes));
    }
    public static void Free(IntPtr pp) {
        Marshal.FreeHGlobal(pp);
    }
}

Mm.Malloc returns a pointer to ‘bytes’ amount of memory via kernel32!GlobalAlloc (which turns out to be a crappy way to manage memory by the way, and is still alive only to support DDE, the clipboard, and OLE, or so I’m told; it works as an example though). Mm.Free takes a pointer to memory that was previously allocated via Mm.Malloc and frees it. Pretty simple.

OK, that’s not incredibly useful, especially considering that we’re just making single-line invocations to the Marshal class. But it’s a starting point.

Ultimately, what we want to ensure is that at the end of a transaction, any memory allocation and deallocation that happened within the transaction is consistent with the outcome of that transaction. That means, quite simply, that if memory was allocated and the transaction commits, we keep the memory allocated around; but if, on the other hand, the transaction rolls back, we must undo the allocation. Similarly, if we free memory and the transaction commits, then the memory remains freed; if it rolls back, we must undo the freeing.

If we want to build such a thing directly on top of existing facilities we clearly can’t do this precisely as I suggest. How do you undo a call to free in the CRT, for example? You can’t. Once you call free, the memory's gone, returned to the pool, and possibly used before your transaction even knows what to do with itself. But it turns out that we can "fake it" sufficiently close enough that most people can’t tell that we're faking it. Here’s what we do instead:

1. When somebody allocates memory, we log a compensating action in the transaction that frees the memory should we roll back. If the transaction commits, we do nothing more.
2. When somebody frees memory, we defer the call to commit time. If it never commit, we never free the memory.

This is fairly well known in database literature. Take a look at Jim Gray’s 1980 paper, A Transaction Model, where he describes REDO and UNDO actions, to see what I mean. (1980! That was ages ago.) What we’re saying basically is that allocation logs an UNDO action and freeing logs a REDO action. The isolation leaks out of this in some regard--evidence of our "faking it"--because the fact that our freed memory isn’t instantaneously available to other allocations might be noticed, especially under high stress conditions. OOMs may result that would have not otherwise happened, and the working set of the program may increase, especially for long running transactions. Cest la vie.

Anyhow… on to the implementation of these ideas. It’s surprisingly simple.

We will allow instances of our Mm class to be created by the implementation. From the viewpoint of a user, the class is still entirely static and cannot be constructed. These instances will become enlistments responsible for implementing transactional semantics and responding to certain event notifications from the System.Transactions machinery. To do so, the class must implement the System.Transactions interface IEnlistmentNotification:

using System;
using System.Collections.Generic;
using System.Runtime.InteropServices;
using System.Transactions;

public sealed class Mm : IEnlistmentNotification {

    /** Fields **/

    private LinkedList<IntPtr> m_freeOnCommit = new LinkedList<IntPtr>();
    private LinkedList<IntPtr> m_freeOnRollback = new LinkedList<IntPtr>();

    [ThreadStatic]
    private static Dictionary<Transaction, Mm> s_currentMm;

    /** Constructors **/

    private Mm() {}

    /** Methods **/

    public static IntPtr Malloc(long bytes) {
        …
    }

    public static void Free(IntPtr pp) {
        …
    }

}

We’ve added two linked lists to hold the deferred (m_freeOnCommit) and compensating actions (m_freeOnRollback). And we have a thread-static dictionary that maps the current transaction to the enlisted instance of Mm. This is pretty straightforward stuff, although there are a plethora of alternative designs. Now let’s see how we get data into these things. The Malloc and Free implementations will change slightly to check for an existing transaction:

public static IntPtr Malloc(long bytes) {
    IntPtr pp = Marshal.AllocHGlobal(new IntPtr(bytes));

    // If insufficient memory, OOM is thrown and we never log the free.
    Mm mm = GetCurrentMm();
    if (mm != null) {
        // Compensating activity to ensure that if we rollback, we free.
        mm.m_freeOnRollback.AddLast(pp);
    }

    return pp;
}

public static void Free(IntPtr pp) {
    Mm mm = GetCurrentMm();
    if (mm != null) {
        // We defer the freeing of memory in case we don't commit.
        mm.m_freeOnCommit.AddLast(pp);
    } else {
        Marshal.FreeHGlobal(pp);
    }
}

This implements the commit and rollback behavior I described above, i.e. we add the memory location to free on to the deferred or compensated list according to the rules we’ve already established. GetCurrentMm is responsible for lazily allocating and enlisting an instance of Mm. If there is no active ambient transaction, it just returns null:

private static Mm GetCurrentMm() {
    // Are we in a transaction?
    Transaction currTx = Transaction.Current;
    if (currTx == null) {
        // Return null to indicate we're not in a transaction.
        return null;
    }

    // Have we already allocated and enlisted a volatile RM for this transaction?
    Mm currMm = null;
    if (s_currentMm == null) {
        s_currentMm = new Dictionary<Transaction, Mm>();
    } else {
        s_currentMm.TryGetValue(currTx, out currMm);           
    }

    // No RM found, create/enlist one.
    if (currMm == null) {
        currMm = new Mm();
        s_currentMm.Add(currTx, currMm);
        currTx.EnlistVolatile(currMm, EnlistmentOptions.None);
    }

    return currMm;
}

And of course we have a RemoveCurrentMm which will be used eventually to remove the enlistment information from our dictionary:

private static void RemoveCurrentMm() {
    Transaction currTx = Transaction.Current;
    if (currTx != null && s_currentMm != null) {
        s_currentMm.Remove(currTx);
    }
}

So now we have all of the information about what should be freed and when, but there’s no code that actually executes the free operations. To do that, all we have to do is implement the IEnlistmentNotification interface properly, iterating the proper list, and invoking Malloc.FreeHGlobal on the contents. In other words, Commit and Rollback just invoke free on all of the memory addresses in the respective linked list:

void IEnlistmentNotification.Commit(Enlistment enlistment) {
    FreeAll(m_freeOnCommit);
    RemoveCurrentMm();
    enlistment.Done();
}

void IEnlistmentNotification.Rollback(Enlistment enlistment) {
    FreeAll(m_freeOnRollback);
    RemoveCurrentMm();
    enlistment.Done();
}

private void FreeAll(LinkedList<IntPtr> toFree) {
    foreach (IntPtr p in toFree) {
        Marshal.FreeHGlobal(p);
    }
}

We’re assuming in all of those cases that FreeAll and RemoveCurrentMm can’t fail. If our commit or rollback processing failed mid-way, that would put the entire process at risk: memory could be leaked or become corrupt. System.Transactions will respond to that by sending InDoubt notifications to all enlistments. Since the only way we can potentially contain and resolve volatile state corruption is to crash the process, that’s exactly what we do:

void IEnlistmentNotification.InDoubt(Enlistment enlistment) {
    Environment.FailFast("State protected by RM is in question");
}

This is a Byzantine response, sure, but it’s the only way we can guarantee that state doesn’t become corrupt when the transaction’s fate is InDoubt. If the fate of one or more resource managers cannot be determined, we don't know whether to commit or fail for sure. We could guess, of course, but guessing doesn’t lead to pleasant behavior in software, especially when we have to debug it. (And if you're making guesses, you'll probably have to spend more time debugging, so it's a double whammy of sorts.)

And that’s it! Now we can use memory operations inside of a transaction, and have it behave as expected. Just as an example, this test case ensures that writing to memory that was allocated in a transaction that eventually aborts causes an AccessViolation:

bool test1success = false;
IntPtr pMem1 = IntPtr.Zero;
try {
    try {
        using (TransactionScope txScope = new TransactionScope()) {
            pMem1 = Mm.Malloc(1024 * 1024); // get 1MB of space
            throw new Exception(); // cause an abort
        }
    } catch {
        // The txn was aborted, we expect reading from memory to fail.
        uint * pInt = (uint *)pMem1.ToPointer();
        *pInt = 0xdeadbeef;
    }
} catch (AccessViolationException) {
    test1success = true;
}
Console.WriteLine("Test 1 succeeded: {0} (rollback of malloc)", test1success);

There are three other tests that may be of interest in the source file for the Mm class and associated code: MallocFree.cs.

Of course this approach is not perfect in several areas. One that comes to mind immediately is the fact that we're doing a potentially expensive lookup for an ambient transaction on every memory allocation and deletion, which could be too much, especially if it happened in some general purpose allocation and deallocation routines. And of course automatically finding the transaction and using might also be a bad idea. We might instead want the user to opt-in to transactional Malloc and Free at the callsite, so that users aren't surprised when their malloc or free never happens (the transaction rolled back). Nevertheless, this article at least cracked the surface of a very difficult problem and surfaced some interesting issues.

Ntdll exports an undocumented function from WinNT.h:

PTEB NtCurrentTeb();

This gives you access to the current thread's TEB (thread environment block), which is a per-thread data structure that holds things like a pointer to the SEH exception chain, stack range, TLS, fiber information, and so forth. This function actually returns you a PTEB, which is defined as _TEB*. _TEB is an internal data structure defined in winternl.h, and consists of a bunch of byte arrays. You can cast this to PNT_TIB (defined as _NT_TIB*), which gives you access to the data in a strongly typed way. And _NT_TIB is a documented data structure, unlike _TEB, meaning you can actually rely on it not breaking between versions of Windows.

For example, this code prints out the current thread's stack base and limit. The base is the start of the user-mode stack, and the limit is the last committed page, which grows as you use more stack:

PNT_TIB pTib = reinterpret_cast<PNT_TIB>(NtCurrentTeb());
printf("Base = %p, Limit = %p\r\n",
    pTib->StackBase, pTib->StackLimit);

There's a shortcut you can take. You can always find a pointer to the TEB in the register FS:[18h]:

PNT_TIB pTib; 
_asm {
    mov eax,fs:[18h]
    mov pTib,eax
}
printf("Base = %p, Limit = %p\r\n",
    pTib->StackBase, pTib->StackLimit);

There's an even shorter shortcut you can take. You can actually find the base and limit in different segments of the FS register, FS:[04h] for the base and FS:[08h] for the limit:

void * pStackBase;
void * pStackLimit;
_asm {
    mov eax,fs:[04h]
    mov pStackBase,eax
    mov eax,fs:[08h]
    mov pStackLimit,eax
}
printf("Base = %p, Limit = %p\r\n",
    pStackBase, pStackLimit);

Unfortunately, the _asm keyword is not supported on all architectures, so the above code is only guaranteed to work on x86 (e.g. the VC++ Intel Itanium compiler doesn't support it). Furthermore, the hardcoded offsets 04h and 08h are clearly wrong on 64-bit: you need more than 4 bytes to represent a 64-bit pointer. NtCurrentTeb hides all of this and uses whatever platform-specific technique is needed to retrieve the information.

Matt Pietrek's 1996 and 1998 Microsoft Systems Jounral articles are the best reference I could find on TEBs, aside from the Windows Internals book.

Believe it or not, this is useful information. I wrote some code recently that took a different code path based on whether it was writing to the stack or the heap, and using the TEB does the trick.

I have written about 7 pages on user-mode stacks in my upcoming concurrency book. This ranges from CLR stack frames to stack overflow to just how stacks work internally in Windows. I haven't found any book or resource that collects all of this information together in one place. It turns out that most developers don't need to worry about stacks at all, but this understanding is crucial to moving forward to more advanced concurrency programming models.

After posting my last article on creating a lazy allocation IAsyncResult, I received a few mails on the ordering of the completion sequence. It was wrong and has been updated. Thanks to those who pointed this out.

I used the following incorrect ordering: 1) set IsCompleted to true, 2) invoke the callback, and 3) signal the handle.

This can lead to deadlocks if the callback waits on the handle. My implementation carefully avoided EndXxx-induced deadlocks (by checking IsCompleted before waiting on the handle), but if the callback directly WaitOne's on the IAsyncResult.AsyncWaitHandle property, the callback will of course deadlock. Directly accessing the handle might be attractive to the callback author, especially for higher level orchestration via WaitAny and WaitAll. So it's probably something we'd like to support. One way to avoid this is to invoke the callback asynchronously with BeginInvoke, but a better solution is to use the correct ordering instead.

The correct ordering is: 1) set IsCompleted to true, 2) signal the handle, and 3) invoke the callback.

The first version I wrote had the correct ordering, since that seemed to be the logical choice. Unfortunately, the Framework Design Guidelines lists the steps in the wrong order, which led me down that path. I've let Brad and Krzys about this. A customer who read my blog actually mailed Brad about this error too, just about simultaneously. There may be rationale behind this, but we've used the correct ordering in the file and network IO APIs since V1.0 so I think it's just wrong.

It's worth pointing out that the network classes already use a lazy allocation scheme very similar to the one I wrote about. Check out the System.Net.LazyAsyncResult internal type in System.dll. I'm advocating for moving file IO onto the same plan in the next release of the Framework. We'll see how it turns out.

Lastly, some might notice I originally said this would be a two part series. Well, I wrote a whole bunch of code to implement a sophisticated LRU-based resurrection caching scheme--to avoid allocating IAsyncResults every time--and then realized that my example doesn't do anything expensive on IAsyncResult creation that would warrant such a thing. The result? It was actually slower than the ordinary lazy version I posted a couple weeks back. I think the techniques I used are interesting nonetheless, so I am going to try and rework the example to incorporate some expensive buffer management, and then see where I stand. But I'm not promising anything just yet. And this was a great reminder that solving actual profiled problems is always more worthwhile than solving perceived, yet unmeasured, non-problems.

Lock free code is hard. But it can come in handy in a pinch.

There have been some recent internal discussions about the IAsyncResult pattern and performance. Namely that, for high throughput scenarios, where the cost of the asynchronous work is small relative to the cost of instantiating new objects, there is a considerable overhead to using the IAsyncResult pattern. This is due to two allocations necessary to implement the pattern: (1) the object that implements IAsyncResult itself, and (2) the WaitHandle for consumers of the API who must access the IAsyncResult.AsyncWaitHandle property. I will address (2) in this article, since it is much more expensive than (1).

Update: I've posted an addendum to this article here.

Rendezvousing

Just to recap, there are four broad ways to rendezvous with the IAsyncResult pattern:

1. You can poll the IAsyncResult.IsCompleted boolean flag. If it's true, the work has completed. If it's false, you can go off and do some interesting work, coming back to check it once in a while.
2. Supplying a delegate callback to the BeginXxx method. This callback is invoked when the work completes, passing the IAsyncResult as an argument to your callback.
3. Waiting on the IAsyncResult.AsyncWaitHandle. This is a Windows WaitHandle, typically a ManualResetEvent, which allows you to block for a while until the work completes.
4. Call the EndXxx method. Internally, this will often check IsCompleted and, if it's false, will wait on the AsyncWaitHandle.

Notice that in cases 1 and 2, the WaitHandle isn't even needed. And in case 4, it's only needed some fraction of the time. Well, it turns out we can avoid allocating it altogether for those cases where it's not used. We can "just" lazily allocate it. Note that for asynchronous IO, the majority of code will use method 2 above. For scalable servers, we often don't want to tie up an extra thread polling or waiting for completion, since that contradicts the primary benefits of Windows IO Completion Ports.

The Requirements

Notice I enclosed the word just above in quotes when mentioning lazy allocation. We could of course use a lock. But that would require that we allocate an object to lock against. We could of course just lock 'this', but that also comes with a performance overhead. We can get away with lock free code in this case, so long as we recognize a very important race condition that we must tolerate. Imagine this case: Thread A checks IsCompleted. It's false. So it accesses the AsyncWaitHandle property, triggering lazy allocation. Meanwhile, Thread B finishes the async work, and sets IsCompleted to true. We need to ensure a deadlock doesn't ensue.

This race could go one of two ways:

1. Thread A lazily allocates and publishes the WaitHandle before Thread B sets IsCompleted to true. Thread B must now witness a non-null WaitHandle when it checks, and it must return the WaitHandle in the signaled state. If it returns an unsigned WaitHandle, Thread A will wait on it, and never be woken up. This is a deadlock.
2. Thread B finishes first, setting IsCompleted to true, and seeing a null WaitHandle. Thread A must see IsCompleted as true and consequently return the event in a signaled state. Just like before, if this doesn't happen, Thread A will wait on an unsigned WaitHandle which will never be signaled. Deadlock.

To ensure both of these cases work, Thread A's read of the WaitHandle field and Thread B's read of IsCompleted must be preceded by a memory barrier. This ensures the memory accesses aren't reordered at the compiler or processor level, either of which could lead to the deadlock situations we are worried about. The CLR 2.0's memory model is not sufficient even with volatile loads, because the load acquire can still move "before" the store release.

An Implementation

Here is one simplistic implementation of a FastAsyncResult class, with ample comments embedded within to explain things:

class FastAsyncResult : IAsyncResult, IDisposable {

 

    // Fields

 

    private object m_state;

    private ManualResetEvent m_waitHandle;

    private bool m_isCompleted;

    private AsyncCallback m_callback;

    internal object m_internal;

 

    // Constructors

 

    internal FastAsyncResult(AsyncCallback callback, object state) {

       m_callback = callback;

       m_state = state;

    }

 

    // Properties

 

    public object AsyncState {

        get { return m_state; }

    }

 

    public WaitHandle AsyncWaitHandle {

        get { return LazyCreateWaitHandle(); }

    }

 

    public bool CompletedSynchronously {

        get { return false; }

    }

 

    public bool IsCompleted {

        get { return m_isCompleted; }

    }

 

    internal object InternalState {

        get { return m_internal; }

    }

 

    // Methods

 

    public void Dispose() {

        if (m_waitHandle != null) {

            m_waitHandle.Close();

        }

    }

 

    public void SetComplete() {

        // We set the boolean first.

        m_isCompleted = true;

 

        // And then, if the wait handle was created, we need to signal it. Note the

        // use of a memory barrier. This is required to ensure the read of m_waitHandle

        // never moves before the store of m_isCompleted; otherwise we might encounter a

        // race that leads us to not signal the handle, leading to a deadlock. We can't

        // just do a volatile read of m_waitHandle, because it is possible for an acquire

        // load to move before a store release.

        Thread.MemoryBarrier();

        if (m_waitHandle != null) {

            m_waitHandle.Set();

        }

 

        // If the callback is non-null, we invoke it.

        if (m_callback != null) {

            m_callback(this);

        }

    }

 

    private WaitHandle LazyCreateWaitHandle() {

        if (m_waitHandle != null) {

            return m_waitHandle;

        }

 

        ManualResetEvent newHandle = new ManualResetEvent(false);

        if (Interlocked.CompareExchange(ref m_waitHandle, newHandle, null) != null) {

            // We lost the race. Release the handle we created, it's garbage.

            newHandle.Close();

        }

 

        if (m_isCompleted) {

            // If the result has already completed, we must ensure we return the

            // handle in a signaled state. The read of m_isCompleted must never move

            // before the read of m_waitHandle earlier; the use of an interlocked

            // compare-exchange just above ensures that. And there's a race that could

            // lead to multiple threads setting the event; that's no problem.

            m_waitHandle.Set();

        }

 

        return m_waitHandle;

    }

 

}

Notice also that we tolerate the race where two threads try to lazily allocate the handle. Only one thread wins. The thread that loses is responsible for cleaning up after itself so that we don't "leak" a WaitHandle (requiring finalization to close it). This is an example of tolerating races instead of preventing them, and is similar to the design we use for jitting code in the runtime, for example.

Some Initial Results

I'll do a more thorough analysis as follow up to my next post, including profiling traces. But the initial results are promising.

I wrote a test harness that calculates the fibonacci series asynchronously, based on the sample code used in the Framework Design Guidelines book. As you can see by the comparisons, the larger the series being calculated, the less substantial the impact my performance work makes:

Size         Normal       Lazy         Improvement  
1            177 ms       62 ms        185%
2            179 ms       63 ms        184%
3            180 ms       65 ms        177%
4            181 ms       66 ms        174%
5            187 ms       69 ms        171%
6            195 ms       79 ms        147%
7            210 ms       97 ms        116%
8            239 ms       122 ms       96%
9            275 ms       165 ms       67%
10           356 ms       257 ms       39%
12           745 ms       631 ms       18%
15           3217 ms      3075 ms      05%

As we would expect, as the ratio of the cost of computation to the cost of allocating the WaitHandle increases (with an increased "size" of the fibonacci series being calculated), the observed performance improvement also decreases. For very small computations, however, this technique can really pay off. In the case of high performance asynchronous IO, for example, where completion often involves simply marshaling some bytes between buffers, this can be a key step in the process of improving system throughput.

As I noted earlier, lock free techniques are almost never worth the trouble unless you've measured a problem, especially due to the maintenance and testing costs for such code. And I jumped right over using a lock for allocation. It turns out in this particular scenario, that technique fares just as well as the lock free code, albeit with a lot more simplicity. It only incurs slight overhead when checking the handle to see if it has been allocated yet as well as when setting it at completion time. Since my test case never has to check the WaitHandle, it only has to enter the lock upon completion, which is relatively cheap. As always, start simple and then go from there.

C# 1.0 shipped with the ability to stack allocate data with the stackalloc keyword, much like C++'s alloca. There are restrictions, however, around what you can allocate on the stack: Inline arrays of primitive types or structs that themselves have fields of primitive types (or structs that etc...). That's it. C# 2.0 now allows you to embed similar inline arrays inside other value types, even for those that are allocated inside of a reference type on the heap, by using the fixed keyword.

And of course, you can allocate arrays of those value types on the stack too:

using System;

 

unsafe class Program {

    struct A {

        internal int x;

        internal fixed byte y[1024];

    }

 

    public static void Main() {

        byte * bb = stackalloc byte[2048];

        Console.WriteLine("&bb         : {0:X}", (uint)&bb);

        Console.WriteLine("&bb[1]      : {0:X}", (uint)&bb[1]);

        Console.WriteLine("&bb[2048]   : {0:X}", (uint)&bb[2048]);

 

        A * a = stackalloc A[2048];

        Console.WriteLine("&a          : {0:X}", (uint)&a);

        Console.WriteLine("&a->x       : {0:X}", (uint)&a->x);

        Console.WriteLine("&a->y[0]    : {0:X}", (uint)&a->y[0]);

        Console.WriteLine("&a->y[2048] : {0:X}", (uint)&a->y[2048]);

        Console.WriteLine("&a[1]       : {0:X}", (uint)&a[1]);

        Console.WriteLine("&a[2048]    : {0:X}", (uint)&a[2048]);

    }

}

The use of this is of course almost always limited to unmanaged interop scenarios. For example, there's at least one place in the BCL where we use this to stack allocate the binary layout of a security descriptor that we then pass into the Win32 CreateMutex API, which avoids having to create a new interop struct. (Whether such hacks are a good thing to put in our code-base is another topic altogether...)

The stack allocated data doesn't outlive the stack frame, so as soon as you return from the function in which the stackalloc occurs, the data is gone. If you pass a pointer to it and somebody stores it, they could later try to dereference a pointer into dead (and possibly since reused) stack space. And reading too far can lead to buffer over- or underflows which bash other data on the stack. Using this requires compilation with /unsafe, and needless to say, you need to be careful with it (if not avoid it altogether).

In managed code, you can pass ByRefs "down the stack." You can't do much aside from that, however, other than use things like ldind and stind on them. And of course, you can cast them to native pointers, store them elsewhere, and so on, but those sorts of (evil) things are unverifiable.

Right? Well, sort of.

In Whidbey, we made a change to the verification rules such that a function can now return a ByRef to a caller. This of course is safe so long as the ByRef doesn't refer to a stack location. A field ref inside a heap-allocated object, static field ref, or an array element ref are all just fine. And of course, a function can just return a ByRef that was passed to it as an argument. Take a look at this IL:

.assembly extern mscorlib {}
.assembly byrefret {}

.class Program extends [mscorlib]System.Object {

    .field static int32 s_x

    .method static void Main() {
        .entrypoint

        call int32& Program::f()
        ldind.i4
        call void [mscorlib]System.Console::WriteLine(int32)

        call int32& Program::g()
        ldind.i4
        call void [mscorlib]System.Console::WriteLine(int32)

        ret
    }

    .method static int32& f() {
        ldsflda int32 Program::s_x
        ret
    }

    .method static int32& g() {
        .locals init (int32 x)
        ldloca x
        ret
    }

}

Function f verifies just fine, since it just returns a ByRef to a static field, whereas function g fails verification, because it returns a ByRef to a local on the stack. You actually can't write code to produce the IL shown above from any of Microsoft's compilers except for VC++, i.e. C# won't let you say "static ref int f() { return ref s_x; }".

Now, why would you ever want such a thing? VC++ needed it, for example, to implement STL.NET. Traditional STL returns references to elements inside of internal data structures, which can subsequently be modified. Without this support, such values would need to be copied, or the STL.NET APIs would have had to deviate from the traditional STL APIs.

Interestingly, this doesn't change the ECMA Specification. It's always been loose on the issue, saying in Section 12.1.1.2 of Partition I: "Verification restrictions guarantee that, if all code is verifiable, a managed pointer to a value on the evaluation stack doesn't outlast the life of the location to which it points." Since you can't return a ByRef to a stack location, we don't violate this guarantee. Our previous verifier was simply being overly strict.

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.