CTOの河合(@neuecc)です。今回はパフォーマンス比較もそうなのですが、どちらかというと、それを具体的な例にして、マイクロベンチマークの測り方の説明をしたいと思っています。その具体的な例、題材なのですが、特に動的コード生成においては、Typeをキーにして生成したデリゲートをキャッシュすることがよくあります。その場合に最速なのはジェネリッククラスを一つ作って、そこに貯めることで
public static class Cache<T> { public static Func<T> cache; }
最速に取り出すことが出来ます。これはEqualityComparer<T>.Defaultなどでも使われている、覚えておきたいC#テクニックの一つです。とはいえ、常に必ずしもTを元にして取り出せるわけではなく、Typeをキーにした辞書を作って、そこから取り出すケースも多いでしょう。
具体的にはMessagePack for C#では Deserialize<T>(byte[]) の他に Deserialize(Type, byte[]) のAPIもあります。フレームワークに統合する場合、フレームワーク側がTypeをパラメータとして渡してくることが多いため、それに応えるために非ジェネリックのAPIが必要になってきます。
Hashtableの秘密
Typeをキーにして何らかの値を詰めていく場合、グローバルにあらゆるところからリクエストされる可能性があるため、スレッドセーフでなければならず、ConcurrentDictionaryがよく使われます。
static ConcurrentDctionary<Type, Action> delegateCache;
これはlock不要のため、lock + Dictionaryよりも高速に動作します。しかし、.NET標準でこのケースにおいて最速の手法はConcurrentDictionaryではありません。実は非ジェネリックのHashtableが最速です。
MSDNのドキュメントを見てみましょう(msdn/Hashtable Class)、そこにはこう記されています。
Hashtable is thread safe for use by multiple reader threads and a single writing thread. It is thread safe for multi-thread use when only one of the threads perform write (update) operations, which allows for lock-free reads provided that the writers are serialized to the Hashtable.
書き込み時のみlockを使っていれば、読み込み側はスレッドセーフという特性を持っています。これはコード生成用に最初の一回だけデリゲートを生成して、Typeをキーにしてキャッシュしておく。のようなシナリオにぴったりです。削除もないし、書き込みは初回の一回だけで、あとはずっと読み込みしかないので。
BenchmarkDotNet
では、実際にどの程度の違いがあるのか、見ていきましょう。マイクロベンチマークにはBenchmarkDotNetを使いましょう。現状.NET標準のベンチマークフレームワークといってもよく、オレオレベンチマークでやるよりも楽、というよりかは、数字の信頼性がずっと高くなります。マイクロベンチマークを正しくやるのはかなり難しいため(Stopwatchで囲めばOKというものではない！ウォームアップ、GC、JITの影響、メモリ計測、etc…）、ある程度の部分をきちんと吸収してくれる重要な土台になっています。プロジェクトを主導しているのはAndrey Akinshin氏で、現在はJetBrainsでRiderの開発をしているようです。
さて、BenchmarkDotNetは非常に正しく、多機能ではあるのだけれど、いきなり入れただけだとどう使っていいのかさっぱりわからなくて、毎回コピペ元を探してくる羽目になります。ので、ここに基本的なコンフィグを置いておきましょう（新たなるコピペ元として）。
class Program { static void Main(string[] args) { // Switcherは複数ベンチマークを作りたい場合ベンリ。 var switcher = new BenchmarkSwitcher(new[] { typeof(DictionaryBenchmark) }); // 今回は一個だけなのでSwitcherは不要ですが。 args = new string[] { "0" }; switcher.Run(args); // 走らせる } } public class BenchmarkConfig : ManualConfig { public BenchmarkConfig() { Add(MarkdownExporter.GitHub); // ベンチマーク結果を書く時に出力させとくとベンリ Add(MemoryDiagnoser.Default); // ShortRunを使うとサクッと終わらせられる、デフォルトだと本気で長いので短めにしとく。 // ShortRunは LaunchCount=1 TargetCount=3 WarmupCount = 3 のショートカット Add(Job.ShortRun); } } // ベンチマーク本体 [Config(typeof(BenchmarkConfig))] public class DictionaryBenchmark { ConcurrentDictionary<Type, Action> concurrentDict; Dictionary<Type, Action> dict; Hashtable hashtable; Type key; [GlobalSetup] public void Setup() { concurrentDict = new ConcurrentDictionary<Type, Action>(); dict = new Dictionary<Type, Action>(); hashtable = new System.Collections.Hashtable(); // 3000件ぐらいを突っ込んで foreach (var item in typeof(int).Assembly.GetTypes()) { concurrentDict.TryAdd(item, () => { }); dict[item] = () => { }; hashtable[item] = new Action(() => { }); } // intのlookup速度を競う key = typeof(int); } // 戻り値を返すようにしているのは最適化で消滅しないようにするため [Benchmark] public Action Dictionary() { // 今回はマルチスレッド環境下をイメージするのでlockいれます lock (dict) { Action _; dict.TryGetValue(key, out _); return _; } } [Benchmark] public Action Hashtable() { var _ = hashtable[key]; return (Action)_; } // ConcurrentDictionaryを基準にしましょう。 [Benchmark(Baseline = true)] public Action ConcurrentDictionary() { Action _; concurrentDict.TryGetValue(key, out _); return _; } }
結果はこうです。
| Method | Mean | Error | StdDev | Scaled | ScaledSD | Allocated |
|---|---|---|---|---|---|---|
| Dictionary | 40.79 ns | 5.815 ns | 0.3286 ns | 1.31 | 0.02 | 0 B |
| Hashtable | 14.97 ns | 1.290 ns | 0.0729 ns | 0.48 | 0.01 | 0 B |
| ConcurrentDictionary | 31.18 ns | 9.007 ns | 0.5089 ns | 1.00 | 0.00 | 0 B |
実際HashtableのほうがConcurrentDictionaryよりも、このようなシナリオでは高速なのです。このことは広く知らてい、るわけではないですが、知っている人は知っています。例えばDapper/SqlMapper.cs#L2989やJil/DeserializeIndirect.cs#L17で、Hashtableが採用されています（そのため.NET CoreではSystem.Collections.NonGenericの参照を要求します）。DapperもJilも、作者はともにStackExchange勤務なので、その縁で知られているテクニックという感じもしますが。私もDapperのコードを見ていたときに気づいて、そこから知りました。
ところでBenchmarkDotNetの見方がそもそもわからない、というのも実際ある。それぞれのカラムの意味は
Mean : Arithmetic mean of all measurements Error : Half of 99.9% confidence interval StdDev : Standard deviation of all measurements Scaled : Mean(CurrentBenchmark) / Mean(BaselineBenchmark) ScaledSD : Standard deviation of ratio of distibution of [CurrentBenchmark] and [BaselineBenchmark] Gen 0 : GC Generation 0 collects per 1k Operations Allocated : Allocated memory per single operation (managed only, inclusive, 1KB = 1024B) 1 ns : 1 Nanosecond (0.000000001 sec)
になっています。Meanは算術平均、Errorは信頼区間に関わる数値で、まぁ大雑把にはMeanの小ささがパフォーマンスです。
なお、このベンチマークはシングルスレッドなので、マルチスレッドで動かした場合はlockの影響が大きくなり、lock + Dictionaryのパフォーマンス低下はもう少し大きくなります。残念ながらBenchmarkDotNetはそのままでParallel実行はサポートしていませんが、Parallel.Forで囲うという雑対応で、見てみましょう。算出される数字にはParallel.Forのオーバーヘッド/回数の違いが含まれるため、シングルスレッド時とでは数字の比較はできませんが、同条件での相対的な比較は可能です。
[Config(typeof(BenchmarkConfig))] public class ParallelBenchmark { ConcurrentDictionary<Type, Action> concurrentDict; Dictionary<Type, Action> dict; Hashtable hashtable; Type key; // この辺は一緒です。 [GlobalSetup] public void Setup() { concurrentDict = new ConcurrentDictionary<Type, Action>(); dict = new Dictionary<Type, Action>(); hashtable = new System.Collections.Hashtable(); foreach (var item in typeof(int).Assembly.GetTypes()) { concurrentDict.TryAdd(item, () => { }); dict[item] = () => { }; hashtable[item] = new Action(() => { }); } key = typeof(int); } // 雑ぃですが。 [Benchmark] public void ParallelDictionary() { Parallel.For(0, 100, x => { lock (dict) { dict.TryGetValue(key, out _); } }); } [Benchmark] public void ParallelHashtable() { Parallel.For(0, 100, x => { var _ = (Action)hashtable[key]; }); } [Benchmark(Baseline = true)] public void ParallelConcurrentDictionary() { Parallel.For(0, 100, x => { concurrentDict.TryGetValue(key, out _); }); } } // Mainのところは2つならべておくとベンリ static void Main(string[] args) { var switcher = new BenchmarkSwitcher(new[] { typeof(DictionaryBenchmark), typeof(ParallelBenchmark) }); // ↑これで実行時に選択可能 switcher.Run(args); }
結果はこうなりました。
| Method | Mean | Error | StdDev | Scaled | ScaledSD | Gen 0 | Allocated |
|---|---|---|---|---|---|---|---|
| ParallelDictionary | 69.603 us | 283.4327 us | 16.0145 us | 6.54 | 1.23 | 0.2035 | 1027 B |
| ParallelHashtable | 9.343 us | 0.5297 us | 0.0299 us | 0.88 | 0.00 | 0.2136 | 921 B |
| ParallelConcurrentDictionary | 10.637 us | 0.4833 us | 0.0273 us | 1.00 | 0.00 | 0.2136 | 950 B |
ブレが多いため、具体的にx倍、みたいなことをこれで断言はできませんが、少なくとも lock + Dictionaryの結果が相対的にかなり悪くなったことが確認できます。
独自の追加専用ハッシュテーブルを作る
よし、ではHashtableを使おう、で完結してしまってもいいのですが、そこから更に先を行ってみましょう。私は先日MicroResolverという最速のDIライブラリを作成したのですが、そこで自作のハッシュテーブルを作ることにより非ジェネリックでのパフォーマンスを向上させることに成功しました。
キーポイントは幾つかあるのですが、そのなかの
var buckets = table[hashCode & tableMaskIndex]; // table size is power of 2, fast lookup
ハッシュテーブル内のバケットの参照方法を除算ではなくビット演算で済ますことで、それなりの成果がありました。Hashtable, Dictionary, ConcurrentDictionary は除算による算出で、良し悪しがあるので一概にビット演算にしたほうがいい、とはいわないのですが、性能向上は見込める気がします。
ついでに、追加側は必ずlockしなければならない、というのも大変なので、lockも内包して、全体的にスレッドセーフで、読み込みはロックフリーで最速、という汎用ハッシュテーブルを作りましょう。シナリオ的にRemoveのサポートもなしで、AddとGetしか用意しません。
internal class ThreadsafeHashTable<TKey, TValue> { Entry[] buckets; int size; // only use in writer lock readonly object writerLock = new object(); readonly float loadFactor; readonly IEqualityComparer<TKey> comparer; public ThreadsafeHashTable() : this(EqualityComparer<TKey>.Default) { } public ThreadsafeHashTable(IEqualityComparer<TKey> comaprer) : this(4, 0.75f, comaprer) { } public ThreadsafeHashTable(int capacity, float loadFactor = 0.75f) : this(capacity, loadFactor, EqualityComparer<TKey>.Default) { } public ThreadsafeHashTable(int capacity, float loadFactor, IEqualityComparer<TKey> comparer) { var tableSize = CalculateCapacity(capacity, loadFactor); this.buckets = new Entry[tableSize]; this.loadFactor = loadFactor; this.comparer = comparer; } public bool TryAdd(TKey key, Func<TKey, TValue> valueFactory) { TValue _; return TryAddInternal(key, valueFactory, out _); } bool TryAddInternal(TKey key, Func<TKey, TValue> valueFactory, out TValue resultingValue) { lock (writerLock) { var nextCapacity = CalculateCapacity(size + 1, loadFactor); if (buckets.Length < nextCapacity) { // rehash var nextBucket = new Entry[nextCapacity]; for (int i = 0; i < buckets.Length; i++) { var e = buckets[i]; while (e != null) { var newEntry = new Entry { Key = e.Key, Value = e.Value, Hash = e.Hash }; AddToBuckets(nextBucket, key, newEntry, null, out resultingValue); e = e.Next; } } // add entry(if failed to add, only do resize) var successAdd = AddToBuckets(nextBucket, key, null, valueFactory, out resultingValue); // replace field(threadsafe for read) System.Threading.Volatile.Write(ref buckets, nextBucket); if (successAdd) size++; return successAdd; } else { // add entry(insert last is thread safe for read) var successAdd = AddToBuckets(buckets, key, null, valueFactory, out resultingValue); if (successAdd) size++; return successAdd; } } } bool AddToBuckets(Entry[] buckets, TKey newKey, Entry newEntryOrNull, Func<TKey, TValue> valueFactory, out TValue resultingValue) { var h = (newEntryOrNull != null) ? newEntryOrNull.Hash : comparer.GetHashCode(newKey); if (buckets[h & (buckets.Length - 1)] == null) { if (newEntryOrNull != null) { resultingValue = newEntryOrNull.Value; System.Threading.Volatile.Write(ref buckets[h & (buckets.Length - 1)], newEntryOrNull); } else { resultingValue = valueFactory(newKey); System.Threading.Volatile.Write(ref buckets[h & (buckets.Length - 1)], new Entry { Key = newKey, Value = resultingValue, Hash = h }); } } else { var searchLastEntry = buckets[h & (buckets.Length - 1)]; while (true) { if (comparer.Equals(searchLastEntry.Key, newKey)) { resultingValue = searchLastEntry.Value; return false; } if (searchLastEntry.Next == null) { if (newEntryOrNull != null) { resultingValue = newEntryOrNull.Value; System.Threading.Volatile.Write(ref searchLastEntry.Next, newEntryOrNull); } else { resultingValue = valueFactory(newKey); System.Threading.Volatile.Write(ref searchLastEntry.Next, new Entry { Key = newKey, Value = resultingValue, Hash = h }); } break; } searchLastEntry = searchLastEntry.Next; } } return true; } public bool TryGetValue(TKey key, out TValue value) { var table = buckets; var hash = comparer.GetHashCode(key); var entry = table[hash & table.Length - 1]; if (entry == null) goto NOT_FOUND; if (comparer.Equals(entry.Key, key)) { value = entry.Value; return true; } var next = entry.Next; while (next != null) { if (comparer.Equals(next.Key, key)) { value = next.Value; return true; } next = next.Next; } NOT_FOUND: value = default(TValue); return false; } public TValue GetOrAdd(TKey key, Func<TKey, TValue> valueFactory) { TValue v; if (TryGetValue(key, out v)) { return v; } TryAddInternal(key, valueFactory, out v); return v; } static int CalculateCapacity(int collectionSize, float loadFactor) { var initialCapacity = (int)(((float)collectionSize) / loadFactor); var capacity = 1; while (capacity < initialCapacity) { capacity <<= 1; } if (capacity < 8) { return 8; } return capacity; } class Entry { public TKey Key; public TValue Value; public int Hash; public Entry Next; // debug only public override string ToString() { return Key + "(" + Count() + ")"; } int Count() { var count = 1; var n = this; while (n.Next != null) { count++; n = n.Next; } return count; } } }
長い！ので要点だけ摘むと、APIは TryAdd, TryGetValue, GetOrAdd の3つのみ。追加と読み込みは出来るけど削除は不可。リード側がスレッドセーフで、ライト側はlock内でやるようになってます。この実装でOKの理由は、ハッシュテーブルの実体が Entry[] bucketsのフィールド一個だけに収めてあるからで、もし読み込み中に追加があっても、削除がないので、内部の連結リストの末尾に追加されるだけなら問題ない。追加時にキャパシティを超えてリハッシュが発生する際にも、全てを新規に生成してEntry[]だけ差し替えればいいので、読み込み中の参照には全く影響しない。
というようになってます。良さそうじゃん？というわけで、計測しましょう。
// ベンチマークに追加 [Benchmark] public Action ThreadsafeHashTable() { Action _; threadsafeHashTable.TryGetValue(key, out _); return _; }
| Method | Mean | Error | StdDev | Scaled | ScaledSD | Allocated |
|---|---|---|---|---|---|---|
| Dictionary | 42.24 ns | 2.043 ns | 0.1154 ns | 1.33 | 0.02 | 0 B |
| Hashtable | 14.94 ns | 3.522 ns | 0.1990 ns | 0.47 | 0.01 | 0 B |
| ConcurrentDictionary | 31.70 ns | 8.067 ns | 0.4558 ns | 1.00 | 0.00 | 0 B |
| ThreadsafeHashTable | 15.20 ns | 2.506 ns | 0.1416 ns | 0.48 | 0.01 | 0 B |
なるほど、ぶっちけほとんど変わらなかった……！誤差範囲でむしろ遅い！おうふ、わざわざ自作するというリスクを犯してまでやることなのだろうか、これが……。それではあんまりなので、更にブーストさせましょう。KeyはTypeで固定します。
// TKeyはTypeで固定する internal class ThreadsafeTypeKeyHashTable<TValue> { // これが // var hash = comparer.GetHashCode(key); // こうなる var hash = key.GetHashCode(); // これが // if (comparer.Equals(entry.Key, key)) // こうなる if (entry.Key == key) } // ベンチマークに追加 [Benchmark] public Action ThreadsafeTypekeyHashTable() { Action _; typekeyHashtable.TryGetValue(key, out _); return _; }
結果はこうです。
| Method | Mean | Error | StdDev | Scaled | ScaledSD | Allocated |
|---|---|---|---|---|---|---|
| Dictionary | 41.705 ns | 6.6646 ns | 0.3766 ns | 1.31 | 0.02 | 0 B |
| Hashtable | 15.018 ns | 3.0491 ns | 0.1723 ns | 0.47 | 0.01 | 0 B |
| ConcurrentDictionary | 31.962 ns | 10.0487 ns | 0.5678 ns | 1.00 | 0.00 | 0 B |
| ThreadsafeHashTable | 14.973 ns | 5.0342 ns | 0.2844 ns | 0.47 | 0.01 | 0 B |
| ThreadsafeTypekeyHashTable | 8.507 ns | 0.0741 ns | 0.0042 ns | 0.27 | 0.00 | 0 B |
圧倒的改善……！2倍弱高速化されています。差分は、 EqualityComparer<Type> 経由でのGetHashCodeとEqualsを直呼び出しに変えたことです。全体的に余計なコードがほとんどない状態なので、たったそれだけで大きな変化が見込めた、ということですね。
Performance Improvements in .NET Coreにて.NET Core 2.0では2倍速くなっている～などの例が挙げられていますが、それにならえば、素朴にConcurrentDictionaryを使うことと比べて4倍の高速化が果たせています。
最後に、そもそもCache<T>.cache が最速ってことなので、実際にどの程度最速なのか見てみましょう。
| Method | Mean | Error | StdDev | Scaled | Allocated |
|---|---|---|---|---|---|
| Dictionary | 41.9966 ns | 9.2133 ns | 0.5206 ns | 1.28 | 0 B |
| Hashtable | 14.6902 ns | 5.3250 ns | 0.3009 ns | 0.45 | 0 B |
| ConcurrentDictionary | 32.9257 ns | 0.6586 ns | 0.0372 ns | 1.00 | 0 B |
| CacheFieldGet | 0.2138 ns | 0.4509 ns | 0.0255 ns | 0.01 | 0 B |
| ThreadsafeHashTable | 14.9698 ns | 4.2571 ns | 0.2405 ns | 0.45 | 0 B |
| ThreadsafeTypekeyHashTable | 8.3876 ns | 0.9811 ns | 0.0554 ns | 0.25 | 0 B |
さすがに圧倒的。
まとめ
DictionaryのルックアップはO(1)でタダだと思いがちですが、そんなことはなく違いが出るものだ、というのは気に留めておくと良さそうです。特にStringがキーの場合（最も使い道としてよくあるケース！）なんて、StringのGetHashCodeとEqualsは、全文字列を舐めて算出するわけで、別に全然タダではありません。ならばどうすれば良いか、というと、使うしかないわけですが、ちょっと中身について思いを馳せて見ると、コードに対して違った印象で見つめることができるのではないでしょうか。
今回やってるのはかなりミクロな差を追求してるので、そこは留意してください。EqualityComparer<T>経由で呼ばなくする程度で2倍の差がつくってことは、つまりそれぐらいに僅差の違いでしかないので、ConcurrentDictionaryでも別に全然遅くありませんし、わざわざそのために非ジェネリックのHashtable使って気を使ったコードを書く必要もあまりありません。
とはいえ、僅かな差なのだし意味がない、そんなところをみるのはC#的ではない（パフォーマンスを追求するならそもそもC#でなくていい）、という意見には反対です。こうした一つ一つの積み重ねは間違いなく意味を持ちますし、他の言語と戦う際の土台でもあると思っています。
