Turing Machines are Programs

VB11 Wish List - Part 1

2010-04-11T14:50:00.004-03:00

With the release of visual studio 2010 coming this week, it's high time to publish wish lists. The Visual Basic .Net of today has come a long way from the BASIC of yonder old days, and not all of it involves making the name longer. However, there's still so much that could be done, or could be done better. These are my wishes and my ideas, and hopefully they will affect Microsoft's decision process in some small way. Unfortunately, I have so many ideas there's no way they could all be implemented. Oh well, here we go!

#1) Public-Get/Private-Set and ReadOnly Auto Properties

One of the features introduced in VB10, and imported from C#, is auto properties. Unfortunately, VB10 auto properties are quite limited compared to their C# counterparts. It is impossible to specify an auto property with a private setter and a public getter (Oh well, at least it's only the most common case (sigh)). It's also not possible to create a ReadOnly auto property, which is odd considering auto properties otherwise act like variables (mostly).

I want the ability to define auto properties with different access levels on the getter and setter and ReadOnly (fixed at construction) auto properties. I suggest the following syntax:


    'Public getter, private setter
    Public Get Private Set Property Value As Integer
    'Fixed after  construction time
    Public ReadOnly  Property Value As  Integer

#2) Flexible 'Implements'

You've probably had this happen to you before: you want to implement something from an interface, but your class doesn't quite match. You have a function but you need a property, you have a property but you need a ReadOnly property, you have a function but you need a subroutine or a function with a weaker return type, etc, etc. You work around the problem by implementing the interface member using a private function/sub/property which delegates to your existing stuff.

All of these not-really-a-mismatch cases should be allowed. The compiler should transparently implement the boilerplate code to match the interface member to the implementing construct.

#3) Infer Redundant Operators

Implementing a comparison operator without its partner currently causes a compile error. If you define '=' but not '<>', or '<' but not '>', or '<=' but not '>=', or vice versa, then you get a completely unnecessary compile error. I hate that compile error. The missing operator is trivial: invert the arguments for an ordering operator or invert the result for an equality operator. The compiler should be doing these trivial transformations for you. Defining an equality operator and an ordering operator should give you all of the comparison operators, no questions asked. At the very least, operators' partners should be inferred.

#4) Comparison Operator: <=>

Ruby has a very nice comparison operator: <=>. It returns the sign of comparing two values: -1 when the first argument is less, +1 when it is greater, and 0 when it is equal. I'd like to see it in VB/.Net.


    Select Case value1 <=>  value2
        Case -1
        Case  0
        Case +1
    End Select

#5) Iterator Blocks

I'm very surprised this didn't make it into VB10. I know the VB team had excellent ideas about it at least as far back as 2008. Iterator blocks? Awesome!


    Function  FromTo(ByVal low As Integer, ByVal high  As Integer) As IEnumerable(Of Integer)
        Return Iterator
                   If low <= high Then
                        Return low
                       Return Each FromTo(low  + 1, high)
                   End If
                End Iterator
    End Function

#6) Linq Zip Operator

I often want to zip sequences together, but I have to break the linq flow and use explicit calls to Enumerable.Zip. There should be a linq operator for zipping:


    Dim  evenItems = From item In  items
                     Zip index In  Naturals
                     Where index Mod  2 = 0
                     Select item

#7) IDisposable Event Subscriptions

You should clean up your event handlers. Failure to do so can result in memory leaks (handlers can't be garbage collected while a long-lived event dispatcher has a reference to them). Just ask the Princeton team from the 2007 DARPA challenge, because they had exactly this type of memory leak. So, ideally, removing event handlers should be as painless as possible.

Unfortunately, removing event handlers isn't painless. First, every properly removed handler requires three lines (store delegate, add delegate, remove delegate). You must store the delegate you are going to add and remove, because otherwise you will try to remove an equivalent-but-different delegate and end up removing nothing. Second, every RemoveHandler line is an identical copy of an AddHandler line, except you replace the 'Add' prefix with 'Remove'. Finally, you add and remove events in different parts of the code, which makes it harder to keep the add/remove lines synced.

In order to overcome the far-away-sync pain, I started using the following pattern for event subscriptions: package the RemoveHandler call into a delegate, and package that inside an IDisposable. You end up with a 'subscription', which can be disposed to remove the event handler. Therefore, instead of using RemoveHandler, you dispose the subscription. This enormously simplifies removing groups of event handlers, because you can keep all the subscriptions in a list of IDisposable. For example:


    Dim  handler = AddressOf SomeMethod
    AddHandler  SomeObject.SomeEvent, handler
    Me.subscriptions.Add(New DelegatedDisposable(Sub() RemoveHandler  SomeObject.SomeEvent, handler))
    ... elsewhere, in the disposal code  ...
    For Each subscription In Me.Subscriptions
        subscription.Dispose()
    Next

Unfortunately, you still have to track the delegate (albeit in a hoisted local instead of a class member), and you still have to repeat yourself in the RemoveHandler call. All of this would be solved if 'AddHandler' returned an IDisposable which, when disposed, removed the added handler. There would be no more need to track the delegate or repeat the handler arguments. Instead of three lines of code per handler, you end up with just one:


    Me.subscriptions.Add(AddHandler  SomeObject.SomeEvent, AddressOf  SomeMethod)

To Be Continued

Linq to Tasks

2010-03-12T18:06:00.000-04:00

One of the more interesting properties of the Linq syntax is that, at heart, it has nothing to do with sequences or XML or SQL. Linq is a really syntax for performing operations with monads, and you can add your own types to it relatively easily. (For the uninitiated: a monad is essentially a wrapper class plus a way to transform functions to use wrapped values instead of normal values). Linq works with sequences because sequences are an extremely common Monad, and so the linq-to-list stuff is implemented as part of .Net. In this post, I'm going to show you an example of adding your own Linq-to-X functionality.

Tasks are a new feature in .Net 4.0. A task represents an asynchronous operation, such as a function running on another thread, and provides methods for working with the eventual result. You can use the ContinueWith methods to chain tasks together, feeding the eventual output of one task into the input of another task. For our purposes, the important thing is that tasks are a monad: they wrap a value, and you can modify functions to operate on tasks instead of normal values (using ContinueWith).

Since tasks are a type of monad, we can use them with Linq. All we have to do is define the necessary extension methods: Select and SelectMany. Select is the function used when you have a single 'From' line in your query, while SelectMany is used when there are multiple 'From' lines. Our task-version of Select will take a task and a function, and return a task for the function's eventual result after being given the task's eventual value. SelectMany is essentially the same thing, but with two tasks and two functions.

    Imports System.Threading.Tasks
 
    Public Module LinqToTasks
        <Extension()>
        Public  Function [Select](Of  TArg, TResult)(ByVal task As Task(Of TArg),
                                                    ByVal func As  Func(Of TArg, TResult)) As Task(Of TResult)
            Return  task.ContinueWith(Function(t)  func(t.Result), TaskContinuationOptions.OnlyOnRanToCompletion)
        End  Function
 
        <Extension()<
        Public  Function SelectMany(Of  TArg, TMid, TReturn)(ByVal task As Task(Of TArg),
                                                            ByVal projection1 As  Func(Of TArg, Task(Of TMid)),
                                                            ByVal projection2 As  Func(Of TArg, TMid, TReturn)) As Task(Of TReturn)
            Return  task.Select(Function(value1)  projection1(value1).
                        Select(Function(value2)  projection2(value1, value2))).Unwrap
        End Function
    End Module

I know that doesn't seem like a lot of code, but that's all of it. We can now use the linq syntax on tasks. But keep in mind that we didn't implement many of the operators, like "where" (what would that even mean for a task?). Here are some examples of using the linq syntax on tasks:

Example #1: Returns a task that evaluates to 35 after five seconds:

        Public  Function TaskTest() As  Task(Of Int32)
            Dim t = New TaskCompletionSource(Of Int32)
            Call  New System.Threading.Thread(Sub()
                                                  System.Threading.Thread.Sleep(5000)
                                                  t.SetResult(5)
                                              End Sub).Start()
            Return  From value In  t.Task
                    Let squared = value * value
                   Let  doubled = value + value
                   Select squared  + doubled
         End Function

Example #2: Returns a task that evaluates to 20 after ten seconds:


        Public  Function TaskTest2() As  Task(Of Int32)
            Dim t = New TaskCompletionSource(Of Task(Of Int32))
            Call  New System.Threading.Thread(Sub()
                                                  System.Threading.Thread.Sleep(5000)
                                                  Dim t2 = New TaskCompletionSource(Of  Int32)
                                                  t.SetResult(t2.Task)
                                                  System.Threading.Thread.Sleep(5000)
                                                  t2.SetResult(1)
                                             End Sub).Start()
            Return  From taskValue In  t.Task
                    From value In  taskValue
                    Select value * 20
        End  Function

As you have seen, allowing linq syntax on a type is as easy as implementing extension methods for the operators. A good learning exercise is to implement the linq operators for the non-generic version of IEnumerable (hint: all the functions involve enumerating). There are tons of types you can linq-ify: collection types, nullables, Lazy<t>, delegates like Func<t>, etc, etc, etc and etc. Try not to overdo it.

Post-Mortem of a Job Application

2010-03-05T13:29:00.004-04:00

I applied for a job recently, and was asked to write a small clone of Arkanoid (aka Breakout) using C++/DirectX. My C++ was rusty and the last DirectX stuff I did was five years ago and in VB6, but I figured I might as well try. At least it would refresh my C++ and force me to learn some DirectX. Unfortunately, I never managed to finish the game (on time). My lack of familiarity caused difficulties but, looking back, I can see that familiarity was not the issue. Learning sucked up some time, but the real time sink came about because of a design decision made only three hours into the project: I decided to write a Rational class instead of using floating point values.

Since this was a job application, I didn't want to do the bare minimum. I came up with the idea to record 'ghosts', so you could race against yourself. If I had the time, I could even feed the ghost data in live from another game for some relatively simple networked multiplayer. Thinking about how I would implement this, I remembered that floating points are not reliable in terms of consistency. Small optimizations made by the compiler, and differences across machines, can make the results of even simple additions come out slightly differently. That could be a problem, so I decided to write a Rational class and use it instead of floating points. That way I could guarantee consistency across machines.

At the beginning, I was reaping benefits. The rationals weren't as fast as floats, since constructing one involved computing a gcd, but the game wasn't even close to taxing the CPU. They even made the physics nice and exact, because all the 2d vector operations I used are closed over the rationals (No rounding errors. At all!). For example, this code computes the *exact* intersection point and normal of a moving point into a line segment:

 
//[example note: Vector2 is an x/y pair  of Rationals. CollisionPoint is a location/normal pair which can be  empty for no collision]
CollisionPoint CollisionPoint :: PointIntoLine(const Vector2 p, const  Vector2 dp,
                                                const Vector2 q1, const  Vector2 q2) {
     assert(dp != Vector2(0, 0));
    assert(q1 != q2);
 
    //Useful  intermediate values
    Vector2 p1 = p;
    Vector2 p2 = p + dp;
    Vector2 dq = q2 - q1;
    Rational f1 = q1.Cross(q2);
    Rational f2 = p1.Cross(p2);
 
    //Intersection  point (of lines extended to infinity)
    Rational d = dp.Cross(dq);
    if (d  == 0) return CollisionPoint(); //no collision due to parallel lines
    Rational cx = (f1*dp.X() -  f2*dq.X())/d;
     Rational cy = (f1*dp.Y() - f2*dq.Y())/d;
    Vector2 intersectionPoint =  Vector2(cx, cy);
 
    //Confirm that the intersection  point is within the segments
    if  (Median(p1.X(), cx, p2.X()) != cx || 
        Median(p1.Y(), cy, p2.Y()) != cy  ||
         Median(q1.X(), cx, q2.X()) != cx ||
        Median(q1.Y(), cy, q2.Y()) != cy)  return CollisionPoint(); //missed
 
    //return the  point of impact and the normal of the line the at point of impact
    return  CollisionPoint(intersectionPoint, - dp.PerpOnto(q2 - q1));
}

The happy times continued until I hit an assert: "denominator < 0". I had decided that a rational's negative sign must always be on the numerator, and put an assert in the constructor to enforce this. Upon first seeing the error, I thought I had made some stupid error in one of the operator functions. Unfortunately, what had happened was far more insidious: integer overflow.

The thing to understand about rationals is that performing operations on them tends to make them 'share' their factors. If you add a/b and c/d, you get (ad + bc)/(bd), which almost always has a larger denominator and numerator even after removing the gcd. In the worst case each addition will square the numerator and denominator, and you only have to square five times to go from 2 to 2^32 and cause an overflow. Well guess what: a physics function involves way more than five additions, not to mention other operations.

I tried to smooth over the problem by rounding, but the problem kept happening. I rounded more aggressively, but it kept happening. Eventually I had rounding statements on practically every other line outside of the physics functions, but it still kept happening. Even my goat sacrifice to Apollo didn't work (maybe he doesn't like goats?). You could pick a physics function at random, give it touchy input, and cause an assertion. To make matters worse, all this tinkering and rounding kept introducing small bugs. Eventually I ran way over on time, and gave up.

If I had gone with the tried-and-true floating points, I would have finished with a potentially-maybe-slightly-out-of-sync ghost, instead of not finishing at all. The lesson I'm taking from all of this is that I shouldn't be experimenting with ideas when I'm on the clock, unless it's necessary. Sometimes they work, but when they don't the cost is too high. Perhaps, now that there's no time limit, I'll rewrite the rationals to use BigIntegers in order to guarantee there are no overflows. That could be an interesting side project.

Asymptotic Notation is Complex

2010-01-04T17:34:00.004-04:00

Have you ever struggled with Big-O notation? I used to. If I saw "n = O(n^2)", I perceived "n equals O applied to n^2". It took time to train my mind to instead perceive "n is asymptotically less than n^2". It never caused any serious problems, it was just an incredibly annoyance. I used to think I was the problem, but now I realize the notation was the problem. In large part this realization comes from reading "The Design of Everyday Things", which talks about people blaming themselves for the failings of the common objects around them. It's time to face facts: Big-O notation sucks.

There are two main problems with Big-O notation: it looks like an equality (it's not), and the symbols are arbitrary (w.r.t. the rest of math). The first problem is by far the worse. Big-O notation is meant to express an ordering, not an equality. Using an equality to represent an ordering is a travesty of usability. It encourages you to make contradictory proofs like: 1 = O(1), 2 = O(1), therefore 1 = 2. You might as well switch a car's gas and brake pedals. The second problem is a learnability issue. If I know what Big-O means, and I see a Big-Omega, I can't infer what that means. I need to memorize all five symbols (o, O, θ, Ω, ω), and their meaning (Do you know what they all mean?). These problems have real consequences. There are many perpetually renewed questions on CS forums about the notation for asymptotic complexity, instead of about asymptotic complexity itself.

Since Big-O notation is so bad, let's design a replacement. We want to express an ordering, so we will use the standard ordering operators (<, <=, =, >=, >). We want it to look distinct, so we'll modify the operators in some way (eg. prefix them with an @ for asymptotic). That's it! The new notation is:

[F(x) = o(G(x))] === [F(x) @< G(x)]

[F(x) = O(G(x))] === [F(x) @<= G(x)]

[F(x) = θ (G(x))] === [F(x) @= G(x)]

[F(x) = Ω (G(x))] === [F(x) @>= G(x)]

[F(x) = ω (G(x))] === [F(x) @> G(x)]

Do you see how much clearer it makes the whole affair? It is now obvious that we are dealing with an ordering, obvious that [F(x) @<= G(x)] is the opposite of [F(x) @> G(x)], and obvious that [F(x) @= G(x)] is equivalent to [F(x) @<= G(x) and F(x) @>= G(x)]. All of the non-obvious parts have been isolated into the '@' symbol. In fact, I bet the notation just taught some people what little-omega (ω) means.

Here are some examples, using the above notation:

1 @<= 2

1 @= 10000

1 @< n

2*n @<= n

n^2 @<= n^10000

2^n @> n

3^n @> 2^n

Isn't that much nicer than Big-O notation? I hope that something similar to the above will replace Big-O in the future. I'm tired of telling people what Big-Omega means.

As a closing note, I want to point out how awkward the usual asymptotic complexity definitions are. Proving [Ǝc>0,e>0.∀x>e.F(x)<=c*G(x)] is usually a lot harder than proving lim(x to inf)(F(x)/G(x)) converges.

Solution - Asymmetric Latency

2009-12-30T13:36:00.004-04:00

The robots cannot figure out which room they are in, and they cannot distinguish the symmetric case from asymmetric cases. They can measure the round trip time, but never the one-way trip time.

Consider that the robots' actions are determined entirely by previously sent and received messages. Delay all messages by five seconds, and a robot's response will be five seconds later. Therefore, if we delay all incoming messages by five seconds, and accelerate all outgoing messages by five seconds, the net delay on the response is 0 seconds. Changing the symmetric case of 2s/2s to 1s/3s will have no effect on the robots' actions because the net delay is unchanged. They cannot tell the cases apart.

It is easier to understand this proof visually. Suppose the delays were equal. Then the propagation of messages might look like this:

Changing the one-way delay while holding the round-trip time constant is equivalent to sliding one of the timelines. The exact same case, except with all of the delay in one direction, looks like this:

Notice that, from the robots' perspective, both cases are equivalent. A2 arrives the same amount of time after A1, B2 arrives the same amount of time after B1, etc. In fact we can make one of the directions have a negative delay (go back in time) and the robots still can't tell the difference (the round trip time is still positive)!

Puzzle - Asymmetric Latency

2009-12-23T02:18:00.001-04:00

Suppose two robots are placed in separate isolated rooms, called A and B. They can communicate, but the communication delay is not symmetric: it takes one second for a message to travel from room B to room A, but three seconds for a message to travel from room A to room B. The robots do not know which room they are in, and they do not have synchronized clocks. The only information they share is some preconceived plan/program for sending messages and responses.

Questions:
1) Can the robots figure out which rooms they are in?
2T) If so, could they figure out the exact values of the one way latencies?
2F) If not, could they at least distinguish cases where the latency is asymmetric from cases where the latency is equal both ways?

The Assumptions We Make

2009-11-10T21:01:00.002-04:00

I loved my algorithms courses in university. The material just 'clicked' and I did extremely well. But, one day awhile after I had finished the course, a thought about hashing occurred. I realized I had been making some very serious assumptions when analyzing algorithmic complexity. This post covers two of those assumptions.

The thought, restructured to actually follow a logical argument, goes something like this: hash tables can't be constant time. There's just no way. If a hash function takes constant time then its output has constant size. If the output has size N, then a table using that output has maximum size 2^N. If the table has a maximum size then we can overflow it by just adding more and more items (ie. it will eventually degenerate into linear time searches of the bins). What's going on?!

Constant Word Size

The constant word size assumption is the assumption that, even though you may have an unbounded number of unique items, they can still have constant size and can still be manipulated in constant time. Copying, comparing, swapping, and a bunch of other operations we often assume are constant time would necessarily become more expensive with huge input sizes.

Suppose you want to sort 2^2048 items (clearly this is a thought experiment!). If each of those items is unique, they must each have a unique binary representation. So, on average, each item must use at least 2048 bits. It suddenly becomes clear that comparing items can't be O(1), but must be at least O(lg n) [because the items have O(lg n) bits].

Let's analyze merge sort using this new realization. It should be immediately obvious that merging becomes more expensive: merging two sublists of size L from a list of size N requires O(L * lg n) time. Since we must merge sublists whose combined size is O(N) for O(lg n) levels before the list is sorted, merge sort will take O(N * (lg n) * (lg n)) time. Wait, what?! Merge sort is O(n lg n), not O(n lg^2 n)! What's going on?!

What's going on is the constant word size assumptions. The O(n lg n) bound actually applies to the number of comparisons you have to perform, not the total computational time. They just happen to coincide exceedingly well in practice (eg. I doubt anyone will ever actually sort 2^64 unique items, certainly never 2^128 unique items).

Essentially every algorithm has a hidden theoretical O(lg n) word-size factor hidden away. Once I realized this, my constant-time hashing dilemma went away. It's the exact same issue, except I was focusing on the output size instead of the input size.

RAM Model vs Physics

Perhaps the most ingrained assumption is the random-access memory model, where memory is unbounded with a constant access time. Unlike the constant word size assumption, this assumption was at least stated in my algorithms course. But reality is, of course, not so forgiving.

You can only fit so much information into a given area, and distance from the processor lower bounds the time it takes to retrieve a bit of information. A sphere with volume N has radius O(N^(1/3)), so accessing a particular bit of data is not just O(lg n), it's O(n^(1/3))! [I remember reading a black hole will eventually form if you exceed O(surface area), so it could even be O(n^(1/2))!]

I don't even want to think about what that does to the time complexity of sorting or hashing.

Summary

It's a bit unsettling to realize I'd been ignoring all these logarithmic factors, and that no one had ever mentioned them to me. Oh well, at least it doesn't matter in practice... Actually, the word size of processors has actually exceeded the increases in the size of data, subtly reinforcing the constant-size assumption.

.Net Design Mistakes - Streams

2009-09-28T16:50:00.000-03:00

For the most part, .Net is a great framework. But it has its share of "WTF?" classes and design decisions. In this series I will cover (vent) these objective (subjective) faults. Today I am covering the mess better known as System.IO.Stream: a class trying to be five interfaces at once. Let's dive right in and cover the major problems.

Problem #1: Tedious to Implement

Suppose I want to implement a stream that flips the bits of a substream. Sounds pretty simple, but here is what comes out:


 Public Class BinaryNotStream
     Inherits IO.Stream
     Private ReadOnly substream As IO.Stream
  
     Public Sub New(ByVal substream As IO.Stream)
         If substream Is Nothing Then Throw New ArgumentNullException("substream")
         If Not substream.CanRead Then Throw New ArgumentException("substream")
         Me.substream = substream
     End Sub
  
     Public Overrides Function Read(ByVal buffer() As Byte, ByVal offset As Integer, ByVal count As Integer) As Integer
         Dim n = substream.Read(buffer, offset, count)
         For i = offset To offset + n - 1
             buffer(i) = Not buffer(i)
         Next i
         Return n
     End Function
  
     Public Overrides ReadOnly Property CanRead As Boolean
         Get
             Return True
         End Get
     End Property
  
     Protected Overrides Sub Dispose(ByVal disposing As Boolean)
         If disposing Then
             substream.Dispose()
         End If
         MyBase.Dispose(disposing)
     End Sub
  
     Public Overrides ReadOnly Property CanSeek As Boolean
         Get
             Return False
         End Get
     End Property
     Public Overrides ReadOnly Property CanWrite As Boolean
         Get
             Return False
         End Get
     End Property
     Public Overrides Sub Flush()
     End Sub
     Public Overrides ReadOnly Property Length As Long
         Get
             Throw New NotSupportedException()
         End Get
     End Property
     Public Overrides Property Position As Long
         Get
             Throw New NotSupportedException()
         End Get
         Set(ByVal value As Long)
             Throw New NotSupportedException()
         End Set
     End Property
     Public Overrides Function Seek(ByVal offset As Long, ByVal origin As System.IO.SeekOrigin) As Long
         Throw New NotSupportedException()
     End Function
     Public Overrides Sub SetLength(ByVal value As Long)
         Throw New NotSupportedException()
     End Sub
     Public Overrides Sub Write(ByVal buffer() As Byte, ByVal offset As Integer, ByVal count As Integer)
         Throw New NotSupportedException()
     End Sub
 End Class

Allow me to summarize my reaction to this: AAAAAAAAAAAAAAAUUUUUUUUUUUUUUUUUUUUUUGGGHHH! Half of the code is throwing NotSupportedExceptions (which is appropriate!)! Pick almost any stream class and you'll find this "NotSupported" boilerplate code. It is a pain to write, a pain to read, and guarantees even dead simple stream class are at least a few dozen lines.

Problem #2: Guess the Type

It boggles the mind that a class must call itself a 'stream' when it can't actually do two thirds of the things a 'stream' does. There is no way to tell the type system a class is a "readable" stream, and no way to require a readable stream parameter. When you implement a function that accepts a stream, you must check that the stream supports reading by querying CanRead. Otherwise, an exception will be thrown when you try to use the stream (possibly much later). Technically, a stream could even change from readable to writable during execution.

Many .net streams change their readability based on arguments given to their constructor. For example, the file stream is not a readable stream and it is not a writable stream. The file stream is a "readable and/or writable" stream (depending on the open type specified). Similarly, the compression streams are "readable xor writable" streams (when compressing you may only write and when decompressing you may only read).

Because of this type flexibility, many of the stream classes have too many responsibilities. Poor DeflateStream has to both compress and decompress data, even though those operations have very different behaviours. Similarly, FileStream has to enforce read/write permissions at runtime instead of just relying on the type system.

Problem #3: Redundant Redundancy

First, streams have a Position property and a Seek method and both have to be implemented, despite the fact that Seek can be implemented entirely in terms of Position and Length. Every time you implement a seekable stream, you re-implement Seek exactly the same way as last time. What a waste of code, and what a great way to introduce blind copy-paste bugs.

Second, streams have an overridable Close method and a Dispose method. Here are their implementations in IO.Stream according to Reflector:


         public virtual void Close() {
             this.Dispose(true);
             GC.SuppressFinalize(this);
         }
         public void Dispose() {
             this.Close();
         }

I think they assumed programmers would find it easier to understanding "closing" a stream as opposed to "disposing" a stream. This was a bad idea. Not only does it create confusion (is disposing equivalent to closing?) and add cruft, it implies you can later re-"open" the stream (you can't). Actually, this issue was mentioned in a Microsoft channel 9 show about the upcoming Linq-to-Events/Reactive-framework (as one of the reasons they decided to only use Dispose).

Problem #4: Not an Interface

Extension methods didn't exist when the stream class was designed and implemented, so the only way to include derived methods (eg. ReadByte uses Read) 'within' a type was an overridable class (I am guessing at Microsoft's reasoning, of course).

I don't really fault Microsoft for this problem: they probably chose the best option at the time. However, times have changed and there are downsides to using classes instead of interfaces. Classes don't allow multiple inheritance, which is probably why there is a single stream type instead of multiple (eg. ReadableStream, WriteableStream). It also means implementers can't be derived from a non-stream base class, which is annoying because sometimes "oh, and you can use it like a stream" is a feature you want to tack onto an existing class.

Proposed Solution

Split IO.Stream's various responsibilities into interfaces:


     Public Interface IReadableStream
         Inherits IDisposable
         Function Read(ByVal buffer() As Byte, ByVal offset As Integer, ByVal count As Integer) As Integer
     End Interface
     Public Interface IWritableStream
         Inherits IDisposable
         Sub Write(ByVal buffer() As Byte, ByVal offset As Integer, ByVal count As Integer)
         Sub Flush()
     End Interface
     Public Interface ISeekableStream
         Inherits IDisposable
         Property Position As Long
         Property Length As Long
     End Interface

IO.Stream can implement the interfaces for forwards compatibility. Extension methods, which wrap stream interface instances inside an IO.Stream, provide backwards compatibility. Extension methods can implement the derived methods from IO.Stream:


         <Extension()>
         Public Function ReadByte(ByVal this As IReadableStream) As Integer
             If this Is Nothing Then Throw New ArgumentNullException("this")
             Dim buffer(0 To 0) As Byte
             Dim n = this.Read(buffer, 0, 1)
             If n = 0 Then Return -1
             Return buffer(0)
         End Function

Eventually, IO.Stream can be deprecated.

Furthermore, define interfaces for combinations of responsibilities:


     Public Interface IRereadableStream
         Inherits IReadableStream
         Inherits ISeekableStream
     End Interface
     Public Interface IRewritableStream
         Inherits IWritableStream
         Inherits ISeekableStream
     End Interface
     ...

The result is the same functionality we have now, except type safe. You no longer need to check if a stream is readable, you no longer need to throw NotSupportExceptions, and you no longer need to write blog posts about how bad streams are.

Exceptions to Die By - The InvalidStateException

2009-09-15T15:51:00.002-03:00

Introduction

When your program fails, you want to throw the right type of exception. You want to provide useful information in the type so the caller can react appropriately to the problem. Lack of type information is one reason why throwing an exception of type Exception is such a bad idea. The .net base class library includes exceptions for most common cases (ArgumentException, InvalidOperationException, IOException, etc.). This post covers a class of custom exceptions I like to use in my own projects, which I call invalid state exceptions.

Description

Most bugs immediately cause an exception to be thrown: if you try to pass null into a non-null method you get an ArgumentNullException, and if you try to pop an empty stack and you get an InvalidOperationException. But the difficult bugs don't throw exceptions immediately: they occur, corrupt the program state, and at some later point this causes an exception to be thrown.

Enter the InvalidStateException. An invalid state exception occurs when the program fails because a state-corrupting bug has already occurred. For example, a list enumeration failing because the list was modified should be an InvalidStateException instead of an InvalidOperationException.


      '''<summary>Indicates an invalid program state has been detected (eg. due to a fault).</summary>
      Public Class InvalidStateException
          Inherits InvalidOperationException
          Public Sub New(Optional ByVal message As String = Nothing,
                         Optional ByVal innerException As Exception = Nothing)
              MyBase.New(If(message, "Reached an unexpected state."), innerException)
          End Sub
      End Class

Invalid state exceptions are generally irrecoverable because it is already too late to fix the problem. They tend to indicate bugs in the interaction of multiple components, and are usually thrown by assumption-checking code. I have found that adding this exception type has increased the amount of assumption checking code I write, which is definitely a good thing.

Derived Types

Usually we know more than just "the program is in an invalid state" when throwing an invalid state exception. The most common assumption I check is that a switch statement hits a defined case, so I have a derived type called ImpossibleValueException. Here are the three derived types I have used:

1. UnreachableException: I usually use this one to silence the compiler's reachability analyzer or to indicate to readers that a case is impossible.


      '''<summary>Indicates a path expected to be unreachable has been executed.</summary>
      Public Class UnreachableException
          Inherits InvalidStateException
          Public Sub New(Optional ByVal message As String = Nothing,
                         Optional ByVal innerException As Exception = Nothing)
              MyBase.New(If(message, "Reached a state which was expected to not be reachable."), innerException)
          End Sub
      End Class

2. ImpossibleValueException: I often throw this one in the default cases of switch statements over enums. I even defined an extension method for constructing it from any value.


      '''<summary>Indicates an internal value expected to be impossible has been encountered.</summary>
      Public Class ImpossibleValueException(Of T)
          Inherits InvalidStateException
          Public ReadOnly Value As T
          Public Sub New(ByVal value As T,
                         Optional ByVal message As String = Nothing,
                         Optional ByVal innerException As Exception = Nothing)
              MyBase.new(If(message, "The {0} value ""{1}"" was not expected.".Frmt(GetType(T).Name, String.Concat(value))),
                         innerException)
              Me.Value = value
          End Sub
      End Class

3. InfiniteLoopException: I defined this one when making a single linked list iterator with cycle detection.


      '''<summary>Indicates the program entered an infinite loop but the problem was caught and the loop aborted.</summary>
      Public Class InfiniteLoopException
          Inherits InvalidStateException
          Public Sub New(Optional ByVal message As String = Nothing,
                         Optional ByVal innerException As Exception = Nothing)
              MyBase.New(If(message, "Detected and aborted an infinite loop."), innerException)
          End Sub
      End Class

Conclusion

The invalid state exception is not well covered by any of the default exception types, which is why I defined it. Once defined, I found myself using it in all kinds of (appropriate!) places. The moral: don't be afraid to define generic exceptions when you find yourself shoehorning a weird exception into the existing types. (Just don't go crazy.)

Concurrency #4: Using the Call Queue

2009-09-15T15:04:00.001-03:00

Introduction

Now that we have implemented a lock free queue, futures, and a call queue, we will start using them to perform concurrent programming. For example, consider a bank account class synchronized using locks:


  Public Class BankAccount
      Private balance As UInteger
      Private ReadOnly lock As New Object()
      Public Function Deposit(ByVal value As UInteger) As UInteger
          SyncLock lock
              balance += value
              Return balance
          End SyncLock
      End Function
      Public Function TryWithdraw(ByVal value As UInteger) As UInteger?
          SyncLock lock
              If balance < style="color: blue;">Then Return Nothing
              balance -= value
              Return balance
          End SyncLock
      End Function
  End Class

Rewriting the class to use queues and futures is dead simple, because the locking is at the method level. Just replace SyncLock blocks with QueueFunc blocks.


  Public Class BankAccount
      Private balance As UInteger
      Private queue As ICallQueue = New ThreadPooledCallQueue()
      Public Function FutureDeposit(ByVal value As UInteger) As IFuture(Of UInteger)
          Return queue.QueueFunc(
              Function()
                  balance += value
                  Return balance
              End Function)
      End Function
      Public Function FutureTryWithdraw(ByVal value As UInteger) As IFuture(Of UInteger?)
          Return queue.QueueFunc(
              Function() As UInteger?
                  If balance < style="color: blue;">Then  Return Nothing
                  balance -= value
                  Return balance
              End Function)
      End Function
  End Class

Message Passing

Look closely at the bank account example. Calling FutureTryWithdraw is like sending a message to the bank account object (saying "please try to withdraw X dollars"), and the future returned by the method is like a reply saying either "Ok, you now have X dollars!" or "Not enough funds!". We've implemented a form of message passing, which is what highly concurrent languages like Erlang are based on.

Message passing is not the holy grail of concurrency, but it is an extremely powerful abstraction. For example, it would be much easier to message-pass to a remote machine than do some type of lock sharing. Message passing also makes it impossible to cause a deadlock (the closest analogue is creating a never-ending message cycle; much easier to debug). Most importantly, it is easier to reason about messages than locks. Proving a lock is used correctly requires looking at the entire program. Proving a message is used correctly only requires looking at part of the program (usually one or two functions).

Messages are not superior to locks in every way, of course. Different methods work better in different situations. For example, there is no message-passing analogue for holding two locks at the same time. In addition, it is natural to lock only part a method but it is not always clear what that would mean in terms of passing messages.

Those Darn Philosophers

I'm going to finish with an implementation of the dining philosophers done with message passing. Put it in a command line project (alongside the other classes introduced in this series). Notice how each class is simple on its own. In fact, the most complex parts are related to writing readable information to the console! In the next post in this series, I will supply implementations of futures for various asynchronous tasks.


  Public Module Main
      Public Sub Main()
          Const NumPhilosphers As Integer = 5
   
          'Setup table
          Dim chopSticks(0 To NumPhilosphers - 1) As Chopstick
          Dim philosophers(0 To NumPhilosphers - 1) As DiningPhilosopher
          For i = 0 To NumPhilosphers - 1
              chopSticks(i) = New Chopstick()
          Next i
          For i = 0 To NumPhilosphers - 1
              philosophers(i) = New DiningPhilosopher(New Random(Environment.TickCount + i), chopSticks(i), chopSticks((i + 1) Mod NumPhilosphers))
          Next i
   
          'Give a bit of stabilizing time for measurements
          Threading.Thread.Sleep(5000)
   
          'Print status updates
          Dim n = 0
          Do
              n += 1
              System.Console.WriteLine("Update #" + n.ToString())
              For i = 0 To NumPhilosphers - 1
                  System.Console.WriteLine("Philosopher #" + i.ToString() + " is " + philosophers(i).Status + ".")
              Next i
              Threading.Thread.Sleep(1000)
          Loop
      End Sub
  End Module
   
  '''Represents a shared resource.
  Public Class Chopstick
      Public queue As ICallQueue = New ThreadPooledCallQueue()
      Private inUse As Boolean
   
      Public Function QueueTryPickUp() As IFuture(Of HeldChopStick)
          Return queue.QueueFunc(Function()
                                     If inUse Then  Return Nothing
                                     inUse = True
                                     Return New HeldChopStick(AddressOf QueuePutDown)
                                 End Function)
      End Function
      Private Function QueuePutDown() As IFuture
          Return queue.QueueAction(Sub()
                                       inUse = False
                                   End Sub)
      End Function
  End Class
   
  '''Represents an acquired resource.
  Public Class HeldChopStick
      Private wasDropped As Boolean
      Private ReadOnly drop As Func(Of IFuture)
      Public Sub New(ByVal drop As Func(Of IFuture))
          Me.drop = drop
      End Sub
      Public Function PutDown() As IFuture
          If wasDropped Then Throw New InvalidOperationException()
          wasDropped = True
          Return drop()
      End Function
  End Class
   
  '''Represents a philosopher trying to share chopsticks for eating.
  Public Class DiningPhilosopher
      Private ReadOnly leftChopStick As Chopstick
      Private ReadOnly rightChopStick As Chopstick
      Private feedings As Integer
      Private lastTime As Date
      Private weightedRate As Double
   
      Public Sub New(ByVal rng As Random, ByVal leftChopStick As Chopstick, ByVal rightChopStick As Chopstick)
          Me.lastTime = Now
          Me.leftChopStick = leftChopStick
          Me.rightChopStick = rightChopStick
          Call TryGrabChopsticks(rng)
      End Sub
   
      'This method isn't thread-safe, but the errors will be marginal [race condition on increments and resets of 'feeding']
      Public ReadOnly Property Status As String
          Get
              'Measure
              Dim t = Now
              Dim dt = t - lastTime
              Dim rate = feedings / dt.TotalSeconds
   
              'Estimate
              If weightedRate = 0 Then
                  weightedRate = rate
              Else
                  'Exponential approach w.r.t. time
                  Dim lambda = 0.9 ^ dt.TotalSeconds
                  weightedRate *= lambda
                  weightedRate += rate * (1 - lambda)
              End If
   
              'Categorize
              Dim category = ""
              Select Case weightedRate
                  Case 0 : category = "Empty"
                  Case 0 To 1 : category = "Starving"
                  Case 1 To 2 : category = "Hungry"
                  Case 2 To 3 : category = "Satisfied"
                  Case Else : category = "Plump"
              End Select
   
              'Finish
              lastTime = t
              feedings = 0
              Return category + " (~" + weightedRate.ToString("0.00") + "/s)"
          End Get
      End Property
   
      Private Sub TryGrabChopsticks(ByVal rng As Random)
          'Try to grab both chopsticks
          Dim futureLeft = leftChopStick.QueueTryPickUp()
          Dim futureRight = rightChopStick.QueueTryPickUp()
   
          'React once both chopsticks have been attempted
          futureLeft.CallWhenValueReady(
              Sub(left) futureRight.CallWhenValueReady(
                  Sub(right)
                      'Call on a new thread because there are sleeps
                      Call New Threading.Thread(Sub() TryHoldChopsticks(rng, left, right)).Start()
                  End Sub))
      End Sub
      Private Sub TryHoldChopsticks(ByVal rng As Random, ByVal left As HeldChopStick, ByVal right As HeldChopStick)
          If right Is Nothing OrElse left Is Nothing Then
              'Oh no! Put down and wait a bit before trying again.
              If left IsNot Nothing Then left.PutDown()
              If right IsNot Nothing Then right.PutDown()
              Threading.Thread.Sleep(10 + rng.Next(10))
          Else
              'Yay! Food!
              feedings += 1
              Threading.Thread.Sleep(50 + rng.Next(50))
              left.PutDown()
              right.PutDown()
   
              'Snooze
              Threading.Thread.Sleep(50 + rng.Next(50))
          End If
   
          'Hungry! Repeat!
          Call TryGrabChopsticks(rng)
      End Sub
  End Class

Concurrency #3: The Queue is the Mailbox

2009-08-17T17:57:00.004-03:00

Introduction

So far in this series, I have introduced futures and a lock-free queue. Now we are going to use those tools to create a call queue, which will just happen to return futures. This queue will allow us to do message-based synchronization, which will be covered in the next post.

Designing the Interface

A call queue's interface is trivial. It accepts actions to run and, in this case, returns a future for when the action has completed.

  
    Public Interface ICallQueue  
        Function QueueAction(ByVal action As Action) As IFuture  
    End Interface

We also want to be able to work with functions, so we will add an extension method that accepts functions and returns a future for the value computed when the queued function finally runs.

  
    Public Module ExtensionsForICallQueue  
        <Extension()>  
        Public Function QueueFunc(Of R)(ByVal queue As ICallQueue, ByVal func As Func(Of R)) As IFuture(Of R)  
            Dim f As New Future(Of R)  
            queue.QueueAction(Sub() f.SetValue(func()))  
            Return f  
        End Function  
    End Module

Notice that the interface does not specify how the actions run. The queue might run them on a separate thread, on the thread pool, or in any other context it wants. The only requirements are that the queued calls must eventually run and they must run in order.

Implementing the Call Queue

The call queue is going to be lock free, making things fast and (more importantly) interesting. The call queue implementation will handle guaranteeing the eventual execution of queued calls, since the lock-free queue handles the in-order stuff. We will need to create a consumer when the queue becomes non-empty, destroy the consumer when the queue becomes empty, and do all of this in parallel.

To simplify reasoning about the very large number of possible thread interleavings, I am only going to focus on the exit point of methods. At every method exit point the queue will guarantee "empty or moving". To be more explicit, at every point the queue guarantees ONE of the following:
1) Queued calls are being executed
2) There is another thread executing inside the queue (which will affect shared state before it finishes)
3) The queue is empty
Given "empty or moving", it is impossible for a method to leave the queue idle in a non-empty state (which would result in calls potentially never being executed).

Alright, let's implement a queue satisfying the above property! All the difficult logic will be placed into private methods for acquiring and releasing consumer responsibilities, and the queue will call them appropriately before exiting methods. Let's start with the simple stuff so we see the big picture. We need a lock-free queue to store queued actions, a method to enqueue actions, and an overridable method to consume them. The consume method is overridable so child classes can override it and do things like call the base method on a new thread, giving a threaded call queue.

  
    Public MustInherit Class AbstractCallQueue  
        Implements ICallQueue  
   
        Private ReadOnly queue As New SingleConsumerLockFreeQueue(Of Node)  
        Private running As Integer 'stores consumer state and is used as a semaphore  
   
        Private Class Node  
            Public ReadOnly action As Action  
            Public ReadOnly future As New Future()  
            Public Sub New(ByVal action As Action)  
                Me.action = action  
            End Sub  
        End Class  
   
        Public Function QueueAction(ByVal action As Action) As IFuture Implements ICallQueue.QueueAction  
            Dim item = New Node(action)  
            queue.BeginEnqueue(item)  
            If TryAcquireConsumer() Then  
                Call Consume()  
            End If  
            Return item.future  
        End Function  
   
        Protected Overridable Sub Consume()  
            Do Until TryReleaseConsumer()  
                Dim item = queue.Dequeue()  
                Call item.action()  
                Call item.future.SetReady()  
            Loop  
        End Sub  
        ...

Notice that the last shared-state-actions performed by QueueAction and Consume are TryAcquireConsumer and TryReleaseConsumer respectively. Therefore if those two methods meet "empty or moving", the queue will work.

The TryAcquireConsumer method will be simple and optimistic, because many producers can call it at the same time. It will just optimistically fail if the queue is empty, and otherwise try to atomically acquire the consumer responsibilities. Now to prove all possible exits meet "empty or moving". The optimistic failure is safe, because if another producer exists to enqueue an item in parallel, then there is some other thread executing inside the queue. The attempt to acquire the lock is safe because if it fails then there is a consumer executing inside the queue, and if it succeeds then we will create a consumer executing inside the queue. Therefore, when this method ends the queue will be empty or there will be some thread executing inside the queue, which proves "empty or moving".

  
        ...  
        Private Function TryAcquireConsumer() As Boolean  
            If queue.WasEmpty Then Return False  
            Return Threading.Interlocked.Exchange(running, 1) = 0  
        End Function  
        ...

Try TryReleaseConsumer method will be less simply. It will first check if the queue is not empty, in which case clearly we should still be consuming and it will fail. Then it will optimistically release the consumer responsibilities. But, between the empty check and releasing responsibilities, a producer may have enqueued an item. Therefore, we have to try to re-acquire consumer responsibilities. If that fails, then we know the queue is empty or another thread is now the consumer. Therefore, if we fail to re-acquire consumer, responsibilities we are done and can safely exit.

We're not done yet. There is one last possibility: some other thread may have acquired consumer responsibilities, emptied the queue, and released those responsibilities just before we acquired them; leaving us with a potentially empty queue! Therefore, if we acquire consumer responsibilities then the first thing we need to do is try to release consumer responsibilities all over again! Therefore we must keep trying until we fail to acquire (in which case we exit the queue) or find a non-empty queue (in which case we process some items then come back). But, as long as we don't give up, "empty or moving" will be satisfied. Therefore, even though the caller can potentially be live-locked, TryReleaseConsumer satisfies "empty or moving". (The live lock is not an issue because, in order for it to occur, progress must be occurring).

  
        ...  
        Private Function TryReleaseConsumer() As Boolean  
            Do  
                If Not queue.WasEmpty Then Return False  
                Threading.Interlocked.Exchange(running, 0)  
                If Not TryAcquireConsumer() Then Return True  
            Loop  
        End Function  
    End Class

A couple call queue types

Hurray, we have an abstract lock-free call queue! Now let's go nuts and implement some concrete types we'll actually want to use. The obvious one is a ThreadedCallQueue, which runs queued calls on an independent thread:

  
    '''<summary>Runs queued calls on an independent thread.</summary>  
    Public Class ThreadedCallQueue  
        Inherits AbstractCallQueue  
        Protected Overrides Sub Consume()  
            Call New Thread(Sub() MyBase.Consume()).Start()  
        End Sub  
    End Class

However, we might have a very large number of call queues in a program, and the start-up and tear-down cost for threads is quite high. The .Net framework provides a ThreadPool class that accepts work items to execute on a limited number of threads. We should create a ThreadPooledCallQueue for running queued calls with the thread pool:

  
    '''<summary>Runs queued calls on the thread pool.</summary>  
    Public Class ThreadPooledCallQueue  
        Inherits AbstractCallQueue  
        Protected Overrides Sub Consume()  
            Call ThreadPool.QueueUserWorkItem(Sub() MyBase.Consume())  
        End Sub  
    End Class

Lastly, we might require our calls to run on the UI thread (attempting to access form controls from another thread causes exceptions). It would be extremely convenient if we had a call queue which didn't require us to Invoke all over the place. Enter the InvokedCallQueue:

  
    '''<summary>Runs queued calls on a control's thread.</summary>  
    Public Class InvokedCallQueue  
        Inherits AbstractCallQueue  
        Private ReadOnly control As System.Windows.Forms.Control  
        Public Sub New(ByVal control As System.Windows.Forms.Control)  
            Me.control = control  
        End Sub  
        Protected Overrides Sub Consume()  
            control.BeginInvoke(Sub() MyBase.Consume())  
        End Sub  
    End Class

There are surely plenty of other interesting ways to run queued calls, but these three have met my needs so far.

Summary

Now we have a bunch of lock-free call queues we can use to order calls from multiple threads. In the next post in this series I will cover how to use the queue for synchronization and compare it with a lock based approach. Fully commented code follows.

  
    '''<summary>Describes a thread-safe call queue for non-blocking calls.</summary>  
    Public Interface ICallQueue  
        '''<summary>Queues an action to be run and returns a future for the action's eventual completion.</summary>  
        Function QueueAction(ByVal action As Action) As IFuture  
    End Interface  
   
    Public Module ExtensionsForICallQueue  
        '''<summary>Queues a function to be run and returns a future for the function's eventual output.</summary>  
        <Extension()>  
        Public Function QueueFunc(Of R)(ByVal queue As ICallQueue, ByVal func As Func(Of R)) As IFuture(Of R)  
            Dim f As New Future(Of R)  
            queue.QueueAction(Sub() f.SetValue(func()))  
            Return f  
        End Function  
    End Module  
   
    ''' <summary>  
    ''' A queue for running actions in order.  
    ''' Debug.Prints unexpected exceptions from queued calls.  
    ''' </summary>  
    ''' <remarks>  
    ''' Consumes items produced by multiple producers.  
    ''' Ensures that enqueued items are consumed by ensuring at all exit points that either:  
    ''' - the queue is empty  
    ''' - or exactly one consumer exists  
    ''' - or another exit point will be hit [by another thread]  
    ''' </remarks>  
    Public MustInherit Class AbstractCallQueue  
        Implements ICallQueue  
   
        Private ReadOnly queue As New SingleConsumerLockFreeQueue(Of Node)  
        Private running As Integer 'stores consumer state and is used as a semaphore  
        Private Class Node  
            Public ReadOnly action As Action  
            Public ReadOnly future As New Future()  
            Public Sub New(ByVal action As Action)  
                Me.action = action  
            End Sub  
        End Class  
   
        ''' <summary>  
        ''' Queues an action to be run and returns a future for the action's eventual completion.  
        ''' Starts running calls from the if they were not already being run.  
        '''</summary>  
        ''' <remarks>  
        ''' Enqueues a sequence of items to be consumed by the consumer.  
        ''' The items are guaranteed to end up adjacent in the queue.  
        ''' </remarks>  
        Public Function QueueAction(ByVal action As Action) As IFuture Implements ICallQueue.QueueAction  
            Dim item = New Node(action)  
            queue.BeginEnqueue(item)  
   
            'Start the consumer if it is not already running  
            If TryAcquireConsumer() Then  
                Call Consume()  
            End If  
   
            Return item.future  
        End Function  
   
        '''<summary>Returns true if consumer responsibilities were acquired by this thread.</summary>  
        Private Function TryAcquireConsumer() As Boolean  
            'Don't bother acquiring if there are no items to consume  
            'This unsafe check is alright because enqueuers call this method after enqueuing  
            'Even if an item is queued between the check and returning false, the enqueuer will call this method again  
            'So we never end up with a non-empty idle queue  
            If queue.WasEmpty Then Return False  
   
            'Try to acquire consumer responsibilities  
            Return Threading.Interlocked.Exchange(running, 1) = 0  
   
            'Note that between the empty check and acquiring the consumer, all queued actions may have been processed.  
            'Therefore the queue may be empty at this point, but that's alright. Just a bit of extra work, nothing unsafe.  
        End Function  
        '''<summary>Returns true if consumer responsibilities were released by this thread.</summary>  
        Private Function TryReleaseConsumer() As Boolean  
            Do  
                'Don't release while there's still things to consume  
                If Not queue.WasEmpty Then Return False  
   
                'Release consumer responsibilities  
                Threading.Interlocked.Exchange(running, 0)  
   
                'It is possible that a new item was queued between the empty check and actually releasing  
                'Therefore it is necessary to check if we can re-acquire in order to guarantee we don't leave a non-empty queue idle  
                If Not TryAcquireConsumer() Then Return True  
   
                'Even though we've now acquired consumer, we may have ended up with nothing to process!  
                'So let's repeat this whole check for empty/release dance!  
                'A caller could become live-locked here if other threads keep emptying and filling the queue.  
                'But only consumer threads call here, and the live-lock requires that progress is being made.  
                'So it's alright. We still make progress and we still don't end up in an invalid state.  
            Loop  
        End Function  
   
        ''' <summary>  
        ''' Runs queued calls until there are none left.  
        ''' Child classes can override and call base implementation using desired method (eg. on a new thread).  
        ''' </summary>  
        Protected Overridable Sub Consume()  
            Do Until TryReleaseConsumer()  
                Dim item = queue.Dequeue()  
                Call item.action()  
                Call item.future.SetReady()  
            Loop  
        End Sub  
    End Class  
   
    '''<summary>Runs queued calls on an independent thread.</summary>  
    Public Class ThreadedCallQueue  
        Inherits AbstractCallQueue  
        Protected Overrides Sub Consume()  
            Call New Thread(Sub() MyBase.Consume()).Start()  
        End Sub  
    End Class  
   
    '''<summary>Runs queued calls on the thread pool.</summary>  
    Public Class ThreadPooledCallQueue  
        Inherits AbstractCallQueue  
        Protected Overrides Sub Consume()  
            Call ThreadPool.QueueUserWorkItem(Sub() MyBase.Consume())  
        End Sub  
    End Class  
   
    '''<summary>Runs queued calls on a control's thread.</summary>  
    Public Class InvokedCallQueue  
        Inherits AbstractCallQueue  
        Private ReadOnly control As System.Windows.Forms.Control  
        Public Sub New(ByVal control As System.Windows.Forms.Control)  
            Me.control = control  
        End Sub  
        Protected Overrides Sub Consume()  
            control.BeginInvoke(Sub() MyBase.Consume())  
        End Sub  
    End Class

Emulating Yield-like Iterators in VB10

2009-08-04T13:54:00.000-03:00

Introduction

One of the defining characteristics of VB10 and C#4 is feature convergence. VB and C# now share optional arguments, dynamic types, multiline lambdas, and auto-properties. However, there are still differences between the two languages. One of the glaring differences is the lack of yield-style Iterators in VB. In this post, I am going to address that difference by constructing a class that uses lambda expressions to achieve functionality similar to yield.

Explicit Iterators vs Yield Iterators

Explicitly implementing an iterator is a huge pain, because of the sheer amount of code required. You have to write a whole class, implement two interfaces (including their non-generic legacy versions), and manually track state. Put it all together and you get massive line waste.

Just to hammer this in, here is a typical iterator implementation to enumerate a contiguous subset of an array:


Public Class SubArrayIterator(Of T)
    Implements IEnumerable(Of T)
    Implements IEnumerator(Of T)
 
    Private ReadOnly array As T()
    Private ReadOnly offset As Integer
    Private ReadOnly length As Integer
    Private index As Integer
    Private cur As T
 
    Public Sub New(ByVal array As T(), ByVal offset As Integer, ByVal length As Integer)
        Me.array = array
        Me.offset = offset
        Me.length = length
    End Sub
 
    Public Function GetEnumerator() As IEnumerator(Of T) Implements IEnumerable(Of T).GetEnumerator
        Return New SubArrayIterator(Of T)(array, offset, length)
    End Function
 
    Private ReadOnly Property Current As T Implements IEnumerator(Of T).Current
        Get
            Return cur
        End Get
    End Property
 
    Private Function MoveNext() As Boolean Implements IEnumerator.MoveNext
        If index >= length Then Return False
        cur = array(index)
        index += 1
        Return True
    End Function
 
    Private Sub Reset() Implements IEnumerator.Reset
        index = 0
    End Sub
 
    Private Sub Dispose() Implements IDisposable.Dispose
        'no unmanaged state
    End Sub
 
    Private Function GetEnumeratorObj() As IEnumerator Implements IEnumerable.GetEnumerator
        Return GetEnumerator()
    End Function
    Private ReadOnly Property CurrentObj As Object Implements IEnumerator.Current
        Get
            Return cur
        End Get
    End Property
End Class

Augh! Fifty lines for something I can describe in less than ten words! Now compare that to this:


        public IEnumerable IterateSubArray<T>(T[] array, int offset, int length) {
            for (int i = 0; i <>
                yield return array[i + offset];
        }

Wow! We jumped from fifty lines to four! The compiler will explicitly implement a large class (it translates the function into a state machine), but all we see is four lines. There are downsides (eg. Reset is not supported, but nobody uses Reset anyways), but they are mostly inconsequential compared to the code savings. The main problem is the lazy evaluation of the iterator causes argument exceptions to be thrown when the iterator is used instead of when it is constructed.

I should probably point out that, using linq, the example enumeration can be just a single line. Remember that it is only for demonstration purposes.

The Controller

The basic idea I have is to use a generator function to implement the enumeration. The function will take a controller, in order to signal special commands like "end of enumeration".


Public Interface IEnumeratorController(Of T)
    Function Break() As T
End Interface

You can add more control methods as you desire them. Other useful possible control methods are "Multiple", which would return a sequence of items to enumerate, and "Repeat", which would return no item to enumerate and run the generator again. Note that the expected usage style of the controller methods is in a return statement (like "return controller.Break()"). This avoids confusing cases like calling break then returning an element to enumerate (Which would take precedence?).

The Enumerator

Now that the controller is defined, we can write a class which implements IEnumerator using a generator function. It's relatively straightforward: you just track the generator's last returned item and a flag for whether or not controller.break has been called yet. We have line waste, but we only have to include this code once instead of once per iterator.


Public NotInheritable Class Enumerator(Of T)
    Implements IEnumerator(Of T)
    Implements IEnumeratorController(Of T)
 
    Private ReadOnly generator As Func(Of IEnumeratorController(Of T), T)
    Private cur As T
    Private break As Boolean
    Public Sub New(ByVal generator As Func(Of IEnumeratorController(Of T), T))
        Me.generator = generator
    End Sub
 
    Public Function MoveNext() As Boolean Implements IEnumerator(Of T).MoveNext
        If Me.break Then Return False 'have previously called controller.break
        Me.cur = generator(Me)
        If Me.break Then Return False 'just called controller.break
        Return True
    End Function
 
    Private Function ControllerBreak() As T Implements IEnumeratorController(Of T).Break
        Me.break = True
        Return Nothing
    End Function
 
    Public ReadOnly Property Current As T Implements IEnumerator(Of T).Current
        Get
            Return Me.cur
        End Get
    End Property
 
    Private ReadOnly Property CurrentObj As Object Implements IEnumerator.Current
        Get
            Return Me.cur
        End Get
    End Property
    Private Sub Reset() Implements IEnumerator.Reset
        Throw New NotSupportedException()
    End Sub
    Private Sub Dispose() Implements IDisposable.Dispose
        'no unmanaged state
    End Sub
End Class

The Generator

With our Enumerator and Controller in hand, we can write a function to enumerate a contiguous subset of an array. We will use a lambda expression for the generator, and a hoisted local variable to keep state:


    Public Function EnumerateSubArray(Of T)(ByVal items() As T, ByVal offset As Integer, ByVal length As Integer) As IEnumerator(Of T)
        Dim index = 0 'hoisted variable used for state
        Return New Enumerator(Of T)(
            Function(controller)
                If index >= length Then  Return controller.Break()
                index += 1
                Return items(index - 1)
            End Function)
    End Function

The result isn't be as compact as using C#'s yield, but is still a huge improvement over explicit implementation. It's essentially like implementing only the MoveNext method instead of an entire enumerator class. The main downside compared to yield is the loss of multiple entry points into the function (we always start at the beginning, not on the line after the last return). We do have one advantage over using yield: we can check arguments upon construction of the iterator (because everything before return New Enumerator(...) is executed immediately).

Enumerable vs Enumerator

An IEnumerable is an object that can be enumerated more than once. It returns a new enumerator for each enumeration, and is the type required by the useful 'for each' loop. In order to implement an IEnumerable we just pull the same trick again: seeding a class with a generator function. Luckily, this time we don't need a controller because an IEnumerable doesn't require state.


    Public NotInheritable Class Enumerable(Of T)
        Implements IEnumerable(Of T)
        Private ReadOnly generator As Func(Of IEnumerator(Of T))
        Public Sub New(ByVal generator As Func(Of IEnumerator(Of T)))
            Me.generator = generator
        End Sub
        Public Function GetEnumerator() As IEnumerator(Of T) Implements IEnumerable(Of T).GetEnumerator
            Return generator()
        End Function
        Private Function GetEnumeratorObj() As IEnumerator Implements IEnumerable.GetEnumerator
            Return GetEnumerator()
        End Function
    End Class

At last, we can properly iterate over that contiguous array subset by using our previous EnumerateSubArray function to generate enumerators:


    Public Function IterateSubArray(Of T)(ByVal items() As T, ByVal offset As Integer, ByVal length As Integer) As IEnumerable(Of T)
        Return New Enumerable(Of T)(Function() EnumerateSubArray(items, offset, length))
    End Function

Conclusion

Even though VB doesn't have a yield keyword, we can still cut the number of lines required for an iterator by a factor a five. All we needed were a couple classes to turn generator functions into an enumerator. It's not as good as using yield, but we don't have yield.

Concurrency #2: The Future is the Message

2009-07-13T02:25:00.004-03:00

Introduction

A future is a thing that may not be available now, but will be available later. This simple abstraction simplifies many concurrent tasks by cleanly separating how they are performed and how their results are used. All the caller cares about is that the result will eventually be available, and all the callee cares about is eventually making the result available.

Implementation

We'll start by defining an interface for future values. Callers will need to be able to check if the future is ready yet, a way to be informed when the future does become ready, and a method to extract the future's value once it is ready. So let's start with an interface which does just that:

     Public Interface IFuture(Of Out R)
        Event Readied()
        ReadOnly Property IsReady() As Boolean
        Function GetValue() As R
    End Interface

That's good, but sometimes we don't want to include a value with the future (e.g. we just want to signal when a subroutine has finished), and some methods only care about the 'will eventually be ready' part of the future. Let's refactor the interface into two interfaces:

     Public Interface IFuture
        Event Readied()
        ReadOnly Property IsReady() As Boolean
    End Interface
    Public Interface IFuture(Of Out R)
        Inherits IFuture
        Function GetValue() As R
    End Interface

Now IFuture(of A) and IFuture(of B) share their common functionality, which is a nice property to have. We will also need classes implementing the IFuture interfaces, so we actually have something to return from future functions. They aren't very hard to implement, so I'll just include what you get if you remove everything but the declarations. Notice that, although IFuture(of R) inherits from IFuture, Future(of R) doesn't inherit from Future. Do you see why?

     Public Class Future
        Implements IFuture
        Public Event Readied() Implements IFuture.Readied
        Public ReadOnly Property IsReady() As Boolean Implements IFuture.IsReady
        Public Function TrySetReady() As Boolean
        Public Sub SetReady() 'Throws an InvalidOperationException if the future was already ready.
    End Class
    Public Class Future(Of R)
        Implements IFuture(Of R)
        Public Event Readied() Implements IFuture.Readied
        Public ReadOnly Property IsReady() As Boolean Implements IFuture.IsReady
        Public Function GetValue() As R Implements IFuture(Of R).GetValue 'Throws an InvalidOperationException if the value isn't ready yet.
        Public Function TrySetValue(ByVal val As R) As Boolean
        Public Sub SetValue(ByVal val As R) 'Throws an InvalidOperationException if the future was already ready.
    End Class

Alright, so now we're all set to start using futures! Well, except these super simple interfaces would be a huge pain to use. We need to define some higher level operations to make things easier. We'll use extension methods to implement them as if they were part of the interface itself. The methods we will require are:
- CallWhenReady: Calls an action when a future is ready, and returns a future for when the action completes.
- EvalWhenReady
: Evaluates a function when a future is ready, and returns a future for the function's output.
- CallWhenValueReady<a>: Calls an action when a future is ready, passing the future's value as an argument, and returns a future for when the action completes.
- EvalWhenValueReady<a,r>: Evaluates a function when a future is ready, passing the future's value as an argument, and returns a future for the function's output.
- Futurize: Takes any value and returns an instantly-ready future for it.
- Defuturize: Takes a future of a future and returns a condensed version, which is just a normal future.
- Defuturize<r>: Takes a future of a future of a value and returns a condensed version, which is just a normal future for the final value.

The simplest and operation is Futurize, and it can be implemented like this:

         <Extension()>
        Public Function Futurize(Of R)(ByVal value As R) As IFuture(Of R)
            Dim f = New Future(Of R)
            f.SetValue(value)
            Return f
        End Function

The most complicated operation to implement is CallWhenReady. It's also the most useful operation, because the other operations can all be implemented easily using CallWhenReady. Here it is:

         <Extension()>
        Public Function CallWhenReady(ByVal future As IFuture,
                                      ByVal action As Action) As IFuture
            Dim lockVal As Integer
            Dim f As New Future()
            Dim notify As IFuture.ReadiedEventHandler
            notify = Sub()
                         If Threading.Interlocked.Exchange(lockVal, 1) = 0 Then 'only run once
                             RemoveHandler future.Readied, notify
                             Call action()
                             f.SetReady()
                         End If
                     End Sub
 
            AddHandler future.Readied, notify
            If future.IsReady Then Call notify() 'In case the future was already ready
 
            Return f
        End Function

Wow, that's a bit complicated! At least the concept is simple. First, we define the notification subroutine, which will run the target action and set CallWhenReady's returned future to ready. Then we make sure the notification subroutine is called once the future is ready. Note that there is a chance the future will become ready between registering for the event and manually checking, which is why the notify subroutine is wrapped in a one time lock.

The rest of the higher level operations are short and sweet because they can be implemented using CallWhenReady. Try to implement them (or just cheat and look at the end of the post).

Some readers might not be familiar with Visual Basic, so I will quickly cover the things used by this method.
- The first line applies the Extension attribute to the method. That tells the compiler the method can be used as if it was part of IFuture. It allows me to write someFuture.CallWhenReady(...) instead of CallWhenReady(someFuture, ...), and includes the method in intellisense. Extension methods are extremely useful, because they make it much easier to discover helper methods.
- The sub ... end sub block is an anonymous subroutine, also called a lambda expression or a closure. Lambda expressions let you inline simple helper functions, but their real power comes from their access to the surrounding variables. For example, CallWhenReady's anonymous notify subroutine uses the arguments passed to CallWhenReady. This is achieved behind the scenes by 'hoisting' those local variables into a private class and passing it to the anonymous method.
- RemoveHandler and AddHandler are used to add and remove the methods called when an Event is raised. In this case we want notify to be called when Readied is fired, then we remove notify to remove unnecessary references (which would prevent the garbage collector from collecting futures derived from any future you held on to).

Example #1

Now we have all the pieces we need in order to use futures. Let's explore a simple example: replacing existing asynchronous methods with futures. We will replace the Net.Sockets.TcpClient BeginConnect/EndConnect methods with a single FutureConnect method. Here is an example of using BeginConnect/EndConnect:

    'Connecting code:
         '...
        '... do whatever you're doing leading up to a connection
        '...
 
        Dim client = New TcpClient
        Try
            'starts a new async task, which calls EndConnect:
            client.BeginConnect(hostname, port, AddressOf EndConnect, client)
        Catch e As SocketException
            'deal with failure to connect
        End Try
 
        '...
 
    Private Sub EndConnect(ByVal ar As IAsyncResult)
        Dim client = CType(ar.AsyncState, TcpClient)
        Try
            client.EndConnect(ar)
        Catch e As SocketException
            'deal with failure to connect
        End Try
 
        '...
        'do whatever you wanted to do with the client once it was connected
        ...
    End Sub

I don't like the Begin/End style methods for a bunch of reasons. Do you see how the BeginConnect method mixes arguments about what you want and what to do with it? That you have to handle the IAsyncResult argument? That the ar.AsyncState member is type unsafe? How we have to call EndConnect for every call to BeginConnect? How this pattern has to repeated every single time you use BeginConnect/EndConnect? All these little problems add up! I don't want to care about these details!

Now we'll implement the same thing with futures. Here is a FutureConnect function:

     Public Function FutureConnect(ByVal hostname As String,
                                  ByVal port As UShort) As IFuture(Of PossibleException(Of TcpClient, SocketException))
        Dim f = New Future(Of PossibleException(Of TcpClient, SocketException))
        Try
            Dim client = New TcpClient
            client.BeginConnect(hostname, port, Sub(ar)
                                                    Try
                                                        client.EndConnect(ar)
                                                        f.SetValue(client)
                                                    Catch e As SocketException
                                                        f.SetValue(e)
                                                    End Try
                                                End Sub, Nothing)
        Catch e As SocketException
            f.SetValue(e)
        End Try
        Return f
    End Function

Essentially, we just wrapped the existing BeginConnect/EndConnect methods inside a future. The main differences are the use of futures and the fact that we create a new TcpClient instead of affecting an existing TcpClient.

Let's use our fancy future connect method. Here is an example:

         '...
        '... do whatever you're doing leading up to a connection
        '...
 
        FutureConnect(hostname, port).CallWhenValueReady(
            Sub(possibleClient)
                If possibleClient.Exception IsNot Nothing Then
                    'deal with failure to connect
                    Return
                End If
                Dim client = possibleClient.Value
 
                '...
                'do whatever you wanted to do with the client once it was connected
                '...
            End Sub
        )
 
        '...

Do you see how the "what I want" and "what I want to do with it" parts are separated? How everything is type safe? How there is no required EndFutureConnect call? We've managed to eliminate those little details. That is a good abstraction at work.

There is a downside to using futures shown here, though. Did you notice that the return value was a PossibleException? That's just a structure which stores a value or an exception. It is impossible for exceptions to safely propagate out of a future the way you expect, so you must encode them into the future's value. The upside is that, because the future's value is type safe, you can't accidentally ignore the possible exception.

Example #2

Suppose you want to do something after a subroutine finishes, but you want to run the subroutine on another thread. Or suppose it's a function running on the other thread and you need to wait for its return value. Futures make this problem trivial. You just write a method that returns a future, and runs the function or subroutine on another thread.


        Public Function FutureThreadedAction(ByVal action As Action) As IFuture
            Dim f As New Future
            Call New Threading.Thread(
                Sub()
                    Call action()
                    Call f.SetReady()
                End Sub
            ).Start()
            Return f
        End Function
        Public Function FutureThreadedFunction(Of R)(ByVal func As Func(Of R)) As IFuture(Of R)
            Dim f As New Future(Of R)
            FutureThreadedAction(Sub() f.SetValue(func()))
            Return f
        End Function

That's it. Now you can call these methods to run functions on other threads, and use futures to work with the return values. I really like this example because, even though we haven't solved any big problems, we've solve one of those tiny annoyances we deal with every day as programmers. The futures are making things easier.

Conclusion

We've really just scratched the surface here. In my next post I will be creating a concurrent call queue which uses futures. In the post after that I will put it all together to implement message passing.

An implementation of futures is posted below. The whole thing is just 170 lines, including comments and whitespace. (My original implementation took upwards of 500 lines, so I'm oddly proud of the line count).


Imports System.Runtime.CompilerServices
 
''''Provides type-safe methods for return values that will be ready in the future, and for passing future arguments into normal functions.
Namespace Futures
    '''Represents a thread-safe read-only class that fires an event when it becomes ready.
    Public Interface IFuture
        '''Raised when the future becomes ready.
        Event Readied()
        '''Returns true if the future is ready.
        ReadOnly Property IsReady() As Boolean
    End Interface
 
    '''Represents a thread-safe read-only class that fires an event when its value becomes ready.
    Public Interface IFuture(Of Out R)
        Inherits IFuture
        ''' 
        ''' Returns the future's value.
        ''' Throws an InvalidOperationException if the value isn't ready yet.
        ''' 
        Function GetValue() As R
    End Interface
 
    '''A thread-safe class that fires an event when it becomes ready.
    Public Class Future
        Implements IFuture
        Private lockVal As Integer
        Public Event Readied() Implements IFuture.Readied
 
        '''Returns true if the future is ready.
        Public ReadOnly Property IsReady() As Boolean Implements IFuture.IsReady
            Get
                Return lockVal = 1
            End Get
        End Property
 
        ''' 
        ''' Makes the future ready.
        ''' Throws an InvalidOperationException if the future was already ready.
        ''' 
        Public Sub SetReady()
            If Not TrySetReady() Then
                Throw New InvalidOperationException("Future readied more than once.")
            End If
        End Sub
        ''' 
        ''' Makes the future ready.
        ''' Returns false if the future was already ready.
        ''' 
        Public Function TrySetReady() As Boolean
            If Threading.Interlocked.Exchange(lockVal, 1) <> 0 Then Return False
            RaiseEvent Readied()
            Return True
        End Function
    End Class
 
    '''A thread-safe class that fires an event when its value becomes ready.
    Public Class Future(Of R)
        Implements IFuture(Of R)
        Private val As R
        Private lockVal As Integer
        Private ReadOnly lockReady As New OneTimeLock
        Public Event Readied() Implements IFuture.Readied
 
        '''Returns true if the future is ready.
        Public ReadOnly Property IsReady() As Boolean Implements IFuture.IsReady
            Get
                Return lockVal = 1
            End Get
        End Property
 
        '''
        '''Returns the future's value.
        '''Throws an InvalidOperationException if the value isn't ready yet.
        '''
        Public Function GetValue() As R Implements IFuture(Of R).GetValue
            If Not IsReady Then Throw New InvalidOperationException("Attempted to get a future value before it was ready.")
            Return val
        End Function
 
        ''' 
        ''' Sets the future's value and makes the future ready.
        ''' Throws a InvalidOperationException if the future was already ready.
        ''' 
        Public Sub SetValue(ByVal val As R)
            If Not TrySetValue(val) Then
                Throw New InvalidOperationException("Future readied more than once.")
            End If
        End Sub
        ''' 
        ''' Sets the future's value and makes the future ready.
        ''' Fails if the future was already ready.
        ''' 
        Public Function TrySetValue(ByVal val As R) As Boolean
            If Threading.Interlocked.Exchange(lockVal, 1) <> 0 Then Return False
            Me.val = val
            RaiseEvent Readied()
            Return True
        End Function
    End Class
 
    Public Module ExtensionsForIFuture
        '''Runs an action once the future is ready, and returns a future for the action's completion.
        <Extension()>
        Public Function CallWhenReady(ByVal future As IFuture,
                                      ByVal action As Action) As IFuture
            Dim lockVal As Integer
            Dim f As New Future()
            Dim notify As IFuture.ReadiedEventHandler
            notify = Sub()
                         If lock.TryAcquire Then 'only run once
                             RemoveHandler future.Readied, notify
                             Call action()
                             f.SetReady()
                         End If
                     End Sub
 
            AddHandler future.Readied, notify
            If future.IsReady Then Call notify() 'in case the future was already ready
 
            Return f
        End Function
 
        '''Passes the future's value to an action once ready, and returns a future for the action's completion.
        <Extension()>
        Public Function CallWhenValueReady(Of A1)(ByVal future As IFuture(Of A1),
                                                  ByVal action As Action(Of A1)) As IFuture
            Return future.CallWhenReady(Sub() action(future.GetValue))
        End Function
 
        '''Runs a function once the future is ready, and returns a future for the function's return value.
        <Extension()>
        Public Function EvalWhenReady(Of R)(ByVal future As IFuture,
                                            ByVal func As Func(Of R)) As IFuture(Of R)
            Dim f As New Future(Of R)
            future.CallWhenReady(Sub() f.SetValue(func()))
            Return f
        End Function
 
        '''Passes the future's value to a function once ready, and returns a future for the function's return value.
        <Extension()>
        Public Function EvalWhenValueReady(Of A1, R)(ByVal future As IFuture(Of A1),
                                                     ByVal func As Func(Of A1, R)) As IFuture(Of R)
            Return future.EvalWhenReady(Function() func(future.GetValue))
        End Function
 
        '''Wraps a normal value as an instantly ready future.
        <Extension()>
        Public Function Futurize(Of R)(ByVal value As R) As IFuture(Of R)
            Dim f = New Future(Of R)
            f.SetValue(value)
            Return f
        End Function
 
        '''Returns a future for the final value of a future of a future.
        <Extension()>
        Public Function Defuturize(Of R)(ByVal futureFutureVal As IFuture(Of IFuture(Of R))) As IFuture(Of R)
            Dim f = New Future(Of R)
            futureFutureVal.CallWhenValueReady(Sub(futureVal) futureVal.CallWhenValueReady(Sub(value) f.SetValue(value)))
            Return f
        End Function
 
        '''Returns a future for the readyness of a future of a future.
        <Extension()>
        Public Function Defuturize(ByVal futureFuture As IFuture(Of IFuture)) As IFuture
            Dim f = New Future
            futureFuture.CallWhenValueReady(Sub(future) future.CallWhenReady(Sub() f.SetReady()))
            Return f
        End Function
    End Module
End Namespace

Concurrency #1: A Multiple-Producer Single-Consumer Lock Free Queue

2009-07-04T20:21:00.002-03:00

Introduction

The later parts of this series are going to require a call queue which accepts calls to run from multiple threads, then ensures they are run in the order they are received. But before we get to a call queue we're going to need a plain vanilla thread-safe queue. My first implementation used the obvious approach: place locks around the Enqueue and Dequeue methods. But when I used this queue, profiling revealed a full quarter of the program's time was spent acquiring and releasing locks! Half of that was attributable to the call queues. I do put a ton of calls through these queues, so I need them be as fast as possible.

Enter lock free data structures, which I'd read a little bit about at the time. Instead of using locks, they use simple atomic operations provided by the hardware. This allows them to be much faster, but it also makes them incredibly hard to write correctly. You need to figure out how to do it without locks, then you need to worry about reads and writes being reordered by modern superscalar processors, then you need to worry about the compiler moving things around, caching reads, removing writes, and other optimizations that work great for single-threaded programs. I really don't want to understate exactly how hard you have to think about lock free stuff. Don't write lock-free stuff unless you're prepared to write an essay explaining why the code is correct (only to find some thread interleaving that takes the whole thing down).

Most lock free queue examples out there use the humble CAS (compare-and-swap) atomic primitive. CAS atomically assigns a value to a variable only if the variable is equal to another value. Here is some pseudo code for CAS. Note that all my code samples are in VB10, which is in beta at the time of this writing.

      Public Function CompareAndSwap(ByRef target As Integer,
                                   ByVal newValue As Integer,
                                   ByVal comparisonValue As Integer) As Boolean
        SyncLock GlobalLock
            If target <> comparisonValue Then Return False
            target = comparisonValue
            Return True
        End SyncLock
    End Function

I wanted to write a unique queue, so I decided to try to avoid using CAS. I ended up using the XCHG (Exchange) atomic primitive. XCHG atomically gets-and-sets a variable, effectively exchanging a new value for the old value. Pseudo code:

      Public Function Exchange(ByRef target As Integer,
                             ByVal newValue As Integer) As Integer
        SyncLock GlobalLock
            Dim oldValue = target
            target = newValue
            Return oldValue
        End SyncLock
    End Function

This is the only atomic primitive I needed for the queue.

Designing the Queue

Queues are typically stored in two ways: as an array or as a linked list. I don't want to even think about how hard it would be to resize an array without acquiring any locks, so the queue is stored using a linked list. There will be a head node, which the consumer will advance in order to dequeue elements, and a tail node which producers will use to enqueue items. The producers will never manipulate the head variable, and items will be published to the queue purely by linking them to the insertion point.

      Public Class SingleConsumerLockFreeQueue(Of T)
        Private head As Node = New Node(Nothing)
        Private insertionPoint As Node = head
        Private Class Node
            Public ReadOnly value As T
            Public [next] As Node
            Public Sub New(ByVal value As T)
                Me.value = value
            End Sub
        End Class
        ...

Essentially the same starting definition you use for any linked list queue. The consumer part is also easy. There is no need for any locks or atomic operations because there is only one consumer, and the producers never manipulate the head variable. We can just implement it as if we were working with a single threaded queue:

          ...
        Public ReadOnly Property WasEmpty As Boolean
            Get
                Return head.next Is Nothing
            End Get
        End Property
        Public Function Peek() As T
            If head.next Is Nothing Then Throw New InvalidOperationException("Empty Queue")
            Return head.next.value
        End Function
        Public Function Dequeue() As T
            If head.next Is Nothing Then Throw New InvalidOperationException("Empty Queue")
            head = head.next
            Return head.value
        End Function
        ...

Note that Peek and Dequeue must only be called from the Consumer thread. You can call WasEmpty from a producer thread, but its return value won't be stable. It's only stable if the queue is non-empty and we called from the Consumer thread (which is why it's WasEmpty instead of IsEmpty). If you've seen CAS-based queues, you'll also notice I avoided some issues by making ".next != null" implicitely equivalent to "another item is queued".

The producers are more complicated. They're going to have to share the insertion point variable by using the XCHG operation. Each producer will exchange a new node for the current insertion point, which will stop producers from interfering with each other:

          ...
        Public Sub BeginEnqueue(ByVal item As T)
            Dim newNode = New Node(item)
            Dim oldInsertionPoint = Threading.Interlocked.Exchange(Me.insertionPoint, newNode)
            oldInsertionPoint.next = newNode
        End Sub
        ...

This queue is essentially identical to a normal queue, except for the XCHG magic in BeginEnqueue. Note that there's a reason I call it BeginEnqueue instead of Enqueue, which comes up later in this post.

Correctness

With the producer and consumer methods defined, we now have a complete queue. But is it correct? The consumer part probably is, but the producer part looks like it could get crazy with lots of threads in there! Let's start by proving the producers don't destructively interfere with each other.

Notice that, for each call to BeginEnqueue, a brand new node is passed as the second argument to XCHG. Therefore, the second argument to XCHG will always be unique. Therefore, the value returned by XCHG will always be unique, because it essentially lags the second argument by one call. Therefore, each producer gets a unique oldInsertionPoint. Also notice that the producers never modify the .next pointer of its own constructed node: they leave that responsibility to the next producer to call XCHG. In fact, the only time a node's .next pointer is ever modified is "oldInsertionPoint.next = newNode". Therefore, there is no write-write race condition on oldInsertionPoint.next = newNode, because oldInsertionPoint is unique to each call and the .next pointer is modified nowhere else. Finally, notice that the .next pointer can only change in the future if it is currently null. This guarantees the property I mentioned earlier: ".next != null" == "another item is queued".

A good mental image of the queue is a big disassembled and growing chain randomly linking itself together until it is a big assembled chain. In later posts I will talk about how I tested the queue in order to truly convince myself it was correct (It wasn't just stress testing.). For now, let's convince ourselves by looking at an example of what happens when two threads contend while enqueueing items.

We start with an empty queue, with the insertion point equal to the head. Then two threads call BeginEnqueue. The threads race, but Thread1 calls XCHG first. Its gets the head as its old insertion point and sets the new insertion point to its constructed node. Now Thread2 pre-empts Thread1 and runs its call to XCHG, getting Thread1's constructed node as its old insertion point. Thread2 continues and finishes, linking Prev2.next to Node2, but leaving the queue still technically empty. Finally, Thread1 finishes and links Prev1.next to Node1, leaving the queue with two items. Even though the thread order was perturbed, the chain still came together correctly. This works for any number of threads. Try it.

To finish this section off, notice that I can actually write a modified BeginEnqueue method to enqueue a sequence of items and guarantee they end up adjacent in the queue. Do you see how to do it?

Performance

Now that I've convinced myself the queue is correct, I want to know how it performs compared to the old locking queue and to CAS-based lock free queues. Actually, comparing it to the old queue was a joke. I profiled my code after I inserted this queue, and it just destroyed the old queue. The queueing overhead was essentially gone. So, I'm going to jump straight to armchair comparing it against CAS queues.

The obvious thing to notice is that all XCHG queue operations are guaranteed constant time. CAS queues, on the other hand, can spend arbitrarily long trying to enqueue their value (in practice this is extremely unlikely). The XCHG operation is also simpler than CAS. Overall, I expect producer throughput to be non-negligibly faster than a CAS based queue. The ability to safely enqueue multiple adjacent items is also nice and could be used to significantly reduce the number of calls to the expensive atomic operations.

The consumer side is essentially equivalent to a CAS queue, in that it could be modified to be multiple-consumer by using CAS. We don't need multiple consumers for a call queue, so I didn't bother making it safe for multiple consumers. The major consumer benefit compared to a CAS queue is that garbage collection is not required. Most lock free data structures require garbage collection, because anytime you explicitly free a node there is a risk that some slow thread still has a reference to it. Here the consumer can safely free nodes when their .next is consumed (because setting .next is the last thing a producer does), making a translation to a low level language like C trivial.

One downside I do want to note, however, is the non-obvious priority inversion. Remember, from the enqueueing example I gave, how Node2 wasn't technically queued when Thread2 finished? It was only queued when Thread1 finished later on. Now imagine a very low priority thread and a very high priority thread continuously enqueueing items. The low priority thread would run the exchange line, and essentially stall the queue until it updated the .next pointer on the next line. The high priority thread would be appending items, but they would not be dequeueable until the low priority queue finished. In other words, the average delay depends on the slowest producer. Luckily, the buffering effect stops this from affecting the average throughput. I would not recommend this queue for real-time systems where milliseconds count and prioritization is king.

Overly Simple Profiling

In order to get an idea of the queue contention, I profiled the time it took 1 to 100 threads to queue 10 000 items each. I'm running on a Core2 Duo processor, and the times were measured using GetTickCount, which probably explains why the low data points are a bit wild. I don't see much usefulness in these numbers, but I needed a pretty graph so make of it what you will. I'm open to suggestions for more relevant tests.

Conclusion

The completed queue class is posted below, along with comments. The class is 48 lines of code plus 82 lines of comments and white space. Lock-free stuff is not a joke: you have to explain yourself. In my next post I will be discussing futures, which will be another integral part of the call queue coming later on.

      ''' <summary>
    ''' A multiple-producer, single-consumer lock-free queue.
    ''' Does NOT guarantee an item has been queued when BeginEnqueue finishes.
    ''' Does guarantee an item will eventually be queued after BeginEnqueue finishes.
    ''' Does guarantee that, for calls simultaneously in BeginEnqueue, at least one will finish with its item having been enqueued.
    ''' Does guarantee that, if BeginEnqueue(Y) is called after BeginEnqueue(X) finishes, Y will follow X in the queue.
    ''' </summary>
    ''' <remarks>
    ''' Performance characteristics:
    ''' - All operations are guaranteed constant time.
    ''' - Latency between BeginEnqueue finishing and the item being enqueued can be delayed arbitrarily by slowing down only one of the producers.
    ''' - (How does this compare to CAS-based implementations in terms of average throughput? It should be higher?)
    ''' </remarks>
    Public Class SingleConsumerLockFreeQueue(Of T)
        ''' <summary>
        ''' Owned by the consumer.
        ''' This node is the end marker of the consumed nodes.
        ''' This node's next is the next node to be consumed.
        ''' </summary>
        Private head As Node = New Node(Nothing)
        ''' <summary>
        ''' This node is the tail of the last partially or fully inserted chain.
        ''' The next inserted chain will exchange its tail for the insertionPoint, then set the old insertionPoint's next to the chain's head.
        ''' </summary>
        Private insertionPoint As Node = head
        ''' <summary>
        ''' Singly linked list node containing queue items.
        ''' </summary>
        Private Class Node
            Public ReadOnly value As T
            Public [next] As Node
            Public Sub New(ByVal value As T)
                Me.value = value
            End Sub
        End Class
 
        ''' <summary>
        ''' Begins adding new items to the queue.
        ''' The items may not be dequeueable when this method finishes, but eventually they will be.
        ''' The items are guaranteed to end up adjacent in the queue and in the correct order.
        ''' </summary>
        ''' <remarks>
        ''' An example of what can occur when two items are queued simultaneously:
        ''' Initial state:
        '''   insert=head -> null
        '''   [queue is empty]
        ''' Step 1: First item is created and exchanged with insertion point.
        '''   head=prev1 -> null
        '''   insert=node1 -> null
        '''   [queue is empty]
        ''' Step 2: Second thread pre-empts and second item is created and exchanged with insertion point.
        '''   head=prev1 -> null
        '''   node1=prev2 -> null
        '''   insert=node2 -> null
        '''   [queue is empty]
        ''' Step 3: Second thread finishes setting prev.next.
        '''   head=prev1 -> null
        '''   node1=prev2 -> insert=node2 -> null
        '''   [queue is empty]
        ''' Step 4: First thread comes back and finishes setting prev.next.
        '''   head=prev1 -> node1=prev2 -> insert=node2 -> null
        '''   [queue contains 2 elements]
        ''' </remarks>
        ''' <implementation>
        ''' Each producer creates a new chain, and exchanges the shared insertion point for the tail of the new chain.
        ''' The producer then links the old insertion point to the head of the new chain.
        ''' A new chain might not be in the main chain when the function exits, but it will be in a chain that will eventually be in the main chain.
        ''' </implementation>
        Public Sub BeginEnqueue(ByVal items As IEnumerable(Of T))
            If items Is Nothing Then Throw New ArgumentNullException("items")
            If Not items.Any Then Return
 
            'Create new chain
            Dim chainHead As Node = Nothing
            Dim chainTail As Node = Nothing
            For Each item In items
                If chainHead Is Nothing Then
                    chainHead = New Node(item)
                    chainTail = chainHead
                Else
                    chainTail.next = New Node(item)
                    chainTail = chainTail.next
                End If
            Next item
 
            'Append chain to previous chain
            Dim prevChainTail = Threading.Interlocked.Exchange(Me.insertionPoint, chainTail)
            prevChainTail.next = chainHead
        End Sub
        ''' <summary>
        ''' Begins adding a new item to the queue.
        ''' The item may not be dequeueable when this method finishes, but eventually it will be.
        ''' </summary>
        ''' <implementation>
        ''' Just an inlined and simplified version of BeginEnqueue(IEnumerable(Of T))
        ''' </implementation>
        Public Sub BeginEnqueue(ByVal item As T)
            Dim chainOfOne = New Node(item)
            Dim prevChainTail = Threading.Interlocked.Exchange(Me.insertionPoint, chainOfOne)
            prevChainTail.next = chainOfOne
        End Sub
 
        ''' <summary>
        ''' Returns true if there were any items in the queue.
        ''' The return value is only stable if the queue is non-empty and you are calling from the consumer thread.
        ''' </summary>
        Public ReadOnly Property WasEmpty As Boolean
            Get
                Return head.next Is Nothing
            End Get
        End Property
 
        ''' <summary>
        ''' Returns the next item in the queue.
        ''' This function must only be called from the consumer thread.
        ''' </summary>
        Public Function Peek() As T
            If head.next Is Nothing Then Throw New InvalidOperationException("Empty Queue")
            Return head.next.value
        End Function
        ''' <summary>
        ''' Removes and returns an item from the queue.
        ''' This function must only be called from the consumer thread.
        ''' </summary>
        Public Function Dequeue() As T
            If head.next Is Nothing Then Throw New InvalidOperationException("Empty Queue")
            head = head.next
            Return head.value
        End Function
    End Class

Concurrency #0: Teaser

2009-07-03T17:12:00.002-03:00

Introduction

Concurrency (aka multithreading) is hard. No, I mean really hard. You just don’t realize how hard it is until you’ve actually done it. The upcoming posts are going to be all about how I do concurrency in .Net via message-passing. This post is a quick introduction to the series.

The "Simple" Way

It all seems so easy at first. You’re introduced to the humble lock, an easy way to make sure threads don't run over each other. Just hold the lock, and everything works, right? Then you hit your very first deadlock. Deadlocks are brutal. The simplest deadlock is when two threads acquire the same two locks, but in the opposite order. For example:
1. Thread 1 - Acquire lock 1.
2. Thread 2 - Acquire lock 2.
3. Thread 1 - Block trying to acquire lock 2, because Thread 2 has it.
4. Thread 2 - Block trying to acquire lock 1, because Thread 1 has it.
Now both threads can't make progress until the other one makes progress, so they're stuck forever. Any other threads that touch the locks are now also going to block forever.

Concurrent programming with locks is a delicate dance between ensuring the threads don't run over each other and making sure the threads don't deadlock. It's highly non-trivial, because those properties are inherently global. You can't just look at part of the program and know it is correct, you have to look at the program as a whole. Locks also don't compose, meaning if you have two methods which are synchronized using locks, the combination is not synchronized. For example if you only dequeue from a queue when it is not empty, a thread could remove the last element between the check and the dequeue.

Teaser

Don't despair, there are better ways to do concurrency! In this series, I will be focusing on message passing. I will build .Net classes for message passing, and I will give examples of using them. First up will be a lock free queue.