8

外部イベントに応答して共有メモリ内の多くのリンクリストを更新する「サーバー」プログラムがあります。クライアントプログラムがリストの更新にできるだけ早く気付くようにしたい（待ち時間が最も短い）。サーバーは、データが入力され、次のポインターが有効な場所に設定されると、リンクリストのノードをマークしstate_ます。FILLEDそれまでstate_はですNOT_FILLED_YET。私はメモリバリアを使用して、内部のデータが実際に準備ができている前のようにクライアントに表示state_されないようにしています（そして、動作しているように見えますが、破損したデータは表示されません）。FILLEDまた、state_コンパイラがクライアントによるループからのチェックを解除しないようにするために、揮発性です。

サーバーコードをまったく同じに保ちながら、クライアントがリンクリストをスキャンして変更を確認するための3つの異なる方法を考え出しました。問題は、なぜ3番目の方法が最速なのかということです。

方法1：すべてのリンクリスト（「チャネル」と呼ばれる）を継続的にラウンドロビンし、ノードが「FILLED」に変更されているかどうかを確認します。

void method_one()
{
    std::vector<Data*> channel_cursors;
    for(ChannelList::iterator i = channel_list.begin(); i != channel_list.end(); ++i)
    {
        Data* current_item = static_cast<Data*>(i->get(segment)->tail_.get(segment));
        channel_cursors.push_back(current_item);
    }

    while(true)
    {
        for(std::size_t i = 0; i < channel_list.size(); ++i)
        {   
            Data* current_item = channel_cursors[i];

            ACQUIRE_MEMORY_BARRIER;
            if(current_item->state_ == NOT_FILLED_YET) {
                continue;
            }

            log_latency(current_item->tv_sec_, current_item->tv_usec_);

            channel_cursors[i] = static_cast<Data*>(current_item->next_.get(segment));
        }
    }
}

方法1では、チャネル数が少ない場合に遅延が非常に小さくなりました。しかし、チャネル数が増えると（250K以上）、すべてのチャネルをループするため、非常に遅くなりました。だから私は試しました...

方法2：各リンクリストにIDを付けます。別の「更新リスト」を横に置いておきます。リンクリストの1つが更新されるたびに、そのIDを更新リストにプッシュします。ここで、単一の更新リストを監視し、そこから取得したIDを確認する必要があります。

void method_two()
{
    std::vector<Data*> channel_cursors;
    for(ChannelList::iterator i = channel_list.begin(); i != channel_list.end(); ++i)
    {
        Data* current_item = static_cast<Data*>(i->get(segment)->tail_.get(segment));
        channel_cursors.push_back(current_item);
    }

    UpdateID* update_cursor = static_cast<UpdateID*>(update_channel.tail_.get(segment));

    while(true)
    {   
            ACQUIRE_MEMORY_BARRIER;
        if(update_cursor->state_ == NOT_FILLED_YET) {
            continue;
        }

        ::uint32_t update_id = update_cursor->list_id_;

        Data* current_item = channel_cursors[update_id];

        if(current_item->state_ == NOT_FILLED_YET) {
            std::cerr << "This should never print." << std::endl; // it doesn't
            continue;
        }

        log_latency(current_item->tv_sec_, current_item->tv_usec_);

        channel_cursors[update_id] = static_cast<Data*>(current_item->next_.get(segment));
        update_cursor = static_cast<UpdateID*>(update_cursor->next_.get(segment));
    }   
}

方法2はひどい待ち時間を与えました。方法1では10us未満の遅延が発生する可能性がありますが、方法2では不可解なことに8msの遅延が発生することがよくあります。gettimeofdayを使用すると、update_cursor-> state_の変更が、サーバーのビューからクライアントのビューに伝達するのに非常に時間がかかったようです（私はマルチコアボックスを使用しているため、遅延はキャッシュによるものと思われます）。だから私はハイブリッドアプローチを試しました...

方法3：更新リストを保持します。ただし、すべてのチャネルを継続的にループし、各反復内で更新リストが更新されているかどうかを確認します。ある場合は、番号を押し込んでください。そうでない場合は、現在繰り返しているチャネルを確認してください。

void method_three()
{
    std::vector<Data*> channel_cursors;
    for(ChannelList::iterator i = channel_list.begin(); i != channel_list.end(); ++i)
    {
        Data* current_item = static_cast<Data*>(i->get(segment)->tail_.get(segment));
        channel_cursors.push_back(current_item);
    }

    UpdateID* update_cursor = static_cast<UpdateID*>(update_channel.tail_.get(segment));

    while(true)
    {
        for(std::size_t i = 0; i < channel_list.size(); ++i)
        {
            std::size_t idx = i;

            ACQUIRE_MEMORY_BARRIER;
            if(update_cursor->state_ != NOT_FILLED_YET) {
                //std::cerr << "Found via update" << std::endl;
                i--;
                idx = update_cursor->list_id_;
                update_cursor = static_cast<UpdateID*>(update_cursor->next_.get(segment));
            }

            Data* current_item = channel_cursors[idx];

            ACQUIRE_MEMORY_BARRIER;
            if(current_item->state_ == NOT_FILLED_YET) {
                continue;
            }

            found_an_update = true;

            log_latency(current_item->tv_sec_, current_item->tv_usec_);
            channel_cursors[idx] = static_cast<Data*>(current_item->next_.get(segment));
        }
    }
}

この方法の遅延は方法1と同じくらい良好でしたが、多数のチャネルにスケーリングされました。問題は、理由がわからないことです。物事にレンチを投げるだけです。「更新で見つかりました」の部分のコメントを外すと、すべてのレイテンシログメッセージの間に出力されます。つまり、更新リストでしか見つからないということです。したがって、この方法が方法2よりもどのように高速になるかわかりません。

テストデータとしてランダムな文字列を生成する完全なコンパイル可能なコード（GCCとboost-1.41が必要）は次の場所にあります：http：//pastebin.com/0kuzm3Uf

更新：更新が発生するまで、3つの方法すべてが効果的にスピンロックされます。違いは、更新が行われたことに気付くのにかかる時間です。それらはすべて継続的にプロセッサに負担をかけるため、速度の違いを説明することはできません。私は他に何も実行されていない4コアのマシンでテストしているので、サーバーとクライアントは競合するものがありません。更新が条件を通知し、クライアントに条件を待機させるバージョンのコードを作成しました。これは、どのメソッドのレイテンシーにも役立ちませんでした。

Update2：3つの方法がありますが、一度に試したのは1つだけなので、state_メンバーをめぐって競合しているのは1つのサーバーと1つのクライアントだけです。

4

4 に答える 4

1

ハーブサッターの同時実行列を読んだことがあるかどうかはわかりません。特にキャッシュの問題に入るとき、それらは非常に興味深いものです。

確かにMethod2、IDが一般的なデータよりも小さいため、メインメモリへのラウンドトリップを頻繁に行う必要がないことを意味するため、ここではより良いように見えます（これは負担になります）。

ただし、実際に発生する可能性があるのは、次のようなキャッシュの行があることです。

Line of cache = [ID1, ID2, ID3, ID4, ...]
                  ^         ^
            client          server

その後、競合が発生します。

これがハーブサッターの記事です：偽共有を排除します。基本的な考え方は、リスト内のIDを人為的に膨らませて、キャッシュの1行を完全に占有するようにすることです。

あなたがそれにいる間、シリーズの他の記事をチェックしてください。おそらくあなたはいくつかのアイデアを得るでしょう。ロックフリーの循環バッファがあり、更新リストに役立つと思います:)

于 2010-03-28T14:25:59.800 に答える
1

仮説: 方法 2 は、更新プログラムがサーバーによって書き込まれるのを何らかの形でブロックしています。

プロセッサ コア自体に加えて、あなたができることの 1 つは、コヒーレント キャッシュです。特定のコアで値を読み取る場合、そのコアの L1 キャッシュはそのキャッシュ ラインへの読み取りアクセスを取得する必要があります。つまり、他のキャッシュが持つそのラインへの書き込みアクセスを無効にする必要があります。値を書き込む場合はその逆です。したがって、これは、「書き込み」状態 (サーバー コアのキャッシュ) と「読み取り」状態 (すべてのクライアント コアのキャッシュ) の間でキャッシュ ラインを継続的にピンポンすることを意味します。

x86 キャッシュ パフォーマンスの複雑さについては、私が完全に理解しているわけではありませんが、(少なくとも理論的には) 3 つの異なるスレッドがこの 1 つのメモリ ロケーションを可能な限りハードに叩くことによって行っていることは、(少なくとも理論的には) 完全にもっともらしいようです。アクセス要求は、サーバー上でサービス拒否攻撃を作成し、場合によっては数ミリ秒間そのキャッシュ ラインへの書き込みを防止します。

サーバーが実際に値を更新リストに書き込むのにかかる時間を調べ、待ち時間に対応する遅延があるかどうかを確認することで、これを検出するための実験を行うことができる場合があります。

クライアント スレッドとサーバー スレッドが同じ L1 キャッシュからデータを取得するように、単一のコアですべてを実行することにより、方程式からキャッシュを削除する実験を試すこともできます。

于 2010-03-28T05:14:05.253 に答える
0

方法 1 と方法 3 の両方に という行があることに気付きましたがACQUIRE_MEMORY_BARRIER、これはマルチスレッド/競合状態と関係があると思いますか?

いずれにせよ、方法 2 にはスリープがありません。つまり、次のコードを意味します...

while(true)
{   
    if(update_cursor->state_ == NOT_FILLED_YET) {
        continue;
    }

プロセッサを叩くつもりです。この種のプロデューサー/コンシューマー タスクを実行する一般的な方法は、ある種のセマフォを使用して、更新リストが変更されたことをリーダーに通知することです。プロデューサー/コンシューマー マルチスレッドを検索すると、多数の例が得られるはずです。ここでの主なアイデアは、update_cursor->state が変化するのを待っている間、スレッドをスリープ状態にできるようにすることです。これにより、このスレッドがすべての CPU サイクルを盗むのを防ぎます。

于 2010-03-28T02:59:17.670 に答える
0

答えを理解するのは難しく、私が提示した情報では公平を期すのは難しいでしょうが、私が提供したソースコードを誰かが実際にコンパイルした場合、彼らは戦うチャンスがあるでしょう ;) 私は「更新リストで見つかった」が印刷されたと言いましたすべてのレイテンシログメッセージの後に、しかしこれは実際には真実ではありませんでした.端末でスクロールバックできる限りにおいてのみ真実でした. 当初、更新リストを使用せずに見つかった多数の更新がありました。

問題は、更新リストに開始点を設定してから各データ リストに開始点を設定するまでの間に、これらの操作に時間がかかるため、遅延が発生することです。リストは、これが行われている間ずっと成長していることを忘れないでください. A と B の 2 つのデータ リストがある最も単純なケースを考えてみましょう。更新リストに開始点を設定すると、リスト A に 30 個の更新があり、リスト B に 30 個の更新があるため、たまたま 60 個の要素が含まれています。交互に行った:

A
B
A
B
A // and I start looking at the list here
B

しかし、更新リストをそこに設定した後、B には多数の更新があり、A には更新がありません。次に、各データ リストに開始位置を設定します。データ リストの開始点は更新の急増の後になりますが、更新リストの開始点はその急増の前にあるため、更新を見つけることなく一連の更新をチェックします。上記の混合アプローチは、更新が見つからない場合にすべての要素を反復処理することで、更新リストの場所とデータ リストの場所の間の一時的なギャップをすばやく埋めることができるため、最適に機能します。

于 2010-04-14T21:52:21.343 に答える