.NETフレームワークのコレクションはここ数年で大幅に進化した。Microsoftの新たに見つかった開放性を利用して、おなじみのデータ構造であるハッシュテーブルを.NETおよびMonoの2つのバージョンで示す。
理論上は、ハッシュテーブルは多少単純な構造(単なる配列の集合)であったり、限定バケット数に分割された関連リストである。そうではるが、マルチスレッドロジックに詳しくあろうとすると、アイテムの検索さえもいくぶん複雑になる可能性がある。
// 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;
}
ここに、疑似スピンロックおよびThreading.Sleepの呼び出しがある。
.NET 2.0および汎用コレクションで、Microsoftはコレクションの内部ロッキングメカニズムをダンプすることを決定した。その代わり、すべてのロッキ ングは外部的に適用される必要がある。そうすることで、Generic.Dictionaryクラスに見られるずっと単純なコードができる。
// 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;
}
HashtableおよびDictionaryのMonoバージョンは互いにかなり違っており、Microsoftの実装とも同様に違っている。
// 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 ();
}
4つの方法を基本的に同時におこなうことが、これでできた。Sleepコマンドでおこなったものについては、間違いなく出来があまり良くない。どれが最良かを決めるのは、自分次第である。