ConcurrentQueue is, like ConcurrentStack, a lockless collection, in that it is implemented without using any locks at all. However, the semantics required for a queue impose a quite different approach; unlike ConcurrentStack, which has a single point of concurrent contention, a queue can be changed at both the head and tail. This means that at least two variables are involved, most likely more. The simple approach of atomically modifying a single variable won't work here.

What does System.Collections.Generic.Queue do?

Well, let's have a look at the non-concurrent queue. This is implemented as a circular buffer. However, this design is very hard to use in a lockless way; when a new item is enqueued and the backing array is full, the array is doubled in size to accommodate the new item.

To resize the array, the entire contents of the queue has to be read sequentially without using locks and copied into a brand new array by a single thread, during which other threads can enqueue and dequeue items many times. This is very tricky to implement without being subject to race conditions and still ensure high performance.

So, instead, ConcurrentQueue forgoes the circular buffer, and uses a linear array instead. More specifically, it needs to be a linear array with a (conceptually) infinite capacity - although there will only be a finite number of items stored in the queue, items can be enqueued and dequeued an unlimited number of times. Such an array can't be created as a single object.

However, you don't need to keep the entire infinite array in memory, you only need the section of the array that is actually storing items. By splitting the array into finite segments you can create and discard segments as items get enqueued and dequeued to the queue. This is what ConcurrentQueue does.

Queue Segments

To demonstrate, I'll be using a queue with a segment size of 4. To start off with, three items are enqueued. These are added to the leftmost available slot of the tail segment:

Three more items are then enqueued. A new segment is created and assigned to the tail:

And another three:

Five items are then dequeued from the head. The head segment is now empty, so it is discarded:

Using this method, the illusion of an infinite linear array can be created using a finite number of segments.

Achieving thread-safety

ConcurrentQueue uses a segment size of 32, and along with the backing array each segment stores the index items are to be added (m_high) and where they are to be removed (m_low):

private class Segment {
    volatile T[] m_array;
    volatile int m_high;
    volatile int m_low;
}

Thread-safety, in this case, depends on the operation of both enqueuing and dequeuing. So we'll look at the operations in isolation, then put them both together.

Enqueuing

To enqueue an item, you need to:

1. Increment the m_high variable. This is now the index the item should be inserted at.
2. Assign the item to the specified slot in m_array.

public void Enqueue(T item) {
    int insertIndex = Interlocked.Increment(ref m_high);
    m_array[insertIndex] = item;
}

That's it! Simple, really...

Dequeuing

Dequeuing acts in a similar way to enqueuing:

1. Increment the m_low variable. The previous index is the index of the item to be dequeued.
2. Return the item stored at the specified slot in m_array.

public T Dequeue() {
    // Increment returns the incremented value of the variable
    int index = Interlocked.Increment(ref m_low);
    return m_array[index-1];
}

But hang on, if we're dequeuing items, we need to check whether the queue is empty first. So checks need to be added to determine when a queue is empty. This depends on the segment state that represents an empty segment. In the case of ConcurrentQueue, this state is when m_low > m_high.

The exact reasons for this specific state representing an empty segment are a gory implementation detail; if you're wondering the reasons for this, then start by working out exactly what m_high and m_low represent.

public bool TryDequeue(out T item) {
    if (m_low > m_high) {
        item = default(T);
        return false;
    }
    
    int index = Interlocked.Increment(ref m_low);
    item = array[index-1];
    return true;
}

All good? Well, no. We've actually introduced a subtle race condition. If we've got a queue with one item in it, and two threads trying to dequeue that one item, then if both threads perform the if (m_low > m_high) check before m_low has been incremented, one will dequeue the item and one will successfully dequeue on an empty queue.

In ConcurrentStack, a similar race condition was solved by using Interlocked.CompareExchange; taking a snapshot, doing some work, then atomically making that work visible to other threads only if the state is still valid. By judicious use of local variables and loops, we can do the same thing here:

public bool TryDequeue(out T item) {
    int index;
    do {
        index = m_low;
        
        // check if the queue is empty
        if (index > m_high) {
            item = default(T);
            return false;
        }
        
        // I think m_low has the same value as index. If it is, replace it with index+1.
        // Return to me what m_low actually was.
        if (Interlocked.CompareExchange(ref m_low, index+1, index) == index) {
            // success - index is now a valid index to dequeue, specific to this thread
            item = m_array[index]
            return true;
        }
        
        // m_low has been changed in the meantime. Go back to the start and try again.
    }
    while (true);
}

In this case, CompareExchange is acting as a conditional Increment.

Combining the two

This is where it gets complicated. The most obvious issue is another race condition, between enqueuing and dequeuing. To reiterate, the steps performed are:

1. Increment the m_high variable. This is now the index the item should be inserted at.
2. Assign the item to the specified slot in m_array.

1. Check if the queue is empty (m_low > m_high). If it is, return false.
2. Increment m_low (if m_low hasn't changed) and return the item.

Start with an empty queue. Thread 1 executes step 1 of enqueuing; m_high is incremented. Thread 2 then tries to dequeue an item; step 1 of dequeuing thinks the queue has items because m_low <= m_high. Step 2 of dequeuing then executes, and the item dequeued is the null value, because thread 1 hasn't yet assigned the enqueued item to the backing array.

Hmm, how to solve this? There's more than one variable involved here; the race condition involves the relationship between two variables, m_high and m_low, not a single variable being changed behind the scenes, which was the problem solved previously using CompareExchange and loops.

Well, we can't swap round the order of operations for enqueuing, because step 1 is what atomically assigns a slot when several threads are enqueuing items at once.

What we need is some sort of notification that enqueuing has finished assigned the item to the backing array. Then the dequeuing thread can wait for that notification before dequeuing the item from the queue:

1. Increment the m_high variable. This is now the index the item should be inserted at.
2. Assign the item to the specified slot in m_array.
3. Set state indicating the item at that index has been enqueued.

1. Check if the queue is empty (m_high >= m_low). If it is, return false.
2. Increment m_low (if m_low hasn't changed).
3. Wait for the state to be set at the index to dequeue.
4. Return the item.

This is the role played by the m_state array in ConcurrentQueue.Segment. Each segment has an int[] m_state alongside the T[] m_array; a 1 in a particular slot indicates the item has been set, and a 0 (the default value) indicates it isn't set. This turns the Enqueue method into this:

public void Enqueue(T item) {
    int insertIndex = Interlocked.Increment(ref m_high);
    m_array[insertIndex] = item;
    m_state[insertIndex] = 1;
}

public bool TryDequeue(out T item) {
    int index;
    do {
        index = m_low;
        
        if (index > m_high) {
            item = default(T);
            return false;
        }
        
        if (Interlocked.CompareExchange(ref m_low, index+1, index) == index) {
            // busywait until m_state[index] is set
            while (m_state[index] == 0) {}
            
            item = m_array[index]
            return true;
        }
    }
    while (true);
}

By marking both m_array and m_state as volatile, this stops the JIT reordering accesses to those arrays, ensuring that the invariant implicit in this code (m_state[index] == 1 if and only if m_array[index] has an item in it) doesn't get broken by the JIT or processors reordering instructions.

Tweaking the control flow a bit, and sprinkling calls to SpinWait.SpinOnce() around as the abstraction of a busywait, and you've got the code of the enqueue and dequeue methods of ConcurrentQueue.

Final notes

There's a couple of things I need to briefly mention. Firstly, I haven't yet covered growing the queue. Creating new segments when the current segment gets full is largely handled by enqueuing. When an item is added to the last slot in a segment, the Enqueue method creates a new segment and assigns it as the next segment in the queue using the m_next variable. When the dequeue method reaches the end of the current segment, it waits for the m_next variable to be set before looking inside that segment to see if there's an item to dequeue.

Secondly, the eagle-eyed among you might have noticed that dequeued items don't get removed from the backing array; they are still referenced from the array when items are dequeued. I can't see any specific threading reason for this, other than giving one less location for possible threading issues. However, more importantly, this guarantees that the invariant I mentioned above is never be broken, which can be important if you're reasoning about the collection.

Keeping references around longer than they need isn't so big an issue; the items referenced in the array are dereferenced all together when the containing segment is dereferenced. However it is something to bear in mind if you have large objects referenced in a ConcurrentQueue for a long time; they might not be garbage collected when they otherwise could be.

Concurrent principles

So what principles can we extract from this examination of ConcurrentQueue?

1. Separating threads

   Increment and CompareExchange are used to atomically assign each thread performing an action a separate slot. Each thread can then do work on that slot concurrently without conflicting with each other.

2. Invariants

   An invariant is used to eliminate a race condition between enqueuing and dequeuing, in this case, m_state[index] == 1 iff m_array[index] has an item in it. This ensures enqueuing and dequeuing on the same slot works as it should. Note that this invariant is maintained even at the cost of keeping things in memory longer than they should.

3. volatile used as a memory barrier

   Furthermore, volatile is used to add memory barriers ensuring the JIT doesn't reorder m_state and m_array array accesses and inadvertantly break the invariant.

Well, that's the core of the ConcurrentQueue class. I haven't even begun to cover the supporting methods, and glossed over most of the gory details. These I leave for you to explore and figure out. It's time to move on! We finally get some locks involved, and peer under the covers at ConcurrentDictionary.

The first concurrent collection we'll look at is ConcurrentStack. This is conceptually the same as System.Collections.Generic.Stack, but is geared towards occasional concurrent modifications.

Now, in these posts I won't be looking to explain what every method does; just like my other explorations of various collection types, I'll be concentrating on the core implementation and concepts used by the collections, and glossing over the more sordid implementation details and scaffolding required to support an ICollection.

So, without further ado, let's get started:

ConcurrentStack

There are three basic operations you can perform on a stack:

1. Push: Push a new value onto the top of the stack
2. TryPeek: Peeking at the top value. In ConcurrentStack, this is quite a simple method.
3. TryPop: Popping the top value off the stack

ConcurrentStack supplements these with PushRange and TryPopRange for pushing and popping an array of values, ToArray, and the standard ICollection methods.

The stack is implemented as a singly-linked list, with nodes represented by the ConcurrentStack<T>.Node private class:

private class Node {
    internal T m_Value;
    internal Node m_Next;
}

The top of the stack is referenced by the volatile m_head variable. An empty stack is represented by a null value in m_head. For example, if you push the integers 1, 2 and 3 onto the stack in that order, the nodes will look like this:

If you then pop a single value off the stack, m_head will point at the '2' node.

Pushing values

So, there are three operations required to push a new value onto the stack:

1. Create a new Node object to hold the new value
2. Setting the node's m_next variable to point to the current head node
3. Changing m_head to point to the newly-created node.

And, straight away, we've got the possibility of a race condition. Say Thread 1 is pushing the value '4' onto the stack. It's just executed step 2:

Now, Thread 2 is scheduled on the CPU and is pushing the value '5'. Thread 2 executes steps 1, 2 and 3:

Thread 1 then executes step 3:

The node successfully pushed by Thread 2 has disappeared from the stack.

So, what we want to do is perform step 3 only if the head hasn't changed in the meantime. If it has been changed, then go back to step 2 to use the updated head node as the value of m_next. Furthermore, this all has to be done atomically so other threads can't see the intermediate state.

This is where Interlocked.CompareExchange comes into play. If you recall my previous post, CompareExchange performs the following as an atomic operation:

public static T CompareExchange<T>(ref T location, T value, T comparand)
  where T : class {
    T origValue = location;
    if (location == comparand)
        location = value;
    return origValue;
}

I think location has the same value as comparand. If it is, replace it with value. Return me what location actually is.

This allows us to do the 'check and assign a new head, else try again' operation atomically, like so:

public void Push(T item) {
    Node node = new Node(item);
    do {
        node.m_next = m_head;
    }
    while (Interlocked.CompareExchange(ref m_head, node, node.m_next) != node.m_next);
}

Or, as words:

1. Create a new node
2. Set the node's next field to the current head
3. atomically{I think the current head is the value of the node's next field. If it is, replace it with the new node}. If the head was't actually the same as the next field, go back to 2.

This has eliminated the race condition we had between steps 2 and 3. Only if the head hasn't been changed is the new node pushed onto the stack as the new head. This loop repeats until CompareExchange successfully sets the head to the new node.

This can easily be generalised to a range of values in PushRange - we can simply change step 1 to construct the list of nodes holding the values being pushed, then using the m_next field of the tail node, and the top node as the new head, like so:

So that's pushing values onto the stack. What about removing them?

Popping values

As you can expect, popping items from the stack can be done in a similar way to pushing them:

Node topNode;
do {
    topNode = m_head;
}
while (Interlocked.CompareExchange(ref m_head, m_head.m_next, topNode) != topNode);

However, it's not quite so simple as that. For one thing, the stack may be empty, so m_head might be null. For another, you need to be able to pop several items off the stack as a single atomic operation, which requires navigating several m_next references at once. We need to be slightly more clever about it.

Let's cover checking for an empty stack first. Checking for null is easy, right? if (m_head == null) return false; So we put this at the start of the pop method:

public bool TryPop(out T item) {
    if (m_head == null) {
        item = default(T);
        return false;
    }

    Node topNode;
    do {
        topNode = m_head;
    }
    while (Interlocked.CompareExchange(ref m_head, m_head.m_next, topNode) != topNode);
    
    item = topNode.m_value;
    return true;
}

However, again, we've got a race condition. The null check only happens once. If another thread were to empty the stack while the current thread is inside the while loop, this leaves us with a NullReferenceException lying in wait when we try and get m_head.m_next.

The simple way to fix this is to do the null check inside the loop, eliminating the race condition:

public bool TryPop(out T item) {
    Node topNode;
    do {
        topNode = m_head;
        
        if (topNode == null) {
            item = default(T);
            return false;
        }
    }
    while (Interlocked.CompareExchange(ref m_head, m_head.m_next, topNode) != topNode);
    
    item = topNode.m_value;
    return true;
}

Sorted. So, what about popping multiple values off the stack? Again, like the null check, this has to be performed inside the while loop using the 'snapshot' of the head we've taken in topNode:

public int TryPopRange(T[] items, int count) {
    int i;
    Node topNode;
    do {
        topNode = m_head;
        Node curNode = topNode;
        i=0;

        while (i<count && curNode != null) {
            items[i] = curNode.m_value;
            curNode = curNode.m_next;
            i++;
        }
    }
    while (Interlocked.CompareExchange(ref m_head, curNode, topNode) != topNode);
    
    return i;
}

In fact, this idea of taking the current head, doing some work on it, then atomically swapping it if it hasn't been changed in the meantime can be generalised:

1. Take an atomic snapshot of the current state
2. Do some work on the snapshot locally to the current thread
3. Atomically make the work visible to all other threads, if the snapshot you took is still a valid representation of the state
4. If it isn't, go back to the start and try again

This is, at its core, how ConcurrentStack works.

Performing atomic operations

So, what underlying aspects of the system let us perform these operations atomically?

1. Object references are atomic
   This lets us take an atomic snapshot of the current state simply by storing the value of m_head in a local variable; m_head will always be pointing at a valid node (or null), it won't be 'half-changed'.
2. Interlocked.CompareExchange is atomic
   This ensures the state-check-and-switch won't be afflicted by race conditions with other threads.
3. m_head is a volatile variable
   m_head is marked as volatile. This means that any changes to that variable by one thread are instantly visible to all other threads on the system; there's no caching to get in the way. Any threads that are attempting to modify m_head will be forced to try again, and they won't overwrite the changes already made.

Gory implementation details

Now, I said at the start that I wouldn't be covering gory implementation details of these collections. However, in this case, there are some important considerations.

If you decompile ConcurrentStack, you'll notice there's a Push method and a PushCore method (similarly for TryPop and TryPopRange). This is a small but significant performance detail; ConcurrentStack assumes there aren't going to be any thread collisions. The public methods all optimistically attempt to perform the operation once. Only if another thread gets in the way do the corresponding Core methods get executed. It is these that contain the full loop logic, along with calls to SpinWait.SpinOnce to try and get the other threads out of the way before they try again.

In fact, TryPopCore goes one step further, and implements a randomised exponential backoff to reduce the chances of several threads all waiting the same amount of time. It does mean that, although ConcurrentStack is lockless, and so eliminates the risk of deadlock, the performance will suffer if there are many threads all modifying the stack at the same time, as each method will have to try several times before its operation succeeds.

That's the essence of how ConcurrentStack is implemented. Next time, I'll take a look at the second lockless concurrent collection, ConcurrentQueue, which goes about achieving thread-safety in quite a different way.

Footnote

I'm now on twitter! If you want to get in touch, comment on the series, or suggest other things I could look at, my username is @simonmcooper

If you've ever had a poke around System.dll or System.Core.dll in Reflector, you may have noticed TypeForwardedToAttributes applied to the assembly:

[assembly: TypeForwardedTo(typeof(Lazy<>))]
[assembly: TypeForwardedTo(typeof(LazyThreadSafetyMode))]
[assembly: TypeForwardedTo(typeof(Action))]
[assembly: TypeForwardedTo(typeof(Action<,>))]
[assembly: TypeForwardedTo(typeof(Action<,,>))]
[assembly: TypeForwardedTo(typeof(Action<,,,>))]

Type forwards

TypeForwardedToAttribute is part of a feature introduced in .NET 2 - Type forwarding. As the documentation says, this is a feature that allows a type to be moved to a different assembly without having to recompile assemblies using that type. This is used extensively by the class libraries when types were moved from System.Core.dll to mscorlib.dll between .NET 3.5 and 4, allowing assemblies compiled against .NET 2 and 3.5 to run on the .NET 4 framework as-is, without having to be recompiled.

However, if you think about it, this is much more than a simple attribute; this is a core change to the CLR type resolution mechanism. Every type that is resolved in an assembly first has to check for the existance of a type forward indicating the type has been moved somewhere else.

This isn't something that can easily be represented in a simple attribute; TypeForwardedToAttribute is actually an example of a pseudo custom attribute.

ExportedType

First, a bit of background. The ExportedType metadata table was originally designed to be used in multi-module assemblies as part of the 'public contract' of an assembly; the manifest module for the assembly would contain an entry in ExportedType for every public type defined in other modules, comprising

• TypeName & TypeNamespace: the exported type's full name
• Implementation: the module (or nested ExportedType) the type can be found.
• TypeDefId: the index within the TypeDef table in the module the type is located.

This allows any tool referencing the multi-module assembly to only need to look in the manifest module to find every public type defined in the assembly and where it can be found; it doesn't have to scan every module comprising the assembly.

When .NET 2 came along, ExportedType was repurposed to store type forwards as well. If Implementation is a reference to an assembly rather than a module, then that assembly is the new location of the type named by TypeName and TypeNamespace (type forwards don't allow you to change the type name or namespace).

So, when the C# compiler sees a type forward in System.Core.dll specified by the attribute

[assembly: TypeForwardedTo(typeof(Action))]

• TypeName: Action
• TypeNamespace: System
• Implementation: assembly reference to mscorlib
• TypeDefId: 0 (type forwards don't use this field)

TypeForwardedFrom

Finally, TypeForwardedFromAttribute is the counterpart to TypeForwardedToAttribute; it specifies the assembly a type has been forwarded from (using an assembly name string, rather than a direct metadata assembly reference). However, unlike TypeForwardedTo, this is a normal attribute, has no effect on CLR type resolution, and exists primarily for bookkeeping purposes.

Type forwards may seem like a niche feature aimed at library writers, but they are invaluable in the right circumstances. In the BCL, they allow programs compiled against the .NET 2 and 3.5 frameworks to run on the .NET 4 framework without needing to be recompiled.

Over the next few weeks, we'll be performing experiments on SmartAssembly to confirm or refute various hypotheses we have about how people use the product, what is stopping them from using it to its full extent, and what we can change to make it more useful and easier to use. Some of these experiments can be done within the team, some within Red Gate, and some need to be done on external users.

External testing

Some external testing can be done by standard usability tests and surveys, however, there are some hypotheses that can only be tested by building a version of SmartAssembly with some things in the UI or implementation changed. We'll then be able to look at how the experimental build is used compared to the 'mainline' build, which forms our baseline or control group, and use this data to confirm or refute the relevant hypotheses.

However, there are several issues we need to consider before running experiments using separate builds:

1. Ideally, the user wouldn't know they're running an experimental SmartAssembly. We don't want users to use the experimental build like it's an experimental build, we want them to use it like it's the real mainline build. Only then will we get valid, useful, and informative data concerning our hypotheses.

2. There's no point running the experiments if we can't find out what happens after the download. To confirm or refute some of our hypotheses, we need to find out how the tool is used once it is installed. Fortunately, we've applied feature usage reporting to the SmartAssembly codebase itself to provide us with that information.

3. Of course, this then makes the experimental data conditional on the user agreeing to send that data back to us in the first place. Unfortunately, even though this does limit the amount of useful data we'll be getting back, and possibly skew the data, there's not much we can do about this; we don't collect feature usage data without the user's consent. Looks like we'll simply have to live with this.

4. What if the user tries to buy the experiment? This is something that isn't really covered by the Lean Startup book; how do you support users who give you money for an experiment? If the experiment is a new feature, and the user buys a license for SmartAssembly based on that feature, then what do we do if we later decide to pivot & scrap that feature? We've either got to spend time and money bringing that feature up to production quality and into the mainline anyway, or we've got disgruntled customers. Either way is bad. Again, there's not really any good solution to this.

5. Similarly, what if we've removed some features for an experiment and a potential new user downloads the experimental build? (As I said above, there's no indication the build is an experimental build, as we want to see what users really do with it). The crucial feature they need is missing, causing a bad trial experience, a lost potential customer, and a lost chance to help the customer with their problem. Again, this is something not really covered by the Lean Startup book, and something that doesn't have a good solution.

So, some tricky issues there, not all of them with nice easy answers. Turns out the practicalities of running Lean Startup experiments are more complicated than they first seem!

You may have noticed that not a lot has happened to SmartAssembly in the past few months. However, the team has been very busy behind the scenes working on an entirely new version of SmartAssembly.

SmartAssembly 6.5

Over the past few releases of SmartAssembly, the team had come to the realisation that the current 'architecture' - grown organically, way before RedGate bought it, from a simple name obfuscator over the years into a full-featured obfuscator and assembly instrumentation tool - was simply not up to the task. Not for what we wanted to do with it at the time, and not what we have planned for the future.

Not only was it not up to what we wanted it to do, but it was severely limiting our development capabilities; long-standing bugs in the root architecture that couldn't be fixed, some rather...interesting...design decisions, and convoluted logic that increased the complexity of any bugfix or new feature tenfold.

So, we set out to fix this. Earlier this year, a new engine was written on which SmartAssembly would be based. Over the following few months, each feature was ported over to the new engine and extensively tested by our existing unit and integration tests. The engine was linked into the existing UI (no easy task, due to the tight coupling between the UI and old engine), and existing RedGate products were tested on the new SmartAssembly to ensure the new engine acted in the same way. The result is SmartAssembly 6.5.

The risks of a rearchitecture

Are there risks to rearchitecting a product like SmartAssembly? Of course. There was a lot of undocumented behaviour in the old engine, and as part of the rearchitecture we had to find this behaviour, define it, and document it. In the process we found some behaviour of the old engine that simply did not make sense; hence the changes in pruning & obfuscation behaviour in the release notes. All the special edge cases we had to find, document, and re-implement.

There was a chance that these special cases would not be found until near the end of the project, when everything is functionally complete and interacting together. By that stage, it would be hard to go back and change anything without a whole lot of extra work, delaying the release by months. We always knew this was a possibility; our initial estimate of the time required was '4 months, ± 4 months'. And that was including various mitigation strategies to reduce the likelihood of these issues being found right at the end. Fortunately, this worst-case did not happen.

However, the rearchitecture did produce some benefits. As well as numerous bug fixes that we could not fix any other way, we've also added logging that lets you find out exactly why a particular field or property wasn't pruned or obfuscated. There's a new command line interface, we've tested it with WP7.1 and Silverlight 5, and we've added a new option to error reporting to improve the performance of instrumented apps by ~10%, at the cost of inaccurate line numbers in reports.

So? What differences will I see?

Largely none. SmartAssembly 6.5 produces the same output as SmartAssembly 6.2. The performance of 6.5 will be much faster for some users, and generally the same as 6.2 for the remaining. If you've encountered a bug with previous versions of SmartAssembly, I encourage you to try 6.5, as it has most likely been fixed in the rearchitecture. If you encounter a bug with 6.5, please do tell us; we'll be doing another release quite soon, so we'll aim to fix any issues caused by 6.5 in that release.

Most importantly, the new architecture finally allows us to implement some Big Things with SmartAssembly we've been planning for many months; these will fundamentally change how you build, release and monitor your application. Stay tuned for further updates!

Apart from Dictionary<TKey, TValue>, there's two other dictionaries in the BCL - SortedDictionary<TKey, TValue> and SortedList<TKey, TValue>. On the face of it, these two classes do the same thing - provide an IDictionary<TKey, TValue> interface where the iterator returns the items sorted by the key. So what's the difference between them, and when should you use one rather than the other? (as in my previous post, I'll assume you have some basic algorithm & datastructure knowledge)

SortedDictionary

We'll first cover SortedDictionary. This is implemented as a special sort of binary tree called a red-black tree. Essentially, it's a binary tree that uses various constraints on how the nodes of the tree can be arranged to ensure the tree is always roughly balanced (for more gory algorithmical details, see the wikipedia link above).

What I'm concerned about in this post is how the .NET SortedDictionary is actually implemented. In .NET 4, behind the scenes, the actual implementation of the tree is delegated to a SortedSet<KeyValuePair<TKey, TValue>>. One example tree might look like this:

Each node in the above tree is stored as a separate SortedSet<T>.Node object (remember, in a SortedDictionary, T is instantiated to KeyValuePair<TKey, TValue>):

class Node {
    public bool IsRed;
    public T Item;
    public SortedSet<T>.Node Left;
    public SortedSet<T>.Node Right;
}

The SortedSet only stores a reference to the root node; all the data in the tree is accessed by traversing the Left and Right node references until you reach the node you're looking for. Each individual node can be physically stored anywhere in memory; what's important is the relationship between the nodes.

This is also why there is no constructor to SortedDictionary or SortedSet that takes an integer representing the capacity; there are no internal arrays that need to be created and resized. This may seen trivial, but it's an important distinction between SortedDictionary and SortedList that I'll cover later on.

And that's pretty much it; it's a standard red-black tree. Plenty of webpages and datastructure books cover the algorithms behind the tree itself far better than I could. What's interesting is the comparions between SortedDictionary and SortedList, which I'll cover at the end.

As a side point, SortedDictionary has existed in the BCL ever since .NET 2. That means that, all through .NET 2, 3, and 3.5, there has been a bona-fide sorted set class in the BCL (called TreeSet). However, it was internal, so it couldn't be used outside System.dll. Only in .NET 4 was this class exposed as SortedSet.

SortedList

Whereas SortedDictionary didn't use any backing arrays, SortedList does. It is implemented just as the name suggests; two arrays, one containing the keys, and one the values (I've just used random letters for the values):

The items in the keys array are always guarenteed to be stored in sorted order, and the value corresponding to each key is stored in the same index as the key in the values array. In this example, the value for key item 5 is 'z', and for key item 8 is 'm'.

Whenever an item is inserted or removed from the SortedList, a binary search is run on the keys array to find the correct index, then all the items in the arrays are shifted to accomodate the new or removed item.

For example, if the key 3 was removed, a binary search would be run to find the array index the item was at, then everything above that index would be moved down by one:

and then if the key/value pair {7, 'f'} was added, a binary search would be run on the keys to find the index to insert the new item, and everything above that index would be moved up to accomodate the new item:

If another item was then added, both arrays would be resized (to a length of 10) before the new item was added to the arrays.

As you can see, any insertions or removals in the middle of the list require a proportion of the array contents to be moved; an O(n) operation. However, if the insertion or removal is at the end of the array (ie the largest key), then it's only O(log n); the cost of the binary search to determine it does actually need to be added to the end (excluding the occasional O(n) cost of resizing the arrays to fit more items).

As a side effect of using backing arrays, SortedList offers IList Keys and Values views that simply use the backing keys or values arrays, as well as various methods utilising the array index of stored items, which SortedDictionary does not (and cannot) offer.

The Comparison

So, when should you use one and not the other? Well, here's the important differences:

• Memory usage
  

  SortedDictionary and SortedList have got very different memory profiles. SortedDictionary...

  1. has a memory overhead of one object instance, a bool, and two references per item. On 64-bit systems, this adds up to ~40 bytes, not including the stored item and the reference to it from the Node object.
  2. stores the items in separate objects that can be spread all over the heap. This helps to keep memory fragmentation low, as the individual node objects can be allocated wherever there's a spare 60 bytes.

  In contrast, SortedList...

  1. has no additional overhead per item (only the reference to it in the array entries), however the backing arrays can be significantly larger than you need; every time the arrays are resized they double in size.

     That means that if you add 513 items to a SortedList, the backing arrays will each have a length of 1024. To conteract this, the TrimExcess method resizes the arrays back down to the actual size needed, or you can simply assign list.Capacity = list.Count.

  2. stores its items in a continuous block in memory. If the list stores thousands of items, this can cause significant problems with Large Object Heap memory fragmentation as the array resizes, which SortedDictionary doesn't have.

• Performance

  Operations on a SortedDictionary always have O(log n) performance, regardless of where in the collection you're adding or removing items. In contrast, SortedList has O(n) performance when you're altering the middle of the collection.

  If you're adding or removing from the end (ie the largest item), then performance is O(log n), same as SortedDictionary (in practice, it will likely be slightly faster, due to the array items all being in the same area in memory, also called locality of reference).

So, when should you use one and not the other? As always with these sort of things, there are no hard-and-fast rules. But generally, if you:

• need to access items using their index within the collection
• are populating the dictionary all at once from sorted data
• aren't adding or removing keys once it's populated

• don't know how many items are going to be in the dictionary
• are populating the dictionary from random, unsorted data
• are adding & removing items randomly

The default (again, there's no definite rules on these sort of things!) should be to use SortedDictionary, unless there's a good reason to use SortedList, due to the bad performance of SortedList when altering the middle of the collection.

Developers might write good code, but no matter how good they are the result will always have bugs in it. It's up to the testers in the team to make sure the final product is as bug-free as it can be.

Deciding what to test

Within a project there's normally no official documentation produced, no official record of what the project should accomplish. The closest thing we get to documentation is the greenlight presentation slides (I'll be covering the greenlight process in a later post). This means there's no specification to validate against, no way of confirming that the project is 'complete'. So how does a tester know what to test in the first place?

Within Red Gate, the same team normally stays on the same product for several minor and major releases (as an example, the same team has worked on SQL Source Control since it's inception back in 2009). Everyone within the team has an intimite knowledge of what the tool does, what problems it solves, how customers use it, and what the main bugs and issues are. Testers are as much a part of the team as the developers or project manager.

This means testers simply don't need a specification. They know how customers use the tool, what bugs they're running into, how new features should interact with existing ones, and (roughly) how they actually work. The testers are fully involved in the project from day 1. This gives the testers deep knowledge of the application and application domain, so they know where and what they should test to ensure the final product works.

How to test a product

As with other things at Red Gate, there's no officially-mandated way of testing a product, no documentation that needs to be produced. It's entirely up to the testers to decide how they want to test the product. Most of the time this will involve writing automated unit and integration tests to run on the build server with each new build. When testing the user interface, this usually means manual testing of all the different parts of the UI to make sure it all behaves sensibly whatever actions the user performs (although some testers are experimenting with automated UI testing).

As a product matures, it gains more and more tests. Not just tests for new features, but tests covering specific bugs encountered by customers. SQL Compare, our oldest existing product, now has over 30,000 unit and integration tests, whereas SmartAssembly (the product I'm working on) was acquired by Red Gate a couple of years ago, and has about 1000 unit tests and counting; Jason's writing more all the time.

At the end of the project, it's up to the testers to give the final go-ahead to release the product to customers. They need to be satisfy themselves that the product is as bug-free as it can be and the new features work as they should, on every configuration the product will be run on, using whatever tools and methods they see fit. Only then does the installer go up on the website, and the online documentation and product web pages updated with the new features and new documentation.

Testers are an integral part of the project team, and only they decide when the product can be released. They act as Red Gate's gatekeepers and quality control.

The vast majority of Red Gate is on the first and second floors (the second and third floors in US parlance) of an office building in Cambridge Business Park (here we are!). As you can see, the building is split into three sections; the two wings, and the section between them.

As well as being organisationally separate, the four divisions are also split up in the office; each division has it's own floor and wing, so everyone in the division is working together in the same area (.NET and DBA on the left, SQL Tools and New Business on the right). The non-divisional parts of the business share wings with the smaller divisions, again keeping each group together.

The canteen

One of the downsides of divisionalisation is that communication between people in different decisions is greatly reduced. This is where the canteen (aka the SQL Servery) comes in. Occupying most of the central section on the first floor, the canteen provides free cooked lunch every day, and is where everyone in the company gathers for lunch.

The idea is to encourage communication between the divisions; having lunch with people in a different division you wouldn't otherwise talk to helps people keep track of what's going on elsewhere in the company. (I'm still amazed at how the canteen staff provide a wide range of superbly cooked food for over 200 people out of a kitchen in which, if you were to swing a cat, it would get severe head injuries.). There's also table tennis and table football tables that anyone can use, provided you can grab them when they're free!

Office layout

Cubicles are practically unheard of in the UK, and no one, including the CEOs, has separate offices. The entire office is open-plan, as you can see in this youtube video from when we first moved in (although all the empty desks are now full!). Neil & Simon, instead of having dedicated offices, move between the different divisions every few months to keep up to date with what's going on around the company; sitting with a division gives you a much better overall impression of how the division's doing than written status reports from the division heads.

There's also the usual plethora of meeting rooms scattered around the place; when we first moved in in 2009 we had a competition to name them all. We've got Afoxalypse A & B, Seagulls A & B, Traffic Jam, Thinking Hats, Camelids A & B, Horses, etc. All the meeting rooms have pictures on the walls corresponding to their theme, which adds a nice bit of individuality to otherwise fairly drab meeting rooms. Generally, any meeting room can be booked by anyone at any time, although some groups have priority in certain rooms (Camelids B is used a lot for UX testing, the Interview Room is used for, well, interviews).

And, as you can see from the video, each area has various pictures, post-its, notes, signs, on the walls to try and stop it being a dull office space. Yes, it's still an office, but it's designed to be as interesting and as individual as possible.