Skip to main content

Posts

Showing posts from 2011

Software Transactional Memory in Pure C#

Concurrent programming is a very difficult problem to tackle. The fundamental issue is that manual locking is not composable , which is to say that if you have two concurrent programs P0 and P1 free of deadlocks, livelocks and other concurrency hazards, and you try to compose P0 and P1 to create a program P2, P2 may not be free of concurrency hazards. For instance, if P0 and P1 take two locks in different orders, then P2 will deadlock. Needless to say, this is a serious problem because composition is the cornerstone of all programming. I've been toying with some ideas for software transactional memory (STM) in C# ever since I started playing with FRP and reactive programming in general. The problem in all of these domains is fundamentally about how to handle concurrent updates to shared state, and how to reconcile multiple, possibly conflicting updates to said state. Rx.NET handles concurrency essentially by removing the identity inherent to shared state. An IObservable<T&g

Type Unification Forbidden - More C#/CLR Irritations

I've written about quite a few irritations of C#/CLR, including asymmetries in CIL , oddly unverifiable CIL instructions , certain type constraints are forbidden for no reason , delegate creation bugs , the lack of higher-kinded types , equality asymmetries between events and IObservable , generics/type parameter problems , lack of usable control over object layouts , and just overall limitations of the CLR VM . I've just smack into yet another annoying problem: type parameter unification is forbidden . The Microsoft Connect bug filed in 2004 was closed as By Design . Here's a simple code fragment demonstrating the problem: class ObserveTwo<T0, T1> : IObservable<T0>, IObservable<T1> { } This will fail with the error: 'ObserveTwo<T0,T1>' cannot implement both 'System.IObservable<T0>' and 'System.IObservable<T1>' because they may unify for some type parameter substitutions This is frankly nonsense. What's

Ad-hoc Extensions in .NET

A recent discussion on LtU brought up a common limitation of modern languages and runtimes. Consider some set of abstractions A, B, ..., Z that we wish supported some custom operation Foo(). Languages like C# give only two straightforward possibilities: inheritance and runtime type tests and casts. Inheritance is straightforward: we simply inherit from each A, B, ..., Z to make A_Foo, B_Foo, ..., Z_Foo, with a custom Foo() method. Unfortunately, inheritance is sometimes forbidden in C#, and furthermore, it sometimes prevents us from integrating with existing code. For instance, say we want to integrate with callback-style code, where the existing code hands our program an object of type A. We can't call Foo() on this A, because it's not an A_Foo, which is what we really wanted. This leaves us with the undesirable option of using a large set of runtime type tests. Now type tests and casts are actually pretty fast , faster than virtual dispatch in fact, but the danger is i

The Most General Concurrent API

Concurrent programming is hard, and many abstractions have been developed over the years to properly manage concurrent resources. The .NET base class libraries have mutexes, spinlocks, semaphores, compare-and-set (CAS) instructions, and more. The Problem Unfortunately, many of these standard abstractions are rather opaque, so predicting their behaviour is difficult, and enforcing a particular thread schedule is nearly impossible. For example, consider the issue of "fairness". Many abstractions to deal with threads are not fair, which is to say that they are not guaranteed to release threads in FIFO order, so a thread could starve . Furthermore, these opaque abstractions do not allow the application to easily specify domain-specific scheduling behaviour. Suppose threads T0, T1, and T2 are blocked on a resource X, in that order. X becomes available, and according to FIFO order, T0 should acquire control next. However, a domain-specific requirement may state that T2 should

ThreadScoped<T> The Next Generation

Jeroen Frijters helpfully pointed out that the CLR implements some hard limits on nesting generics, which is 99 for .NET 4 based on my tests. My previous implementation of ThreadScoped<T> was thus limited to 99 instances. Not very useful! The solution is actually quite simple, which I briefly outlined on Jeroen's blog: add more type parameters and use a simple base-99 counting scheme to generate new instances. Each additional type parameters thus increases the permutations 99 fold. One type index parameter yields 99 1 instances, two type index parameters yields 99 2 instances, three type index parameters yields 99 3 , and so on. No one in the foreseeable future will require more than 99 3 , which is almost a million thread-local variables, so I've added two more type index parameters to make Ref<T0, T1, T2> . The instance allocation function is now: internal override ThreadScoped<T> Allocate() { // If 'next' is null, we are at the end of th

Faster Thread-Local Data with ThreadScoped<T>

Awhile ago, Jeroen Frijters blogged about .NET 4's new ThreadLocal<T>, and how it was implemented. It was based on a neat generics trick exploiting the fact that the CLR does not erase types. Indexing a generic type X with a type T, means X<string> has distinct static and thread-local fields from say, X<int>. I've actually used this trick before to implement a type of safe reflection. Jeroen's sample implementation exploiting this trick for thread-local instance variables seemed far too complicated however, and it suffered from a number of limitations that he notes in his post. If Microsoft's implementation was even more complicated as was claimed, I wasn't confident it would perform very well at all. I decided to do my own implementation, without conforming the ThreadLocal<T>'s interface since I have very specific applications in mind. ThreadScoped<T> As I suspected, my implementation was considerably simpler , coming in a

Idioms in C# with LINQ

There's a great post on implementing idioms with LINQ, and the example application was to implement formlets, as WebSharper does for F#. Tomas's post is well written, so if you're unclear on the above concepts I recommend reading it first before proceeding with this article. The claim in that post is that idioms can only be encoded via LINQ's 'join' operators. While strictly true if you stick to all the LINQ rules, because LINQ queries are just naive syntactic transforms you don't have to follow the rules. You can thus exploit this to hijack the signatures for the SelectMany overloads to yield idiom signatures. It's not all sunshine and roses though, as there are consequences. Overview LINQ is a standard set of methods one can implement that the C# compiler can use to provide "query patterns". This query: var foo = from x in SomeFoo from y in foo.Values select y; is translated by the C# compiler to: var foo = Some

IObservable<T> and Delegate Equality

Equality and identity are often intermingled in the .NET framework. .NET delegates correctly implement a straightforward structural equality , where if two delegates are equal if they designate the same method and the same object, regardless of whether the delegate is a unique instance: class Bar { public void Foo(int i) { } } var bar = new Bar(); Action<int> a1 = bar.Foo; Action<int> a2 = bar.Foo; Console.WriteLine("Delegate Equality: {0}", a1 == a2); // prints: // Delegate Equality: True However, an IObservable<T> created from delegates does not respect structural equality, and reverts to an identity criterion: // use a1 and a2 from previous code sample var o1 = Observer.Create<int>(a1); var o2 = Observer.Create<int>(a2); Console.WriteLine("Observable Equality: {0}", o1 == o2 || o1.Equals(o2) || EqualityComparer<IObserver<int>>.Default.Equals(o1, o2)); //prints: // Obs

Open Instance Delegate for Generic Interface Methods

Ran into a snag when developing the latest abstraction for Sasa. The problem is distilled to its simplest form in this Stack Overflow question. In summary, while the CLR supports open instance delegates to interface methods , and supports delegates to generic interface methods, it does not seem to support the composition of the two, ie. an open instance delegate to a generic interface method. The following trivial example fails when creating the delegate with a NotSupportedException: interface IFoo { void Bar<T>(T j); } class Foo : IFoo { public void Bar<T>(T j) { } } static void Main(string[] args) { var bar = typeof(IFoo).GetMethod("Bar") .MakeGenericMethod(typeof(int)); var x = Delegate.CreateDelegate(typeof(Action<IFoo, int>), null, bar); } However, the CLR does support open instance delegates to generic class methods. For some reason interfaces are singled out here, and it'