パフォーマンス最適化技術: アルゴリズム

アルゴリズムとその実装にはさまざまな種類がありますが、この記事ではシングルコア、シングルスレッドのアルゴリズムではなく、マルチコア、マルチスレッドのアルゴリズムについて説明します。すべてのアルゴリズムの種類について説明するわけではありませんが (これは著者の能力を超えています)、マルチコアネットワークデバイスで一般的なアルゴリズムと、可能な最適化アプローチについて説明します。これらのアプローチの一部は検証されていますが、他のアプローチはまだアイデア段階にあり、データによってサポートされていません。

マルチコアアルゴリズムの最適化には、ロックフリーとロックレスの 2 つの目標があります。

ロックフリーは完全にロックフリーな設計であり、次の 2 つの方法で実装できます。

CPU ごとのデータは、その名前が示すように、各コアまたはスレッドに独自のプライベートデータ構造があります (ここでのプライベートは、スレッドローカルデータとは異なります。ここでのプライベートは論理的にプライベートであるという意味であり、他のスレッドがこのデータにアクセスできないという意味ではありません。一方、スレッドローカルデータはスレッドプライベートデータ構造であり、他のスレッドはアクセスできません。もちろん、論理的にプライベートであるか物理的にプライベートであるかに関係なく、共有データをスレッドプライベートデータに変換することで、ロックや競合を回避できます)。グローバル変数は共有されますが、ローカル変数はプライベートであるため、より多くのローカル変数を使用することで、ロックフリーの目的も達成できます。
CAS は、アトミック操作である比較とスワップに基づいています (スピンロックの実装にも比較とスワップが必要ですが、スピンロックには LOCKED と UNLOCKED の 2 つの状態しかありませんが、CAS 変数には複数の状態があるという違いがあります)。次に、CAS の実装はハードウェアによって保証される必要があります (アトミック操作)。CAS は一度に 32 ビットを操作できますが、一度にメモリブロックを比較および変更できる MCAS もあります。 CAS に基づくデータ構造には統一された一貫した実装方法がないため、ロックベースのアルゴリズムほど単純で直接的ではない場合があります。データ構造ごとに異なる CAS 実装方法があり、読者は自分で検索できます。

ロックレスの目的は、ロックを減らすことではなく、ロックの競合を減らすことです。これはロックの粒度に関係します。ロックの粒度が小さいほど、待機時間は短くなり、同時実行時間は長くなります。

ロックの競合では、ロックを取得した後に異なるスレッドがどのような異なるアクションを実行するかを考慮する必要があります。セッションプールの割り当てと解放を例に挙げます。複数のスレッドが同じセッションプールにアクセスし、セッションを割り当てたり解放したりするとします。セッションプールは tailq であり、割り当てはヘッドで行われ、解放はテールで行われます。

複数のスレッドが同時にセッションプールにアクセスする場合、セッションプールを保護するためにスピンロックが必要です。そうすると、割り当てと解放という 2 つの異なるアクションが互いに競合し、複数のスレッド上の割り当てまたは解放も互いに競合することになります。

ここで、割り当てに 1 つのロックを使用し、解放に 1 つのロックを使用して両端キューを生成することを検討できます。これにより、割り当てと解放の間の競合を減らすことができます。

http://www.parallellabs.com/2010/10/25/practical-concurrent-queue-algorithm/ (この記事を参照)。

2 つのプールを使用して、1 つのプールを割り当て、1 つのプールを解放することも検討できます。割り当てられたプールを使い切った後、2 つのプールのポインタを交換します (このとき、両方のプールが空の場合を検討します。これにより、割り当てと解放の競合が軽減されるだけで、この競合を完全に排除することはできません)。

ロックベースまたは CAS ベース (ロックフリー) のデータ構造のいずれであっても、ステートマシンが必要です。異なる状態で異なる処理を実行し、ロックの粒度を上げます。つまり、状態の数ではなく、状態マシンの数を増やし、状態保護の範囲を縮小します。これは実際に体験してみる必要があります。

元記事: パフォーマンス最適化の方法とテクニック: アルゴリズム

【編集者のおすすめ】