Enhanced Weak Events Part Two - Immutable Event Entry List

Posts in this series

- Part One: DynamicMethod vs. Expression Tree Compilation
- Part Two: Immutable Event Entry List (this post)
- Part Three: Synchronized Events (to be written)
- Part Four: Custom Events and unsolved problems (to be written)
- Dynamic Code Generation With Lambda Expressions (to be written)

C# Events - Basics

Just for a start, let me reinforce some preliminary definitions in an very factual way.

• Delegates are tuples composed by a reference (A) to a method, and a reference (B) to a target object.
  - All delegates are made immutable;
  - The reference (B) will be null if the method is static;
  - When a delegate is invoked, the referenced method is called. If the method is an instance method, the target object reference is used;
  
• Multicast Delegates encapsulate a collection of delegates.
  - When invoked, all of its delegates are invoked in an unspecified order;
  - Multicast delegates can only be created by composition or decomposition. Composition is the merging of two delegates into a new multicast delegate. Decomposition is a subtraction of one delegate from another;
  - There's no such thing as an empty multicastdelegate. If a decomposition would create one, the result is null;
  - For all purposes, a multicast delegate is a delegate;
  
• C# Events are nothing more than a special type of property that have add and remove accessors instead of get and set.
  - Only events of a delegate type can be declared;
  - Due to the special accessors, only the class that owns the event can reset its value or invoke its delegate, if it's not null;
  - When add is called, the current delegate is composed with the delegate that was provided;
  - Conversely, remove does a decomposition;
  

C# Events - Not So Basics

Having said that, let's dive deeper. When it comes to c# events, there are two interesting problems that can be easily overseen. The simpler one is that an event is always initialized with null, and they can always be decomposed to null later on. In other words, an event can be null at any time. Since it's not possible to invoke a null delegate (without causing a NullReferenceException), any class that provides an event has be to sure that the event is not null before invoking it.

The other problem appears in multithreaded applications. A thread might be adding or removeing an event handler while the event is in the middle of an invocation. This is a race situation, and has to be correctly handled. If you want to check a complete explanation on this subject, I recommend you to read Eric's post on events and races.The generally recommended solution to both problems is the following pattern:

var handler = this.MyEvent;
if (handler != null) handler(this, eventArgs);

Now, let's move to main subject of this post.

Mutable Event Entry List

As you may already have noticed, my custom events were born from Daniel Grunwald's WeakEvents. Internally, to represent each event entry* he chose to use a List<EventEntry>. Using regular a List<T> seems very convenient. It will make add and remove operations simple and quick to execute, but there is a downside. List<T>'s are mutable.

One of the major disadvantages of mutable objects appear on multithreaded applications. Consider the problems that I've introduced above. They apply to custom events too. Alas, that invocation pattern can't be used.

One goo point is that even an empty WeakEvent will never be null, so we don't event-is-null problem. The concurrency problem, though, can't be avoided. As the event entry list is mutable, any access to it should be synchronized if we want to make the custom event thread-safe.

Looking at Grunwald's code that makes the invocation of a WeakEvent, I noticed that the entry list is copied to an array before invoking the entries. No locks are made. Is that enough? Unfortunately, the answer is no. Copying the list to an array is not an atomic operation. If the list is modified in the middle of the copy, things will probably get messy. Even if he had enclosed the copy in a lock block, there would still be the performance problem caused by the copy itself.

* An event entry is an abstraction of an event handler delegate. Weak event entries, for example, serve the same purpose of a regular delegate. The sole difference being that it does not keep a strong reference to the target object.

Immutable Event Entry List

Naturally, my suggestion is to use an immutable list to store event entries. By the way, as I mentioned in the beginning, all delegates are immutable. And regular c# events use immutable multicast delegates internally. There's probably a good reason they did it that way, and I don't see why custom events should differ. Let's consider some aspects of this decision.

• Lower invocation overhead: There's no need to copy event entries before invoking them because the list does never change. All that's needed before the invoking is to read the current list object and store a reference to it in a local variable. If the event is changed by other thread, a new list will be created, but the invocation will be working on an untouched list object.
  
  The only possible problem may happen when an handler is removed, but an invocation is being made. The result is that the handler is invoked even after it has been removed from the event. Actually, this is a third interesting problem. The post from Eric Lippert (events and races) that I've suggested earlier talks about this stuff too. If you read it, you'll see that my custom events are actually imitating the exactly same behavior that regular c# events have.
  
  Unfortunately, there is also a trade-off involved. Add and remove operations will be inevitably slower. Each time they happen, a new list has to be created, and a partial copy of the current entries will be made. Personally, invoking performance has higher priority than adding or removing performance, so I think this trade-off is acceptable. If anyone disagrees, I'll be very happy to hear your thoughts.
  
  
• Thread-safety: Invoking an event when its entry list is immutable completely thread-safe without any need for locks. That's a great win.
  
  Add and remove, on the other hand, are not thread safe. I can say as an excuse that the mutable-list-approach is not thread-safe too. At least, I did not created a problem that was not there before.
  
  Looking at regular events, we can see that even they are not thread-safe when it comes to add and remove. Would the C# language team let so big a hole in the language? Of course not. The solution is hidden from the programmer's eyes. Whenever you declare a regular c# event, the compiler generates the two accessors (add and remove). Both of them are them decorated with this custom attribute:[System.Runtime.CompilerServices.MethodImpl(MethodImplOptions.Synchronized)]. You can make a test assembly and decompile it to see. Or you can read this old MSDN article too.
  
  So, in my opinion, locking should be avoided unless there's no alternative. In a reusable component (like custom events), it's preferable to let it be not thread-safe and free of locks than forcing an overhead that is not always required. A developer that uses your component should be able to use any synchronization mechanism he wants, and only if needed. Inside the .NET Framework, almost all collection implementations are not synchronized for this reason. Following the same pattern, I won't put any locks on my Custom Events. User developers should be aware of that, and put locks around add/remove it they need it.
  

Conclusion

In a world where multi-core processors are everywhere, multithreading and immutability are increasingly important. If you want to read more about immutability in C#, you might want to check this out.

If you read this far, you probably are interested in events. A very extensive article you might want to read is on codeproject.

Finally, as usual, here is the download link for the latest version (v1.1) the my CustomEvents' source code. See ya!

Microsoft Parallel Extensions CTP released

In the past years, evolution of computing is turning to the grounds of high level concurrecy. Processors are becoming faster by being multi-core, and not by having higher frequencies. The time is coming so that even simple programs will be concurrent too. Parallel programs are harder to code, harder to test and can cause pseudo-random bugs that can drive programmers crazy. The best solution for this, as to many problems, is a dependable library and/or language support.

There are several types of problems that require specific solutions. Making a responsive UI, for instance. How many application have you seen that simply stay frozen while it's processing something? I've made some of them myself. And the programmer cannot be blamed, most projects don't have the time (and money) to invest on a responsive UI. The WPF framework solves this in a very neat way. Its interface engine is fully concurrent. But that's a subject for other post.

Yesterday, Microsoft released another CTP of its Parallel Extensions (PFX) library. You may get the details at their blog or at MSDN. In case you're not familiar with it, I'll give a short brief here. Basically, the library's comprehended by three parts:

- Task Parallel Library
Provides some imperative ways to express parallelism. The simpler one is the Invoke method. It receives a set of actions in the form of delegates and executes them concurrently, returning after all the actions have completed. If you have a loop in which iterations may run in parallel, you can use the For or the ForEach methods. When the problem requires a little more elaboration, there's the Task system. It's a set of classes that works somewhat like what the ThreadPool class does, but with much greater flexibility and control.

- PLINQ
It's a implementation of LINQ that allows anyone to easily make declarative parallel queries. All it's needed is to transform the IEnumerable<t> into a IParallelEnumerable<t> using the AsParallel() extention method. It's not optimized yet, but it certainly can boost many applications with almost no code change.

- Coordination Data Structures
It has a group of synchronization classes that enhance those that currently exists in the framework. Also, there are some thread-safe collection classes. Coincidently, they've created a ConcurrentQueue class that serves the same purpose as the one I've posted!

A detail that you can't avoid noticing in this framework is the extensive use of delegates. LINQ itself is based on delegates being passed to other functions. This type of construct is called a higher-order function. Another construct that is present in PFX is the continuation. Also, there are recurrent remarks in its documentation about side-effects and why they have to be avoided. All these characteristics are usually associated with functional langagues. No surprise some of the samples are in F#.

Functional programming has lived almost only at the academic world, but its future looks different. It holds a lot of interesting and useful concepts. The disturbing part is that very few programmers really know these concepts. Do you know any skilled/experienced/old programmer that can't understand OO programming? Well, can you really understand functional programming? I don't. At least not yet.

A C# BlockingQueue

Ok, things didn't go as I planned, so I'll stop promising and start delivering. This time I'll share with you a code I've used before.

The problem is quite simple and is not new: exchange messages between threads. One possible solution is message queuing, but it's too bulky to use inside a single process. The simplest way to make threads communicate is through shared variables, but it's obviously too simple.

So, what kind of feature I was looking for? To begin with, it needed to be fast and light. Secondly, it had to work in a fire-and-forget fashion, i.e., I wanted a thread to be able to send a message (or task, job, whatever) to another thread and go on. Obviously, in order to such a thing to function, it would have to use some sort of internal buffer. So, it looked like what I needed was a thread-safe FIFO queue.

All right, I could simply use a Queue<t> and wrap its calls around a lock statement. Or, even easier, use a non-generic Queue and transform if by calling the Queue.Synchronized() method. In both ways, we'd get a simply synchronized thread-safe queue.

Is that all? Of course not. Suppose we have a producer-consumer problem to solve. Usually, when the buffer is empty, the consumer is supposed to idly wait for an new item. How could we accomplish that using a synched queue? If we try to dequeue from an empty Queue, a exception is thrown. We could check the item count before dequeueing, but there would be two steps involved and it wouldn't be thread-safe even if the Queue instance is synched. Another possibility is catching the queue-is-empty exception, which is a very lousy trick. Anyway, we wouldn't be able to avoid writing synchronization code and this is not what I wanted.

So, considering that you are introduced to the problem, let me show the wish list that I gathered in the form of an interface:

public interface IBlockingQueue
{
/// <summary>Max number of item in the queue (-1 means there's no limit)</summary>
int MaxQueueDepth { get; }

/// <summary>Returns false when there's something wrong, e.g., queue full</summary>
bool TryEnqueue(object item);

/// <summary>Returns false when there's no message to read</summary>
bool TryDequeue(out object item);

/// <summary>Returns false when a timeout or an abort happens</summary>
bool WaitEnqueue(object item, int millisecondsTimeout, FuncGetVolatileFlag ExternalAbortSignaled);

/// <summary>Returns false when a timeout or an abort happens</summary>
bool WaitDequeue(out object item, int millisecondsTimeout, FuncGetVolatileFlag ExternalAbortSignaled);
}

public delegate bool FuncGetVolatileFlag();

TryDequeue() and TryEnqueue are two simply synchronized methods to access the queue. The other two (WaitDequeue() and WaitEnqueue()) are much more interesting. The first one will try to dequeue and, if the queue is empty, will wait for a new item. The latter will try to enqueue and, if the queue is full, will wait until there's room for the new item.

But that's still not enough. A common problem in a multithreaded application is when you need to close it and there are some threads still running. There's several possible approaches on how to close them. The safer choice might be to wait for every thread to end, but it might take too long. One alternative is to terminate everyone, but it's very risky. I think the best pick is to ask somehow the threads to stop and wait until they do so. With my blocking queue, you can choose between any of the 3.

Let me explain how. As you can see, I've put two addicional parameters. Both have the same purpose: cancel the action and return the code execution to the client code. Whilst the fisrt is obviously a timeout, one might wonder what that other parameter is. It's a delegate of a type that accepts functions that like this:bool func(). Its name is ExternalAbortSignaled and its type name is FuncGetVolatileFlag, so I hope it's not hard to recognize how it's used.

In order to eliminate any doubts, I'll describe it. The idea is that, while waiting, the ExternalAbortSignaled delegate will be called in short intervals. If it returns true at any time, the waiting ends and no item is enqueued/dequeued. Also the function returns false. In that way, it's possible to provide the queue an anonymous method that merely returns the value of a boolean flag. Whenever the flag is set to true, the wait function will return promptly and the application as a whole will be able to respond faster.

As you may know, java has a built-in BlockingQueue already. Sadly, java has direct support for delegates. So, I think it would be hard to code a functionality like an abort flag in an elegant way.

Now, if you want to know what is the best way to implement the waiting synchronization code, I'll let the explanation to Joseph, which is much more eloquent than me. It might be a good idea to take a look at my source code too. The technique that I've chosen is through Wait and Pulse.

Some ideas for future enhancements that I've thought of are:
- TryPeek() and WaitPeek()
- Transactions

Source code download link at google code

[Updated at 2008-04-28]