国または地域と言語

    国または地域と、言語を選んでください。

    おすすめ

      すべての国と地域

        キャラクターを選ぶ

        上部のバーとプロフィールに表示されます。いつでも変更できます。

        低レイテンシーのC++

        メモリレイアウト、キャッシュの挙動、ロックフリーキュー、レイテンシーの測定方法を説明します。

        • 6 件のシナリオ
        • 30 分ずつ
        • 話すか入力して 回答します
        • レポートの基準: 選んだレベル

        質問は合成音声が行います。

        面接のレベル

        練習シナリオ

        シナリオを選んでください。各面接は、選んだレベルのレポートで終わります。

        30 min4 段階ミドル レベル

        マーケットデータのメッセージの配置

        フィードハンドラーは、注文の各更新を、1バイトのside、8バイトのdoubleの価格、4バイトの数量、1バイトのフラグ、8バイトの注文idをこの順に宣言した構造体に保存しています。エンジンは、64バイトのキャッシュラインを持つ64ビットのマシンで、これを1秒に数百万件走査します。

        面接を始める
        ルーブリックと準備求められる内容: mid レベルの回答 · 準備に3レッスン

        ミドル の基準

        • 最後にだけパディングが残るように、フィールドを大きいものから順に、8バイトの2つのフィールド、次に数量、次に1バイトの2つのフィールドの順に並べます。構造体は24バイトになるので、64バイトのラインに、ちょうど2つではなく2つより多くの更新が収まります。
        • 価格は専用の連続した配列、つまり配列の構造体に保持します。そうすればループは、ほとんど使わない更新全体を読み込むのではなく、64バイトのキャッシュラインごとに8個の価格を読めるからです。価格は固定小数点の整数として保存し、比較での浮動小数点の丸めも避けます。
        • レイアウトが変わってしまわないよう、sizeofとoffsetofに対するstatic_assertのチェックを追加し、その後、現実的なデータでのベンチマークで前後の走査を測定します。キャッシュミスが同じなのに実行が速くなったなら、ほかの何かが変わったことになるので、ハードウェアカウンターからキャッシュミスも読み取ります。
        30 min4 段階ミドル レベル

        1つのキャッシュラインにある2つのカウンター

        2つのスレッドがそれぞれ自分のカウンターを更新します。一方は受信したメッセージを数え、もう一方は送信した注文を数えます。カウンターは、1つの構造体の中で隣り合った2つの64ビットのアトミックな整数です。2つのスレッドは同じカウンターに触れることがないのに、2つ目のスレッドを追加すると両方のスレッドが遅くなりました。

        面接を始める
        ルーブリックと準備求められる内容: mid レベルの回答 · 準備に3レッスン

        ミドル の基準

        • alignas(64)かパディングで各カウンターを別々のキャッシュラインに置きます。そうすれば各コアが相手を無効化せずに自分のラインを保てるからです。C++17には、その配置のための移植性のあるヒントとしてstd::hardware_destructive_interference_sizeもあります。
        • はい。各カウンターの書き込み手は1つだけなので、所有するスレッドは通常のローカルの件数を持ち、数千件のメッセージごとにrelaxedのアトミックなストアで公開できます。その場合、読み取る側はわずかに古い値を見ることになりますが、統計用のカウンターなら問題ありません。
        • スレッド1つ、共有ラインでのスレッド2つ、パディングで修正した後のスレッド2つでスループットを測定します。最後の2つの実行の差で原因を切り分けられるからです。Linuxでは、perf c2cがコア間を行き来するキャッシュラインを報告するので、構造体を直接特定できます。
        30 min4 段階ミドル レベル

        ロックフリーの単一プロデューサー・単一コンシューマーキュー

        フィードのスレッドは、解析した更新をキューを通じて戦略のスレッドに渡します。pushするスレッドとpopするスレッドはそれぞれちょうど1つで、容量は1,024スロットに固定されており、ホットパスでは決してロックを取ったりメモリを割り当てたりしてはいけません。

        面接を始める
        ルーブリックと準備求められる内容: mid レベルの回答 · 準備に3レッスン

        ミドル の基準

        • プロデューサーはまずスロットに書き込み、その後新しいtailをreleaseでストアし、コンシューマーはスロットを読む前にtailをacquireでロードします。この組み合わせで、プロデューサーが書いたデータをコンシューマーが見ることが保証されるからです。コンシューマーはheadをreleaseで公開するので、プロデューサーがまだ読まれているスロットを上書きすることはありません。
        • スロットの確保をアトミックにする仕組みがないので、プロデューサーが2つあると、両方が同じtailを読んで同じスロットに書き込む可能性があります。複数のプロデューサーにはtailに対するcompare exchangeかスロットごとのシーケンス番号が必要で、コストが高くなるので、キューは単一プロデューサーのままにし、その型でそれを明示します。
        • 失われたり順序が入れ替わったりした項目は欠けとして現れるので、プロデューサーが連番を送り、コンシューマーがすべての番号を1回ずつ順に受け取ることを確認するストレステストを実行します。ThreadSanitizerのもとでも実行し、可能であれば、より弱いメモリモデルのハードウェアでも実行します。
        30 min4 段階ミドル レベル

        tick-to-tradeのレイテンシの測定

        戦略はマーケットデータの更新を読み取り、判断し、注文を送信します。チームは平均のtick-to-tradeのレイテンシーを4マイクロ秒と報告していますが、トレーダーは一部の注文の到着が遅すぎると言っています。1日分の取引から、タイムスタンプ付きのサンプルが1百万件あります。

        面接を始める
        ルーブリックと準備求められる内容: mid レベルの回答 · 準備に3レッスン

        ミドル の基準

        • 実時間の時計は飛ぶことがあるので、steady_clockやCPUのタイムスタンプカウンターなどの単調な時計を使って、更新が届いた時刻と注文がネットワークに渡された時刻にタイムスタンプを付けます。生のカウントを保存し、セッションの後に換算します。そうすればホットパスでの計時のコードを安く保てます。
        • テールのレイテンシーはたいていジッター、つまりヒープの割り当て、ページフォールト、コンテキストスイッチ、静かな時間帯に冷えたキャッシュなどから生じるので、遅いサンプルをイベントと突き合わせます。遅い注文がアイドルの間隔の後に集中しているか、バーストの間に集中しているかを確認します。それぞれ別の原因を示すからです。
        • それぞれがジッターの既知の原因を取り除くので、スレッドを分離したコアに固定し、メモリを事前に確保してページアウトしないようにロックし、静かな時間帯にも経路を温かく保ちます。そのうえで、1つの平均ではなく、同じ再生データでの前後のパーセンタイルの分布全体を比較します。
        30 min4 段階ミドル レベル

        メッセージハンドラーから割り当てを取り除く

        メッセージのハンドラーは、各注文の更新をstd::stringのシンボルに解析し、フィールドのstd::vectorを作り、シンボルをキーとするstd::mapで銘柄を検索します。プロファイリングによると、ハンドラーは時間の大部分をメモリアロケーターで費やしています。

        面接を始める
        ルーブリックと準備求められる内容: mid レベルの回答 · 準備に4レッスン

        ミドル の基準

        • ビューはハンドラーがすでに所有しているメモリを指すので、何もコピーも割り当てもされません。そのため、フィールドを受信バッファーのstd::string_viewのスライスとして解析します。固定長のフィールドは、拡張するstd::vectorではなく、事前に確保した構造体に直接入れられます。
        • 配列の読み取りはツリーの探索ではなく1回のメモリアクセスで済むので、起動時に一度、各シンボルを小さな整数のidに対応付け、ホットパスではそのidで配列を参照します。フィードがシンボルしか送らない場合は、起動時にサイズを決めたオープンアドレス法のハッシュテーブルを使います。これはメモリ割り当てを一切しません。
        • 再利用すれば汎用のアロケーターをホットパスから外せるので、注文のオブジェクトは起動時に事前に確保したプールから取り出し、取消や約定のときに返します。プールが枯渇したときにどうするか、たとえば新しい注文を拒否してアラートを出すことを事前に決め、メッセージごとのメモリ割り当ての回数を測定して、ゼロになることを証明します。
        30 min4 段階ミドル レベル

        追加、取消、約定に対応する注文板

        取引所のフィードから届く、それぞれ注文idの付いた追加、取消、約定をもとに、1つの銘柄の板を構築してください。価格は0.01ティック単位で動き、ほぼすべての動きは直近の約定から500ティック以内にあります。戦略は、メッセージのたびに最良の買い気配と売り気配を読み取ります。

        面接を始める
        ルーブリックと準備求められる内容: mid レベルの回答 · 準備に3レッスン

        ミドル の基準

        • 注文idから注文ノードへのハッシュマップを持ち、各レベルは注文を侵入型の双方向連結リストで保持します。そうすれば取消のときにidでノードを見つけ、レベルを探索せずにリンクを外せるからです。ノードは自分の価格を保存しているので、どのレベルの合計を減らせばよいかも分かります。
        • 最良の買い気配のインデックスを追跡し、そのレベルが空になったら注文のある次のレベルまで下に走査します。動きが板の上のほうに集中していれば、その走査は短く済むからです。それで十分に短くない場合は、空でないレベルのビットマップを使えば、走査を数回のワード演算に減らせます。
        • 未知のidは通常メッセージを取りこぼしたことを意味するので、クラッシュさせたり推測したりはしません:板を疑わしい状態として印を付け、フィードのシーケンス番号に欠けがないかを確認し、復旧のためにスナップショットを要求します。板が再構築されるまで、戦略にはその板で取引しないよう伝えます。

        面接ハブの利用

        面接ハブはAll Accessに含まれています。続けるには、プランを選ぶかアカウントにサインインしてください。

        プランを見るサインインまたは登録

        Your Work Gym account

        Save your progress and pick up on another device. Your browser's progress comes with you.

        or

        You can keep practicing without an account.

        ヘルプとフィードバック

        質問、うまく動かない点、アイデアなどをお寄せください。メールで返信します。

        どのような内容ですか?

        返信のためだけに使用します。