Coding for Performance : Collections

.NET provides over 21 built-in collection types, including concurrent and generic versions of many popular data structures. Most programs will only need to use a combination of these and you should rarely need to create your own.

Some collections still exist in the .NET Framework only for backward compatibility reasons and should never be used by new code. These include:

• ArrayList
• Hashtable
• Queue
• SortedList
• Stack
• ListDictionary
• HybridDictionary

The reasons these should be avoided are casting and boxing. These collections store references to Object instances in them so you will always need to cast down to your actual object type.

The boxing problem is even more pernicious. Suppose you want to have an ArrayList of Int32 value types. Each value will be individually boxed and stored on the heap. Instead of iterating through a contiguous array of memory to access each integer, each array reference will require a pointer dereference, heap access (likely hurting locality), and then an unboxing operation to get at the inner value. This is horrible. Use a non-resizable array or one of the generic collection classes instead.

In the early versions of .NET there were some string-specific collections that are now obsolete because of the power of generics. Examples include NameValueCollection, OrderedDictionary, StringCollection, and StringDictionary. They do not necessarily have performance problems per se, but there is no need to even consider them unless you are using an existing API that requires them.

The simplest, and likely the most-used, collection is the humble Array. Arrays are ideal because they are compact, using a single contiguous block, which improves processor cache locality when accessing multiple elements. Accessing them is in constant time and copying them is fast. Resizing them, however, will mean allocating a new array and copying the old values into the new object. Many of the more complicated data structures are built on top of arrays.

Choosing which collections to use depends on many factors, including: semantic meaning in the APIs (push/pop, enqueue/dequeue, Add/Remove, etc.), underlying storage mechanism and cache locality, speed of various operations on the collection such as Add and Remove, and whether you need to synchronize access to the collection. All of these factors can greatly influence the performance of your program.

Generic Collections

The generic collection classes are

• Dictionary<TKey, TValue>
• HashSet
• LinkedList
• List
• Queue
• SortedDictionary<TKey, TValue>
• SortedList<TKey, TValue>
• SortedSet
• Stack

These deprecate all of the non-generic versions and should always be preferred. They incur no boxing or casting costs and will have better memory locality for the most part (especially for the List-style structures that are implemented using arrays).

Within this set, though, there can be very large performance differences. For example, Dictionary, SortedDictionary, and SortedList all store key-value relationships, but have very different insertion and lookup characteristics.

• Dictionary is implemented as a hash table and has O(1) insertion and retrieval times. See Appendix B for a discussion of Big O notation if you are not familiar with this.
• SortedDictionary is implemented as a binary search tree and has O(log n) insertion and retrieval times.
• SortedList is implemented as a sorted array. It has O(log n) retrieval times, but can have O(n) insertion times in the worst case. If you insert random elements it will need to resize frequently and move the existing elements. It is ideal if you insert all of the elements in order, and then use it for fast lookups.

Of the three, SortedList has the smallest memory requirements because it uses arrays. The other two will have much more random memory access, but can guarantee better insertion times on average. Which one of these you use depends greatly on your application’s requirements.

The difference between HashSet and SortedSet is similar to the difference between Dictionary and SortedDictionary.

• HashSet uses a hash table and has O(1) insertion and removal operations.
• SortedSet uses a binary search tree and has O(log n) insertion and removal operations.

List, Stack, and Queue all use arrays internally and thus have good locality of reference for efficient operations on many values, however when adding a lot of values, they will resize these internal arrays as needed. To avoid wasteful resizing and the CPU and GC overhead it causes, if you know the size beforehand, you should always pre-allocate the needed space by passing a capacity value via the constructor or changing the collection’s Capacity property. List has O(1) insertion, but O(n) removal and searching. Stack and Queue can only add or remove from one end of the collection so have O(1) time in all operations.

LinkedList has O(1) insertion and removal characteristics, but it should be avoided for primitive types because it will allocate a new LinkedListNode object for every item you add, which can be wasteful overhead.

Concurrent Collections

They are all located in the System.Collections.Concurrent namespace and are all defined for use with generics:

• ConcurrentBag (A bag is similar to a set, but it allows duplicates)
• ConcurrentDictionary<TKey, TValue>
• ConccurentQueue
• ConcurrentStack

Most of these are implemented internally using Interlocked or Monitor synchronization primitives. You can and should examine their implementations using an IL reflection tool.

Pay attention to the APIs for insertion and removal of items from these collections. They all have Try methods which can fail to accomplish the operation in the case another thread beat them to it and there is now a conflict. For example, ConcurrentStack has a TryPop method which returns a Boolean value indicating whether it was able to pop a value. If another thread pops the last value, the current thread’s TryPop will return false.

ConcurrentDictionary has a few methods which deserve special attention. You can call TryAdd to add a key and value to the dictionary, or TryUpdate to update an existing value.
Chapter 6 • Using the .NET Framework
190
Often, you will not care whether it is already in the collection and want to add or update it—it does not matter. For this, there is the AddOrUpdate method which does exactly that, but rather than having you provide the new value directly, you instead need to pass two delegates: one for add and one for update. If the key does not exist, the first delegate will be called with the key and you will need to return a value. If the key does exist, the second delegate is called with the key and existing value and you need to return a new value (which could just be the existing value).

In either case, the AddOrUpdate method will return to you the new value—but it is important to realize that this new value may not be the value from the current thread’s AddOrUpdate call! These methods are thread safe, but not atomic. It is possible another thread calls this method with the same key and the first thread will return the value from the second thread.

There is also an overload of the method that does not have a delegate for the add case (you just pass in a value).

A simple example will be helpful:

 dict.AddOrUpdate( 

// Key I'm trying to add 0,

 // Delegate to call when adding--return string value based on the key 

key => key.ToString(), // Delegate to call when already present -- update existing value

 (key, existingValue) => existingValue); 

dict.AddOrUpdate(

 // Key I'm trying to add 

0,

 // Value to add if new 

"0", 

// Delegate to call when already present--update existing value

 (key, existingValue) => existingValue);

The reason for having these delegates rather than just passing in the value is that in many cases generating the value for a given key is a very expensive operation and you do not want two threads to do it simultaneously. The delegate gives you a chance to just use the existing value instead of regenerating a new copy. However, note that there is no guarantee that the delegates are called only once. Also, if you need to provide synchronization around the value creation or update, you need to add that synchronization in the delegates themselves—the collection will not do it for you.

Related to AddOrUpdate is the GetOrAdd method which has almost identical behavior.

string val1 = dict.GetOrAdd(

// The key to retrieve

0,

// A delegate to generate the value if not present

k => k.ToString());

string val2 = dict.GetOrAdd(

// The key to retrieve

0,

// The value to add if not present

“0”);
The lesson here is to be careful when using concurrent collections. They have special requirements and behaviors in order to guarantee safety and efficiency, and you need to understand exactly how they are used in the context of your program to use them correctly and effectively.

Other Collections

There are a handful of other specialized collections that ship with .NET, but most of them are string-specific or store Objects so can safely be ignored. Notable exceptions are BitArray and BitVector32.

BitArray represents an array of bit values. You can set individual bits and perform Boolean logic on the array as a whole. If you need only 32 bits of data, though, use BitVector32 which is faster and has less overhead because it is a struct (it is little more than wrapper around an Int32).

Creating Your Own Collection Types

I have rarely had the need to create my own collection types from scratch, but the need does occasionally arise. If the built-in types do not have the right semantics for you, then definitely create your own as an appropriate abstraction. When doing so, follow these general guidelines:

1. Implement the standard collection interfaces wherever they make sense (IEnumerable, ICollection, IList, IDictionary<TKey, TValue>).
2. Consider how the collection will be used when deciding how to store the data internally.
3. Pay attention to things like locality-of-reference and favor arrays if sequential access is common.
4. Do you need to add synchronization into the collection itself? Or perhaps create a concurrent version of the collection?
5. Understand the run-time complexity of the add, insert, update, find, and remove algorithms. See Appendix A for a discussion of Big O complexity.
6. Implement APIs that make semantic sense, e.g. Pop for stacks, Dequeue for queues.

For all your application development needs, visit www.verbat.com for a fiscally conscious proposal that meets your needs ( So I can keep this blog going as well!!!!)

Alternatively click through the link   if you found this article interesting. (This will help the companies Search engine rankings)