A blog about software – researching it, developing it, and contemplating its future.

A Publication! In Public!

with 7 comments

The team I work on doesn’t get much publicity.  (Yet.)

But recently some guys I work with submitted a paper to OOPSLA, and it was accepted, so it’s a rare chance for me to discuss it:

Uniqueness and Reference Immutability for Safe Parallelism

This is really groundbreaking work, in my opinion.  Introducing “readable”, “writable”, “immutable”, and “isolated” into C# makes it a quite different experience.

When doing language design work like this, it’s hard to know whether the ideas really hold up.  That’s one epic advantage of this particular team I’m on:  we use what we write, at scale.  From section 6 of the paper:

A source-level variant of this system, as an extension to C#, is in use by a large project at Microsoft, as their primary programming language. The group has written several million lines of code, including: core libraries (including collections with polymorphism over element permissions and data-parallel operations when safe), a webserver, a high level optimizing compiler, and an MPEG decoder. These and other applications written in the source language are performance-competitive with established implementations on standard benchmarks; we mention this not because our language design is focused on performance, but merely to point out that heavy use of reference immutability, including removing mutable static/global state, has not come at the cost of performance in the experience of the Microsoft team. In fact, the prototype compiler exploits reference immutability information for a number of otherwise-unavailable compiler optimizations….

Overall, the Microsoft team has been satisfied with the additional safety they gain from not only the general software engineering advantages of reference immutability… but particularly the safe parallelism. Anecdotally, they claim that the further they push reference immutability through their code base, the more bugs they find from spurious mutations. The main classes of bugs found are cases where a developer provided an object intended for read-only access, but a callee incorrectly mutated it; accidental mutations of structures that should be immutable; and data races where data should have been immutable or thread local (i.e. isolated, and one thread kept and used a stale reference).

It’s true, what they say there.

Here’s just a bit more:

The Microsoft team was surprisingly receptive to using explicit destructive reads, as opposed to richer flow-sensitive analyses (which also have non-trivial interaction with exceptions). They value the simplicity and predictability of destructive reads, and like that it makes the transfer of unique references explicit and easy to find. In general, the team preferred explicit source representation for type system interactions (e.g. consume, permission conversion).

The team has also naturally developed their own design patterns for working in this environment. One of the most popular is informally called the “builder pattern” (as in building a collection) to create frozen collections:

isolated List<Foo> list = new List<Foo>(); 
foreach (var cur in someOtherCollection) {
    isolated Foo f = new Foo();
    f.Name = cur.Name; // etc ... 
    list.Add(consume f); 
immutable List<Foo> immList = consume list;

This pattern can be further abstracted for elements with a deep clone method returning an isolated reference.

I firmly expect that eventually I will be able to share much more about what we’re doing.  But if you have a high-performance systems background, and if the general concept of no-compromises performance plus managed safety is appealing, our team *is* hiring.  Drop me a line!


Written by robjellinghaus

2012/11/02 at 14:06

Posted in Uncategorized

7 Responses

Subscribe to comments with RSS.

  1. Thanks, Rob…..have printed it out for Dad and I to read (and reread)….keep us on your list……Mom


    2012/11/04 at 09:05

  2. Looking forward to this “million lines of code” aka probably midori project, hope this will make it into a commercial project, sounds so innovative and promising! Coupled with a tightly optimized compiler this whole safe parallelism infrastructure seems a great step forward.

  3. “Midori” isn’t it you are working for? 🙂

    Hopefully.. it gets commercialized in near future. And, what is it going to replace eventually.. the current line of Windows OS? or, more likely, will it host Azure?

  4. […] ZDnet-Bloggerin Mary Jo Foley meldet. Sie wurde darauf hingewiesen, dass die Microsoft-Entwickler Rob Jellinghaus und Joe Duffy, von denen bekannt ist, dass sie an Midori arbeiten, über den Artikel gebloggt […]

  5. […] team claims it's written millions of lines of code, creating a web server, an MPEG decoder, and many other applications. This, in Microsoft's usual […]

  6. It would be really cool if this could be retrofitted to some olde software that’s still in use and badly needs performance improvements, but is 1) used by a very small group of people, so it’s not attractive as a commercial development target; and 2) has to be verified to match single-threaded operation in the reference implementation; and 3) the original is in Fortran!

    Mike B

    2012/12/03 at 18:19

  7. That’s a dense, dense paper. Only a few pages in, but how can isolation be recovered after conversion to writeable without tracking? I can see it if the whole object graph gets inspected, but at first glance that would seem as costly as tracking.

    Must read more! Awesome ideas.


    2012/12/06 at 12:16

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: