先日大量のデータを処理集計するために Dictionaryに格納していたのですが
10万件を超えたあたりで急に速度が落ちることがありました。
Dictionaryのキーを任意作成のStructにしておりましたが 別にテストで作成したものでは1万、10万、100万はDictionaryの個数に比例して増加しておりました。
(1万件が80msecならば 10万件は800msecのような状態)
今回のデータ処理用に作成したものは10000件で100msec程度だったので 30万で3秒前後だと考えておりましたが実際には7時間でした。
遅い原因を調べるために.Netのソースを確認し結果的にはStructのHashCodeが重複しやすい物の場合は今回の様な結果になるのではないかと思いました。
DictionaryのContainKeyの内部で使用している部分
public bool TryGetValue(TKey key, out TValue value)
{
if (key == null) throw new ArgumentNullException("key");
int bucketNo, lockNoUnused;
// We must capture the m_buckets field in a local variable. It is set to a new table on each table resize.
Tables tables = m_tables;
IEqualityComparer comparer = tables.m_comparer;
GetBucketAndLockNo(comparer.GetHashCode(key), out bucketNo, out lockNoUnused, tables.m_buckets.Length, tables.m_locks.Length);
// We can get away w/out a lock here.
// The Volatile.Read ensures that the load of the fields of 'n' doesn't move before the load from buckets[i].
Node n = Volatile.Read(ref tables.m_buckets[bucketNo]);
while (n != null)
{
if (comparer.Equals(n.m_key, key))
{
value = n.m_value;
return true;
}
n = n.m_next;
}
value = default(TValue);
return false;
}
GetBucketAndLockNoはこの通り
private void GetBucketAndLockNo(
int hashcode, out int bucketNo, out int lockNo, int bucketCount, int lockCount)
{
bucketNo = (hashcode & 0x7fffffff) % bucketCount;
lockNo = bucketNo % lockCount;
Assert(bucketNo >= 0 && bucketNo = 0 && lockNo < lockCount);
}
上記Nodeの取り出しのバケットNoがhashcodeを使用しているのでカスタムのKeyを使用する場合はHashCode十分に分散するか考えて作成していかないといけないのかもしれません。
遅い原因はチェック中なのでHashCodeの件は間違っているかもしれません進展があれば再び書きたいと思います。
ちなみにコードはこちらで確認できます。