I am naturally drawn to teams that work at an insane pace. The momentum, and persistent drive to increase that momentum, generates amazing results. And it's crazy fun.

In such environments, however, I've found one thing to be a constant struggle for everybody on the team -- leaders, managers, and individual doers alike: remembering to take the necessary time to do the right thing. This sounds obvious, but it's very easy to lose sight of this important principle when deadlines loom, customers and managers and shareholders demand, and the overall team is running ahead at a breakneak pace.

A nice phrase I learned from a past manager of mine was, "sometimes you need to slow down to speed up."

By taking shortcuts today, though attractive in that they help meet that next closest deadline, you almost always pay for them down the road. You might subsequently become quagmired in bugs because quality was comprimised from the outset. You may create a platform that others build upon, only to realize later that the architecture is wrong in need of revamping, incurring a ripple effect on an entire software stack. You may realize that your whole system performs poorly under load, such that just when your startup was beginning to skyrocket to success, users instead flee due to the poor experience. The manifestation differs, but the root cause is the same.

The level of quality you need for a project is very specific to your technology and business. I'll admit that working on systems software demands different quality standards than web software, for example. And the quality demands change as a project matures, when the focus shifts from writing reams of new code to modifying existing code... although the early phases are in fact the most challenging: this is when the most critical cultural traits are not yet set but are developing, when things have the highest risk of getting set off in the wrong direction, and is when you are most likely to scrimp on quality due to the need to make rapid progress on a broad set of problems all at once.

So how do you ensure people end up doing the right thing? Well, I'd be lying if I didn't say it is a real challenge.

As a leader, it is important to create a culture where individuals get rewarded for doing the right thing. Nothing beats having a team full of folks that "self-police" themselves using a shared set of demanding principles.

To achieve this, leaders needs to be consistent, demanding, and hyper-aware of what's going on around them. You need to be able to recognize quality versus junk, so that you can reward the right people. You need to set up a culture where critical feedback when shortcuts are being taken is "okay" and "expected." I've made my beliefs pretty evident in prior articles, however I simply don't believe you can do this right in the early days without being highly technical yourself. As a team grows, your attention to technical detail may get stretched thin, in which case you need to scale by adding new technical leaders that share, recognize, and maintain or advance these cultural traits.

You also can't punish people for getting less done than they could have if they took those shortcuts. Many cultures reward those who hammer out large quantities of poorly written code. You get what you reward.

In fact, you must do the opposite, by making an example out of the people who check in crappy code.

Facebook has this slogan "move fast and break things." It may seem that what I'm saying above is at odds with that famous slogan. Indeed they are somewhat contradictory, however paradoxically they are also highly complementary. Although you need to slow down to do the right thing, you do also need to keep moving fast. If that seems impossible, it's not; but it sure is difficult to find the right balance.

I have a belief that I'm almost embarassed to admit: I believe that most people are incredibly lazy. I think most quality comprimise stems from an inherent laziness that leads to details being glossed over, even if they are consciously recognized as needing attention. The best developers maintain this almost supernatural drive that comes from somewhere deep within, and they use this drive to stave off the laziness. If you're moving fast and writing a lot of code, strive to utilize every ounce of intellectual horsepower you can muster -- sustained, for the entire time you are writing code. Even if that's for 16 hours straight. If at any moment a thought occurs that might save you time down the road, stop, ponder it, course correct on the fly. This is a way of "slowing down to speed up" but in a way where you can still be moving fast. Many lazier people let these fleeting thoughts go without exploring them fully. They will consciously do the wrong thing because doing the right thing takes more time.

I've developed odd habits over the years. As a compile runs, I literally pore over every modified line of code, wondering if there's a better way to do it. If I see something, I push it on the stack and make sure to come back to it. By the time I've actually commited some new code -- regardless of whether it's 10,000 lines of freshly written code, or a 10 line modification to some existing stuff -- chances are that I've read each line of code at least three times. I disallow any detail I see to slip through the cracks. And my mind obsesses over all aspects of my work, even during "off times" (e.g., eating dinner, walking down the hallway, etc). Each of these opportunities represents a chance to slow down, reflect, and course correct.

Do I still miss thing? Sure I do. But that's why it's so critical to have a team around you who shares the same principles and will help to identify any shortcomings that I've missed.

Another practice I encourage on my team is fixing broken windows. I'm sure folks are aware of the so-called broken windows theory, where neighborhoods in which broken windows are tolerated tend to accumulate more and more broken windows with time. It happens in code, too. If people are discouraged from stopping to fix the broken windows, you will end up with lots of them. And guess what, each broken window actually slows you down. As more and more accumulate, it can become a real chore to get anything meaningful done. I guarantee you will not be able to move very fast if too many broken windows pile up and start needing attention. Slowing down to fix them incrementally, as soon as they are noticed, speeds you up down the road.

Building a quality-focused team isn't easy. But creating a culture that slows down to do the right thing, while simultaneously moving fast, provides an enormous competetive advantage. It's not as common as you might think.

I mentioned a few months back that my team had collaborated with MSR to publish a paper to OOPSLA about some novel aspects of our programming language (see here and here).

I was excited when Jonathan over at InfoQ asked to interview me about this work. We had a fun back and forth, and I hope the result helps to clarify some of the design goals and decisions we made along the way.

You can check it out here: Uniqueness and Reference Immutability for Safe Parallelism.

It's really hard to build a great team. It can take years of hard work and an enormous amount of patience.

The reality is that there's only a finite (read: small) number of truly amazing software developers in the world, especially compared to the opportunities and exciting projects available to them.

And yet, great teams are fueled first and foremost by great people. I often liken this to the aphorism "a rising tide lifts all boats."

The original meaning of the phrase of course had nothing to do with software. It was the notion that focusing on growth of the overall economy's GDP will necessarily have a positive impact on the incomes of individuals within that economy. Now, of course, it's not always true, and I'm no theoretical economist, however the basic idea in spirit is an intuitively interesting one.

Applying this thinking to teams, it implies you should always strive to hire better and better people. That by doing so, the overall quality of the team will rise. Hiring better and better people has a nonlinear impact to the culture, because a team is not just a disjoint set of nodes, but is instead a fully connected graph of individuals who have conversations and collaborate together. A greater overall quality of the team means richer connections and more powerful, higher quality innovation and software. It means your chance of truly changing the world has grown nonlinearly as well.

I strive to only hire people who are better than me, and better than people already on the team, in some interesting dimension. As soon as you let your high standards drop even an ounce, the average drops and there is a cumulative snowballing effect. The connections grow weaker, and a nonlinear drop in quality and innovation will occur. This is my nightmare scenario because it can go downhill very quickly.

This applies to an entire company as well as individual teams. Including what can happen should the tides lower. The brain drain begins as a slow drip, and can quickly turn into a torrential downpour in an instant. It often starts from the top, because culture and hiring start from the top.

Now, I will be the first to admit that raising the tide is hard. Damn hard, in fact. I have another phrase which is "always be on." That incredible engineer you worked with ten years ago just might be the piece missing in the puzzle today, and a good way to lift the boats. Opportunities come and go when you least suspect them, and you want those people to want to join your team. I have several individuals that literally took years of effort to recruit. And the wait was well worth it. This advice applies to individual contributers as much as it does to managers. You never know if in a few years, you'll be leading a team, kicking off your own startup, or even just helping to make your own team a better place.

And as a leader you owe all of this to your existing team. By lifting the boats, your entire team benefits. They grow, learn new things, and reach new heights in their own careers.

Despite being hard work, this all pays off the end. There is very little I find more satisfying in life than building and growing a great team, seeing the year over year improvements, and creating amazing things together. Perhaps even more than coding. (gasp)

The very notion of "authority" is 90% in your head. And it's one that often holds back otherwise very capable people.

This is yet another one that I got entirely wrong early in my own career.

When starting a new job, it's natural to be in what I call "understanding and assessment" mode. In fact, coming into a new job and telling everybody how they are doing things wrong is a recipe to not only get you off on the wrong foot, but also permanently poison your relationship with what would have been very important allies down the road. However, it's critical to turn the corner at some point before it's too late. The more experience you have, the less time it should take.

When I first came to Microsoft, I was suddenly surrounded by lots of smart people with momentum and energy on whatever it was that they were building. This led me to initially assume that these people knew what was going on. It led me to assume that, simply because some guy has the title of "Corporate Vice President" or "Distinguished Engineer", they knew what was going on. In fact, in my first day on the job -- and I will never forget this -- I was in a design meeting where I had the "audacity" to tell another DE (Microsoft's highest ranking technical position at the time) that I disagreed with what he was saying. I was polite about it, and to this day think I was right. However, I was pulled aside afterwards and told how stupid a move that was. And what's worse, I actually listened for my first two years and went out of my way not to rock the boat too much. This was against my better judgment. I was still young, and had come from another job where I was confident and could safely question anything; but I made the silly mistake of thinking "well, maybe things are different around here." I still wish I could get those two years back.

Allow me to let you in on a little secret. (Well, okay, it's not really a secret, but if only I could go back and tell my younger self this. And I suppose it ought to be obvious.) These people don't always know what is going on. It's probably safe to assume that these people have been rewarded in their careers because, statistically speaking, they are right more often than they are wrong. But it's still just statistics. And truthfully, if they are any good, they will like being questioned. They enjoy the technical debate. This is a critical aspect of a great team.

In fact, if they don't enjoy the debate, you are likely in the wrong place. The person who told me I was being stupid was actually right. The organization I had joined punished, rather than rewarded, people who questioned people in positions of authority. As soon as I realized this, I got out. It's a very personal preference, I suppose, but I personally prefer organizations that reward and promote people based on ability and direct impact. Sadly, in organizations where authority prevails, advancement is almost always based on who-likes-who, ass-kissing, and time-in-position. For folks looking for cozy jobs with guaranteed income, perhaps this is ideal; but you're quite unlikely to grow rapidly, build amazing things, and change the world in such places.

The employees I love the most are those that ask tons of questions and aren't afraid to tell me when I'm wrong. These people are inquisitive about everything, whether the topic is highly technical or pure business. By questioning my own views, and forcing me to articulate them, there is an overall strengthening of the culture. Not only do I benefit as a leader by having to methodically think through and defend my approach to problem solving, however those around me also benefit because (a) often they end up influencing the organization in big ways, and (b) even if my original stance survives, they understand the rationale behind certain decisions and can grow as a result. And it's fun! -- albeit passionately heated at times.

In fact, it's painful for me to see the opposite. An employee who has been trained to blindly respect authority. I was an admittedly rebellious youngster, so I've always known that this trait is simply not in my nature. I often reflect on how lucky I am to have landed in software rather than the military. Even when making those mistakes early in my career, I knew in my heart that they were mistakes at the time. But I do know that some people feel comfortable with a hierarchy of authority. They like the structure, and questioning it simply isn't an option. Sadly, some such people are beyond repair.

These days, I have to say that kids who grew up programming in their teens are the most fearless and rebellious. I have a dirty admission: I love hiring and mentoring and growing these individuals the most, because they have yet to be "trained" to respect authority. Once a vulnerable person early in their career has been brainwashed, it is an incredibly difficult thing to reverse. And so, as their career progresses, the longer these habits sit unaddressed, the less salvageable they become. Thankfully I caught it early on. I've managed plenty of folks who didn't.

Now, you can't be an asshole about it. And you can't be arrogant. Software is all about people and collaboration, and all of this questioning must be done with a single goal in mind: to make the software, the organization, and/or its people better. Authority is there for a reason, which is that ultimately someone needs to run the business, make decisions, and have their butt on the line. Sometimes the simple reality is that a leader's intuition is extremely good, and though data may be lacking to support the decision, you can trust it. It's okay to agree to disagree, or sometimes admit that someone simply has a stronger background than you in a particular area and so maybe you aren't in a position to fully understand why a certain decision was made. I have always tried to turn such occasions into learning opportunities. Jot down a few notes, and go read about it afterwards. I always jot down and research any term I hear that I'm not totally on top of, technical or business. It happens all the time.

In your next job interview, go out of your way to question a thing or two. If the person on the other end acts offended, either you asked in the wrong way (remember: respectful but inquisitive), or you shouldn't take the job. If it's a startup, read the business plan ahead of time and come prepared with some hard questions. If it's a corporation, ask what is rewarded, find holes in the technical architecture, question areas of the engineering process that could be improved. I really do think this is one of the most important cultural traits of a well-run team. And I guarantee you'll have way more fun on such a team, perhaps the most important cultural trait of all.

The best people in software have an innate ability to communicate using code. They have an idea and simply code it up, thereby making it reality. In fact, the best people are, I would say, obsessed with code.

Pick somebody in software that has done great things. Bill Gates comes to mind for me, because that’s who inspired me to get started in software. He wrote code for as long as he could manage, and famously delivered code reviews even as his company grew to 1,000s of engineers. No matter who you pick, I am sure one thing rings true: they obsessed over the details. And when it comes to software, those details are in the code.

Those who cannot read and write code must spend all of their time convincing other people of their ideas, and are usually sufficiently disconnected from reality (i.e., the code) that their ideas do not work in practice. This is an awful situation to be in, particularly at a company whose primary asset is code. Worse, most people voluntarily place themselves into this category, particularly over time in their careers, because they believe that coding is "not one of their job responsibilities." What rubbish!

I have three particular pet peeve examples to give.

The first is what I like to call the "mediocre mid-level manager syndrome." I’ll admit that when you manage large enough teams, you have to give up on a bit of coding. I will personally never give it up entirely, even as I manage teams of 1,000s of engineers. I will always use the product my team is building, I will read the checkins to at least understand what’s going on and stay grounded, and, assuming I continue to manage groups building development platforms, I will write code using that platform. But for managers who assume responsibility for 10 or fewer engineers, there is absolutely no excuse for slacking in these areas. It’s just pure laziness, and the teams suffer enormously: such teams typically lack "adult supervision" in the area of engineering culture, lack a role model, and build wrong and crappy things. In short, such managers literally add negative value. I can’t tell you how many "Software Development Leads" at large corporations fall into this category. That this is often culturally accepted is totally broken; needless to say, it is not acceptable on my teams.

The second is something I call "code is beneath me." The two most prominent examples are folks late in their careers and researchers. The former often goes hand in hand with the mid-level manager problem. But I’ve seen it afflict software engineers too: "I’ve been a professional developer for 10 years, so my job is now to tell others what to do rather than doing anything myself." At this point, they might adopt the title Architect. The research issue, however, quite frankly perplexes me. Computer Science is an odd mixture of pure math and applied engineering. I get that many CS researchers are more math-oriented, and wish to basically do mathematics rather than software. I also get that much of this research bears fruit. But in my experience there is a very large contingency of researchers that do not produce "first rate mathematics," and yet resist becoming grounded in code. The idea that you can improve the state of software, whose bloodline is code, without ever writing a line of it or becoming proficient in it, is complete insanity. And yet it’s generally accepted.

The last example, which is close to home since I made this mistake myself for a couple years early in my career, is "I manage things, I don’t build them." The title of Program Manager is a specific manifestation of this problem. Most have backgrounds in CS, and have probably written a little code. But most PMs are also usually not very good at it, don’t love it, and probably haven’t written much since leaving school. And yet these people are often "in charge" of making decisions about features, prioritization, and competitive offerings. It’s true that some people have great intuition and can make some good decisions without knowing how things work. But when it comes to software, those abilities need to be grounded by the code. If that’s not interesting to them, I always encourage considering positions in sales and marketing, HR, or one of the other organizations in such companies that isn’t focused on actually building the software. I would literally abolish the PM position at my company if I could. Those who love code should become developers.

I have the utmost respect for people who have fallen into any of these traps, but then realizes it and gets out. Hey, I did so myself.

Even those that write code often don’t do it enough. I’ve seen so many fall into the trap of debating whether or not something would work, or how elegant it would be. Certain people are afraid of failure, or find it difficult to get motivated to "start" coding. The best people, however, realize that questions are easily answered by writing the code in prototype form. They go from 0-60 in an instant, having a vision of what they would like to build, and letting nothing get in the way. I call this "oozing code from your fingertips." I do think some of this is a skillset thing. In software, the top 20% are easily 50X more productive than the bottom 20%. But I also think these traits can be learned, given role models who exhibit and demonstrate the behavior.

Finally, I do encourage software leaders to read as much code as they can. Reading code is a great way to learn how things work, and to stay on top of what’s actually happening in your project. And it keeps your mind fresh, and often leads to new ideas.

If it isn’t obvious, I might have a slightly atypical bias here. But it’s one of the things I am most passionate about with respect to running software teams. Code speaks. Love the code.

I’ve been managing software teams for several years. Perhaps more importantly, I have worked for some excellent leaders and have had the opportunity to learn from their good (and bad) habits.

Because I haven’t written a line of .NET code in a few years now, that blogging well has kind of run dry. And sadly my team is not yet ready to openly share our platform externally, so I cannot blog about that either.

As a result, I thought it would be fun to start a series about leadership in software. Not just the kind of leadership expected of managers, but also individual developers and architects. I have no idea how frequently I’ll write something, however just having a continuum of content to contribute to when I have a spare moment will help liven this place back up again, I’m sure. Furthermore, one lesson that’s been imparted upon me over the years is that "writing is thinking"; so by writing this stuff down, I’m sure it will crystalize even further.

The series will be called "Software Leadership" because, after all, it’s about the software. I hope you enjoy.

I mentioned recently that a paper from my team appeared at OOPSLA in October:

Uniqueness and Reference Immutability for Safe Parallelism (ACM, MSR Tech Report [PDF])

It's refreshing that we were able to release it. Our project only occasionally gets a public shout-out, usually when something leaks by accident. But this time it was intentional.

I began the language work described about 5 years ago, and it's taken several turns of the crank to get to a good point. (Hint: several more than even what you see in the paper.) Given the novel proof work in collaboration with our intern, folks in MSR, and a visiting professor expert in the area, however, it seemed like a good checkpoint that would be sufficiently interesting to release to the public. Perhaps some day Microsoft's development community will get to try it out in earnest.

There seems to have been some confusion over the goals of this work. I wanted to take a moment to clear the air.

First, despite assertions elsewhere, the primary focus of this work was not "implicit parallelism." Instead, I would summarize our goals as:

1. Create a single language that incorporates the best of functional and imperative programming. Both offer distinct advantages, and we envisioned marrying the two.
2. Codify and statically enforce common shared-memory state patterns, such as immutability and isolation, with minimal runtime overhead (i.e., virtually none).
3. Provide a language model atop which can be built provably safe data, task, and actor-oriented concurrency abstractions. Both implicit and explicit. This includes, but is not limtied to, parallelism.
4. Do all of this while still offering industry-leading code quality and performance, rivaling that of systems-level C programs. Yet still with the safety implied by the abovementioned goals.

The language features in the paper are a vast subset of the full suite needed to achieve our overall project goals. However, these alone have exceeded our original expectations.

I've programmed a great deal in functional languages. I'm a long-time lover of LISP and ML, and my closest friends know about my hard-core dedication to Haskell (expressed in an admittedly odd manner). In fact, Haskell's elegant marriage of pure functional programming with monads, notably the state monad, was a major inspiration for the design of the type system. There are of course many other influences, such as regions, linear types, affine types, etc.; however, I'd say Haskell was the strongest.

In some sense, we have simply taken the reverse angle of Haskell with its monads: what would it be like to embed pure functional programming within an otherwise imperative language?

This first goal is proving to be my fondest aspect of the language. The ability to have "pockets of imperative mutability," familiar to programmers with C, C++, C#, and Java backgrounds, connected by a "functional tissue," is not only clarifying, but works quite well in practice for building large and complex concurrent systems. It turns out many systems follow this model. Concurrent Haskell shares this high-level architecture, as does Erlang. Well-written C# systems do the same, though the language doesn't (yet) help you to get it right.

Of course, as called out by the second goal, immutability and controlled side-effects are tremendously useful features on their own. Novel optimizations abound.

And it helps programmers declare and verify their intent. As mentioned in the paper, we have found/prevented many significant bugs this way. Did you ever want to verify that your contracts and assertions are pure, such that conditional compilation doesn't change the outcome of your program? Or that your sort comparator isn't mutating the elements while performing its comparisons? Neither has much to do with concurrency, although the latter facilitates parallel sorts. Many other systems introduce specific verification techniques to address specific problems, rather than employing a general purpose type system.

I would say the strength with respect to concurrency is not the type system itself, but rather what you can do with it.

The focus on implicit parallelism in the recent forum discussions was unfortunate. I guess "implicit parallelism" just makes for catchy and controversial titles. Yes, the type system makes implicit parallelism "safe and possible," some forms of which are indeed profitable, but it's not as though suddenly all of your for loops are going to run 8-times faster after a recompile. The optimization angle is an orthogonal, but very real, concern. There are decades of research and experience here.

Even when tasks are explicitly spawned, however, the fact that the type system catches unsafe mutable state capture that would lead to race conditions is, I dare say, game changing. I could never go back to the old model of instruction-level races, which now-a-days feels like programming a PDP6 to me (no insults implied). And yes, data parallel works great in this model. It may take a bit of imagination, rereading the article, and perhaps looking at related work such as Deterministic Parallel Java, to understand how, but it does.

The effort grew out of my work on Software Transactional Memory in 2004, then Parallel Extensions (TPL and PLINQ), and then my book, a few years later. I had grown frustrated that our programming languages didn't help us write correct concurrent code. Instead, these systems simply keep offering more and more unsafe building blocks and synchronization primitives. Although I admit to contributing to the mess, it continues to this day. How many flavors of tasks and blocking queues does the world need? I was also dismayed by the oft-cited "functional programming cures everything" mantra, which clearly isn't true: most languages, Haskell aside, still offer mutability. And few of them track said mutability in a way that is visible to the type system (Haskell, again, being the exception). This means that races are still omnipresent, and thus concurrent programs expensive and error prone to write and maintain.

Reflecting back, I am somewhat amazed that the language has taken so long to hatch. Type systems that are sound and strike the right balance of utility and approachability are hard work!

I am ecstatic that we've been able to make inroads towards solving these hard problems. My team is, quite simply, an amazing group of people, and without them the ideas would have never made it beyond the "that will never work" phase. I look forward to sharing more about our work in the years to come.

.NET holds an enormous advantage over C++.

Well, okay, there are a few, but I’m thinking about one in particular: A single string type.

What’s not to love about that? Anybody who has done more than an hour’s worth of Windows programming in C++ should appreciate this feature. No more zero-terminated char* vs. length-prefixed char* vs. BSTR vs. wchar_t vs. CStringA vs. CStringW vs. CComBSTR. Just System.String. Hurray!

There’s one very specific thing not to love, however: The ease with which you can allocate a new one.

I’ve been working in an environment where performance is critical, and everything is managed code, for several years now. That might sound like an oxymoron, but our system can in fact beat the pants off all the popular native programming environments. The key to success? Thought and discipline.

We, in fact, love our single string type. And yet our team has learned (the hard way) that string allocations, while seemingly innocuous and small, spell certain death.

It may seem strange to pick on string. There are dozens of other objects you might allocate, like custom data types, arrays, lists, and whatnot. But there tend to be many core infrastructural pieces that deal with string manipulation, and if you build atop the wrong abstractions then things are sure to go wrong.

Imagine a web stack. It’s all about string parsing and processing. And anything to do with distributed processing of data is most likely going to involve strings at some level. Etc.

There are landmine APIs lurking out there, like String.Split and String.Substring. Even if you’ve got an interned string in hand (often rare in a server environment where strings are built from dynamically produced data), using these APIs will allocate boatloads of tiny little strings. And boatloads of tiny little strings means collections.

For example, imagine I just want to perform some action for each substring in a comma-delimited string. I could of course write it as follows:

          string str = ...; string[] substrs = str.Split(','); foreach (string
   subtr in substrs) { Process(substr); }
   
        

Or I could write it as follows:

          string str = ...; int lastIndex = 0; int commaIndex; while ((commaIndex
   = str.IndexOf(',', commaIndex)) != -1) { Process(substr, lastIndex, commaIndex); lastIndex
   = commaIndex + 1; }
   
        

The latter certainly requires a bit more thought. That’s primarily because .NET doesn’t have an efficient notion of substring – creating one requires an allocation. But the performance difference is night and day. The first one allocates an array and individual substrings, whereas the second performs no allocations. If this is, say, parsing HTTP headers on a heavily loaded server, you bet it’s going to make a noticeable difference.

Honestly, I’ve witnessed programs that should be I/O bound turn into programs that are compute-bound, simply due to use of inefficient string parsing routines across enormous amounts of data. (Okay, the developers also did other sloppy allocation-heavy things, but string certainly contributed.) Remember, many managed programs must compete with C++, where developers are accustomed to being more thoughtful about allocations in the context of parsing. Mainly because it’s such a pain in the ass to managed ad-hoc allocation lifetimes, versus in-place or stack-based parsing where it’s trivial.

"But gen0 collections are free," you might say. Sure, they are cheaper than gen1 and gen2 collections, but they are most certainly not free. Each collection is a linked list traversal that executes a nontrivial number of instructions and trashes your cache. It’s true that generational collectors minimize the pain, but they do not completely eliminate it. This, I think, is one of the biggest fallacies that plagues managed code to this day. Developers who treat the GC like their zero-cost scratch pad end up creating abstractions that poison the well for everybody.

Crank up .NET’s XmlReader and profile loading a modest XML document. You’ll be surprised to see that allocations during parsing add up to approximately 4X the document’s size. Many of these are strings. How did we end up in such a place? Presumably because whoever wrote these abstractions fell trap to the fallacy that "gen0 collections are free." But also because layers upon layers of such things lie beneath.

It doesn’t have to be this way. String does, after all, have an indexer. And it’s type-safe! So in-place parsing at least won’t lead to buffer overruns. Sadly, I have concluded that few people, at least in the context of .NET, will write efficient string parsing code. The whole platform is written to assume that strings are available, and does not have an efficient representation of a transient substring. And of course the APIs have been designed to coax you into making copy after copy, rather than doing efficient text manipulation in place. Hell, even the HTTP and ASP.NET web stacks are rife with such inefficiencies.

In certain arenas, doing all of this efficiently actually pays the bills. In others arenas, it doesn’t, and I suppose it’s possible to ignore all of this and let the GC chew up 30% or more of your program’s execution time without anybody noticing. I’m baffled that such software is written, but at the same time I realize that my expectations are out of whack with respect to common practice.

The moral of the story? Love your single string type. It’s a wonderful thing. But always remember: An allocation is an allocation; make sure you can afford it. Gen0 collections aren’t free, and software written to assume they are is easily detectible. String.Split allocates an array and a substring for each element within; there’s almost always a better way.

A glimpse of some research we've done recently just appeared at OOPSLA last week:

Uniqueness and Reference Immutability for Safe Parallelism

A key challenge for concurrent programming is that side-effects (memory operations) in one thread can affect the behavior of another thread. In this paper, we present a type system to restrict the updates to memory to prevent these unintended side-effects. We provide a novel combination of immutable and unique (isolated) types that ensures safe parallelism (race freedom and deterministic execution). The type system includes support for polymorphism over type qualifiers, and can easily create cycles of immutable objects. Key to the system's flexibility is the ability to recover immutable or externally unique references after violating uniqueness without any explicit alias tracking. Our type system models a prototype extension to C# that is in active use by a Microsoft team. We describe their experiences building large systems with this extension. We prove the soundness of the type system by an embedding into a program logic.

The official ACM page is here, and a tech report version is available on MSR's website.

As I said, this is just a glimpse. Its focus was mainly on the type soundness work we've done jointly with MSR, and less about the language, syntax, and uses. You'll have to use your imagination to fill in the rest ;-)

I often wish that .NET had erred on the side of offering postmortem instead of premortem finalization.

The distinction here is when exactly the finalizer runs, i.e. after or before the GC has actually reclaimed an object. This governs whether a dying object is (a) accessible from within its own finalizer, and therefore (b) eligible to become resurrected. Postmortem finalization occurs after the object is long gone, and hence says “no” to both of these questions; premortem finalization happens beforehand and hence says “yes.”

.NET chose the latter.

The primary downside of premortem finalization, setting aside the confusing nature of resurrection, is that the object in question cannot be collected until after its finalizer has run. This should be fairly obvious: it is only that second time the object is found to be dead “again” that we know the finalizer has or has not resurrected it.

This may seem like a small matter. But it matters quite a lot when building high performance software. In a garbage collected system, relying on high rates of finalization to keep up with demanding workloads almost never works. But in a premortem finalization system, even moderate demands become cause for concern.

Premortem finalization leads to finalized objects getting promoted to the elder generations before actually dying. If you check the value of GC.GetGeneration(this) within an object’s finalizer, for example, you will notice it is one greater than the generation in which the object was found to be dead the first time. Say it was found dead in Gen1; then GC.GetGeneration(this) will return ‘2’. Yet another collection must happen, in Gen2 to boot, in order to actually reclaim this object. And, of course, it’s not just this object, but also the transitive closure of objects to which it refers.

This approach penalizes the majority use case of finalizable objects. At least on .NET, most objects merely invoke CloseHandle on an IntPtr in the finalizer. This clearly needn’t hold up freeing the managed state. And resurrection is a dubious scenario anyway: such objects quickly end up in Gen2 where collections are expensive and infrequent. If you’re pooling via resurrection because you create expensive objects at a high rate of birth and death, manual memory management (or a different design altogether) is likely your only savior.

Although Java’s finalizers are also premortem, the JDK offers the facilities necessary to implement postmortem finalization on your own. It entails using WeakReference and ReferenceQueue . See this article if you are curious.

.NET doesn’t offer the notifications required to do the same. You can, however, learn from postmortem finalization to write better premotem finalizers: prefer simple finalizable objects that refer to only the state necessary to implement finalization – which ordinarily means no other managed objects. The SafeHandle abstraction is a good example of this. Most implementations are comprised of a simple IntPtr. This pattern will ensure that collateral promotion due to finalization is more contained.

After saying all of this, I hope it is just amusing trivia. I'm sure nobody is writing finalizers these days anyway.

It's been unbelievably long since I last blogged.

The reason is simple. I've been ecstatic in my job and, every time I think to write something, I quickly end up turning to work and soon find that hours (days? months?) have passed. This is a wonderful problem to have, but not so good for keeping the blog looking fresh and new. (I've also been writing a fair bit of music lately.) Well, this weekend I managed to lock myself out of my VPN access, and decided that this was a sign that I ought to dust off the cobwebs on a blog entry or two that I've had in the works for quite some time.

The topic for today is generics, a feature many of us know and love. Specifically, their impact on software performance, something I frequently see developers struggling to understand and tame in the wild.

The blessing; and, the curse

I absolutely love generics. I can hardly imagine writing code without them these days. The code reuse, higher-order expressiveness, beautiful abstractions, and static type-safety enabled by first class parametric polymorphism are all game-changing. And being a language history wonk, I'm delighted to see many mainstream programming languages stealing a page from ML and theoretical CS generally.

Generics, however, are not free. And in some circumstances, they are, dare I say, rather expensive. Few language features surpass generics in the ability to write a concise and elegant bit of code, which then translates into reams of ugly assembly code out the rear end of the compiler. I am of course speaking mainly to models in which compilation leads to code specialization (like .NET's), versus erasure (like Java's).

Most developers coming from a C++ background understand code expansion deeply, because they program with templates. Unlike templates, however, there is ample runtime type information (RTTI) associated with generic instantiations… such that the costs associated with generics frequently – and perhaps surprisingly – are a superset of those costs normally associated with C++ templates. At the same time, because the compiler understands parametric polymorphism, it can sometimes do a better job optimizing, e.g. with techniques like code sharing.

Basically, with templates and erasure, the equation for predicting code expansion is super simple. You get it all (in the former) or you get none of it (in the latter), but with specialized generics this equation is quite complex.

Paradoxically, these same costs are the main value that generics bring to the table! Write a little type-agnostic code and then "instantiate" that same code over multiple types without repeating yourself. But, generics are not magic; did you ever stop to wonder things like: What machine code is generated for these types? Does the compiler need to specialize the actual code that runs on the processor for unique instantiations, or is it all the same? And if it does need to specialize, where, how, and why? And perhaps most importantly, what hidden costs are there, and how should I think about them while writing code?

Before reading further, paranoia need not ensue. The point of this article is merely to raise your awareness. All programmers should know what the abstractions they use cost, and make conscious tradeoffs when writing code with them. The aforementioned benefits of generics really are often "worth it," both in the elegance and reusability of abstractions, and in developer productivity. In my experience, however, the associated costs are so subtle and ill-documented that even people who write highly generic code typically remain unaware of them. Even more subtly, these costs are somewhat different in nature when pre-compiling your code, such as with .NET's NGen technology.

This brief essay will walk through a few such costs in the context of the .NET Framework and CLR's implementation of generics. This is in no way an exhaustive study of generic compilation, and your mileage will vary from one platform to the next. Although the studies presented would apply to other implementations of generics, the reality is that if you're writing code in, say, Java – where type erasure is employed rather than code specialization – then all of this is going to be less relevant to you.

With no further delay, let's get started.

Code, RTTI, oh my

When considering costs, we must always think about both size and speed.

There is at least as much assembly code created for an instantiation as the code you've written for the generic abstraction in C# or MSIL. A simple mental model – that thankfully turns out isn't entirely accurate, thanks to some sharing optimizations described below – is that for each instantiation of a generic type or method you get a new copy of that code specialized to the type in question. Obviously, this increases code size. And just as obviously, it will add some runtime cost to JIT compile the code (if you aren't using ahead of time compilation), as well as putting more pressure on I-cache and TLB.

Another source of significant cost is the runtime data structures needed for RTTI and Reflection, like vtables and other metadata. Quite simply, the runtime needs to know the identity of each generic instantiation, to prevent things like casting a List<Int16> to a List<String>, and even List<Object> to List<String>; and given that there is often distinct code generated for unique instantiations, the vtable contents for those different List<T> instantiations are going to look quite different.

And of course, there are statics. Each generic instantiation gets its own set, requiring extra storage and another level of indirection when fetching them. Unique statics means D-cache and TLB pressure. It turns out that code shared across AppDomains, like mscorlib.dll, already need such things. But I have found that it's surprisingly common for a developer to throw a static field (or nested class!) onto an outer generic type, without actually needing it to be replicated for each unique instantiation.

In addition to the immediate effects, generic types often refer to other generic types which refer to other generic types … and so on. Instantiating a root type is akin to instantiating the full transitive closure.

To make our discussion friendly and familiar, we shall use the .NET Framework's List<T> type – presumably one of the most commonly used generic types on the planet – to illustrate many of these costs. And unfortunately, you'll also see that many of the common performance pitfalls plague this type too. (So, really, you need not feel bad if your own code is guilty of them too.)

Why the distinct code, anyway?

There is only one copy of List<T>'s code in mscorlib's MSIL. It is essentially just a blueprint for the list class.

When I create a List<Int16> in my program and use it, however, there clearly needs to be some assembly code created in order to execute List<T>'s associated functionality, just with any T's used by List<T>'s code replaced by actual 2-byte short integers. And similarly, if I were to instantiate a List<String>, all those T's need to be replaced by pointer-sized object references, either 4- or 8-bytes depending on machine architecture, that are reported live to the garbage collector.

This is what leads to our simple mental model above, in which each instantiation gets its own copy of the code. In this case, both List<Int16> and List<String> would be entirely independent types at runtime, with wholly separate copies of the machine code.

Certainly if I manually went about creating my own Int16List and StringList types, they would be distinct types with distinct machine code generated. Being a prudent developer, however, I'd probably try to arrange to share as much of the implementation as possible between the two types, perhaps using implementation inheritance. But alas, there's no way I could share it all: any code specific to Int16 or String, for example, would surely differ, both in MSIL and in the native code.

Generics basically give you the ability to do this same thing, without you needing to do the factoring of type-independent and type-specific code yourself. The compiler does that for you.

Why might the code be different? As stated above, Int16 values are 2 bytes and String pointers are native word sized (4 bytes on 32-bit, 8 bytes on 64-bit). All the code that passes values of type T on the stack, either as arguments or return values, moves instances into and out of memory locations (like the T[] backing array), and so on, needs to be specialized based on the size of T. This wouldn't be true of a generics implementation that used type erasure, like Java's, but then you'd need to box the value types on the heap so that everything is a pointer. If T is a Float, we will likely emit code that uses floating point math instead of general purpose registers. Any tables that report GC roots are likely to be different, since object references can be embedded inside struct values that get laid out on the stack. And so on. Some day you might want to compare the machine code for a simple generic Echo<T> method for different kinds of T's; it is really easy to do, and is quite illustrative.

A naïve wish might go as follows. Imagine that I had written my own dedicated Int16List and StringList types, and that we diffed the resulting machine code between the distinct list types; we'd presumably find a fair bit of duplication for all the reasons stated above. It would be a nice property if, when we used the generic List<Int16> and List<String> types, and similarly diffed the resulting assembly, the amount of specialized code would be no greater than the amount of specialized code between our best hand-written Int16List and StringList types. I.e., only parts that need to be different are different.

We could go even further with our wish. Imagine I had a List<DateTime> and List<Int64>. Both are 8-byte values, and do not contain any GC references. If I were writing a specialized 8ByteValueList in C++ and had immense performance constraints, I would, again being a prudent developer, probably use some type unsafe code, with nasty reinterpret_casts, so that I could use the same list type to store any kind of 8-byte value. (Except in C++ I could even store pointers!) It would also be a nice property if generics did some of this for us, while still retaining the type safety we love about generics.

It turns out we will get neither of our wishes exactly, although we will get something close to the spirit of our wishes.

Code sharing

Indeed, the CLR does arrange to share many generic instantiations. The rule is simple, although it is subject to change in the future (being an optimization and all): instantiations over reference types are shared among all reference type instantiations for that generic type/method, whereas instantiations over value types get their own full copy of the code. In other words, List<String> and List<Object> are backed by the same code, but List<DateTime> and List<Int64> get their own.

It is true that, in theory, List<DateTime> and List<Int64> could use the same shared code, because they are of identical size and have GC roots in the same locations (trivially, because neither has one). But there are additional restrictions on generated code that makes this problematic, for example if we were talking about Double and Int64. In short, the CLR doesn't actually share value type instantiations as of the 4.0 runtime, although clearly it could in certain situations (value types of the same size with GC roots in the same locations).

As you might guess, this extends to multi-parameter generics in obvious ways. A Dictionary<Object, Object> is shared with a Dictionary<String, String>, etc., and a Dictionary<Int64, Object> is shared with a Dictionary<Int64, String>. A Dictionary<DateTime, DateTime> is not, however, shared with a Dictionary<Int64, Int64> instantiation, as per the above.

My pal Joel Pobar wrote a post eons ago describing how code sharing works in great detail, which I do not intend to rehash. Please refer to his post for an excellent overview of how code sharing works.

An important thing to remember, however, is that no matter how much code sharing happens, you still need distinct RTTI data structures. So although List<Object> and List<String> share the same machine code, they have distinct vtables; sure, each table is full of pointers to the same code functions, but you are still paying for the runtime data structures. A distinct instantiation, therefore, is never actually free!

Transitive closures

Why am I making such a big deal about code sharing, anyway?

Another surprising aspect of generics is the transitive closure problem. Particularly when doing pre-compilation of generics, each unique instantiation doesn't simply lead to a specialized version of the code associated with the type being directly instantiated. The whole transitive closure of types, starting with that root type, will also be compiled. This can be a surprisingly huge number of types! JIT is much more pay-for-play, such that you get one level of explosion at a time, but once there is code that calls a particular type's method, even if that code is lazily compiled, creation of the type is forced.

To illustrate this, let's take our friend List<T>. Before examining the list, how many generic types would you expect that a single new List<T> instantiation instantiates?

What if I told you that a single List<int> instantiation creates (at least) 28 types? And that, say, five unique instantiations of List<T> might cost you 300K of disk space and 70K of working set? Well, of course, if you are writing a script, or something with fairly loose performance requirements, this might not matter much. But if topics like download time, mobile footprint, and cache performance are important to you, then you probably want to pay attention to this. To a first approximation, size is speed.

Yes, you heard me right: 28 types. Holy smokes... How can this be?!

Nested types are one obvious answer, and indeed List<T> has two: an Enumerator class (which is reasonable), and one to support the legacy synchronized collections pattern (which we presumably wish we didn't have to pay for). The larger answer here, however, is functionality. Yes, functionality! This is a great example where the cost of generics explodes as you add more features. Start simple, keep adding stuff, as has happened to List<T> over the years, and you will soon find that a series of elegant abstractions adds up to a gut-wrenching bucket of bytes.

Here's a quick sketch of the transitive closure of generic types used by List<T>:

          List<T> T[] type IList<T> type ICollection<T> type
   IEnumerable<T> type IEnumerator<T> type ReadOnlyCollection<T> type
   (AsReadOnly) (Nothing more than List<T>) IComparer<T> type (BinarySearch,
   Sort) {Array.BinarySearch<T> method (BinarySearch)} ArraySortHelper<T>
   type IArraySortHelper<T> type GenericArraySortHelper<T> type EqualityComparer<T>
   type (Contains) IEqualityComparer<T> type IEquatable<T> type NullableEqualityComparer<T>
   type Nullable<T> type EnumEqualityComparer<T> type {JitHelpers.UnsafeEnumCast<T>
   method} ObjectEqualityComparer<T> type Predicate<T> delegate type (Find*)
   Action<T> delegate type (ForEach) {Array.LastIndexOf<T> method (LastIndexOf)}
   Comparison<T> delegate type (Sort) Array.FunctorComparer<T> type (Sort)
   Comparer<T> type GenericComparer<T> type NullableComparer<T> type
   ObjectComparer<T> type {Array.Sort<T> method (Sort)} ArraySortHelper<T>
   type (see earlier) Enumerator inner type SynchronizedList<T> inner type IList<T>
   interface (see earlier) ICollection<T> interface (see earlier) IEnumerable<T>
   interface (see earlier) {Interlocked.CompareExchange<Object> method (SyncRoot)}
   {_emptyArray T[] static field} 
        

I'm not trying to pick on List<T>. This class is only unique in this regard in that it offers a large transitive closure of (mostly useful!) functionality. And it's not the only guilty party. We recently shaved off 100K's of code size on my team, for example, that were being lost simply because all the LINQ methods were declared as instance methods on the base collection class, rather than being extension methods as in .NET. We found nested enumerator and iterator types, cached static lambdas as static fields, and huge transitive closures of other generic types, all allocated when you just touched any collection type. Any collections library is apt to be full of this stuff, since they are highly generic. But collection libraries are certainly not the only places to go sniffing for such problems.

As an aside, it turns out that extension methods are a great way to make generic abstractions more pay-for-play.

Adding it up

Let's see what the above adds up to. I ran some programs through NGen as a quick and dirty experiment, and inspected the on-disk sizes and also the runtime working set sizes. I ensured clrjit.dll was not loaded into the process. Here's what I found. Take these numbers with a grain of salt, as they will change from release to release; they are simply rules of thumb. When in doubt, crank up NGen, DumpBin, and/or start trawling the heap with VADump yourself!

One empty type with no methods in CLR 4.0 seems to cost roughly 0.2K bytes of on-disk metadata, and about 0.7K in x64 working set. (This is a good rule of thumb irrespective of generics… in terms of order of magnitude, you can think "one empty type means 1K of memory.") A single List<S> instantiation, where S is an empty struct, is in the neighborhood of 60K on-disk metadata, and 14K of x64 working set. A single List<C> instantiation, however, where C is an empty class, is only – surprise – about 7K on-disk and 4K in-memory. Why the large discrepancy? Well, it just so happens that mscorlib.dll already includes an instantiation or two of List<T> over reference types, so this 4K is the incremental cost on top of reusing what is there; remember, there are still unique vtables and data structures still required for RTTI.

Rico did a similar analysis a few years back, and concluded that each unique List , where E was an enum type, cost 8K. Why the increase to 14K over the years? x64 and ever-increasing functionality on the basic collections classes, presumably. Remember, it's not just List<T> that has grown, it's also everything that List<T> uses internally as an implementation detail.

Dynamic specialization with dictionaries

Some specialization in behavior can be accomplished with dynamic runtime behavior, rather than static code specialization. A prime example is the following:

          class C { public static void M<T>() { System.Console.WriteLine(typeof(T).Name);
   } } 
        

Where does the program get the value of typeof(T) from? If you look at the MSIL, you will see that C# has emitted a ldtoken MSIL instruction. For some struct type, we can compile that as a constant in the code, because it is getting its own copy of the code. What occurs when two instantiations share code, like M<String> and M<Object>, however? As you might guess, there is an indirection.

The thing we usually use for such indirections – the vtable – is nowhere to be found in this particular example, because M is a static method. To deal with this, the compiler inserts an extra "hidden" argument, frequently called a generic dictionary, from which the emitted assembly code can fetch the type token. The cost here typically isn't bad, because many of the operations that pull in the dictionary are already RTTI or Reflection-based, and would require an indirection already (e.g., through a vtable).

The operations which require a dictionary of some kind include anything that has to do with RTTI and yet no vtable is readily accessible: typeof, casts, is and as operators, etc. And as you might guess, if instantiations aren't shared (such as with value types on the CLR), no dictionary is needed, because the code is fully specialized. There are also multiple kinds of dictionaries used by the runtime, depending on whether you are using a generic type, method, or some combination of both.

JITting when you didn't mean to

There are two primary ways in which you will JIT compile when using generics, even if you were good doobie and used NGen to reduce startup time.

One way is if you instantiate a new generic type exported from mscorlib.dll with a type argument also defined in mscorlib.dll, that wasn't already instantiated inside mscorlib.dll. (See my old Generics and Performance blog entry for more details.) You can very easily see this happening by using an instantiation like Dictionary<DateTime, DateTime>, and watching the clrjit.dll module getting loaded.

The other way is generic virtual methods (GVMs). It turns out that GVMs pose incredible difficulty for ahead of time separate compilation, because the compiler cannot know statically which slot in the vtable points at the particular implementation you are about to call. (Unless you use whole program compilation, something not offered by .NET at present time.) For each such method, there's an unbounded set of possible specialized instantiations a slot might point to, and so the vtable cannot be laid out in a traditional manner. C++ doesn't allow templated virtual methods for this very reason.

Thankfully, GVMs are somewhat rare. However, it only took 5 minutes of poking around to find one that is quite front-and-center in .NET: in the implementation of LINQ, there is an Iterator<T> type that has a method declared as follows:

          public abstract IEnumerable<TResult> Select<TResult>(Func<TSource,
   TResult> selector); 
        

All we need to do is figure out how to tickle that method, and we're guaranteed to JIT. As it turns out, sure enough, the following code does the trick and forces clrjit.dll to get loaded in .NET 4.0:

          int[] xs = …; int[] ys = xs.Where(x => true).Select(x => x).ToArray(); 
        

The Iterator<T> type is used for back-to-back Where and Select operators, as a performance optimization that avoids excess allocations and interface dispatch. But because it depends on a GVM, it does incur an initial penalty for using it, even if you have used NGen to avoid runtime code generation.

In conclusion

The moral of the story here is not that you should fear generics. Beautiful things can be built with them.

Instead, it's to use generics thoughtfully. Nothing in life is free, and generics are no exception to this rule. If code size is important to you, then you will want to have performance gates measuring your numbers against your goals; if you are working in a codebase that uses generics heavily, and you end up spending any significant time on code size optimizations, you will want to try to track down large transitive closures. As I stated above, you could really be throwing away 100K's of code here.

And as to the surprise JITting, I've seen teams compiling with NGen and having a functional gate that fails any new code that causes clrjit.dll to get loaded at runtime. Although tracking down the root cause might be tricky when that gate fails, at least you won't let the camel's nose under the tent.

Investing in tools here is a very good idea.

When it comes down to it, really thinking about what code must be executed by the process is helpful. Step back and imagine you were writing this all in C++, with the associated performance concerns front-and-center: consider how you'd arrange to reuse as much implementation as you can, manage memory efficiently, perhaps employ unsafe tricks that would have violated type safety and so are offlimits in .NET, and all that jazz. Then step back and be grateful that you have a type- and memory-safe environment to help you write more robust code, but also be realistic about what you are paying in exchange.

I hope you've learned a useful thing or two in this article. If you'd like to learn more, here are a few other good resources:

1. An MSR paper on the original implementation of .NET generics: http://research.microsoft.com/pubs/64031/designandimplementationofgenerics.pdf
2. Rico's "Six Questions About Generics and Performance" blog entry: http://blogs.msdn.com/b/ricom/archive/2004/09/13/229025.aspx
3. Joel Pobar's "Generics and Code Sharing" blog post: http://blogs.msdn.com/b/joelpob/archive/2004/11/17/259224.aspx
4. My "Generics and Performance" blog entry: http://www.bluebytesoftware.com/blog/2005/03/23/DGUpdateGenericsAndPerformance.aspx

Cheers.

InfoQ recently asked me a few questions about concurrency and programming languages, and here is what I had to say:

http://www.infoq.com/articles/Interview-Joe-Duffy

A little teaser:

"The major shift we face will be that mainstream languages will start to incorporate more concurrency-safety -- immutability and isolation -- and the platform libraries and architectures will better support this style of software decomposition. OOP developers are accustomed to partitioning their program into classes and objects; now they will need to become accustomed to partitioning their program into asynchronous Actors that can run concurrently. Within this sea of asynchrony will lay ordinary imperative code, frequently augmented with fine-grained task and data parallelism."

As an aside, I know I've been super quiet lately.  I never thought I'd go months without blogging.  My sincere apologies for this; work has been too all-consuming / fun, and I've been unable to carve out much time for anything else.  (Speaking of which, we are still hiring: email me at joedu at you-know-where dot com if you are interested.)  I'm about to head out to Europe for a few weeks, where hopefully I'll have a bit of time to write up something exciting to share.  Cheers.

After spending more time than I’d like to admit over the years researching memory model literature (particularly Java’s terrific JMM and related publications), subsequently trying to “fix” the CLR memory model, reviewing proposals for new C++ memory models, and beating my head against the wall for months developing a new memory model that supports weakly ordered processors like the kind you’ll find on ARM in a developer-friendly yet power-efficient way, I have a conclusion to share.

Volatile is evil

Why? Let me recount the reasons:

1. It doesn’t mean what you think.
2. It used to have a very specific purpose — to enure memory operations with external side-effects did not get reordered — and has since gotten bastardized and used for many secondarily-related purposes.
3. Even if you think it does mean what you think, the annotation scheme is all wrong. Volatile annotates a storage location, and yet what really matters is what happens when accessing said storage locations. The fences occur when you access the variable, not when you declare it. And yet from a readability perspective, they are completely invisible and easy to miss.
4. And even if you don’t care about readability, the meaning of volatile changes wildly when you switch platforms. Today it’s store / release, tomorrow it’s write / read fences. Perhaps it’s even sequentially consistent. And the label of “store / release” could actually be a white lie, as with the CLR’s memory model thanks to store buffer forwarding and the lack of fences in the CLR JIT’s x64 stores.
5. Performance, man, performance! Sure sequential consistency as the default sounds nice on the tin, but once you’re running that mobile app on ARM, and sucking up 160 cycles for each write you perform, you’re going to curse volatile like the plague.

And so the moral of the story follows...

Attempting to “fix” volatile is a waste of time

Instead, a new world order has arrived. We must take a two-pronged approach to solving instruction-level interleaving bugs, neither prong having much to do with the traditional definition of memory models or volatiles. We must:

1. Eliminate memory ordering from 99% of developers’ purviews. This is already the case with single-threaded programs, because code motion in compilers and processors is limited to what only affects concurrent observations. So the answer is pretty clear: developers must move towards single-threaded programming models connected through message passing, optionally with provably race-free fine-grained parallelism inside of those single-threaded worlds.
2. Leave the memory model esoterica to the Einsteins, and radically change its meaning. Data dependence and transitive visibility of memory operations are in. Volatiles on storage locations are out. Instead, we must throw fences into programmer’s faces, and force them to understand each and every one that occurs. And moreover, force them to decide about each and every one that occurs. Specifically, hidden fences thanks to volatile are no longer. Those who cannot take it should fall into the 99% bucket already mentioned above, versus the 1% bucket.

Let’s set #1 aside for now, since it’s obviously a huge can of worms.

But what about #2? It is quite encouraging that the C++0x group is firmly on the path of #2. See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2145.html for more details. In a nutshell, each location that you’d have ordinarily tagged volatile instead becomes a template atomic type. And then each read / write has the opportunity to specify the desired kind of fence, whether that is acquire (for reads), release (for writes), fully ordered, or relaxed (meaning no fence).

I do think it’d be worth them considering compiler-only fences too. So that relaxed means fully-relaxed, and there is a fence in-between that merely prevents the compiler from optimizing the memory operation. This pays homage to volatile’s legacy in C as merely a variable that mustn’t be subject to optimizations, because operations against these variables pertain to, say, memory-mapped device I/O.

Another nitpick of mine is that I’d have required each access to specify the fence, whereas C++0x implicitly uses full fence if left unspecified at the callsite. It’s a minor convenience, but I like always having the fence spelled out very explicitly in the code. Lock-free access to shared variables is sufficiently dangerous that automatic sequential consistency is the least of your problems.

Nevertheless, the C++0x direction is a massive good step forward, and these are just minor details.

My hope is that .NET follows suit. And the timing couldn’t be more apropos as “now”: we are moving forward in a heavily mobile, distributed-system-on-a-chip, and heterogeneous world, where processor memory models will necessarily continue to weaken. The overly strong x86 memory model, kept alive primarily to ensure compatibility, has simply grown too expensive to accommodate. The power benefits and architectural simplifications are hard to argue with, and because compatibility becomes less of an issue as new platforms arise (e.g. for mobile), the world moves to the cloud, and hence there is legacy to worry about, I do hope that processor vendors seize the opportunity. ARM certainly has. It is less about out-of-order execution as it is about coherency costs. Truthfully, I’d be disappointed if anything else happened, even though the risk to compatibility for shrink-wrapped software scares the hell out of me. But this is most certainly the right way to go, long-term. As software platforms move in the direction of #1 – as I also foresee – the need for fences dwindles. The cost of supporting the current .NET memory model is too great and will become a liability with time.

Thankfully, it is quite simple to build a veneer atop .NET that works a lot more like atomic . For example, imagine that we had a new System.Threading.Volatile static class, and that it offered the moral equivalent to atomic inner types for each atomic primitive we can synchronize against:

          namespace System.Threading { public static class Volatile { public
   struct Int32 {..} public struct Int64 {..} … public struct Reference
      where T : class {..} … } }
   
        

Now instead of tagging a location as ‘volatile’, you would use one of these primitives. For example, rather than:

          static volatile MySingleton s_instance;
        

You would say:

          static Volatile.Reference<MySingleton> s_instance;
        

Each class has a similar set of operations. For example:

          namespace System.Threading { public static class Volatile { public
   struct Int32 { public Int32(int value); public int ReadAcquireFence(); public int
   ReadFullFence(); public int ReadCompilerOnlyFence(); public int ReadUnfenced(); public
   void WriteReleaseFence(int newValue); public void WriteFullFence(int newValue); public
   void WriteCompilerOnlyFence(int newValue); public void WriteUnfenced(int newValue);
   public int AtomicCompareExchange(int newValue, int comparand); public int AtomicExchange(int
   newValue); public int AtomicAdd(int delta); public int AtomicIncrement(); public int
   AtomicDecrement(); // Etc…, bitwise ops, other math ops, etc. } } }
        

Of course, only the integer types would offer the increment, decrement, add, and related operators. And it turns out that offering different kinds of fences on the Atomic* operations would be incredibly useful too, because processors like ARM do not couple the fence to the compare-and-swap / load-locked-store-conditional as x86 processors do. Taking advantage of this can be huge if you are writing performance critical code, like a concurrent garbage collector whose atomic swaps need not imply ordering with the surrounding instruction stream. You can quibble over the details, like whether these should use enums instead of the name to encode the fence-kind. I did it this way to keep the implementations branch-free, although with a decent inlining JIT compiler, it’d probably optimize those away thanks to constant propagation.

It’s quite trivial to implement these APIs atop existing .NET primitives. I built a little library that does so, but it was so boring and repetitive I decided not to post it alongside this blog entry as originally intended.

With the above definition, we can very clearly see the fences involved in doing, say, double-checked locking:

          static Volatile.Reference<MySingleton> s_instance; public static
   MySingleton Instance { get { MySingleton instance = s_instance.ReadAcquireFence();
   if (instance == null) { instance = new MySingleton(); instance = s_instance.AtomicCompareExchangeRelease(instance,
   null); } return instance; } }
        

We see there are two fences. One is an acquire and, depending on what your memory model says about data dependence, is probably unnecessary. Most sane memory models guarantee that data dependent loads do not pass. So we needn’t worry that we’ll see a non-null s_instance whose contents haven’t been initialized. (If we were talking structs, it’d be another story.) Nevertheless, it’s definitely required that we use a release-only fence for the publication of the object. This guarantees writes to fields within the MySingleton constructor have completed prior to the write of the new object to the shared instance field. The point here is that you are forced to think about the fences, and you actually see them.

Of course, most platforms need to provide the bare minimum of fencing to assure type safety, particularly for languages like C#. My understanding is that C++0x has decided, at least for now, not to offer type-safety in the face of multithreading. That means you might publish an object and, if stores occur out-of-order, the reader could see an object partially initialized with an invalid vtable pointer. In C# and Java, the language designers have thankfully decided to shield programmers from this. The need for fences also extends to unsafe code like strings, where – were it possible for a thread to read the non-zero length before the char* pointer was valid – writes to random memory could occur and hence threaten type-safety. Thankfully, again, C# and Java protect developers from this, mostly due to the automatic zero’ing of memory as the GC allocates and hands out new segments.

There are costs to offering this type safety assurance. So you can understand why the C++ designers want to keep fences out of object allocation. If you have #1 above, however, the costs are dramatically lower and more acceptable. But the world is – unfortunately – still a freethreaded one, and we have several years to go before we’ve reached the final destination. As a step forward, however, the death of volatile is a welcomed one. Say it with me.

“Sayonara volatile.”

Here’s hoping that .NET 5.0 takes this step forward too.

I rambled on and on a few weeks back about how much performance matters. Although I got a lot of contrary feedback, most of it had to do with my deliberately controversial title than the content of the article. I had intended to post a redux, but something more concise is on my mind lately.

GC-based memory management is a boon to productivity, not to mention program safety. Few would argue with this. However, the most effective developers know how their particular GC works, and optimize their program’s data structure, allocation, and lifetime behavior to suit their particular GC best.

This is dangerous, but a pragmatic fact of life. It is dangerous because who’s to say that the runtime team doesn’t intend to entirely revamp the GC’s collection strategy next release, at which point your thoughtfulness may actually harm you? It’s a pragmatic fact for a few reasons: it’s probably not likely that the behavior of your favorite GC is going to change too fundamentally over time; if it did, you’d need to rethink things anyhow; oh, and when was that next release anyway (2 or more years out); and finally, what do you care about more, the theoretical loose coupling, or real results today?

One of the worst data structures for traversal is a linked list. That’s because its contents are fetched by pointer-chasing, an act that usually destroys locality, unless the data associated with each pointer was carefully constructed to live next to its previous and next pointer’s data. This seldom happens, because the main point of a linked list is to free you from such constraints.

One of the best data structures for traversal, on the other hand, is an array. Adjacent elements are truly adjacent to one another in memory, meaning that as you fetch the i’th element from memory, you’re probably pulling in the i’th, i+1’th, …, and so on, thanks to spatial locality. Of course, if the elements are just pointers, then you're back to the chasing game; as with anything, it depends.

How many elements you prefetch of course depends on the size of the elements with respect to your processor’s cache line. If you’re working with 8-byte elements, and 128-byte cache lines, then you may pay 100 cycles for the first fetch, and then amortize that cost over the subsequent 15 found cheaply in cache for 10 cycles. The result is about 250 cycles total; compare this to a linked list, where you’ll probably spend 1,600 cycles, or more than 6X the cost. And of course you’re trashing other data in the cache in the process. As you traverse more and more of the list, the numbers snowball, and the amortization of locality, or lack thereof, provides a stark contrast.

There’s another subtle reason why this is important. Stop and think about what happens when a GC occurs.

Yep, that’s right. Your data structures need to be traversed during a GC, after all, to ascertain the liveness of any pointers held within. That scan looks a whole heck of a lot like the same traversal I just described, and enjoys the same locality properties. So we can immediately conclude that data structures whose traversal is efficient will translate into less time spent in the GC chasing pointers, and better cache efficiency.

For programs that are sensitive to long pause times, this is huge. I talk to customers all the time whose programs are sensitive to microsecond-long GC delays, and – aside from ensuring good GC lifetime practices, like ensuring all objects either die young or live long – being conscious about locality can be immensely important. Especially for any long-lived, large data structures that will be subject to Gen2 collections throughout their lifetime.

There is another useful trick to know. If a data structure contains no pointers, the GC will not have to trace these pointers. Obvious, right? A linked list inherently contains pointers, so this trick really doesn’t apply: the GC will need to traverse the whole live portions of the object graph. What’s interesting is that an array, on the other hand, may or may not contain elements that contain pointers. For example, an array of ints clearly has no pointers, whereas an array of string references clearly does. This doesn’t just apply to the primitive types, but also custom structs which may or may not contain references. When the GC encounters such an array, its contents need not be traversed: instead, the array is alive, and that's that. Yet another opportunity to eliminate pointer chasing. Not only does this save the GC from doing some heavy lifting, but the pointer-free structs eliminate the need for the GC write barriers on array stores too.

So think of all this next time you’re confronted with the decision to employ a tree, graph, or linked list, and whether a dense, and perhaps pointer-free, representation could be beneficial. Even if it means you must replace pointers with index calculations. The locality benefits may not matter, but then again, they may. And at least you can knowingly make a balanced tradeoff, with these potential advantages in mind.

I have several positions open on my team here at Microsoft.

My team's responsibility spans multiple aspects of a research operating system’s programming model. The three main areas are concurrency, languages, and frameworks. When I say concurrency, I mean things like asynchrony and message passing, data and task parallelism, distributed parallelism, runtime scheduling and resource management, and heterogeneity and GPGPU. When I say languages, I mean type systems, mostly-functional programming, verified safe concurrency, and both front- and back-end compilation. And when I say frameworks, I mean virtually anything you could imagine wanting out of a platform framework: all things XML, data interoperability (database, web services, etc.), collections, transactions, multimaster synchronization, and even low level things, like regex, numerics, and globalization.

Our team is 100% developers, and we have an “everybody codes, everybody loves to code” culture. Even managers are expected to spend a significant amount of time prolifically writing code.

All of these components are new and built from the ground up. So self-drive and an ability to have a vision and make it happen are incredibly important.

We are always happy to hire great, hard-working people, regardless of years of experience. If you’re extremely strong in one or more of the abovementioned areas, more of a generalist, are an amazing coder, or all of the above, you’d fit in perfectly. This is the most amazing team of people I’ve ever worked with. If you are interested, please email your resume to me at joedu AT microsoft DOT com.

That immutability facilitates increased degrees of concurrency is an oft-cited dictum. But is it true? And either way, why?

My view on this matter may be a controversial one. Immutability is an important foundational tool in the toolkit for building concurrent – in addition to reliable and predictable – software. But it is not the only one that matters. Making all your data immutable isn’t going to instantly lead to a massively scalable program. Natural isolation is also critically important, perhaps more so. And, as it turns out, sometimes mutability is just what the doctor ordered, as with large-scale data parallelism.

Isolation first; immutability second; synchronization last

Stepping back for a moment, the recipe for concurrency is rather simple. Say you’ve got multiple concurrent pieces of work running simultaneously (or have a goal of getting there); for discussion’s sake, call them tasks. Take two tasks. The first critical decision has two cases: either these tasks concurrently access overlapping data in shared-memory, or they do not. If they do not, they are isolated, and no precautions associated with racing memory updates are needed. If they do share data, on the other hand, then something else must give. If all concurrently accessed data is immutable, or all functions used to interact with data are pure, then dangerous concurrency hazards are avoided. All is well. If some data is mutable, however, then this is where things get tricky, and higher-level synchronization is needed to make accesses safe. This decision tree is straightforward and clear.

I have listed those four attributes – isolated, immutable and pure, and synchronization – in a very intentional order. Thankfully, this order mirrors the natural top-down hierarchical architecture of most modern object- and component-based programs: we have large containers that communicate through well-defined interfaces, each comprised of layers of such containers, and somewhere towards the leaves, a fair amount of intimate commingling of knowledge regarding data and invariants.

This order also reflects the order of complexity and execution-time costs, from least to most. Isolation is simple, because components depend on each other in loosely-coupled ways, and in fact scales superiorly in a concurrent program because no synchronization is necessary, the “right” data structure may be chosen for the job – immutable or not – and locality is part-and-parcel to the architecture. Immutability at least avoids the morass of synchronization, which can affect programs immensely in complexity, runtime overheads, and write-contention for shared data. It is clear that synchronization is something to avoid at all costs, particularly anything done in an ad-hoc manner like locks.

Making the concurrency

But where did all this concurrency come from, anyway?

It came from two things:

1. The coarse-grained breakdown of a program into isolated pieces.
2. The fine-grained data parallelism.

On #1: Program fragments that are isolated are already half-way down the road to running concurrently as tasks. The second half of this journey, of course, is teaching them to interact with one another asynchronously, most frequently through message-passing or by sticking them into a pipeline. The details of course depend on what programming language you are using. It may be through agents, actors, active objects, COM objects, EJBs, CCR receivers, web-services, something ad-hoc built with .NET tasks, or some other reification. Nevertheless the isolation is common to all these.

On #2: Data parallelism, it turns out, often works best with mutable data structures. These structures must be partitionable, of course, so that tasks comprising the data parallel operations may operate with logically isolated chunks of this data safely, even if they are parts of the same physical data structure. So chunks of them are isolated even though they don’t appear to be. This is trivially achievable with many important parallel-friendly data structures like arrays, vectors, and matrices. Capturing this isolation in the type system is of course no small task, though region typing gets close (see UIUC’s Data Parallel Java).

But you usually don’t want these structures to be immutable, because they can be modified in constant-time and space if they are their classic simple mutable forms. Programmers doing HPC-style data-parallelism a la FORTRAN, vectorization, and GPGPU know this quite well. Compare this a world where we are doing data-parallelism over immutable data structures, where modifications often necessitate allocations or more complicated big-oh times due to clever techniques meant to avoid such allocations, as with persistent immutable data structures. This is likely less ideal. It is true that some data parallel operations are not in-place against mutable data – as with PLINQ – at which point purity, but not immutability, is key. The two are related but not identical: immutability pervades the construction of data structures, whereas purity pervades the construction of functions. But if you can get by with one copy of the data, why not do it? Particularly since most datasets amenable to parallel speedups are quite large.

Immutability: the bricks, not the mortar

Notice that the concurrency did not actually come from immutable data structures in either case, however. So what are they good for?

One obvious use, which has little to do with concurrency, is to enforce characteristics of particular data structures in a program. A translation lookup table may not have been meant to be written to except for initialization time, and using an immutable data structure is a wonderful way to enforce this intent.

What about concurrency? Immutable data structures facilitate sharing data amongst otherwise isolated tasks in an efficient zero-copy manner. No synchronization necessary. This is the real payoff.

For example, say we’ve got a document-editor and would like to launch a background task that does spellchecking in parallel. How will the spellchecker concurrently access the document, given that the user may continue editing it simultaneously? Likely we will use an immutable data structure to hold some interesting document state, such as storing text in a piece-table. OneNote, Visual Studio, and many other document-editors use this technique. This is zero-cost snapshot isolation.

Not having immutability in this particular scenario is immensely painful. Isolation won’t work very well. You could model the document as a task, and require the spellchecker to interact with it using messages. Chattiness would be a concern. And, worse, the spellchecker’s messages may now interleave with other messages, like a user editing the document. Those kinds of message-passing races are non-trivial to deal with. Synchronization won’t work well either. Clearly we don’t want to lock the user out of editing his or her document just because spellchecking is occurring. Such a boneheaded design is what leads to spinning donuts, bleached-white screens, and “(Not Responding)” title bars. But clearly we don’t want to acquire a lock and then make a full copy of the entire document. Perhaps we’d try to copy just what is visible on the screen. This is a dangerous game to play.

Immutability does not solve all of the problems in this scenario, however. Snapshots of any kind lead to a subtle issue that is familiar to those with experience doing multimaster, in which multiple parties have conflicting views on what “the” data ought to be, and in which these views must be reconciled.

In this particular case, the spellchecker sends the results back to the task which spawned it, and presumably owns the document, when it has finished checking some portion of the document. Because the spellchecker was working with an immutable snapshot, however, its answer may now be out-of-date. We have turned the need to deal with message-level interleaving – as described above – into the need to deal with all of the messages that may have interleaved within a window of time. This is where multimaster techniques, such as diffing and merging come into play. Other techniques can be used, of course, like cancelling and ignoring out-of-date results. But it is clear something intentional must be done.

In conclusion

It is safe to say that immutability facilitates important concurrent architectures and algorithms. It can really help big time, for sure. But it is clearly no panacea. Whether mutability or immutability is the right choice for a particular data structure in your program, as with all things, depends.

It could be the case that choosing a piece-table for storing your text facilitates large-scales of concurrency in version two of your software application, but that in version one you have no use for it. Making that call ahead of time may pay in spades down the road, even if it comes at a marginal cost up-front. Or it could be that choosing an immutable data structure costs you in time and space, and you never end up exploiting the fact that you could have shared that particular structure in a zero-cost way across agents in your program.

One thing’s for sure: I’m glad to be programming in languages like C#, F#, Clojure, and Scala, where I’ve got a choice.

In .NET today, readonly/initonly-ness is in the eye of the provider. Not the beholder.

Although both C# and the CLR verifier go to great pains to ensure you don't change a readonly/initonly field outside of its constructor (or class constructor, in the case of a static field), this guarantee doesn't imply what you might imagine. It means what it says: you can't change such fields except for in certain contexts.

If you try, C# won't let you, including forming byrefs to them:

v.cs(0,0): error CS0191: A readonly field cannot be assigned to (except in a constructor or a variable initializer)
v.cs(0,0): error CS0192: A readonly field cannot be passed ref or out (except in a constructor)
v.cs(0,0): error CS0198: A static readonly field cannot be assigned to (except in a static constructor or a variable initializer)
v.cs(0,0): error CS0199: A static readonly field cannot be passed ref or out (except in a static constructor)

And neither will the CLR verifier:

[IL]: Error: [c:\v.exe : C::Main][offset 0x00000001] Cannot change initonly
    field outside its .ctor.

Of course, attempting to invoke an operation on a readonly struct will make a defensive copy locally, and invoke the method against that. This ensures the readonly contents cannot change.

One unfortunate hole in this safety is with unions. You do not need unsafe code to break readonly, and yet the effect is the same as with an unverifiable program that writes to a readonly field:

struct S1 {
    public readonly int X;
}

struct S2 {
    public int X;
}

[StructLayout(LayoutKind.Explicit)]
struct S3 {
    [FieldOffset(0)]
    public S1 A;
    [FieldOffset(0)]
    public S2 B;
}

Now we can change A.X via B.X, even though A.X is supposedly readonly:

S3 s3 = ...;
int x = s3.A.X;
s3.B.X++;
ASSERT(x == s3.A.X); // false; it is +1

The same would have been true even if the field S3.A was marked readonly.

This is quite an evil trick. I have to be honest that I believe this is a CIL verification hole, and should produce unverifiable MSIL much like when you try to overlay structs containing overlapping GC references. Nevertheless, it is what it is.

Let's step back. Why does all of this matter, anyway, and what guarantees were we hoping that readonly would provide?

It would be ideal, I assert, if the guarantee was not just "the target field can only be written to in the constructor", but also "the target field, once read, cannot be observed with a different value later on". This would not be true during construction, but we'd like to say it holds at all other times.

The above example throws a wrench in this idea. As does the following example. But this new example will be more disturbing, because the solution is not a simple verifier change.

What would you expect this program to print to the console?

struct S {
    public readonly int X;

    public S(int x) { X = x; }

    public void MultiplyInto(int c, out S target) {
        System.Console.WriteLine(this.X);
        target = new S(X * c);
        System.Console.WriteLine(this.X); // same? it is, after all, readonly.
    }
}

S s = new S(42);
s.MultiplyInto(10, out s);

As you may or may not have guessed, the output is "42" followed by "420". Yes, the value of 'this.X' changes after we have assigned to 'target' inside MultiplyTo, because the caller aliases the out-param with the 'this' param. Recall that parameter passing for structs in C# is done byref, so that these two references actually physically point to the same location when that call is made. The assignment to 'target', therefore, actually replaces the entire contents of 'this' all at once. And hence this gives the illusion that readonly fields are shifting.

You might be tempted to say that this can be prevented with alias analysis. But this is deceptively difficult to do. Consider this more complicated example:

class C {
    public struct S S;
}

void M1(C c) {
    M2(c, out c.S);
}

void M2(C c, out S s) {
    c.S.MultiplyInto(10, out s);
}

It is in no way clear inside M2 that the two aliases refer to the same location. The aliasing occurred higher up in the stack. Although byrefs are restricted to stack-only passing, making the necessary alias analysis tantalizingly close to attainable, it is nontrivial to say the least. Presumably we would have had to have blocked the forming of the byref within M1, rather than its use within M2. We could fall back to runtime checks, but that is also unfortunate for numerous reasons.

The moral of the story? Structs as containers of readonly values are not to be trusted, at least not for situations that call for bulletproof safety, such as caching values in the compiler rather than rereading them, because the fields are readonly. Although C# and the CLR do a good job at verifying readonly/initonly are done right at the initialization site, there are still places where these guarantees break down. Thankfully the byref aliasing problem does not threaten thread-safety, but the union problem does. And in conclusion, I do have to imagine all of this will get fixed somewhere down the road, it's just a matter of when and where.

My article about Transactional Memory (TM) was picked up by a few news feeds recently.

If I had known this would occur, I would have written it with greater precision.  Because my article presents a mixture of technical challenges interspersed among more subjective and cultural issues, I am sure it is difficult to tease out my intended conclusion.  To summarize, I merely believe adding TM to a shared memory architecture alone is insufficient.

Indeed, I remain a big fan of transactions.  Atomicity, consistency, and isolation, and coming up with strategies for achieving all three in tandem, are part and parcel to architecting software.

After watching Barbara Liskov's OOPSLA Turing Award reprise, I decided to reacquaint myself with some old Argus papers this weekend.  It has been some time since I last read them.  Argus was Liskov's language for distributed programming and her follow-on to CLU.  As with most research done by brilliant people, the work was way ahead of its time, has appeared in ad-hoc incarnations and permutations over time, and remains relevant today.  This research is particularly interesting to work that my team is doing right now, especially its notion of guardians.  And it is relevant to the TM discussion too.

The Argus approach of using isolation to coarsely partition state and operations into independent bubbles, and then communicating asynchronously between the so-called guardians that are responsible for this state, is an architecture that is common among most highly concurrent programs.  This aids state management and fault tolerance.  Argus makes an interesting observation that, although guardians may be sent messages concurrently -- and indeed activities themselves may even introduce local concurrency -- manipulation of state can be done safely and even in parallel thanks to transactions.

The requirement is that messages are atomic and commute.  Transactions, it turns out, are a convenient way of implementing this requirement.

You will observe a similar architecture in other places, including in some languages that have adopted TM.  Haskell has moved in this direction.  Everything is purely functional and so, of course, no state is mutated in an unsafe way by default.  However, with the introduction of concucrrency comes mutable cells for message passing and with parallelism comes indeterminism.  You can push the state management problem up indefinitely, but at the top there are almost always mutable operations on real-world state (even if it is "just I/O").  Haskell programs have a safe architecture to begin with, and it is the intentional and careful addition of specific facilities that forces one to focus on the problematic seams.  One could say that Haskell starts clean and stays clean, versus most shared memory-based languages which start dirty and try to attain cleanliness (at least when it comes to concurrency).

Why aren't transactions sufficient, then, given that the I in ACID stands for Isolation?  You wouldn't model a database as one flat table in which each row is a single byte, however, would you?  As you begin to decompose your program into isolated state, your bubbles (or guardians) are the tables, and your objects are the rows.  This is just an analogy but I find it useful to think in these terms.  Taking a bunch of intermingled state and pouring transactions on top is not going to give you this nicely partitioned separation of state which has proven to be the lifeblood of concurrency.

Even once you've attained a more isolated architecture, however, transactions are not a panacea.  They are just one of many viable state management techniques in a programmer's arsenal, hierarchical state machines being another notable example.  And in fact, many of the problems I mentioned in the TM article are still worrisome even when you start from the right place.  From within a guardian, you may wish to enlist the aid of another unrelated guardian to perform a coordinated atomic activity, because a higher level invariant relationship between them must be preserved.  Or an application which composes multiple guardians may wish to do so atomically.  Even Argus required manual compensation for such things.  This can be solved in part by DTC.  But experience suggests that continuing to push the enlistment scope one level higher eventually leads to substantial problems.  A topic for another day, I suppose.

My primary conclusion is that TM is a great complement to highly concurrent programs, but only so long as you start from the right place.  The Argus and Haskell approaches are conducive to large-scale concurrency, but it is primarily because of the natural isolation those models provide; the addition of transactions address problems that remain after taking that step.  But without that first step, they would have gotten nowhere.

We use static analysis very heavily in my project here at Microsoft, as a way of finding bugs and/or enforcing policies that would have otherwise gone unenforced.  Many of the analyses we rely on are in fact minor extensions to the CLR type system, and verge on “effect typing”, an intriguing branch of type systems research that has matured significantly over the years.

Many of these annotations are done on methods, rather than types.  A few examples include:

1. [MayBlock] indicates that a method is free to call methods that might block.
2. [NoAllocations] indicates that a method is neither allowed to allocate, nor call another method that might allocate
3. [Throws(...)] indicates that a method is allowed to throw an exception of a type in the set { … }, or call other methods that may throw exceptions in the set { … }.
4. And so on.

It turns out there’s a general way for handling these annotations.  And indeed, you will quickly find that pursuing ad-hoc solutions to each independently leads to troubles.  We shall briefly look at the generalization.

We must first observe that each falls into one of two categories: additive or subtractive.  MayBlock and Throws are additive.  They say what is permitted.  NoAllocations, on the other hand, is subtractive, because the annotation declares what is not permitted.  This distinction, we shall see, is crucial.

First we can imagine that each distinct effect shown above has a distinct effect type.

The types EMayBlock, ENoAllocations, and EThrows correspond to the annotations above.  This will permit us to model effects using subtyping polymorphism.  We will use the usual notation, i.e. “S <: T” means “S is a subtype of T”, or “a S is substitutable in place of a T”.  For example, String <: Object.  Throws is special, because it has a type hierarchy of its own beneath the root type.  As you might guess, this hierarchy is infinite in size and is comprised of each possible permutation of exception types.

There are two special kinds of effects: the null effect (ENil), and a set of other effects (EMany).  The latter permits us to create a new, unique effect type merely by concatenating a list of other effect types.

Each method is then given an EMany effect type containing its full set of effect types.  For example:

[MayBlock, Throws(typeof(FileNotFoundException)), NoAllocations]
void M() { … }

Is given the distinct effect type EMany { EMayBlock, EThrows(typeof(FileNotFoundException)), ENoAllocations }.

We should make one generalization before moving on.  ENil ~ EMany { }.  In other words, having no effects is equivalent to a list of no effects.  Furthermore, EMany { } ~ EMany { ENil }.  In other words, having a list of no effects is equivalent to having no effects.

Now we are ready to weave everything together.  The main question confronting us is as follows: What is the subtyping relationship between the various effect types, including the null and list types?

The easiest to do away with is the EMany type.  Given two EMany types E and F, then E <: F if, for all effects T in E’s type set, there exists an effect type U in F’s type set such that T <: U.  In simpler terms, a list is a subtype of another list so long as all of its components are also subtypes of a component of the other.  This is very abstract, but we shall see soon why it is useful.

Now we get to see why the additive and subtractive distinctions are so important:

Given an additive effect type EAdditive, we say ENil <: EAdditive.

Given a subtractive effect type ESubtractive, we say ESubtractive <: ENil.

The first statement says that a method with no effects is substitutable for a method with additive effects, and the second says that a method with subtractive effects is substitutable for a method with no effects.  The corollaries are perhaps just as important.  A method with additive effects cannot take the place of a method with no effects, whereas a method with subtractive effects can.

For the simple single-effect case, effects depicted in this way represent points on a line, where ENil is zero, subtractive effects are negative integers, and additive effects are positive integers.  The lattice obviously becomes rather complicated as many effects accumulate.

Where does substitutability come up with respect to methods, anyway, you may ask?  The first is in determining which other methods can be called.  If a method M with effects E is trying to call another method N with effects F, this is permitted so long as F <: E.  The next is in virtuals and overriding.  A virtual with effects E may be overridden by a method with effects F so long as F <: E.  The following example illustrates this idea, in addition to the composition of the subtyping rules we have shown so far:

class C
{
    public virtual void M() {}
    [MayBlock, NoAllocations]
    public virtual void N() {}
}

class D : C
{
    [MayBlock, NoAllocations]
    public override void M() {}
    public override void N() {}
}

In this example, the four methods are given the following effect types:

• C::M gets EMany { ENil }, or just ENil.
• C::N gets EMany { MayBlock, NoAllocations }.
• D::M gets EMany { MayBlock, NoAllocations }.
• D::N gets EMany { ENil }, or just ENil.

What does all this gibberish mean?  Well it’s straightforward and intuitive, actually.

We are attempting to add the MayBlock and NoAllocations effects to the overridden M method which has none.  Because MayBlock is additive, this is illegal (someone might call C::M thinking the code will not block), whereas it is OK for NoAllocations (calls through D::M are assured no allocations will happen, even though calls through C::M are guaranteed no such thing).  Similarly, we are attempting to remove both effects from the overridden N method.  Because MayBlock is additive, this is OK (M isn’t required to block, even though calls through C::M may suspect it of doing so), whereas it is decidedly not OK for NoAllocations (calls through C::M will reasonable assume allocations do not happen, whereas D::M would be free to perform them).  It may take some thought to convince yourself that this is correct, but I hope that you find that it is.  All of this works because of the subtyping of effect types.

All of this works similarly with delegates.  The source delegate signature is akin to the base class in the above example, whereas the target method being bound to is like the override.

Things get a little more complicated when considering the EThrows effect.  It is additive, so it is of course true that ENil <: EThrows(*).  However, what if we have two different EThrows, and wish to inquire about substitutability of one in place of the other?  We can come up with a simple rule that is general purpose for all set-of-type kinds of effects.  Namely, consider two instances A and B of the same effect type:

Given an additive effect type EAdditive, then A <: B if, for all types T in A’s set-of-types, there exists a type U in B’s set-of-types such that T <: U.

Given a subtractive effect type ESubtractive, then A <: B if, for all types T in A’s set-of-types, there exists a type U in B’s set-of-types such that U <: T.

These sound quite similar, except that they end differently (i.e. T <: U vs. U <: T).  We may illustrate the additive case with EThrows; to illustrate the subtractive case, let us imagine we can declare a ENoAllocations effect type that specifies which precise types may not be allocated:

class A{}
class B : A{}

class C
{
    [Throws(typeof(Exception)), NoAllocations(typeof(A))]
    public virtual void M() {}
    [Throws(typeof(FileNotFoundException)), NoAllocations(typeof(B))]
    public virtual void N() {}
}

class D : C
{
    [Throws(typeof(FileNotFoundException)), NoAllocations(typeof(B))]
    public override void M() {}
    [Throws(typeof(Exception)), NoAllocations(typeof(A))]
    public override void N() {}
}

The results should not be surprising.  D::M overrides C::M’s exception list, by being more specific and declaring that FileNotFoundException is thrown instead of just Exception.  This is OK.  Whereas D::N overrides C::N’s list by being more general purpose, specifying Exception instead of FileNotFoundException.  This is clearly not OK.  The NoAllocations type works in exactly the reverse.  D::M attempts to prohibit allocations of B, but this is merely one possible subtype of the base method C::M’s declaration of A, and therefore this is illegal.  Whereas D::N ensures no instances of A are allocated, which of course subsumes the base method C::N’s declaration that no B’s are allocated.

Everything gets a little more interesting when you consider generics.  For example, how would we type a general purpose Map method?  (This pattern arises quite frequently.)  We would presumably want it to somehow “acquire” the effects of the delegate it invokes on all elements in a list.  For example:

U[] Map<T, U>(T[] input, Func<T, U> func);

This declaration is stronger than necessary.  The Func<T, U> class – prepackaged with the .NET Framework – does not have any effects on it.  So it may not, for example, bind to a method that has any additive effects like Throws on it.  This is rather unfortunate.

To solve this we could imagine treating effects with parametric polymorphism:

[Effects(E)]
U Func<T, U, [EffectParameter] E>(T x);

This fictitious syntax merely says that Func can be instantiated with an effect type E, and that the Func “method” itself acquires the effect E.  (Admittedly I should stop using faux-attribute syntax for illustrations since we’ve reached this level of language integration.)  Now Map can be declared as such:

[Effects(E)]
U[] Map<T, U, [EffectParameter] E>(T[] input, Func<T, U, E> func);

This says that Map has the same effects as the Func that is supplied as an argument.  It turns out that we may want to extend this further, by enabling symbolic manipulation of effects.  We may wish, for example, to specify that the Func is not allowed to block, by stating it does not have [MayBlock] in it.  You could imagine using something very similar to generic constraints to achieve this.  It is also interesting to allow concatenation of multiple effect types, both through partial and full specialization.  For example, Map above may clearly have effects of its own.  You also tend to want generic constraints like, 'where E : F', which of course just depends on the aforementioned subtyping rules.  And of course C# 4.0's co- and contravariance can be applied to effects too.

Anyway, I have probably gone beyond most readers’ interest level in this subject.  Things sure do get very interesting when you allow symbolic manipulation of effects.  They get even more interesting when you begin to think of types as having “permissible effects” attached to them.  However, the main thing I wanted to point out with this brief article is that this pattern arises quite frequently.  And despite everyone struggling through what seem to be odd corner cases as they develop ad-hoc solutions, there really is a sound generalization behind it all.  Many languages have first class effect typing, and I have found it liberating to think of many of these type system annotations through that lens.  Perhaps you shall too.

Sometimes you need to wait for something before proceeding with a computation.

Perhaps you need to know the value of some integer that is being computed concurrently.  Maybe you need to wait for the bytes to flush to disk before telling another process the file is consistent and ready to read.  Or you need to get that next row back from the database before painting it on the UI.  It could be that you need to wait for the missile to leave the bay before closing the bay door.  And so on.

And sometimes there’s simply nothing better to do while waiting for these things to happen other than to let the CPU halt (or let other processes on the machine run).  You need to twiddle your thumbs a bit, and exhibit a little patience.  Or at least your program does.  This is simply an unfortunate fact of life.

This manifests numerous ways in our programming models:

        1) Waiting on an event.
        2) Waiting to acquire an already-held lock.
        3) Finding that the GUI message queue is empty and doing a MsgWaitForMultipleObjectsEx.
        4) Finding that the COM RPC queue is empty and doing a CoWaitForMultipleHandles.
        5) Issuing an Ada rendezvous ‘accept’ and finding that no messages await you, thus blocking.
        6) Issuing an Erlang ‘receive’ and finding that no messages await you, thus blocking.
        7) Waiting on a .NET 4.0 task.
        8) Issuing a ContinueWith on a .NET 4.0 task.
        9) And so on.

There are three big distinctions to make about the characteristic nature of this waiting: namely, (1) what condition's establishment is being sought -- i.e. the reason for the wait, (2) whether multiple such conditions of interest may be waited on simultaneously, and, related, (3) whether waiting for said condition(s) necessarily means that the processing of some other conditions that may arise elsewhere, but require the blocked context to run, cannot occur.

I will be the first to admit that this statement is rather abstract.  But it really does matter.

For example, MsgWaitForMultipleObjectsEx is a pumping wait.  Not only do you wait for the occurrence of one of several events to get set, but the arrival of a new top-level message at the message queue (either GUI or COM RPC-related) causes immediate processing of that message, presuming the thread is blocked at that call at the time.  Although you can be deeply nested in some complicated code, you “jump” to the event loop to run the message handling code.  Vanilla WaitForMultipleObjectsEx works in a similar way vis-à-vis APCs, provided the wait is alertable.  This is quite different from a fully blocking non-pumping wait, which only waits for one or more very specific events, but does not dispatch messages simultaneously.

Win32 esoterica aside, the concepts appear elsewhere.  The moral equivalent in Ada or Erlang is to do a selective-accept or -receive, intentionally not dispatching certain messages that might arrive in the meantime.  (To be fair, you can also do this in COM with message filters.)  This often happens when you nest accepts and receives.  You may be capable of processing messages A-Z at the top-level tail recursive loop; but if that nested accept only knows about message kinds M and N, then there are 24 other kinds that will not be picked up in the meantime.

Not pumping for messages is dangerous.  And it can lead to deadlock if you pump for the wrong ones.  Like if you’re accepting M or N, yet the triggering of M or N depends on first processing some message K waiting in the queue.  COM RPCs with cycles run face first into this.  And/or not pumping can lead to responsiveness and scalability problems.  Perhaps M or N eventually does arrive, yet little old K needs to wait an indeterminate amount of time before it is seen.  Whereas we could have overlapped its processing.  This is why most STAs pump while waiting, and, similarly, why many Erlang processes consist of a main loop that is prepared to handle any message the process accepts at that top level loop.  They may seem very different but they are strikingly not.

Yet paradoxically pumping for messages is also dangerous.  You must predict all the kinds of messages that may reentrantly get executed, and your state at the point of the blocking call must be consistent enough to tolerate them.  (At least those that will actually happen.)  In COM STAs, this can be wholly unpredictable and indeed because the CLR auto-pumps on STAs the blocking points can be hidden.  Overly aggressively admitting messages may seem like the right thing to do, until you’ve wedged yourself into some unforeseen inconsistent state.  You can avoid this by making each message handler atomic; see Argus.  But if you can't or don't have the discipline to do that, or aren't quite sure, you must not pump.  You either avoid pumping altogether or you selectively pump messages that do not touch the state encapsulated by the pump.  Or you lock access to state with a non-recursive lock and run the risk of deadlock.

I have found it clarifying to think about blocking in event loop concurrency and state machine terms, advancing from one state to the next in between waits.  It’s a slippery model, but particularly when working in message passing systems that employ event loops, it can help to identify all the familiar problems with shared memory, blocking, and consistency.

Indeed it is interesting how blocking and non-blocking systems can rapidly approach each other.  Starting from either extreme tempts you to tiptoe closer and closer to the middle.  The familiarity of the other extreme tempts you.  Until, alas, you just might meet in the middle.