InfoQ

News

On the Evolution of the .NET Collections

Posted by Jonathan Allen on Jun 05, 2008 03:22 PM

Community
.NET
Topics
.NET Framework ,
Open Source ,
Programming

The collections in the .NET Framework have evolved significantly over the years. Taking advantage of Microsoft's new found openness, we show two versions of a familiar data structure, the hash table, in both .NET and Mono.

In theory the hash table is a rather simple construct, just collection of arrays or linked lists divided into a finite number of buckets. Yet even the act of retrieving an item can be rather complex if you try to be too clever with multi-threading logic.

//   Copyright (c) Microsoft Corporation.  All rights reserved.

public virtual Object this[Object key] {
         get {
             if (key == null) {
                 throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
             }
             uint seed;
             uint incr;

             // Take a snapshot of buckets, in case another thread does a resize
             bucket[] lbuckets = buckets;
             uint hashcode = InitHash(key, lbuckets.Length, out seed, out incr);
             int  ntry = 0;
             bucket b;
             int bucketNumber = (int) (seed % (uint)lbuckets.Length);
             do
             {
                 int currentversion;
                 //     A read operation on hashtable has three steps:
                 //        (1) calculate the hash and find the slot number.
                 //        (2) compare the hashcode, if equal, go to step 3. Otherwise end.
                 //        (3) compare the key, if equal, go to step 4. Otherwise end.
                 //        (4) return the value contained in the bucket.
                 //     After step 3 and before step 4. A writer can kick in a remove the old item and add a new one
                 //     in the same bukcet. So in the reader we need to check if the hash table is modified during above steps.
                 //
                 // Writers (Insert, Remove, Clear) will set 'isWriterInProgress' flag before it starts modifying
                 // the hashtable and will ckear the flag when it is done.  When the flag is cleared, the 'version'
                 // will be increased.  We will repeat the reading if a writer is in progress or done with the modification
                 // during the read.
                 //
                 // Our memory model guarantee if we pick up the change in bucket from another processor,
                 // we will see the 'isWriterProgress' flag to be true or 'version' is changed in the reader.
                 //
                 int spinCount = 0;
                 do {
                     // this is violate read, following memory accesses can not be moved ahead of it.
                     currentversion = version;
                     b = lbuckets[bucketNumber];

                     // The contention between reader and writer shouldn't happen frequently.
                     // But just in case this will burn CPU, yield the control of CPU if we spinned a few times.
                     // 8 is just a random number I pick.
                     if( (++spinCount) % 8 == 0 ) {
                         Thread.Sleep(1);   // 1 means we are yeilding control to all threads, including low-priority ones.
                     }
                 } while ( isWriterInProgress || (currentversion != version) );
                 if (b.key == null) {
                     return null;
                 }
                 if (((b.hash_coll & 0x7FFFFFFF) == hashcode) &&
                     KeyEquals (b.key, key))
                     return b.val;
                 bucketNumber = (int) (((long)bucketNumber + incr)% (uint)lbuckets.Length);
             } while (b.hash_coll < 0 && ++ntry < lbuckets.Length);
             return null;
         }

Yes folks, there is a pseudo-spin lock and call to Threading.Sleep in there.

With .NET 2.0 and generic collections, Microsoft decided to dump the internal locking mechanisms for collections. Instead, any locking must be applied externally. This gives us the much simpler code found in the Generic.Dictionary class.

//   Copyright (c) Microsoft Corporation.  All rights reserved.

private int FindEntry(TKey key) {
    if( key == null) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    if (buckets != null) {
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
        }
    }
    return -1;
}

The Mono versions of the Hashtable and Dictionary are likewise very different from each other and from the Microsoft implementations.

// Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)

public virtual Object this[Object key]
{
     get
     {
         if (key == null)
             throw new ArgumentNullException("key", "null key");

         Slot[] table = this.table;
         int[] hashes = this.hashes;
         uint size = (uint)table.Length;
         int h = this.GetHash(key) & Int32.MaxValue;
         uint indx = (uint)h;
         uint step = (uint)((h >> 5) + 1) % (size - 1) + 1;

         for (uint i = size; i > 0; i--)
         {
             indx %= size;
             Slot entry = table[indx];
             int hashMix = hashes[indx];
             Object k = entry.key;
             if (k == null)
                 break;

             if (k == key || ((hashMix & Int32.MaxValue) == h
                 && this.KeyEquals(key, k)))
             {
                 return entry.value;
             }

             if ((hashMix & CHAIN_MARKER) == 0)
                 break;

             indx += step;
         }

         return null;
     }

And their dictionary implementation.

// Copyright (C) 2004 Novell, Inc (http://www.novell.com)
// Copyright (C) 2005 David Waite
// Copyright (C) 2007 HotFeet GmbH (
http://www.hotfeet.ch)

public TValue this [TKey key] {
    get {
        if (key == null)
            throw new ArgumentNullException ("key");

        // get first item of linked list corresponding to given key
        int hashCode = hcp.GetHashCode (key);
        int cur = table [(hashCode & int.MaxValue) % table.Length] - 1;
        // walk linked list until right slot is found or end is reached
        while (cur != NO_SLOT) {
            // The ordering is important for compatibility with MS and strange
            // Object.Equals () implementations
            if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key))
                return valueSlots [cur];
            cur = linkSlots [cur].Next;
        }
        throw new KeyNotFoundException ();
    }

 

Well there you have it; four ways to do essentially the same time. The one with the Sleep command is undoubtedly the worse, I'll it to you to decide which is the best.

1 comment

Reply

Collections by Sam Allen Posted Jun 5, 2008 7:28 PM
  1. Back to top

    Collections

    Jun 5, 2008 7:28 PM by Sam Allen

    Very interesting, wish I knew more

Exclusive Content

Ruby.rewrite(Ruby)

In this RubyFringe talk, Reginald Braithwaite writes Ruby code to read, write, and rewrite Ruby. Demos include extending Ruby with conditional expressions, call-by-name and more.

Book Except and Interview : Aptana RadRails, An IDE for Rails Development

Aptana RadRails: An IDE for Rails Development by Javier Ramírez discusses the latest Aptana RadRails IDE, a development environment for creating Ruby on Rails applications.

Fast Bytecodes for Funny Languages

Cliff Click discusses how to optimize generated bytecode for running on the JVM. Click analyzes and reports on several JVM languages and shows several places where they could increase performance.

Scott Ambler On Agile’s Present and Future

Scott Ambler, Practice Lead for Agile Development at IBM, speaks on the current status of the Agile community and practices having a look at the perspective of the Agile’s future.

Manager's Introduction to Test-Driven Development

Dave Nicolette and Karl Scotland try to introduce non-technical managers to one of the most popular Agile development techniques: Test-Driven Development (TDD).

Structured Event Streaming with Smooks

Smooks is best known for its transformation capabilities, but in this article Tom Fennelly describes how you can also use it for structured event streaming.

How to Work With Business Leaders to Manage Architectural Change

Successful architectures evolve over time to meet changing business requirements. Luke Hohmann presents how to collaborate with key members of your business to manage architectural changes.

Colors and the UI

In this article, Dr. Tobias Komischke explains how colors used in a GUI can influence our interaction with a computer and offers advice on using the appropriate colors for the interface.