Frank Bakker

Takeaways from PDC09

2009-11-25T19:35:32Z

So after a few days back home I got some time to think about the takeaways from PDC09.

As you might have heard by now Microsoft did not have a lot of mayor announcements this year. Nothing of the scale of Windows Azure they came up with last year. They did release Windows Identity Foundation (FKA Geneva) and there is this thing they called Dallas, which is like a marketplace for online data that can be accessed by REST like services. But for the most of it it was more of what was already publically known.

So what did I take home from LA. For once it is good to see that Microsoft does not radically change its strategy, but instead continues on the road they set up in the last years. Further on there seems to be an increased focus on making things simpler and really make software development more productive. Visual Studio 2010 has some great new debugging features like intellitrace and the new features for debugging concurrent applications and the new features in the entity framework (Lazy loading / POCO support) will make it possible to get real productivity gains in in real life projects.

So PDC09 was not as spectacular as we all might have hoped, but it certainly was worth my while.

Getting ready for PDC09

2009-11-16T14:01:00Z

Last Saturday Marcel, Raimond and I arrived in LA to attend the Microsoft Professional Developers Conference 2009. We used Sunday to do some sightseeing and get used to the LA time zone. While I am not fully adapted yet I now have some time to kill before breakfast.

Even though the schedule contains a lot of session I am really looking forward to (most time slots have more than one interesting title so I will have to choose), most of it does not seem to be all that world shocking. Most sessions look like logical steps in the direction that was set out the last few years. But we might as well get totally flabbergasted by tomorrows key-note, we will just wait and see.

Today there are some pre-conference workshops, of which I plan to attend a Workshop called "Patterns of Parallel Programming". I will keep you posted of anything worth your and my time.

New coordination datastructures in .Net 4.0 Beta 2

2009-11-12T08:39:00Z

To be honest a have not spent too much time looking at .Net 4.0 beta 2 yet. But I do keep up with the blogs concerning Parallel Extensions. Josh Philps has just posted an entry about the changes that were made in the Coordination Data Structures (CDS) in Beta 2. The CDS are the types that have been added to the framework that will help writing concurrent applications without having to do (to much of) your own synchronization. I used two of the CDS classes (ConcurrentDictionary(Tkey, TVAlue) and Lazy<T>) in the CacheDictionary that I wrote about in this article.

public class CacheDictionary<TKey, TValue>   
    where TValue : class // needs to be a ref type due to current limitation of lazyInit<>   
{   
    ConcurrentDictionary<TKey, LazyInit<TValue>> _cacheItemDictionary = new ConcurrentDictionary<TKey, LazyInit<TValue>>();   
  
    public TValue Fetch(TKey key, Func<TValue> producer)   
    {   
        LazyInit<TValue> cacheItem;   
        if (!_cacheItemDictionary.TryGetValue(key, out cacheItem))   
        {   
            cacheItem = new LazyInit<TValue>(() => producer(), LazyInitMode.EnsureSingleExecution);   
  
            if (!_cacheItemDictionary.TryAdd(key, cacheItem))   
            {   
                // while we never remove items, if TryAdd fails it should be present   
                cacheItem = _cacheItemDictionary[key];   
            }   
        }   
        return cacheItem.Value;   
    }   
}  

In this cache I used ConcurrentDictionary<TKey, TValue> to store the cache items. To check if an item is present or should be created, I used TryAdd(key, cacheItem). This will return false if the item is allready present in the cache, in that case I assume the item can be retrieved from the dictionary with the indexer[]. This will work because the cache I implemented (unfortunately) does not yet support removals. If the cache would support any kind of mechanism to remove or invalidate items in the cache, the fetch method would have to handle the case of an item beeing removed between the TryAdd() and the retrieval.

The problem here is that up till beta 2 there was no good way to do the Add and "Get if allready present" in a single atomic operation. To work around this I would have to either use my own lock (that would remove all benefits of using a CuncurrentDictionary in the first place) or create a loop that keeps on calling TryAdd() and TryGetValue() until one of them succeeds.

I submitted this feedback to the parallel extensions forum with the suggestion to add an operation TryGetOrAddValue() that does these two operations in a single atomic method. I am pretty happy (and a bit proud :-) to see that this suggestion has found its way into the framework. The actual operation is now called GetorAdd(), (without the Try) which makes sense because either the Get or the Add will allways succeed. The PFX team really does seem to listen to custmer feedback!

As a bonus they actually added an overload for GetOrAdd which accepts a delegate that is executed only if the item was not yet in the dictionary. I have not yet looked into the details, but it looks like this does exactly what my CacheDictionary.Fetch operation did! This means that (unless I add support for cache expiration) my CacheDictionary will no longer be needed at all, as all its functionality has now been incorporated into the Framework! Now how Cool is that

Visualizing Linq operators: The Info Support Linq Posters

2009-03-17T07:25:00Z

Over the last few months I have been working on a little project to make Linq ‘come to life’ in two full size posters that developers can hang on the wall of their offices. The Linq posters demonstrates the usage of all Linq operators using visual sequences of female and male figures. Since this week the final result is ready and can be ordered in Print / Downloaded from our website http://www.infosupport.com/linq free of charge!

So why create a Linq poster?

Since even before C# 3.0 got out, a lot of articles and blog-posts have been written describing Linq. Most of these start with explaining the new C# language features: like extension Methods and Lambda expression and then explain how Linq is built on top of this, usually followed by the basics of comprehension syntax and the deferred execution model. What most of these articles don’t do, is give you a good overview of what is in the box, by that I mean the complete set of 50! operators that make up the Linq vocabulary. To really get all out of Linq that is in it I believe you should have a good sense of the available operators, because the real power of Linq is in it’s complete set of operators.

That is why we decided to create a set of two poster to visualize all available Linq operators (we could not fit all operators on a single poster at a reasonable scale). Each operator is demonstrated using a little sequence of colored female and male figures like the following example.

If you would like to decorate your office (or bedroom) in Linq style, visit our website http://www.infosupport.com/linq to get your copies.

CacheDictionary for .Net 3.5, using ReaderWriterLockSlim ?

2009-03-15T13:23:00Z

In my previous post I described how to create a thread safe data cache using PFX. PFX however is scheduled to be released as a part of the .Net framework 4.0 which means we will have to wait a while before we can use this in real world applications. That’s why I created an implementation using the generic Dictionary combined with a ReaderWriterLockSlim which are both available in .Net 3.5. today.

   1: public class CacheDictionary<TKey, TValue>   2: {   3:     ReaderWriterLockSlim _cacheLock = new ReaderWriterLockSlim();   4:     Dictionary<TKey, LazyInit<TValue>> _cacheItemDictionary = new Dictionary<TKey,LazyInit<TValue>>();   5:     6:     public TValue Fetch(TKey key, Func<TValue> producer)   7:     {   8:         LazyInit<TValue> cacheItem;   9:         bool found;  10:    11:         _cacheLock.EnterReadLock();  12:         try  13:         {  14:             found = _cacheItemDictionary.TryGetValue(key, out cacheItem);  15:         }  16:         finally  17:         {  18:             _cacheLock.ExitReadLock();  19:         }  20:    21:         if (!found)  22:         {  23:             _cacheLock.EnterWriteLock();  24:             try  25:             {  26:                 if (!_cacheItemDictionary.TryGetValue(key, out cacheItem))  27:                 {  28:                     cacheItem = new LazyInit<TValue>(producer);  29:                     _cacheItemDictionary.Add(key, cacheItem);  30:                 }  31:             }  32:             finally  33:             {  34:                 _cacheLock.ExitWriteLock();  35:             }  36:         }  37:    38:         return cacheItem.Value;  39:     }  40: }

This Implementation uses the (thread safe version of) the double-check locking pattern. This code first checks if the item exists using only a read lock, and only if the item is not found it acquire a write lock. To be sure the item was not added in between it checks again and adds the new item if it is still not found. Assuming there will be a fairly large amount of cache hits compared to cache misses, this is (in theory) more efficient than exclusively locking the dictionary right away, because multiple readers can get items from the cache concurrently and we only block other threads if we need to add a new item.

Just like in my previous implementation, I did not want to keeping the cache locked while actually retrieving or creating the item that needs to be cached. In the PFX version I did this by using LazyInit<T>, which will also be part of .Net 4.0 (They actually just renamed it to Lazy<T>). Because I wanted the cache to work on .Net 3.5, I created my own implementation of LazyInit<T> which is not as versatile and highly optimized as the .Net 4.0 version, but does the job and is actually quite simple (see code below). While the cache-wide write lock is held, all I do is create an instance of LazyInit<T> and store that instance in the dictionary. After the cache-wide lock is released I call LazyInit.Value which will actually call the delegate to create the item as needed. LazyInit<T> uses a lock as well, but each instance has it’s own lock object, this way each instance will be initialized exactly once, but different items can be initialized concurrently.

   1: public class LazyInit<T>   2: {   3:     Func<T> _producer;   4:     object _lock = new object();   5:     T _data;   6:     volatile bool _created;   7:     8:     public LazyInit(Func<T> producer)   9:     {  10:         _producer = producer;  11:     }  12:    13:     public T Value  14:     {  15:         get  16:         {  17:             if (!_created)  18:             {  19:                 lock (_lock)  20:                 {  21:                     if (!_created)  22:                     {  23:                         _data = _producer.Invoke();  24:                         _created = true;  25:                         _producer = null;  26:                     }  27:                 }  28:             }  29:             return _data;  30:         }  31:     }  32: }

Actually being quite happy with this implementation which does a minimum of locking while still being thread safe I sat back and relaxed.

Only A short time after I created this implementation, a blog post by Joe Duffy, the Lead developer / Architect behind PFX, showed up in my feed reader:

Reader/writer locks and their (lack of) applicability to fine-grained synchronization

In this post Joe compares the ReaderWriterLockSlim to (among others) a normal Mutex better known as the C# lock() statement. On a 4 core machine, when there are mostly readers and only a few writers, the reader/writer lock should theoretically be about 4 times as fast as the mutex. The reader / writer lock will allow multiple reader to execute concurrent on all four cores and the mutex only allows one thread to execute at a time leaving 3 cores idle while the other is holding the lock.

As it turns out, the mutex outperforms the ReaderWriterLockSlim in many scenario’s, especially in those cases where the locks are held for a relatively short time (like in a single peek in a dictionary). In stead of being 4 times faster the ReaderWriterLockSlim is actually about half as fast as the mutex! It seems that the internal book-keeping that needs to be done by the ReaderWriterLockSlim is way more expensive than the penalty of 3 cores being idle for a short time while 1 thread is holding the lock. Even Joe’s experimental highly optimized spinning ReaderWriterLock does not do a much better job in these scenario’s

ReaderWriterLockSlim start to outperform the mutex when the lock needs to be kept for a longer time (which you should generally avoid anyway). The number of cores will probably influence the results as well, I think running the same test on a 256 core box will increase the performance of the reader writer lock compared to the mutex, but unfortunately I have not been able to test this.

To test how this influenced my CacheDictionary, I created yet another implementation using a mutex in stead of the reader writer lock. Compared to the ReaderWriterLockSlim version this code is actually quite simple because it does not need to do the double check locking and the lock() statement does not require an explicit finally block. I did stick to the LazyInit aproach the avoid locking the whole cache while creating the items to cache.

   1: public class CacheDictionary<TKey, TValue>   2: {   3:     object _cacheLock = new object();   4:     Dictionary<TKey, LazyInit<TValue>> _cacheItemDictionary = new Dictionary<TKey,LazyInit<TValue>>();   5:     6:     public TValue Fetch(TKey key, Func<TValue> producer)   7:     {   8:         LazyInit<TValue> cacheItem;   9:    10:         lock (_cacheLock)  11:         {  12:             if (!_cacheItemDictionary.TryGetValue(key, out cacheItem))  13:             {  14:                 cacheItem = new LazyInit<TValue>(producer);  15:                 _cacheItemDictionary.Add(key, cacheItem);  16:             }  17:         }  18:         return cacheItem.Value;  19:     }  20: }

I ran some simple performance test on my dual core machine to compare this code to the ReaderWriterLockSlim version. My results were similar to Joe’s, the version with the Mutex is way faster then ReaderWriterLockSlim, even when there are only readers and not a single writer! The actual results depend on a lit of factors, like the number of items in the dictionary and of course the amount of work that is done in the delegate that produces the cache item, but in general the reader/writer version took about 1.5 times as long on the same scenario as the Mutex version. As in many cases: Simplicity wins!

For the near future, I will stay away from reader writer locks unless it is absolutely necessary to hold a lock for a fair amount of time. Maybe I will revisit this statement when commodity hardware reaches 32 or 64 cores.

Joe Duffy concludes his post on this topic with: “Sharing is evil, fundamentally limits scalability, and is best avoided.” While in general I think he is right, the whole point of a cache is to share the result of a previous request with future requests in order to improve performance. Since caching implies sharing you should always be aware of the concurrency issues involved, that is why I tried to handle most of these issues in this generic utility.

Implementing a Thread Safe cache using the Parallel Extensions

2008-12-31T14:19:00Z

Caching objects based on a key is a very common task in software development, making it both thread safe and scalable however is not quite trivial. That's why I implemented a generic implementation of such a cache, to handle the concurrency issues I used the Parallel Extensions to the .NET framework (PFX).

[Update: See this post for a cache that works with .Net 3.5 without PFX]

A implementation pattern I have seen quite often, uses a dictionary to store cached items based on a cache key and looks like the following:

   1: Dictionary<int, Item> _cachedItems = new Dictionary<int, Item>();   2: object _lock = new object();    3:     4: public Item GetItem(int id)   5: {       6:     Item result;       7:     if(!_cacheItems.TryGetValue(id, out result))       8:     {           9:         lock(_lock)          10:         {              11:             if(!_cacheItems.TryGetValue(id, out result))  12:             {                  13:                 result = CreateItem(id); // does the actual expensive work of creating the item  14:                 _cacheItems.Add(id, result);  15:             }  16:         }  17:     }      18:     return result;  19: }

This implementation uses a pattern known as 'double check locking', this allows for items already in the cache to be retrieved without using a lock, only if the item is not found it acquires a lock, checks again for the item having been added by another thread between checking the first time and acquiring the lock, and then creates the item and stores it for future use.

There are some problems with this implementation. The first and most important is that the MSDN documentation guarantees the dictionary only to be thread safe for multiple concurrent readers, not for reads and a write at the same time. In this implementation the first TryGetValue is done outside the lock and could conflict with an Add from an other thread. To get this right you will need to use more sophisticated locking using for instance a ReaderWriterLockSlim or always lock the entire cache even when only reading.

Another problem is that the CreateItem() Method, which does the actual expensive work to get the data we want to cache (e.g. call a Web Service), is done inside the lock that synchronizes access to the cache. This means that even if multiple different items are requested, only one item will be created at a time, this can be killing the performance you wanted to improve by caching. Finally this implementation requires the same pattern to be (wrongly) implemented over and over again because the code to create an item usually differs for every scenario.

To solve these problems once and for all I created a generic CacheDictionary using PFX. This CacheDictionary does not allow for items to be directly added or retrieved, instead the Fetch() method takes the key of the requested item and a delegate that will create the item if needed. If the item is found in the cache it will be returned, if not the provided delegate is invoked to create the item and store it for later use.

   1: public class CacheDictionary<TKey, TValue>      2:     where TValue : class // needs to be a ref type due to current limitation of lazyInit<>      3: {      4:     ConcurrentDictionary<TKey, LazyInit<TValue>> _cacheItemDictionary = new ConcurrentDictionary<TKey, LazyInit<TValue>>();      5:      6:     public TValue Fetch(TKey key, Func<TValue> producer)      7:     {      8:         LazyInit<TValue> cacheItem;      9:         if (!_cacheItemDictionary.TryGetValue(key, out cacheItem))     10:         {     11:             cacheItem = new LazyInit<TValue>(() => producer(), LazyInitMode.EnsureSingleExecution);     12:     13:             if (!_cacheItemDictionary.TryAdd(key, cacheItem))     14:             {     15:                 // while we never remove items, if TryAdd fails it should be present     16:                 cacheItem = _cacheItemDictionary[key];     17:             }     18:         }     19:         return cacheItem.Value;     20:     }     21: }  

To store the items I used the ConcurrentDictionary<TKey, TValue> provided with the September 2008 CTP of PFX. Internally the ConcurrentDictionary does all the required synchronization magic so I don't need to write a single lock myself. The ConcurrentDictionary looks a bit like the normal Dictionary<TKey, TValue>, but the methods are a bit different. In does for instance not support Add() and Remove() methods, but only TryAdd() and TryRemove(). This is because with a ConcurrentDictionary you can never be sure of it's state while other threads may be adding or removing items at any moment.

To use the ConcurrentDictionary as a store for the cache the first step is to Try to Get the item with a TryGetValue(). If it is not found the new item is 'created' and I Try to Add it to the cache. This might fail if another thread beat me to it, in that case I can be sure the item exists (I don't support removes yet) and just get it using the indexer.

Inside the ConcurrentDictionary I don't store the cached items directly. Instead I wrap the actual items in another class introduced by the PFX, LazyInit<T>. LazyInit<T> allows a very simple implementation of lazy object initialization. When creating an instance of LaziInt<T> the constructor expects a delegate that will create the item as needed. In this case I use the delegate that was provided in the call to Fetch() (due to some issues in the current CTP it can't be passed directly). When the LazyInit.Value property is called for the first time, the delegate is executed and the result is stored in this instance of LazyInit for any subsequent calls. Internally LazyInit has it's own synchronization logic which makes sure each item is created only once, this synchronization is done per instance of the LazyInit class. By using LazyInit here I'm sure each cache item is created only once without holding a lock for the the whole cache while doing so. Furthermore it allows me to 'try' to store the instance of the LazyInit object in the cache before actually creating the item itself. Only If the TryAdd() succeeds this instance of LazyInit is actualy used to create the item.

Note: In the current CTP of PFX, LazyInt<T> has some limitations, the most important one is that it will only allows T to be a reference type. That is why this CacheDictionary currently also requires TValue to be a reference type. It is expected that this limitation will be removed when PFX ships.

This CacheDictionary currently does not support expiration policies like for instance the ASP.Net web cache does. I found the ASP.Net cache however not to be very versatile while it only has one global cache store for an entire AppDomain and only allows string keys. Maybe pluggable expiration policies will be something for a next version of CacheDictionary, there are however a lot of scenario's where expiration is not really an issue and it is of course always possible to flush the entire CacheDictionary by just creating a new instance :-). Any suggestions for improvement however are welcome.

F# to ship as part of Visual Studio 2010

2008-12-11T07:46:29Z

To be honest I don't really like to blog about stuff that is already 'out there' on the web. There are however some topics that I personally think are important and don't always get the attention they deserve. These topics mostly concentrate around parallel programming (see my blogroll in the sidebar). So for these topics I will make an exception.

Today Don Syme announced that F# will be released with Visual Studio 2010. I had expected this news to get out at the PDC last October, but for some reason we were kept in the dark a little longer.

I think this is a mayor step in bringing functional programming to mainstream software development.

More context information in Linq queries

2008-12-02T10:28:00Z

Last week I posted on how to use an elements sequence number in Linq queries. In the project I just finished working on, we wrote a lot of Linq queries where we needed even more information related to an elements position in the sequence, like comparing it to the the element that came directly before or directly after it.

To be concrete: the input sequence contains all (ordered) historical versions of the same insurance policy object. From this sequence we need to filter all items for which a specific property has changed since the previous version. This could be implemented like:

   1: Version previous = null;   2:     3: foreach (var version in Versions)   4: {   5:     if (previous != null && previous.amount != version.amount)   6:     {   7:         // do something with this item   8:     }   9:     previous = version;  10: }

Once you have gotten addicted to the declarative style of Linq, writing code like this just doesn't cut it anymore. I wanted to be able to use the filtered items as a sequence so it can be used in a Linq query.

Using the pattern I described last week this could be written like

   1: Versions.select((item, index) => new {item, index}).Skip(1)   2:         .where(v=>Versions.ElementAt(v.index - 1).amount != v.item.amount)

This query finds each items index number and uses it to find the preceding item using the ElementAt() method. This makes it possible to compare each item to it's previous item in the where clause. The Skip(1) is needed because the first element obviously doesn't have a previous item.

The ElementAt() method however is not very efficient, because in most cases to find a single item it iterates the sequence from the begin to the requested item. Finding each item's preceding item by re-looping the sequence again can get you into serious performance issues when using larger sets.

Because I needed this kind of queries a lot in this project, I wanted to make then both easy to write and efficient in execution. So I wrote an extension method I called WithContext() that wraps each input item in a container object, along with some information about its context in the sequence. This allows for the code above to be written as:

   1: Versions.WithContext().Where(v=>v.Previous != null && v.Previous.Amount != v.Current.Amount)

To select the duration of each version, based on its own StartDate and the StartDate of the next item, I can now write:

   1: Versions.WithContext().Select(v.Next.StartDate - v.Current.StartDate)

WithContext() takes an IEnumerable<T> and returns an IEnumerable<ElementWithContext<T>>. ElementWithContext is a simple class that provides properties to retrieve the Current item as well as the Previous and the Next. While at it I added properties to get all Preceding and all Following items, as well as the sequence number.

   1: public class ElementWithContext<T>   2: {   3:     public T Previous { get; private set; }   4:     public T Current { get; private set; }   5:     public T Next { get; private set; }   6:     public int Index { get; private set; }   7:     8:     public IEnumerable<T> Preceding { get; private set; }   9:     public IEnumerable<T> Following { get; private set; }  10:    11:     internal ElementWithContext(T previous, T current, T next,  12:         int index, IEnumerable<T> preceding, IEnumerable<T> following)  13:     {  14:         Current = current;  15:         Previous = previous;  16:         Next = next;  17:         Index = index;  18:         Preceding = preceding;  19:         Following = following;  20:     }  21: }

The implementation of WithContext() looks a bit like the code in the first sample. It loops the input sequence and for each element it yields a new ElementWithContext. To find the next element I did a kind of 'look ahead' in the for loop. To do this I tweaked the input sequence so that it represents all 'Next' items' . I did this by first adding an empty element at the end (the last item does not have a Next item) and then skip the first item (the first 'next' item is the second in the sequence). This way WithContext() conforms to Linq's 'deferred execution' model by not taking more items from the input then necessary.

   1: static public IEnumerable<ElementWithContext<T>> WithContext<T>(this IEnumerable<T> source)   2: {   3:     // initialize the previous and current item for the first source element   4:     T previous = default(T);   5:     T current = source.FirstOrDefault();   6:     int index = 0;   7:     8:     // Loop all 'Next' items   9:     foreach (T next in source.Union(new[] { default(T) }).Skip(1))  10:     {  11:         yield return new ElementWithContext<T>(previous, current, next,  12:                 index, source.Take(index), source.Skip(index + 1));  13:    14:         previous = current;  15:         current = next;  16:         index++;  17:     }  18: }

One more item that I'll keep handy on my personal utility belt :-)

Oh, and thanks to Erno for pointing me to this Live Writer Add-In for the code snippets. I hope this helps reading these way to long code samples (sorry for that).

Selecting or filtering on the sequence number in Linq

2008-11-23T16:34:00Z

A few weeks ago I was writing a Linq query where I needed each items sequence number (or index) as a part of the filter expression in a Where operation. To simplify the actual problem let's say I needed to filter out only the odd items. One (wrong) way to do this would be:

int i = 0;
var filtered = input.Where(x => i++ % 2 == 1);

This will appear to work at first but it only works correct the first time the filtered sequence is iterated. I will not get into this to deep here, but it has to do with the lambda updating the outer variable which is a bad idea.
Fortunately there is a correct (and easier) way to do this. As it turns out the Where extension method has an extra overload that excepts a lambda function with two input parameters. When you use this overload the lambda receives an extra input parameter which indicates the sequence number of the current item. The correct code looks like this.

var filtered = input.Where((x, i) => i % 2 == 1);

As I wanted to write the rest of the query in Linq comprehension syntax (yes it does have some advantageous sometimes), I wanted to write something like

var filtered = from x in input
               // other Linq stuff
               where ???? % 2 == 1
               select x;

Comprehension syntax however does not have a built in way to refer to the sequence number (as far as I could find out in 15 min with Google). Bummer :-(

I did find that the Select method has an overload just like the Where method, that accepts a lambda with a sequence number parameter. This allows the sequence number to be used in the query's output.

var withSequenceNumber = input.select((item, index) => new {item, index})

Just like in the where clause, it is not possible to use the sequence number in comprehension syntax's select clause. It is however possible to mix normal C# syntax and comprehension syntax and make the sequence number available to all the comprehension syntax operators:

var filtered = from x in input.select((item, index) => new {item, index})
              // other Linq stuff
              where x.index %2 == 1
              select x.item;

By first selecting each item along with its sequence number into an anonymous type, the rest of the query can refer to the sequence number as x.index and the item itself as x.item. As an extra bonus the original sequence numbers of the items before filtering are still available after filtering, so they could be used in the select clause to be presented in the ouput.

Parallel Extensions for .Net Framework will be included in .Net 4.0

2008-10-16T07:24:00Z

I has been a while since I wrote a post on parallel programming. Since that time a lot has happend in field of parallel programming.

Microsoft has been working hard on implementing the Parallel Extensions for .Net Framewok (PFX) and has now anounced that it will be a core part of the next version of the .Net Framework (right into mscorlib.dll). See the post on the PFX blog PFX blog . If you are interested in Parallel programming I strongly recomend reading up on the PFX blog. I also expect more details to be anounced at the upcoming PDC (to bad I won't be there).

FPX includes a task scheduler that promisses to scale well beyond two of four CPU's / cores and allowes LINQ to objects queries to be executed parallel (PLINQ). The later, and probably lesser known aditions include so called Coordination Data Structures (CDS) these include thread safe collection classes, like stacks an queues. One of my personal favorites of the CDS is LazyInit<T>. LazyInit is a smart little helper class that makes it easy to implement Lazy Initialization of fields or local variables, of course this is done thread safe so that it can be used in parallel scenario's.

Can't wait to use these new goodies in real life projects!

More fun with Extension Methods and Lambda's: Creating a generic tree visitor

2008-06-06T06:10:00Z

One of the most common data structures in Software Engineering is the tree. In the .Net framework for instance you can find them in the file system, the controls of a win-forms application, nodes in an XML document etc.

A common task with trees is to traverse all nodes to look for a specific node or perform an operation on each node. This is usually called visiting. Many tree like data structures unfortunately don't have a built-in visiting mechanism, so we usually need to build this ourselves with something like a recursive method.

What I wanted to do is to write an generic implementation to visit any recursive tree. While the basic algorithm to do this is not very complicated, there are two factors that make it difficult to make the implementation generic, the first is that the type of the nodes is different for each tree, the second is that the way to obtain the children of a node is different for each tree. C# 2.0 solved the first problem with generics, and now C# 3.0 has solved the second problem with Lambda expressions.

A generic tree visitor should allow me to iterate all nodes as a single Enumerable<T>, which of course has the advantage that it can be used it a foreach or a Linq query. So the code I Would like to write to visit a tree would be something like the following:

foreach (var node in root.VisitDepthFirst(n => n.GetChildNodes()))

{

// ...

}

Where VisitDepthFirst is a generic extension method that operates on the root object. The extension method receives a Lambda expression that is used on a node to retrieve all it's children. For most trees this is a single property or method which return a collection of all child objects.

See the implementation of the depth first visitor below

static public IEnumerable<T> VisitDepthFirst<T>(this T root, Func<T, IEnumerable<T>> childSelector)

{

if (root == null) yield break;

// we return the root

yield return root;

// then we do a recursive Depth first search of all children and yield each item we find

foreach (var child in childSelector(root).SelectMany(c => c.VisitDepthFirst(childSelector)))

{

yield return child;

}

When testing this in a Win-forms application I first tried the following

foreach (var control in groupBox2.VisitDepthFirst(c => c.Controls))

{

control.Text = "Done";

}

This however leads to a a few compiler errors. The first is has to do with the fact that groupBox2 is of type GroupBox and not Control therefore the compiler expects the Lambda expression to return IEnumerable<GroupBox > instead of IEnumerable<Control>. The second problem is that the ControlsCollection does not implement a generic IEnumerable<> at all but in stead only the non-generic IEnumerable.

To fix this I had to be a bit more explicit about the type of the node and use Linq's Cast<>() Extension method to convert the Controls collection to IEnumerable<Control>. The following is the correct way to do this.

foreach (var control in groupBox2.VisitDepthFirst<Control>(c => c.Controls.Cast<Control>()))
{
control.Text = "Done";
}

Likewise visiting all nodes in an xml document is done as follows

foreach (XmlNode childNode in xmlDocument.VisitDepthFirst<XmlNode>(n => n.ChildNodes.Cast<XmlNode>()))

{

}

To be complete I also created a breath-first search. I don't know if I'll ever use it, but why not.

static public IEnumerable<T> VisitBreathFirst<T>(this T root, Func<T, IEnumerable<T>> childSelector)

{

if (root == null) yield break;

Queue<T> open = new Queue<T>();

// the open queue contains the items that have already been visited, but who's children have not

yield return root;

open.Enqueue(root);

while (open.Count >0)

{

T item = open.Dequeue();

foreach (T child in childSelector(item))

{

yield return child;

open.Enqueue(child);

}

While I think this is a nice example of generics and Lambda's, I have to be hones that I'm not quite sure if this should have been implemented as Extension Methods. The problem here is that these extension methods operate on any object without restriction, which makes them pop up in intellisense all over the place once you add the using directive. The alternative ofcource is to make it a normal static method and loose the syntactic sugar of extension methods.

Any comments on that one?

Using C# 3.0 Extension methods and Lambda expressions to avoid nasty Null Checks

2008-02-02T19:14:00Z

In the project I am currently working on we use a domain model with a quite deep nested structure of classes, code like the following is quite common.

// do something with the Adress
Console.Writeline(Contract.Parties.Client.Adress.Street);

The problem with this is that not all Contacts have a related Parties object and if we do have a Parties object sometimes the Client object is Null. This lead to writing a lot of code code like the following:

if (Conract != Null &&
    Contract.Parties != null &&
    Contract.Parties.Client != null &&
    Contract.Parties.Client.Adress != null)
{
    // do something with the Adress
    Console.Writeline(Contract.Parties.Client.Adress.Street);
}

There are a few problems with this code, the first of which is that it is quit verbose. Second it evaluates the same properties over and over again. In order to reduce the double work we could introduce some extra local variables and create a separete if statement for every step, this will make it even more verbose than it is allready.

Of course C# 3.0 has a lot of new syntax tricks, like extension methods, lambda expression and type inference. I had seen some nice examples (mostly Linq related) but had not been using these features to the max myself. Somehow I got the idea that these features would help me solve the Null checking problem.

I figured that the code I wanted to write was something like the following.

if (Contract
    .NullSafe(c => c.Parties)
    .NullSafe(p => p.Client)
    .NullSafe(c => c.Address) != null)
{
    // do something with the adress
    Console.Writeline(Contract.Parties.Client.Adress.Street);
}

The idea is that all parts of the path are expressed in separate lambda expressions which are chained together. If any link in the chain returns null, the rest of the path is never evaluated and the result of the whole expression will also be null.
All I had to do to make this possible was write one single extension method that would operate on any object, I was quite amazed that I could do this with verry little code that, besides some generic stuff, was actually quite simple.

        public static TResult NullSafe<T, TResult>(this T target, Func<T, TResult> func)
        {
            if (target != null)
                return func(target);
            else
                return default(TResult);
        }

All the generics make it look a lot more complicated than it actually is. This extension method receives two arguments, the first of which is the object it operates on and the second is a generic Func<T, TResult> delegate (the lambda expression). The return type of the extension method is automatically inferred from the return type of the lambda that is passed in. This allows you to call NullSafe again on the result of the first call and use IntelliSense to type p.Client in the second lambda.
The nice thing about extension methods is, besides that they can operate on any existing class without changing it, that they can also operate on Null references without causing a NullReferenceException!! This makes it possible to test for null inside the extension method. If the object it is called on is not null it evaluates the lambda expression and returns the result. Otherwise it returns the default value of the expected return type, for reference types this is Null.
To make life even better I created another overload of NullSafe that was even simpler

        public static void NullSafe<T>(this T target, Action<T> action)
        {
            if (target != null)
                action(target);
        }

Instead of a generic Func<T, TResult> delegate this one receives a Generic Action<T> delegate and returns void.
This removes the need to retype the whole path inside the if, it actually removes the if altogether.

Contract
    .NullSafe(c => c.Parties)
    .NullSafe(p => p.Client)
    .NullSafe(c => c.Address)
    .NullSafe(a =>
    {
        // do something with the adress
        Console.Writeline(a.Street);
    });

To bad for me, my current project is still on C# 2.0 so I'll keep doing it old school style :-(

Exercise

If you would also like some practice with C# 3.0, I would like challenge you to write something that allows me to do the same thing for IEnumerable<T>, I would like to write something like the following

foreach (Order order in Contract
    .NullSafe(c => c.Parties)
    .NullSafe(p => p.Client)
    .NullSafe(c => c.Orders)
    {
        // do something with order
        Console.Writeline(o.Amount);
    }

Where Client.Orders is of type IEnumerable<Order>. The idea is that I want to iterate every Order in Contract.Parties.Client.Orders. If at any stage in the path (including the Orders collection) we encounter a Null reference we will just loop an empty enumerator and do nothing.

Will our current programming model survive multi-core hardware?

2007-07-29T12:37:00Z

For years the innovations of CPU's have been focused on increasing the speed at which a single sequence of instructions gets executed (mainly by increasing the clock frequency). In the last years this trend is changing from increasing sequential execution speed to parallel execution (multi CPU / hyper-threading / multi core). If this trend continues the number of processor cores will no longer be measured in dual or quad, but in K, M or G.

Today's popular programming languages (both OO as procedural) encourage (or force) us to write software as a sequence of statements that get executed in a specific order. This paradigm is called an execution thread and it maps very nicely on the traditional CPU model which has a single instruction pointer. Executing tasks in parallel is made possible by calling a system API that creates a new execution thread. This is more a platform than a language feature, which requires even more system API's to do the required locking and synchronization.

Generally multi threading is considered an advanced and error prone feature. This is why it is generally used only in situations where parallel execution is an explicit requirement, like in server processes to handle multiple client requests and in GUI applications to allow background processing while the UI keeps handling user events. In situations where tasks could be executed parallel, but there is no direct need to do so, we usually stick to our traditional sequential programming model. This is a great waste of the hardware’s parallel processing ability

My personally experience to non-sequential languages is pretty much limited to SQL and XSLT. Maybe it is time to spread the horizon and take a look at some of the modern Functional languages like F# and Fortress. Who is with me?

Lack of support for generic base classes in Windows Forms designer

2007-04-28T11:25:00Z

Just recently having started my first real life .Net 2.0 project I wanted to utilize all the cool new features in my day-to-day job. One of those features is of course the support for Generics in C#. But, as with all cool stuff, getting your hopes up to high can get you disappointed.

In our Windows forms application we use a design pattern in which a UserControl defines a callback interface which is implemented by a mediator. This makes sure we have a loose coupling between the UserControl and the source of the rest of the application.

To avoid having a lot of duplicate code I decided to make a base class that does some of the stuff related to initializing the mediator. While every control will have a different mediator interface this called for generics (sample code is written by hand, so don't mind the compiler errors).

class ViewControlBase : UserControl <TMediator>
where TMediator : IMediator
{
TMediator _mediator;

protected TMediator Mediator
{
get { return _mediator; }
}

public InitMediator(IMediator mediator)
{
_mediator = (TMediator) mediator;
// some more generic stuff
}
}

Now the viewControls are derrived from ViewControlBase like this

class CustomerView : ViewControlBase<ICustomerMediator>
{
// ... Use typed access to the Mediator property
}

By using a generic base I was able to have Typed access to the Mediator in all the derived classes, and I avoided writing the initialization code over and over again. Hitting F5 proved all worked just as expected.

But when I opened one of the ViewControls in the designer the designer was filled with an error saying something was wrong. Usually this means that you have to rebuild the solution, clean up, rebuild some more and eventually it works. Not is time :-(

The error stated that the class CustomerView was not 'Designable' because it was not able to create an instance of ViewControlBase. That is true, it is however possible to create an instance of ViewControllerBase<TMediator>

I found a work-around (or a dirty Hack) by creating an empty dummy class like this

class CustomerView : CustomerViewDummy
{
//...
}

class CustomerViewDummy: ViewControlBase<ICustomerMediator>
{}

Now CustomerView is no longer (directly) derived from a generic class the designer stops complaining and shows the control in design view as expected. Since I didn't really like this solution I went back to old-school and duplicated the same code in every control (Bummer!)

Timezone aware DateTime stucture in .Net 2.0 ?

2007-03-22T20:00:00Z

The last year and a half I have been working on a project based on .Net framework 1.1, that (among other things) involved handling multiple time zones. If you have ever worked on such a project you either did it wrong without knowing or you have spent a whole lot of time getting it nearly 100% right. The biggest problems are the XML serialization that always assumes en DateTime represents local time, and the lack of a specific Date-only data type which is time zone independent. When it comes to handling DateTimes in different time zones .Net framework 1.1 just doesn't cut it.

Framework 2.0 brings partly good news, only last week I happened to 'intellisense' over a new property on the DateTime structure; DateTime.Kind. It seems that Microsoft has found a use for 2 unused bits in the 64 bits that hold up the data for a DateTime structure. These 2 bits were not enough to store the actual UTC offset. Instead they choose for three possible values, Local, UTC and Unknown. This is a big improvement because it solves the incorrect XML serialization problem of UTC DateTimes.

The lack of the actual UTC offset in the DateTime structure still has the downside of not being able to handle time zones other than UTC or your own (the one configured in the regional settings) without storing the offset in a separate field and doing your own transformations. Of course the DateTime being a structure which cannot be inherited from doesn't really help to create a generic solution for this one. Second it causes an ambiguity in the hour in the fall when the clock shifts to daylight saving time. This can cause an UTC time being converted to local and back to UTC not to be the same as the original. Last time this happened some of our unit tests broke because the daily build cycle runs exactly within this hour.