In Orcas, we offer a new reader/writer lock: System.Threading.ReaderWriterLockSlim.

Motivation for a new lock

The primary reason for creating this type was that we wanted to provide an official reader/writer lock for the .NET Framework that people could actually rely on for performance-critical code.  It was no secret that the current ReaderWriterLock type was such a pig, costing somewhere around 6X the cost of a monitor acquisition for uncontended write lock acquires, that most people avoided it entirely.  Jeff Richter wrote an entire MSDN article about this, and Vance Morrison showed how to build your own on his weblog.  It was really too bad customers couldn't depend on the class in the Framework, and to be honest most devs really shouldn't be in the business of writing and maintaining their own reader/writer lock.

Second, we had a large number of qualms with the existing lock’s design.  It had funny recursion semantics (and is in fact broken in a few thread reentrancy cases we know about), and has a dangerous non-atomic upgrade method.  Did you know that you actually need to check the WriterSeqNum before and after a call to our ReaderWriterLock’s UpgradeToWriteLock method to ensure it didn’t change during the upgrade?  You do.  The code actually releases the reader lock before upgrading to the write lock, which allows other threads to sneak in, acquire the lock in between, and possibly change state that was read during the decision to upgrade.  The reason?  If we upgraded and then released the read lock, two threads trying to simultaneously upgrade would deadlock one another.  All of these problems represent very fundamental flaws in the existing type’s design.

So we decided to build a new one that solves all of these problems.  To be honest, I would have liked to fix the current one, but the existing API and compatibility responsibilities make that just about impossible.  We considered obsoleting the existing one, but as I note at the end of this article, there are still reasons to prefer the old lock.

Three modes: read, write, and upgradeable-read

The new ReaderWriterLockSlim supports three lock modes: Read, Write, and UpgradeableRead, and has the methods EnterReadLock, EnterWriteLock, EnterUpgradeableReadLock, and corresponding TryEnterXXLock and ExitXXLock methods, that do what you’d expect.  Read and Write are easy and should be familiar: Read is a typical shared lock mode, where any number of threads can acquire the lock in the Read mode simultaneously, and Write is a mutual exclusion mode, where no other threads are permitted to simultaneously hold the lock in any mode.  The UpgradeableReadLock will probably be new to most people, though it’s a concept that’s well known to database folks, and is the magic that allows us to fix the upgrade problem I mentioned earlier.  We’ll look at it more closely in a moment.

The performance of the new lock is roughly equal to that of Monitor.  When I say “roughly”, I mean that it’s within a factor of 2X in just about all cases.  And the new lock favors letting threads acquire the lock in Write mode over Read or UpgradeableRead, since writers tend to be less frequent than readers, generally leading to better scalability.  We’d originally considered providing a set of contention management options to choose from, but decided in the end to ship a simpler design that works well for most cases.

Upgrading

Let’s look at upgrades more closely now.  The UpgradeableRead mode allows you to safely upgrade from Read to Write mode.  Remember I mentioned earlier that our old lock breaks atomicity in order to provide deadlock-free upgrade capabilities (which is bad, particularly since most people don't realize it).  The new lock neither breaks atomicity nor causes deadlocks.  We acheive this by allowing only one thread to be in the UpgradeableRead mode at once, though there may be any number of other threads in Read mode while there’s one UpgradeableRead owner.

Once the lock is held in the UpgradeableRead mode, a thread can then read state to determine whether to downgrade to Read or upgrade to Write.  Note that this decision should ideally be made as fast as possible: holding the UpgradeableRead lock forces any new Read acquisitions to wait, though existing Read holders are still permitted to remain active.  (Sadly the CLR team seems to have removed two methods, DowngradeToRead and UpgradeToWrite, that I had originally designed for this purpose.  I admit what follows isn’t the most obvious way to do it.)   To downgrade, you simply call EnterReadLock followed by ExitUpgradeableReadLock: this permits other Read and UpgradeableRead acquisitions to finish that were previously held up by the fact that there was an UpgradeableRead lock held.  To upgrade, you similarly call EnterWriteLock: this may actually have to wait until there are no longer any threads that still hold the lock in Read mode.  There’s no real reason to also exit the UpgradeableReadLock at this point unlike the downgrade case, though in some cases it makes your code more uniform.  E.g.:

ReaderWriterLockSlim rwl = …;
…
bool upgraded = true;
rwl.EnterUpgradeableReadLock();
try {
    if (… read some state to decide whether to upgrade …) {
        rwl.EnterWriteLock();
        try {
            … write to state …
        } finally {
            rwl.ExitWriteLock();
        }
    } else {
        rwl.EnterReadLock();
        rwl.ExitUpgradeableReadLock();
        upgraded = false;
        try {
            … read from state …
        } finally {
            rwl.ExitReadLock();
        }
    }
} finally {
    if (upgraded)
        rwl.ExitUpgradeableReadLock();
}

Recursive acquires

Another nice feature with the new lock is how it treats recursion.  By default, all recursive acquires, aside from the upgrade and downgrade cases already mentioned, is disallowed.  This means you can’t call EnterReadLock twice on the same thread without first exiting the lock, for example, and similarly with the other modes.  If you try, you get a LockRecursionException thrown at you.  You can, however, turn recursion on at construction time: pass the enum value LockRecursionPolicy.SupportsRecursion to your lock’s constructor, and voila, recursion will be permitted.  The chosen policy for a given lock is subsequently accessible from its RecursionPolicy property.

There’s one special case that is never permitted, regardless of the lock recursion policy: acquiring a Write lock when a Read lock is held.  We considered enabling this, or at least giving a new enum value for it, but decided to hold off for now: if it turns out customers need it, we can always add it later.  But it’s dangerous and leads to the same Read-to-Write upgrade deadlocks that the old lock was prone to, and so we didn’t want to lead developers down a path fraught with danger.  If you need this kind of recursion, it’s a “simple” matter of changing your design to hoist a call to either EnterWriteLock or EnterUpgradeableReadLock (and the corresponding Exit method) to the outermost scope in which the lock is acquired.

There are corresponding properties IsReadLockHeld, IsWriteLockHeld, and IsUpgradeableReadLockHeld, to determine whether the current thread holds the lock in the specified mode.  You can also query the WaitingReadCount, WaitingWriteCount, and WaitingUpgradeCount properties to see how many threads are waiting to acquire the lock in the specific mode, and CurrentReadCount to see how many concurrent readers there are.  The RecursiveReadCount, RecursiveWriteCount, and RecursiveUpgradeCount properties tell you how many recursive acquires the current thread has made for the specific mode.

Some limitations: reliability

Lastly, I mentioned there are some caveats around where this lock’s use is appropriate.  Well, there’s one, really: it’s not hardened to be reliable.  This means a few things.

First, unlike the existing ReaderWriterLock, the ReaderWriterLockSlim type does not cooperate with CLR hosts through the hosting APIs.  This means a host will not be given a chance to override various lock behaviors, including performing deadlock detection (as SQL Server does).  Thus, you really ought not to use this lock if your code will be run inside SQL Server.

Next, the lock is not robust to asynchronous exceptions such as thread aborts and out of memory conditions.  If one of these occurs while in the middle of one of the lock’s methods, the lock state can be corrupt, causing subsequent deadlocks, unhandled exceptions, and (sadly) due to the use of spin locks internally, a pegged 100% CPU.  So if you’re going to be running your code in an environment that regularly uses thread aborts or attempts to survive hard OOMs, you’re not going to be happy with this lock.  Unfortunately the lock doesn’t even mark critical regions appropriately, so hosts that do make use of thread aborts won’t know that the thread abort could possibly put the AppDomain at risk: many hosts would prefer to wait, or immediately escalate to an AppDomain unload, if an individual thread abort is necessary while the thread is in a critical region.  But in the case of ReaderWriterLockSlim, a host has no idea if a thread holds the lock because the implementation doesn’t call Begin- and EndCriticalRegion.  And the kind of problems I mentioned in the previous post are always an issue with ReaderWriterLockSlim, because we don't necessarily guarantee that there will be no instructions in the JIT-generated code between the acquisition and entrance to the following try block.

Summary

In summary, the new ReaderWriterLockSlim lock eliminates all of the major adoption blockers that plagued the old ReaderWriterLock.  It performs much better, has deadlock-free and atomicity-preserving upgrades, and leads developers to program cleaner designs free of lock recursion.  There are some downsides to the new lock, however, that may cause programmers writing hosted or low-level reliability-sensitive code to wait to adopt it.  Don’t get me wrong, most people really don’t need to worry about these topics, so I apologize if my words of warning have scared you off: but those that do really need to be told about the state of affairs.  Thankfully, I’m confident that many of these issues will be fixed in subsequent releases.  And for most developers out there, the new ReaderWriterLockSlim is perfect for the job.

[Update 2/19/07: the search for Jim has been called off after just about three weeks.  Thanks to everybody who helped, and best wishes to Jim's family.]

Jim Gray, a Microsoft technical fellow who is best known for his seminal work on database transactions and data management, has been missing for almost a week.  He took his 40-foot sailboat, Tenacious, last Sunday to scatter the remains of his late mother near the Farallon Islands off the coast of California, and has been missing ever since.  This article has additional details.

Although the Coast Guard has called off the search, friends and family are chartering private aircraft, scouring satellite imagery, and NASA even made a special run of its ER-2 aircraft to generate additional data.  Werner Vogels has more information on his website, including how you can help with the search.

Jim actually provided important feedback while I was thinking and writing about PLINQ, and was one of the most supportive and excited reviewers of the project.  Not to mention all of the papers he wrote or was involved with that inspired a lot of the direction.  I’d be very sad to see his life cut short, particularly in this way.

I previously mentioned the X86 JIT contains a "hack" to ensure that thread aborts can't sneak in between a Monitor.Enter(o) and the subsequent try-block.  This ensures that a lock won't be leaked due to a thread abort occurring in the middle of a lock(o) { S1; } block.  In the following example, that means an abort can't be triggered at S0:

Monitor.Enter(o);
S0;
try {
    S1;
} finally {
    Monitor.Exit(o);
}

If an abort could happen at S0, it'd be possible for a thread to acquire lock o, but before entering the try block, be asynchronously aborted, and then not run the finally block to release the lock on o.  This would lead to an orphaned lock, and probable deadlocks later on during execution.  Debugging an instance of such a deadlock would of course be rather difficult because it depends on a very subtle race condition that must occur within the tiny window of a single instruction.  On a single-processor machine, this would require a precariously placed context switch, but as more and more cores are added to the machines that this software runs on, the probability simply increases.

Characterizing this as a "hack" was a little harsh.  It's really just a byproduct of the way that the X86 JIT generates code.

For an asynchronous thread abort to be thrown in a thread, that thread must be either: (1) polling for the abort in the EE or (2) running inside of managed code.  And even if the thread is in managed code, we may not be able to abort it, as is the case if the thread is currently executing a finally block, inside a constrained execution region, etc.  The C# code generation for the lock statement ensures there are no IL instructions between the CALL to Monitor.Enter and the instruction marked as the start of the try block.  The JIT correspondingly will not insert any machine instructions in between the two.  And since any attempted thread aborts in Monitor.Enter are not polled for after the lock has been acquired and before returning, the soonest subsequent point at which an abort can happen is the first instruction following the call to Monitor.Enter.  And at that point, the IP will already be inside the try block (the return from Monitor.Enter returns to the CALL+1), thereby ensuring that the finally block will always run if the lock was acquired.

This might seem like an implementation detail, but the reality is that we can never change it.  Too many people depend on this guarantee.

It turns out that Whidbey's X64 JIT does not guarantee this behavior.  (I suspect IA64 doesn't either, but don't know for sure.)  In fact there's a high probability that this won't work: there is always a NOP instruction before the CALL and the instruction marking the try block in the JITted code.  This is done to make it easier to identify try/catch scopes during stack unwind.   This means that, yes indeed, an abort can happen at S0 on 64-bit.

This will likely be fixed for the next runtime release, but I can't say for sure.

Update 4/17/08: This was indeed fixed for the X64 JIT in Visual Studio 2008.  Note that when compiling C# code targeting both X86 and X64, if you do not use the /o+ switch, this problem can still occur due to extra explicit NOPs inserted before the try.

The framework implements a method Monitor.ReliableEnter, by the way, that could be used to avoid orphaning locks in the face of thread aborts, but it's internal to mscorlib.dll.  It sets an out parameter within a region of code that cannot be interrupted by a thread abort, which the caller can then check inside the finally block.  The acquisition then gets moved inside so that, if the CALL is reached, the finally block is guaranteed to always run.  You'd then write this instead:

bool taken;
try {
    Monitor.ReliableEnter(o, out taken);
    S1;
} finally {
    if (taken)
        Monitor.Exit(o);
}

It's also possible the CLR team would expose this API in the future.  We wanted to in Whidbey, but didn't have enough time.  If 64-bit code generation was changed so that it doesn't emit a NOP before the try block, however, we probably wouldn't need ReliableEnter after all.

Joel tagged me on this silly 5 things you didn't know about me meme.  Since it's floating around, and because I’d hate to disappoint a crazy Australian who’s apt to shoot vinegar in my eyes with a Super Soaker (woof, woof), I figure I'll give it a shot:

1. I played in a heavy metal band when I was a teenager.  I was the lead guitarist, and loved to shred it up, with a sort of { 80's metal, 90's heavy metal, neo-classical, blues } style, influenced heavily by Slayer, Metallica, Pantera, GnR, Yngwie Malmsteen, Joe Satriani, and Stevie Ray Vaughan.  (Odd combination?  You bet!)  Don’t ask for pictures, I have conveniently "lost" them.  I stopped playing guitar for several years, but picked it back up in the past year and have been playing daily (focusing on building better music theory technical depth, but still shredding: my recent obsession is Dragonforce).  I also created several independent industrial and experimental techno CDs.  I try again every now and again, but I seem to have lost the patience.
2. I stopped playing in the heavy metal band because I "accidentally" punched a guy in the face in a mosh pit at a Sepultura concert.  This broke my hand in several places and was quite unpleasant.  (I did stay for the whole set, I'm happy to report.  The bar was kind enough to supply a plastic cup with some ice.)  The emergency room wrapped it in a cast, and then after 4 weeks, it had healed incorrectly.  So then I had to have it manually rebroken, and spent the entire summer in a new cast.  At the end, I had no hand or arm strength, my finger was crooked (making it hard to hold a pick), and my band had broken up because we couldn't play out (and they apparently didn't have the motivation to replace me temporarily).  This was the end of my dreams of being a rock star.
3. When I was 18 years old, I weighed a whopping 260 pounds.  Most of it was muscle, resulting from me working out literally every single day, and I have the stretch marks to show it.  I was a big dude, benched a little more than my weight, and even played center for a short period in high school football (I wasn’t keen on the fact that it’s apparently protocol that the quarterback routinely lays his hands on the center’s butt).  Now I weigh about 160 and have no muscle.
4. I started programming when I was 12.  This came about because a local gaming place (Gamer's Guild in Milford, MA) had set up a new BBS system, on which they provided several MUDs, MOOs, MUSHes, etc., on their Commodore Amiga 3000's and 4000.  I became hooked, especially when I found out you could get access to the source code and actually change it.  When CircleMUD came out, circa '92 (IIRC), I got serious about hacking code, doing the bulk of my MUD programming on a hand-assembled Slackware Linux 1.0 IBM PC.  Ironically, yours truly (a Microsoft employee) did most of his learning on the Linux OS, using GNU's C Compiler.  (I actually refused to use DOS until I started doing games programming that required graphics and found some cool DOS toolkits.  I refused Windows even longer, until I got sick of using 'lynx' to browse the WWW.  I have always found Windows API programming, with UPPER_CASE type names everywhere, rather ugly and I simply didn't get it at first.)  I set up my own 8-line BBS and later in '94 converted to co-located Internet hosting, running a heavily modified CircleMUD (3.1?) for a year and a half.  There was typically around 20 players signed on at any given point.
5. I am VERY obsessive about things.  I want to buy as many books as I can get my hold on, read them all the time, write code every waking moment, drink wine every night, go out for 15 course dinners every night, play guitar and learn every scale, major and minor, mode, modification, chord, arpeggio, I like to work, work, work until I am barely awake, and so on.  It drives my friends completely nuts, but it keeps me busy.  I've been that way ever since I was a little kid, so I don't think it's going to change anytime soon.

I don't know many people, so I'm going to commit meme heresy and not link to anybody else.  Sorry.

I was recently asked by a customer how to guarantee alignment of CLR data on 16-byte boundaries.  They needed this capability to interoperate with code that uses SSE vector instructions to manipulate the data (which require 16-byte alignment).  The bad news is that there’s no real good way of doing this.  That is, there isn’t any “align at N bytes” feature for the CLR in which type layout and stack and heap allocation cooperate.  The good news is that you can fake it.

(I spoke about alignment with respect to atomic cmpxchg8b instructions previously, right here, for those interested in reading about that too.)

The details of how to go about ensuring 16-byte alignment depend on whether you allocate your data on the stack or the GC heap.  For illustration purposes, imagine we’re dealing with an array of float32[]’s.  We’d like to ensure the beginning lies on a 16-byte boundary:

1. float [] a0 = new float[N]; // GC-allocated array of N floats
2. float * a1 = stackalloc float[N]; // stack-allocated array of N floats

If you use the former, GC allocation (1), you’re going to have a really tough time.  The GC moves objects around on you as it performs compactions, and only aligns the 1st element of the array on a 4-byte boundary.  So even if you manage to get your object allocated on a 16-byte boundary (by chance), it is apt to move during a subsequent GC.

To solve this problem, you’d have to pin the object.  Pinning causes GC fragmentation, so I really encourage you to avoid this approach and go with stack allocation, (2), if you can afford it.  A float[] on the stack is similarly aligned to begin at a 4-byte boundary, but, unlike (1), it will subsequently not move around.  Of course stack allocation is often impossible, or difficult, if you are writing a reusable library that may be called in an unknown context (where the caller may have very little stack left).  This is a tradeoff you would have to make.  If the pinning is very short lived, i.e. the duration of a single function call, it might be tolerable for you, a la P/Invoke.

Regardless of whether you choose (1) with pinning or (2) by itself, you’ve now got a stable address.  And you can use the stable address to calculate the next 16-byte element in the array from the base address, and then use that as the start of the array.  You will need some extra padding at the end for the worst case, which is base + 3, meaning at most 12 bytes, so you need to allocate 3 extra floats in the array.  Here’s an example:

void * AlignUp(void * p, ulong alignBytes) {
    ulong addr = new UIntPtr(p).ToUInt64();
    alignBytes -= 1; // adjust pointer for arithmetic
    if (((1<<(IntPtr.Size*4 - 1)) - alignBytes) <= addr) throw new Exception(“overflow”);
    ulong newAddr = (addr + alignBytes) & ~alignBytes;
    return new UIntPtr(newAddr).ToPointer();
}
…
float * p = stackalloc float[N + 3];
p = (float *)AlignUp(p, 16);
… use p …

Note that if you were to use an array of doubles instead, you’d have some challenges.  That’s because a 8-byte value on the 32-bit CLR is only 4-byte aligned, and therefore you can end up with a situation where the next 16-byte granularity is in the middle of a single element.  For example, 12 + 8 = 20 byte, +8 = 28 byte, +8 = 36 byte, and so on.  None of these are 16-byte aligned.  Not that it really matters, so long as you allocate enough memory, but you will need to do some casting of the array reference, as shown in the above code, to do the arithmetic.

Note also that there’s a StructLayout attribute that allows you to specify alignment, through its padding field, but sadly this doesn’t impact the GC’s heap or the JIT’s stack alignment, and so it’s useless for our purposes.  Though the relative alignment within the data structure will be correct, the absolute alignment is not guaranteed to be so.

OK, so I know all of this isn’t pretty.  But it works.

I will be giving a PLINQ talk at the Declarative Aspects of Multicore Programming (DAMP) workshop at POPL next week:

[Update: 1/23/07 -- added a link to the slide deck below.]

PLINQ: A Query Language for Data Parallel Programming

Microsoft’s language integrated query (LINQ) technology provides an expressive syntax and suite of APIs which facilitate classic data parallel operations: filtering, mapping, reductions, loop tiling, sorts, nested loops parallelism, prefix scans, and more.  In this talk, we look at a new set of extensions to the LINQ technology, called parallel LINQ (PLINQ), which automatically optimizes and parallelizes query operations based on dynamic runtime information.  We believe that the use of a familiar SQL-like syntax will broaden the reach of PLINQ in industry, and provides programmers with a more declarative and flexible way of expressing data-intensive computations.

Download presentation (PPT).

The workshop is being chaired by Guy Blelloch from CMU, is located in Nice, France, and features some interesting recent research in the field of parallel programming.  If anybody will be in town and wants to meet up, please drop me a line at joedu AT microsoft.

I’m a big food addict. When I first moved to the Seattle area from Boston about three years ago, I was initially quite depressed. I expected that Seattle’s food scene would be totally bland in comparison to Boston’s, and NYC was no longer a “quick” drive away (for the occasional binge). Sadly, I still can’t say that most of Seattle’s top restaurants come even close to NYC, but it’s much better than I expected. Many of the better restaurants are right up there with Boston’s. The selection is much smaller, sure, but after a few years I’ve settled on some favorites. I’ve listed these below in approximate order of my most to least favorite.

(Note that the list isn’t complete. I’ll be updating it as time goes by.)

For anybody who recently moved to the area, is visiting, or has been here for a while and hasn’t checked out the food scene, this list might come in handy when making a choice. I even gave each five 1-5 star ratings—overall experience, food taste, food presentation, wine list, value, and service, just like a famous food critic would. (My descriptions, on the other hand, make it quite apparent that I’m not one.) Overall experience is not just the average of the other four, it’s really just how I rate the restaurant’s dining experience in general. A bit arbitrary, yes. I’ve also marked each with a rough guideline on price/person: $ is $0-$20, $$ is $20-$50, $$$ is $50-$100, $$$$ is $100-$200, and $$$$$ is >$200.

All this list really indicates is my personal likes and dislikes; grab a Zagat’s Guide for more detailed and thorough ratings. You also might want to check out tastingmenu.com. It’s a wonderful site with very detailed essays on individual meals and beautiful photographs. Everybody has their own personal taste, and I happen to disagree with some of their ratings, but that’s to be expected.

5 STARS OVERALL

Mistral
http://mistralseattle.com/
New French -- Seattle, WA (Belltown)
Food taste: 5
Food presentation: 5
Wine list: N/A (pairings)
Service: 3
Price: $$$$$

Mistral rivals some of the best restaurants in the US, and certainly beats out all others I’ve eaten at in Seattle, including the Herbfarm. This is pure foodie paradise and a great way to spend 5 hours. Dishes are elegantly and classically presented, but with many new-age molecular gastronomy components and techniques weaved seamlessly throughout. While the food is clearly French-heavy, most dishes were minimalist and surprisingly light, with judicious use of cream and butter.

I recommend the Mistral Experience, which is 9 courses and 6 (or so) paired wines. I actually ended up with 8 or 9 glasses, due to a complimentary glass of Champagne, an extra glass of dessert wine, and a few surprises tossed into the mix. Mistral offers only tasting menus, no a la carte, which surprisingly caused an entire six top to get up and leave(!) the first time I were there. Perhaps it was the price, which somehow ended up at $600 or so for two people. It was well worth it, though. The chef had absolutely no problem creating a 9 course vegetarian menu on the fly. And yes, I always ask in advance about this when I make reservations, as I would feel rude dropping in to a tasting menu-only restaurant and expecting them to completely rearrange the menu to be vegetarian friendly. Most good restaurants don’t mind.

I was at first taken aback by Mistral’s very simple interior design. It’s a pale white with hardwood floors, 12 or so tables, and subtle and warm candle lighting. The ceilings are very high, and there are only a couple windows, aside from the front glass. The result is an elegant, cozy, and quaint atmosphere, but also feels a little like you’re at a cocktail party in some chic art studio located in a dark LA alleyway, with a décor which hasn’t yet been filled out. After a few courses, the initial shock passed, and I eventually found it calming.

I have to admit the wait-staff took me off guard. The Maître d' was aloof and seemingly 100% clueless, and our waiter was a bit aggressive. To be honest, I was completely put off by his demeanor and surfer-like descriptions of the food, wine, etc. (duuuude). But to be fair… after a few courses, it became evident why he works there. He was absolutely passionate about the food and wine, and was oozing with detail after detail about the cuisine. He had a story to tell about every dish and every wine. In the end, he gave a different, but good, experience compared to what I was expecting. In a phrase, decidedly unpretentious and food geeky. The 3 rating for service is primarily because of the Maître d', not him.

Sadly I don’t tend to take very good notes when I dine out. Here are some things that stand out in my mind. Robuchon-like cauliflower soup, with nice European (high fat content) butter. Ferran Adria-like carrot and cucumber foams, without feeling ridiculously out of place. Sous-vide hamachi tuna, which was absolutely delicious and unexpected. Sous-vide as a cooking technique creates an odd meaty texture for fish (particularly tuna), but cooks it perfectly and evenly throughout. Plenty of exotic fishes and meats, mallard duck, foie gras. Fingerling potato puree with chive oil. Many, many fruit reductions, including pomegranate and quince. There were two desserts, one of which was a bursting(!) with vibrant flavor passion fruit sorbet, and tasted, well, like I had just crushed open and slurped the innards of a passion fruit. It had just the right level of pleasing sourness, and thankfully wasn’t enhanced with any sweetener at all. Desserts like maple ice cream, little hand-made cookies, and pastry. Everything had a place on the plate and wandered only a little bit, keeping the palate sufficiently amused.

The paired wines are perfectly selected, jumping all over the map, and don’t feel like just an afterthought. Pace was perfect. Given the size of the meal and starting time (9 courses, starting at 7pm), you might expect to have been a little rushed, but I wasn't. And the portions were just the right size; at the end, I was no more full than if I had eaten a typical 4-course dinner at a slightly less extravagant restaurant.

Rover’s
http://www.rovers-seattle.com/
Classic French -- Seattle, WA (Madison Park)
Food taste: 5
Food presentation: 4
Wine list: 5
Service: 4
Price: $$$$$

Rover’s cranks out classic French cuisine like no other Seattle restaurant. What makes Rover’s truly special, aside from its perfect execution and taste, are that dishes are typically locally-inspired, highlighting seasonal, fresh ingredients. All of this integrated into a truly French menu that whisks you away to Paris. OK, sure they always have great diver scallops, foie gras, truffles, … and I’m not sure how much of this is from Washington and Oregon, but these focal points are at least augmented with seasonal and regional flavors. This isn’t country style comfort food… it’s high end, small-to-medium sized dishes, but with plenty of cream, heavy butter, and warm flavors.

Go for the 8-course tasting menu, I say. You’ll feel it more than most 8-course tasting menus due to the heavy French flavors, but you won’t regret it. The wine list rocks and will keep you occupied hunting for a bottle for a couple days if you’re into that kind of thing, although you’ll have a tough time finding a bottle for under $200. Rover’s never disappoints. It puts all other classic French restaurants in Seattle to shame (of which there are very few, of course).

4 STARS OVERALL

The Herbfarm
http://www.herbfarm.com/
New American --Woodinville, WA
Food taste: 4
Food presentation: 4
Wine list: 5
Service: 4
Price: $$$$$

I’ve been here many, many times, and I’ve never been disappointed. They have only one seating per night of about 100 people (just an approximate guess), and the atmosphere is very much like going our for a night at the theatre. The menu is completely prix fixe, no a la carte. It makes for a nice, 5 hour-long evening out. If you show up 30 minutes early, you get a tour of the herb garden. After doing this a couple times, it gets a little old (since the script doesn’t change at all), but you do get to munch on some really fresh herbs to whet the appetite.

What truly makes the Herbfarm great is the ever-changing, seasonal, and locally inspired menu. If you check out their website, you’ll notice the menu rotates every two weeks or so, featuring locally available and seasonally fresh ingredients. The Mycologist’s Dream is our favorite (here’s a sample menu), featuring dozens of varieties of mushrooms, often foraged the morning before the meal from all over the state of Washington. And it’s great for vegetarians.

The food is squarely in the New American category. The dishes are very good and usually vibrantly seasoned with fresh herbs. The simple, light dishes are definitely what they do best—e.g. consommés, poached fish, simple mushroom dishes—but when things get heavy, the herbs tend to get lost in the mix and the result is usually good, but not special. I must admit that I find the style to be borderline “tired,” but that’s probably a reflection of how I feel about New American restaurants in general as I write this (you'll notice there are quite a few in Washington). Because the Herbfarm's specialty is locally produced, seasonal ingredients, the menu style can fluctuate quite a bit: without these light, herby dishes, it’s hard to find a common theme from one visit to the restaurant to the next. As a result you don't really go back craving your favorite dish as you would many other restaurants.

The paired wine selections are usually good, but sometimes not stellar. They have a massive and wonderful winelist which due to the paired wines you seldom get to explore. But in addition to the 5 paired wines, you can order others from their list. Last time, I ordered a tasty flight of Madeiras, ranging from 1890 to 1960.

The Harvest Vine
http://www.harvestvine.com/
Spanish / Tapas -- Madison Park, WA
Food taste: 5
Food presentation: 4
Wine list: 3
Service: 3
Price: $$$

I’ve died and gone to… Basque, Spain! This teensy little restaurant seats probably 40 people total, 20 seats of which are available at or around the tapas bar. They always keep those seats available for walk-ins, so you can usually get lucky on a weeknight (or at the right time on weekends; I’m not telling, sorry :) ).

Foods range from pure Spanish comfort dishes, like rustic cheese, three kinds of olives prepared in three different marinades, fried piquillo peppers with sea salt, fresh white anchovies, delicious, oozing with fat Serrano ham, blood sausages, and chorizo to new-age, but Spanish-inspired, treats like foie gras, monk fish liver, squab, ox, and scallops. The wine list is good, though not great, featuring almost exclusively Spanish and Portuguese wines. I’m salivating for a glass of Jerez right now (a fortified dessert wine, made the same way as Sherry, in fact Sherry is just the English word for Jerez (similar to how Sherry is Xérès in French)).

The Harvest Vine is always a treat.

Café Juanita
http://www.cafejuanita.com/
Northern Italian -- Kirkland, WA
Food taste: 4
Food presentation: 4
Wine list: 3
Service: 3
Price: $$$$

This is one of the best Northern Italian restaurants I’ve ever eaten at. And this is having eaten at plenty of Italian restaurants in the Boston area which is famous for its Italian North End neighborhood. There’s always a good mix of hearty and light dishes, with plenty of exotic meat, foul, and fish, spanning things like wagyu beef, prosciutto, braised octopus, boar, venison, foie gras, veal sweetbreads, …, the list just goes on and on. Just about every time I’ve gone, they have had a seasonal Mediterranean fish, usually baked with a simple ragout of herbs, olives, capers, and served whole. Last week it was Branzino (a.k.a. spigola). I’ve never been disappointed. They have just an OK selection of vegetarian dishes and salads.

They also have some wonderful cheeses, which you can often get paired with an aperitif (like grappa, a balsamic vinegar martini, etc.). The desserts are also very good. I’ll never forget the olive oil ice cream that I had there last winter: surprisingly delicious! Service is spotty, sometimes great, sometimes just OK, really depending on the server. Timing is usually very good but sometimes off. The décor is pretty bland, but as you can tell by my lack of a décor rating for the restaurants, that kind of thing doesn’t really put me off that much so long as the food knocks me out.

Lark
http://www.larkseattle.com/
New American -- Seattle, WA (Capitol Hill)
Food taste: 5
Food presentation: 4
Wine list: 2
Service: 3
Price: $$$

Lark is a new favorite of mine, and one at which I find myself at least one night every other week. Like the Harvest Vine, the restaurant is very walk-in friendly and thus conducive to impulsive dining out decisions.

The food at Lark is simple and just a tiny bit bigger than tapas sized dishes. This is classic New American food, but with some interesting twists and inventive ingredient combinations. A couple weeks back I had foie gras terrine with quince jam; they frequently have fresh, seasonal mushrooms sautéed delicately with just a little herb (like parsley) and sea salt; yellowtail carpaccio; always a wonderful squab or pheasant dish, usually with something like an apple frisee or nut compote. They also have some really great classics. You can’t go wrong with some cheese, of which they have a great selection, served with fresh, local honeycomb. Rosti potatoes with clabber cream, pommes de terre “Robuchon”, gnudi, and any of their salads are always a treat.

I have two gripes about Lark. First is that the winelist is pretty much crap. Thankfully I’m usually in on a weeknight, which means I’m up for at most a glass or two of something, in which case their by-the-glass list isn’t too far off the mark. But if you’re looking for a bottle, I’d recommend bringing your own instead. The second is timing. At Lark they tend to assume that you’re going to share a lot of the dishes. When I order things in a particular order, saying clearly “as the first course”, “as the main course”, etc., I am saying this for a reason. Pay attention! The food more than makes up for both problems, thankfully.

3 STARS OVERALL

Crush
New American -- Seattle, WA (Capitol Hill)
Food taste: 3
Food presentation: 4
Wine list: 3
Service: 3
Price: $$$$

Crush is a strong, solid, very good restaurant. I can’t honestly say that the food is great enough to put it up into the 4 star category, however, mostly because the composition of ingredients and flavors is at the same time predictable and over the top. Many dishes have way too much going on, but then again many are simple and delicious. Particularly given the interior décor, which consists of plasticy white chairs located in a white-and-black decorated old house, and the difficulty in getting reservations, I get the impression they are trying to appeal to the non-foodie chic crowd a little bit too much.

I tremendously enjoyed the sautéed Hudson Valley foie gras with warm huckleberries on a slice of pumpernickel bread. It had huge, warm flavors and awesome fat content. The sea scallops and Maui onion confit was also terrific. When I think of Crush, I think of consistently good New American food where you can’t go wrong. I don’t think I’ve had a dish I didn’t like there, although their portions are often a little bit much for me.

Il Terrazzo Carmine
http://ilterrazzocarmine.com/
Italian -- Seattle, WA (Pioneer Square)
Food taste: 3
Food presentation: 3
Wine list: 4
Service: 2
Price: $$$$

Restaurant Zoë
http://www.restaurantzoe.com/
New American -- Seattle, WA (Belltown)
Food taste: 3
Food presentation: 3
Wine list: 2
Service: 3
Price: $$$

Café Campagne
http://www.campagnerestaurant.com/cafe_home.html
French (Bistro) -- Seattle, WA (Pike Place)
Food taste: 4
Food presentation: 3
Wine list: 2
Service: 2
Price: $$$

Dahlia Lounge
Pacific Northwest -- http://tomdouglas.com/dahlia/
Seattle, WA (Downtown)
Food taste: 3
Food presentation: 3
Wine list: 3
Service: 2
Price: $$$

Dahlia is Tom Douglas’s most upscale restaurant. In some ways, it feels like Tom is trying too hard with this one. Having eaten at his others, he is in his element when the dishes are very rustic with lots of complex flavors woven throughout, sort of sloppy, exemplified by the Palace Kitchen. I call it “hunting lodge food”, since there’s usually some game meat and generally themes that you’d imagine enjoying after a long day’s hunt. (I don’t hunt by the way, so this is purely inspired by movies, books, and other works of fiction on the topic. :P) Dahlia, on the other hand, tries to be a little minimalist while at the same time giving the same huge, rustic, and yes, sloppy feel to the dishes. If it sounds strange, it is. It kind of doesn't work for me, although some dishes are hits: I am completely in love with their Italian Bread Salad, with rustic bread cubes, fresh mozarella, kalamata olives, fruity olive oil, chunky strips of cured ham, etc. as a lunch.

I think everybody should try Dahlia, but it’s not the kind of place I’d go to on, say, a weekly basis. The food can get a little repetitive and is very predictable, as are all of Tom’s restaurants. It’s almost comfort food, but at that price, I have a dozen other comfort food restaurants that I’d rather hit up. It’s a matter of personal taste really. The bakery next door has some serious artesianal bread and pastries. Check it out; the bakery is definitely worthy of a trip on Sunday morning just to get a loaf to snack on.

Nishino
http://www.nishinorestaurant.com/
Japanese -- Seattle, WA (Madison Park)
Food taste: 3
Food presentation: 3
Wine list: 3
Service: 2
Price: $$$

Lola
http://tomdouglas.com/lola/
New Greek -- Seattle, WA (Downtown)
Food taste: 4
Food presentation: 3
Wine list: 2
Service: 2
Price: $$$

Veil
http://www.veilrestaurant.com/
New American -- Seattle, WA (Pioneer Square)
Food taste: 3
Food presentation: 4
Wine list: 2
Service: 3
Price: $$$

2 STARS OVERALL

Tango
http://tangorestaurant.com/
Spanish / Tapas -- Seattle, WA (Capitol Hill)
Food taste: 3
Food presentation: 3
Wine list: 3
Service: 3
Price: $$$

Palace Kitchen
http://tomdouglas.com/palace/
Pacific Northwest -- Seattle, WA (Downtown)
Food taste: 4
Food presentation: 2
Wine list: 2
Service: 3
Price: $$$

Campagne
http://www.campagnerestaurant.com/camp_home.html
Classic French -- Seattle, WA (Pike Place)
Food taste: 3
Food presentation: 3
Wine list: 4
Service: 2
Price: $$$$

Seastar
http://www.seastarrestaurant.com/
Bellevue, WA
Food taste: 3
Food presentation: 3
Wine list: 3
Service: 3
Price: $$$

Purple Café and Wine Bar
http://www.thepurplecafe.com/
Pacific Northwest -- Kirkland, WA, Woodinville, WA, and Seattle, WA (Downtown)
Food taste: 2
Food presentation: 2
Wine list: 3
Service: 3
Price: $$$

Monsoon
http://www.monsoonseattle.com/
New Vietnamese -- Seattle, WA (Capitol Hill)
Food taste: 3
Food presentation: 3
Wine list: 2
Service: 3
Price: $$$

Cactus
http://www.cactusrestaurants.com/
Mexican -- Kirkland, WA, Seattle, WA (Madison Park), and Seattle, WA (Alki Beach)
Food taste: 4
Food presentation: 3
Wine list: 1
Service: 2
Price: $$

Brasa
http://www.brasa.com/
New Mediterranean -- Seattle, WA (Belltown)
Food taste: 3
Food presentation: 2
Wine list: 2
Service: 2
Price: $$$

1 STAR OVERALL

Many of these places are comfort food and quick bite places. It’s a little unfair to label them “1 star” since comparing a great Southern Indian restaurant to somewhere like Mistral is like comparing apples to oranges. Each is amazingly good, but are for vastly different purposes (and with different price points). C’est la vie.

The Dish
Breakfast -- Seattle, WA (Ballard)
Food taste: 3
Food presentation: 1
Wine list: N/A
Service: 2
Price: $

Udupi Palace
Indian (Southern) -- Bellevue, WA
Food taste: 4
Food presentation: 1
Wine list: N/A
Service: 1
Price: $

Preet’s
http://www.preets.com/
Indian (Punjabi) -- Redmond, WA
Food taste: 3
Food presentation: 2
Wine list: N/A
Service: 2
Price: $

Kabul
http://www.kabulrestaurant.com/
Afghan -- Seattle, WA
Food taste: 3
Food presentation: 2
Wine list: N/A
Service: 2
Price: $$ (a little expensive for what you get)

Serious Pie
http://tomdouglas.com/serious/
Seattle, WA (Downtown)
Food taste: 3
Food presentation: 1
Wine list: 1
Service: 1
Price: $$

Wild Ginger
http://www.wildginger.net/
Pacific Rim -- Seattle, WA (Downtown)
Food taste: 2
Food presentation: 2
Wine list: 2
Service: 2
Price: $$$ (overpriced)

Szmania’s
http://www.szmanias.com/
German -- Seattle, WA (Magnolia)
Food taste: 3
Food presentation: 2
Wine list: 2
Service: 2
Price: $$$

Typhoon
http://www.typhoonrestaurants.com/
Thai -- Redmond, WA (Pioneer Square)
Food taste: 3
Food presentation: 3
Wine list: N/A (good tea list, though)
Service: 1
Price: $$

Mediterranean Kitchen
Middle Eastern -- Bellevue, WA and Seattle, WA (Queen Anne)
Food taste: 2
Food presentation: 2
Wine list: 1
Service: 2
Price: $$

I Love Sushi
http://www.ilovesushi.com/
Bellevue, WA and Seattle, WA (Lake Union)
Food taste: 2
Food presentation: 2
Wine list: N/A
Service: 2
Price: $

This place serves up good middle-of-the-road sushi, not too great, not too bad either. The raw fish is where it’s at here—I’m not overly crazy about the cooked foods. It gets busy on weekdays during lunch, but you can snag a Bento Box to go which is a fun treat.

Third Floor Fish Café
http://www.fishcafe.com/
Pacific Northwest -- Kirkland, WA
Food taste: 3
Food presentation: 2
Wine list: 2
Service: 2
Price: $$

Shamiana
http://shamianarestaurant.com/
Indian and Pakistani -- Kirkland, WA
Food taste: 3
Food presentation: 2
Wine list: 1
Service: 2
Price: $$

Marina Park Grill
http://www.marinaparkgrill.com/
Pacific Northwest -- Kirkland, WA
Food taste: 2
Food presentation: 2
Wine list: 2
Service: 2
Price: $$

Some pretty decent seafood dishes and seaside fare, like burgers and salads. It’s right on the waterfront and is a great place to stop by while walking around Kirkland and hanging out at the park. All around decent place with a not-too-shabby by-the-glass winelist. I wouldn’t go out of your way to eat here for dinner, but it makes a great late Sunday afternoon lunch on a warm summer day. There’s a little ice cream shop right around the corner for a nice treat afterwards while you walk through the park.

Chutney’s
http://www.chutneys.com/
Indian -- Bellevue, WA
Food taste: 2
Food presentation: 2
Wine list: 1
Service: 1
Price: $$

Malay Satay Hut
http://www.chutneys.com/
Malaysian -- Redmond, WA
Food taste: 3
Food presentation: 1
Wine list: N/A
Service: 1
Price: $

NEXT ON MY LIST…

These are restaurants I haven’t been to yet, but that I’ve heard first hand are quite good. They are listed in the order in which I plan on visiting them (or in the case of Gypsy, hope ;) ). And yes, I am rather embarrassed I haven’t tried Canlis or Lampreia yet. I suspect both will be either 4 or 5 stars. My intent is to do so in the first couple weeks of the new year.

Gypsy
Invitation only. :(

Lampreia
http://www.lampreiarestaurant.com/

Canlis
http://www.canlis.com/

Le Gourmand

La Carta de Oaxaca
http://www.lacartadeoaxaca.com/

Cascadia
http://www.cascadiarestaurant.com/html/

Carmelita
http://www.carmelita.net/

Izumi

Deadlocks aren’t always because you’ve taken locks in the wrong order.

In many systems, tasks communicate with other tasks through shared buffers.  In a concurrent shared memory system, these buffers might be simple queues shared between many threads.  In COM and Windows GUI programs these buffers might take the form of a window’s message queue.  In any case, if some task A performs a synchronous message send to task B, and task B does a synchronous send to task A, near simultaneously, and if neither task continues to process incoming messages, both will be blocked forever.

This is the classic reentrancy versus deadlock problem.  Ensuring that both A and B continue to process incoming messages while blocked on a send will eliminate the deadlock, albeit at the cost of possible reentrancy headaches.  Better yet, you could just send messages asynchronously.

Things can get quite a bit more complicated than this, of course.  Imagine that we have three operations, A, B, and C, being run over N concurrent streams of data.  We use data parallelism to partition the input data into and replicate the operations over the N streams, such that we have A0…AN-1, B0…BN-1, and C0…CN-1 operating on disjoint input.  A0 produces data for B0 which produces data for C0, and so on.  Elements are pulled on demand from the leaves (A0…AN-1) to the root (C0…CN-1), using a single execution resource (like a thread) per stream, i.e. E0…EN-1.

This is quite a bit like many real data parallel systems, including stream processing.

Imagine that sometimes AN finds that some input data must be given to BM instead of BN (where N != M); there is a similar story for B and C too.  We might be tempted to use some form of shared buffer to perform the inter-task communication here.  In other words, when A0 finds something for B1, it sends the data to it by placing it into B1’s input buffer.  This might be done asynchronously, i.e. A0 needn’t wait for B1 to actually consume the message, hence avoiding the sort of deadlock we noted earlier.

Unfortunately, since it might take some unknowable amount of time for B1 to process its input, we might worry about excessive memory usage for these buffers.  So we could put a bound on its maximum size using an ordinary bounded buffer… but once we’ve done that, we have turned what was an asynchronous send into a possibly-synchronous one, and in doing so introduced the same deadlock problem with which I began this whole discussion.

We could solve this by ensuing that, whenever a task must block because the destination buffer is full, it also processes incoming messages in its own buffer.  In other words, we use reentrancy.  Sadly, things are not always quite so simple.

Imagine this case: A0 has found data for B1, but B1’s buffer has become full.  So A0 is now waiting for B1 to process messages from its buffer to make room.  Nobody else will produce data for A0 at this point, so it’s stuck waiting.  Sadly, B1 has too become blocked trying to send a message that it has found for C0.  Because the same execution resource E0 that must free space in C0’s buffer is currently blocked in A0 waiting for B1 to free space from its buffer, and because the execution resource E1 is also waiting for E0, we now have a very convoluted deadlock on our hands.

The solution?  There’s no reason to keep the execution resource E0 occupied in A0 waiting for B1 in this case.  E0 could instead be freed up to run C0, freeing space for B1, and untangling the system.  Reentrancy strikes again, but this time, in a good way.  Note that in a heterogeneous system where these buffers are not controlled by the same resource, this solution is difficult to realize in practice.  Maybe A uses a custom bounded buffer written in C# to communicate, B uses SendMessages and COM message queues, and C uses GUI messages.  In this case, orchestrating the waiting to be deadlock free becomes a real challenge.

You might have noticed I'm blogging a lot more about native code than I used to.  Most of my day-to-day work still has to do with managed code, but I've been dazzled by all the new cool things in Vista that you can't do yet in managed code (and probably won't be able to for some time to come, since the CLR needs to keep running on old OSes).  And, besides, many low-level Windows changes impact managed code too, like the fairness post from last week.

My question to you is:  Do you vehemently like or dislike either category of post?  Does the split between the two work?  I'm trying hard to keep it at about 50/50. 

I'm wondering not just for blogging reasons.  As you might imagine, my book is looking to be very similar to my blog.  It is, after all, "Concurrent Programming on Windows", which sometimes involves using native code to access features that managed doesn't expose to you.  Similarly, the CLR gives you many things that Windows alone doesn't give you.  I'm trying reeeeealllly hard to ensure the prose is not schizophrenic, flows and progresses nicely, and doesn't repeat things: e.g. "here's how you do it in VC++, here's how you do it in C#, ..."  This can be a challenge for many things, but is obviously very important.  Thankfully a huge portion of the book is more about applying the technologies generally, which tends to be pretty common across both environments.

So ... what do you think?