免責事項：この問題に対する最も効果的な解決策を作成しようとはしていません。 次のように、プロセッサキャッシュを操作する機能に基づいてデータ構造を構築する方法を説明したいと思います。 多くの場合、最適化の問題を解決するとき、原則としてプロセッサアーキテクチャについては考えません。 また、Cache-Conscious Binary Searchの理想的な実装を作成するつもりはありません。このアプローチがかなり単純な例に及ぼす影響を確認したいと思います（また、コードを簡素化するため、頂点の数はN = 2 ^ K-1に等しくなります）。 C＃をプログラミング言語として使用します（全体的なパフォーマンスは重要ではありません。主な重点は世界最速のプログラムを作成することではなく、問題を解決するためのさまざまなアプローチの相対的な比較です）。 また、アルゴリズムは大きな配列でのみ有効であるため、すべてのタスクでこのアプローチを使用する必要はありません。最初に実用的であることを確認する必要があります。 読者は、プロセッサキャッシュとは何か、どのように機能するかについての基本的な理解を持っていることを前提としています。
バイナリ検索の古典的な実装を考えてみましょう：ソートされた配列
a
といくつかの要素
x
、それらを探します：
public bool Contains(int x) { int l = 0, r = N - 1; while (l <= r) { int m = (l + r) / 2; if (a[m] == x) return true; if (a[m] > x) r = m - 1; else l = m + 1; } return false; }
この実装では、アルゴリズムの最初の反復で、互いに離れている配列要素に要求が行われます。 15要素の配列の検索ツリーを描画しましょう。
図から、このようなツリーを通過すると、最初に7番目の要素にアピールし、次に（
a[7]!=x
）3番目または11番目にアピールすることがわかります。 このような小さなアレイでは、これは重要ではありませんが、大きなアレイでは、これらのアクセスはプロセッサキャッシュの異なる行に対応し、パフォーマンスに悪影響を及ぼします。 配列への連続したアクセスがメモリの近い部分に収まるように、要素を並べ替えてみましょう。 最初の近似では、幅の単純な検索を使用して、ツリーの各レベルを次々に並べることができます。 テストツリーでは、次の結果が得られます。
これで、最初の反復で対処する配列の要素は、互いに遠くありません。 しかし、反復回数が増えても、多くのキャッシュミスが発生します。 この状況を修正するために、「大きな」バイナリ検索ツリーを小さなサブツリーに分割します。 このような各サブツリーは、元のツリーのいくつかのレベルに対応し、サブツリー要素は互いに近くに配置されます。 したがって、キャッシュミスは主に次のサブツリーへの移行中に形成されます。 サブツリーの高さは、プロセッサアーキテクチャに応じて選択して変更できます。 この例を使用して、サブツリーの高さを2にした構造データを示します。
それでは、実際の研究に移りましょう。 実験の純度と正確な結果を得るために、 BenchmarkDotNetプロジェクトを使用して時間を測定します。 追加の最適化なしで、考慮されたアルゴリズムの最も単純な実装を考えてみましょう（ソースコードは GitHub で提供されています）。 異なるサブツリーの高さで、従来の実装とキャッシュを意識した実装を比較します（CacheConsciousSearchKは高さKのサブツリーに対応します）。 ツリーの高さを24にします。私のマシン（Intel Core i7-3632QM CPU 2.20GHz）では、次の結果が得られました（アルゴリズムはプロセッサアーキテクチャに非常に敏感であるため、まったく異なる時間の見積もりを得ることができます）。
// Microsoft.NET 4.5 x64 SimpleSearch : 6725ms CacheConsciousSearch1 : 4428ms CacheConsciousSearch2 : 3963ms CacheConsciousSearch3 : 3778ms CacheConsciousSearch4 : 3774ms CacheConsciousSearch5 : 3762ms
ベンチマークソースコード
念のため、ベンチマークを.NET Frameworkのさまざまなバージョンで、異なるビットサイズで起動しました。 すべての構成で同様の結果が得られました。
public class CacheConsciousBinarySearchCompetition : BenchmarkCompetition { private const int K = 24, N = (1 << K) - 1, IterationCount = 10000000; private readonly Random random = new Random(); private Tree originalTree; private int[] bfs; protected override void Prepare() { originalTree = new Tree(Enumerable.Range(0, N).Select(x => 2 * x).ToArray()); bfs = originalTree.Bfs(); } [BenchmarkMethod] public void SimpleSearch() { SingleRun(originalTree); } [BenchmarkMethod] public void CacheConsciousSearch1() { SingleRun(new CacheConsciousTree(bfs, 1)); } [BenchmarkMethod] public void CacheConsciousSearch2() { SingleRun(new CacheConsciousTree(bfs, 2)); } [BenchmarkMethod] public void CacheConsciousSearch3() { SingleRun(new CacheConsciousTree(bfs, 3)); } [BenchmarkMethod] public void CacheConsciousSearch4() { SingleRun(new CacheConsciousTree(bfs, 4)); } [BenchmarkMethod] public void CacheConsciousSearch5() { SingleRun(new CacheConsciousTree(bfs, 5)); } private int SingleRun(ITree tree) { int searchedCount = 0; for (int iteration = 0; iteration < IterationCount; iteration++) { int x = random.Next(N * 2); if (tree.Contains(x)) searchedCount++; } return searchedCount; } interface ITree { bool Contains(int x); } class Tree : ITree { private readonly int[] a; public Tree(int[] a) { this.a = a; } public bool Contains(int x) { int l = 0, r = N - 1; while (l <= r) { int m = (l + r) / 2; if (a[m] == x) return true; if (a[m] > x) r = m - 1; else l = m + 1; } return false; } public int[] Bfs() { int[] bfs = new int[N], l = new int[N], r = new int[N]; int tail = 0, head = 0; l[head] = 0; r[head++] = N - 1; while (tail < head) { int m = (l[tail] + r[tail]) / 2; bfs[tail] = a[m]; if (l[tail] < m) { l[head] = l[tail]; r[head++] = m - 1; } if (m < r[tail]) { l[head] = m + 1; r[head++] = r[tail]; } tail++; } return bfs; } } class CacheConsciousTree : ITree { private readonly int[] a; private readonly int level; public CacheConsciousTree(int[] bfs, int level) { this.level = level; int size = (1 << level) - 1, counter = 0; a = new int[N]; var was = new bool[N]; var queue = new int[size]; for (int i = 0; i < N; i++) if (!was[i]) { int head = 0; queue[head++] = i; for (int tail = 0; tail < head; tail++) { a[counter++] = bfs[queue[tail]]; was[queue[tail]] = true; if (queue[tail] * 2 + 1 < N && head < size) queue[head++] = queue[tail] * 2 + 1; if (queue[tail] * 2 + 2 < N && head < size) queue[head++] = queue[tail] * 2 + 2; } } } public bool Contains(int x) { int u = 0, deep = 0, leafCount = 1 << (level - 1); int root = 0, rootOffset = 0; while (deep < K) { int value = a[root + u]; if (value == x) return true; if (++deep % level != 0) { if (value > x) u = 2 * u + 1; else u = 2 * u + 2; } else { int subTreeSize = (1 << Math.Min(level, K - deep)) - 1; if (value > x) rootOffset = rootOffset * leafCount * 2 + (u - leafCount + 1) * 2; else rootOffset = rootOffset * leafCount * 2 + (u - leafCount + 1) * 2 + 1; root = (1 << deep) - 1 + rootOffset * subTreeSize; u = 0; } } return false; } } }
Mono 3.3.0では、結果も同様であることが判明しました。
これらの写真から、従来のバイナリ検索の実装はCache-Consciousの実装よりも大幅に劣っていることがわかります。 最初は、サブツリーの高さの増加に伴い、速度は向上しますが、この傾向は長くは続きません（サブツリー内に多数のキャッシュミスがある場合、サブツリーはほとんど役に立ちません）。
もちろん、Cache-Conscious Binary Searchは、プログラムをプロセッサキャッシュの機能に適合させる方法の一例にすぎません。 そのようなキャッシュを意識したデータ構造は、データ構造が十分に大きく、連続したリクエストがメモリの異なる部分にある場合、アプリケーションの最適化に非常に役立ちます。 しかし、Cache-Consciousの下ですべてを書き直そうとしないでください。コードがより複雑になり、効率の向上は使用するプロセッサアーキテクチャに大きく依存することに注意してください。 実際には、まず、優れた漸近性、さまざまな推定値、ヒューリスティックなどを備えた最適なアルゴリズムを選択することを考え、すべてが本当に悪くなる時間にCache-Consciousを保存することをお勧めします。
あなたのためのクイックアプリ！
次のトピックも読むことができます。
更新する MikeMirzayanovによる更新：このようなトリックがあります。 長さnの配列でbinpo検索で検索する必要がある場合は、sqrt（n）要素によってsqrt（n）ブロックに分割できます。 次に、ログのビン検索（sqrt（n））を使用して、必要なブロックを検索し、その中でログの2番目のビン検索（sqrt（n））で要素を見つけます。 合計で、同じログ（n）が取得されますが、キャッシュにはさらに多くのヒットがあります。 長さsqrt（n）のかなり短い配列を見るたびに。