BT

.NETコレクションの展開について

| 作者: Jonathan Allen フォローする 525 人のフォロワー , 翻訳者 編集部 フォローする 0 人のフォロワー 投稿日 2008年6月11日. 推定読書時間: 12 分 |

.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コマンドでおこなったものについては、間違いなく出来があまり良くない。どれが最良かを決めるのは、自分次第である。

原文はこちらです:http://www.infoq.com/news/2008/06/Hashtable

この記事に星をつける

おすすめ度
スタイル

こんにちは

コメントするには InfoQアカウントの登録 または が必要です。InfoQ に登録するとさまざまなことができます。

アカウント登録をしてInfoQをお楽しみください。

あなたの意見をお聞かせください。

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする
コミュニティコメント

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

ディスカッション

InfoQにログインし新機能を利用する


パスワードを忘れた方はこちらへ

Follow

お気に入りのトピックや著者をフォローする

業界やサイト内で一番重要な見出しを閲覧する

Like

より多いシグナル、より少ないノイズ

お気に入りのトピックと著者を選択して自分のフィードを作る

Notifications

最新情報をすぐ手に入れるようにしよう

通知設定をして、お気に入りコンテンツを見逃さないようにしよう!

BT