C# Dictionary型のキーの型にKeyValuePairを指定した場合のパフォーマンスについて

あるアルゴリズムを実装しているときに、System.Collections.Generic.Dictionary型のキーの型としてKeyValuePair構造体を指定してAddメソッドやContainsKeyメソッドを実行していたところ、極端にパフォーマンスが悪いと感じたので色々調べてみました。

例としては、ちょうど以下のような感じ。

Dictionary<KeyValuePair<Int32, Int32>, Int32> d = 
        new Dictionary<KeyValuePair<Int32, Int32>, Int32>();

パフォーマンスの比較として、キーの型をInt32型、String型に指定した場合とKeyValuePair型に指定した場合のAddメソッドとContainsKeyメソッドの処理速度を計測しました。コードは以下の通り。

using System;
using System.Collections.Generic;
using System.Diagnostics;

class Program
{
    public static void Main()
    {
        Int32 count = 10000;

        {
            /////////////////////////////////////////////////////
            //Key type is Int32

            Dictionary<Int32, Int32> d = 
                new Dictionary<Int32, Int32>();

            //Profile Add()
            Stopwatch sw = Stopwatch.StartNew();
            for (Int32 i = 0; i < count; i++)
            {
                d.Add(i, i);
            }
            Console.WriteLine("KeyType = Int32, Add: {0}", 
                sw.Elapsed);

            
            //Profile ContainsKey()
            sw = Stopwatch.StartNew();
            for (Int32 i = 0; i < count; i++)
            {
                d.ContainsKey(i);
            }
            Console.WriteLine("KeyType = Int32, ContainsKey: {0}", 
                sw.Elapsed);
        }


        {
            /////////////////////////////////////////////////////
            //Key type is String
            
            Dictionary<String, Int32> d = 
                new Dictionary<String, Int32>();

            //Profile Add()
            Stopwatch sw = Stopwatch.StartNew();
            for (Int32 i = 0; i < count; i++)
            {
                d.Add(i.ToString(), i);
            }
            Console.WriteLine("KeyType = String, Add: {0}", 
                sw.Elapsed);


            //Profile ContainsKey()
            sw = Stopwatch.StartNew();
            for (Int32 i = 0; i < count; i++)
            {
                d.ContainsKey(i.ToString());
            }
            Console.WriteLine("KeyType = String, ContainsKey: {0}", 
                sw.Elapsed);
        }


        {
            /////////////////////////////////////////////////////
            //Key type is KeyValuePair<Int32, Int32>
            
            Dictionary<KeyValuePair<Int32, Int32>, Int32> d =
                new Dictionary<KeyValuePair<Int32, Int32>, Int32>();

            //Profile Add()
            Stopwatch sw = Stopwatch.StartNew();
            for (Int32 i = 0; i < count; i++)
            {
                d.Add(new KeyValuePair<Int32, Int32>(i, i), i);
            }
            Console.WriteLine("KeyType = KeyValuePair<Int32, Int32>, Add: {0}",
                sw.Elapsed);


            //Profile ContainsKey()
            sw = Stopwatch.StartNew();
            for (Int32 i = 0; i < count; i++)
            {
                d.ContainsKey(new KeyValuePair<Int32, Int32>(i, i));
            }
            Console.WriteLine("KeyType = KeyValuePair<Int32, Int32>, ContainsKey: {0}",
                sw.Elapsed);
            
        }

        Console.ReadKey();
    }
}

</pre>


<br>
<p>計測結果は以下の通り</p>
<pre>
KeyType = Int32, Add: 00:00:00.0015558
KeyType = Int32, ContainsKey: 00:00:00.0002344
KeyType = String, Add: 00:00:00.0034935
KeyType = String, ContainsKey: 00:00:00.0025053
KeyType = KeyValuePair<Int32, Int32>, Add: 00:00:03.4268371
KeyType = KeyValuePair<Int32, Int32>, ContainsKey: 00:00:03.3606329

実験環境

OS	Windows Vista Home Premium
CPU	Intel Core2 Quad 2.66GHz
Memory	4GB
開発環境	Visual Studio 2005

やはり、KeyValuePair型をDictionary型のキーに指定した場合は、Int32型やString型に比べ極端に遅くなってる。Int32型をキーにした場合に比べAddメソッドで数千倍、ContainsKeyメソッドで数万倍も遅い。

Dictionary型の内部的な実装はどのようになっているかは分からないが、KeyValuePair型のような複合的なデータ構造をDictionary型のキーに指定すると遅くなるということか。

これは特に大量のデータを扱うバッチ処理などのシステムを実装する際にはかなり注意しなければならない。