高頻度取引を含む低レイテンシアプリケーション向けC++パターン
(arxiv.org)- 高頻度取引（HFT）のようにレイテンシがそのまま競争力になる領域で、公開情報が不足しているC++最適化の知見を、実験と実装を中心に整理
- 成果物は Low-Latency Programming Repository、マーケットニュートラルなペアトレーディング戦略の最適化、C++ Disruptorパターンライブラリの3つに分かれる
- ベンチマークでは速度、キャッシュ活用、統計的有意性をあわせて確認し、Cache WarmingとConstexprがレイテンシ削減で大きな効果を示す
- 最適化されたペアトレーディング戦略は実行速度と収益性が改善し、Disruptor実装は従来のキュー方式より優れた性能を示す
- 今後の課題は、リポジトリの拡張、実際の取引環境でのテスト、Disruptorと取引アルゴリズムの統合後のシステム全体のベンチマーク
HFT低レイテンシ最適化の目標
- 目標は、レイテンシに敏感なコードを最適化して実行速度を高めること
- 焦点は、高頻度取引で使われるプログラミング戦略とデータ構造に置かれている
- 金融業界、特に公開市場を扱うバイサイド企業は、機密性と競争優位のため関連知識をあまり公開しない
- この空白を埋めるため、さまざまな手法を収めたカスタムの Low-Latency Programming Repository を作成し、統計的ベンチマークで検証する
3つの成果物
-
Low-Latency Programming Repository
- 理論集にとどまらず、統計的ベンチマークを含む実用ガイドとして機能する
- HFTシステムのレイテンシを下げるためのプログラミング手法、デザインパターン、ベストプラクティスをキュレーションする
-
マーケットニュートラルな統計的裁定ペアトレーディング戦略の最適化
- レイテンシ削減手法とCPUレベルの最適化を統合する
- 実行速度と収益性で改善を示す
-
C++ Disruptorパターンライブラリ
- 従来のキュー方式より性能向上を示す
- HFTシステムのOrder Management System（OMS）にこのようなデータ構造を適用できることを示す
公開知識が不足している理由
- HFTシステム最適化の知識は主に業界実務者から生まれるが、機密性と競争優位のため、最新研究や実装の詳細は公開されにくい
- レイテンシ改善、コード効率、キャッシュ最適化といった領域は、特に公開資料が限られている
- 経済・金融の観点からのHFT研究や、アルゴリズム取引の数学モデル研究は存在するが、コード最適化やレイテンシ削減の詳細技術まで扱う例はまれ
- C++関連の文献は比較的多くても、超低レイテンシHFTシステムの文脈へ直接つながるものは限られている
- オンラインのブログや投稿は平均レイテンシのデータを表面的に提供する場合が多く、キャッシュアクセスや命令実行レイテンシの詳細な動作分析は不足している
評価と性能改善
- 評価指標には速度、キャッシュ活用、統計的有意性などが含まれる
- Low-Latency Programming Repositoryの手法のうち、Cache WarmingとConstexprがレイテンシ削減で最も大きな効果を示す
- Disruptorパターンの実装は、リングバッファ、シーケンス番号、特殊な待機戦略を活用し、従来のキュー方式よりレイテンシと速度の面で優れた性能を出す
- マーケットニュートラルなペアトレーディング戦略は、CPUレベルの最適化とレイテンシ削減手法によって実行速度と収益性が改善される
公開リポジトリと今後の作業
- リポジトリ、取引戦略、Disruptorライブラリは
https://github.com/0burak/imperial hftにある - 今後の作業にはリポジトリの拡張が含まれる
- 最適化された取引アルゴリズムを実際の取引環境でテストする課題が残っている
- Disruptorパターンを取引アルゴリズムと統合し、システム全体レベルのベンチマークを行う方向も含まれる
1件のコメント
Hacker Newsの意見
この記事は、このテーマについてかなり基礎的な入門に見える
学部生を教えた経験からすると、学生でもこうした内容はたいていすでに知っている。コンピュータアーキテクチャの授業で、分岐予測、キャッシュコヒーレンシ、命令キャッシュのような性能の基本要素を学ぶからだ
古典的な性能低下要因であるフォルスシェアリング(false sharing)をまったく扱っていないのは意外で、主にシングルスレッドのレイテンシに焦点を当てているように見える。fat LTO、PGO、
[[likely]]、[[unlikely]]のような「無料」の最適化ヒントも抜けていて驚いたより深い性能問題になると、特定の入出力API、同期プリミティブ、プロセス間通信、難解なコンパイラ組み込み機能の使い方にまで踏み込む必要がある
低レイテンシプログラマに最も欠けがちで、教えるのも難しいのは、一種の偏執性だ。不要なアロケーション、コピー、性能低下要因に対する本物の恐怖と怒りが必要になる。ホットループの真ん中でオブジェクトキャッシュを外してアロケータへ向かう呼び出しを見つけようと、callgrindでベンチマークを強迫的に回すような感覚だ
個人的には、低レイテンシサーバを作っていて、ベクタ入出力操作を組み立てるより、小さなオブジェクト群を連続バッファにコピーして単一の
writeを行うほうが全体として速いと気づいた瞬間が重要だった。無料のコピーは存在せず、fat pointerも例外ではない現在得られる最良の資料もC++カンファレンスの講演がいくつかある程度で、物足りなさが多かった
見せびらかしたい誘惑は脇に置いて考えると、この文書はこの分野への優れた貢献であり、おそらく初の権威ある参考資料かもしれない。他の講義から似た情報を組み合わせられるといった曖昧な話は貢献ではないし、誰の役にも立たない
まず、生の速度を得るためにフロントエンドFPGAで負荷を単純な資産別データストリームに分ける。ただし、反復開発、人材、サプライチェーンなどの摩擦が大きすぎるので、ここで実際の実行までやろうとする誘惑は避ける。入力はFIXストリームのようなもので、出力は低レイテンシバスに沿って資産別のバイナリイベントストリームに分割され、低価格MCUで構成した拡張型クラスタの資産別セグメントへ入る
次に、資産別MCUベースの実行プラットフォームでは汎用OSの前提を取り除き、実際に入手できるハードウェア上で人間が書ける低レベルコードにより、より高速な切り替えを可能にする。第三に、利益？ この構成では、汎用OSベースの監督者が全体の状態を監視しながら、必要に応じて個々の要素を再プログラムして戦略を止めたり変えたりする必要がある
実際のレイテンシがどれほど低いかが鍵になる。ある地点からは、エンジニアリングよりもハードウェアをコアにより近づけるコストを払うほうがよいのではないかと思う。これは、その取引所やプールが提供するルール、データセンター、リンクインフラに大きく左右されるだろう
収益性のある運用の多くは、どのプールに接続しているかを公開せず、規制や利用規約を無視してフロントランニングを事業にしている可能性もありそうだ。その場合、2つの実行地点間の相対的なネットワーク地理レイテンシのほうが、1地点までの絶対レイテンシよりも強力になる
実際、コンパイラ側の人たちがよく言う常識では、PGOがなくてもほとんどの場合こうしたヒントは逆効果だということだ。現代のコンパイラはこうしたヒントよりも自前の解析パスを信頼しており、たいてい無視する
ちなみに、実際のコードでこうしたヒントを見たのは、コンパイラが容易に挿入できる場所だけだった。たとえば
malloc呼び出し後のnullチェックのような場合だ強調したいのはこの部分だ
「このテストの出力は、検定統計量(t-statistic)と対応するp値だ。スコアとも呼ばれるt-statisticは、残差に対する単位根検定の結果である。より負のt-statisticは、残差が定常的である可能性が高いことを示唆する。p値は、この検定の帰無仮説、すなわち共和分がないという仮説が真である確率の尺度を提供する。テスト結果は、およそ0.0149のp値と-3.7684のt-statisticを出した。」
この部分はLLMで書いたように見える
例も本当に変だ。5年間、1日1回の終値相関を見たうえで、65マイクロ秒のレイテンシでスプレッドを計算するコードを書いている。実際にやることとしては筋が通らない。内部ループでスプレッド統計を計算することもないだろうし、65マイクロ秒は内部ループとしては遅すぎる
要するに最適化手法を練習することが目的なのかもしれないが、最適化対象としてはかなり代表性に欠ける
C++で LMAX Disruptorパターンを使った株式取引所の実装を作った
https://github.com/sneilan/stock-exchange
LMAX Disruptorの基本実装も、いくつかのC++ファイルで作ってある
https://github.com/sneilan/lmax-disruptor-tutorial
ただ、これをRustで作り直そうと考えている。独自のWebSocketプロトコル、認証システム、SSLなどを実装したところまで進んだが、メモリ管理と依存関係はRustのほうがずっと楽だと気づいた。特に1人のソフトウェアプロジェクトならなおさらだ
メモリアクセスはコンパイラとCPUの両方で並べ替えられる可能性があるため、元のLMAX Disruptor論文で説明されているバリアを得るには、生産者と消費者の位置に
std::atomicを使う必要があるgetメソッドでは、消費者位置を進めた後、つまり生産者にスロットを解放した後で、キュー内部要素へのポインタを返している。そのため、ユーザーがアクセスしている間に上書きされる可能性があるさらに、生産者位置と消費者位置が同じキャッシュラインに入る可能性が高く、偽共有が発生する
T *item = &this->shared_mem_region->entities[this->shared_mem_region->consumer_position];this->shared_mem_region->consumer_position++;this->shared_mem_region->consumer_position %= this->slots;次のようにできる
uint64_t mask = slot_count - 1; // 2進数ですべて1item = &slots[ pos & mask ];pos ++;つまり、除算/剰余をビットANDに置き換えて、計算を少し減らせる。ただし、リングバッファのサイズは2のべき乗でなければならない
さらに、
uint64_tのような全範囲のシーケンス番号を使うこともできる。ラップアラウンドは自動的に処理される。2つのシーケンス番号を引いても、ラップを考慮して問題なく動作する。バッファが満杯か空かを区別するためにスロットを1つ空けておかなければならない、ばかげた問題もなくなるもちろん、「生きている」シーケンス番号のウィンドウがリングバッファのウィンドウサイズを絶対に超えないよう注意する必要がある
メモリ管理は
std::shared_ptrに変えることを検討してもよい。速度を落とさずに、その心配を完全になくしてくれるソケットについては、自前コードより性能がよく、面倒な例外ケースも減らしてくれるフリーでオープンソースのライブラリがある。たとえば
FD_ISSETを走査する方式はepollやkqueueより遅い依存関係の管理は、C++が他の言語より明らかに荒削りだ。管理するより見つけるほうが難しいこともある。使えるライブラリコードがあちこちにあり、中にはインターネットの忘れられた片隅に隠れているものもある。見つけ出すこと自体が一つの技術で、うまくやれば大きな見返りがある
考えているシステムでは、SPSCリングバッファに勝つのは難しそうで、必要なら昔ながらのロックでワークスティーリングも実装できるだろう
https://martinfowler.com/articles/lmax.html
https://github.com/CppCon/CppCon2017/blob/master/Presentatio...を思い出す
偽サーバーが注文データを再生し、2台目のサーバーが実行時間を計算し、テスト対象サーバーとハードウェアスイッチでパケット時間を測定するスライドは、本当に気持ちいいほどハードコアだ
金融業界で働きたいとは思わないが、ベンチマークのためだけにラック単位のハードウェアを買うことが経済的に成り立つレベルの性能クリティカルなシステムを扱うのは面白そうだ
LMAX Disruptorと多くの共通点を持つC++ロギングライブラリを作ったし、HFTコミュニティでもある程度使われているようだ
もともとの目的は、本番環境で事後デバッグのために非常に詳細なログを、性能低下なしに残せるようにすることだった。問題解決に重要な情報をログに入れると性能に影響するのではないかと渋る同僚がいたが、このライブラリでその議論は終わった
[1] https://github.com/mattiasflodin/reckless
コンパイル時ディスパッチのもう一つの利点は、コンパイラがどの関数が呼び出されるかを静的に判断できる場合、呼び出された関数のコードを呼び出し地点に直接インライン化できること
そうすれば関数呼び出しのオーバーヘッドをすべて取り除き、デッドコード削除や定数伝播のような追加の最適化も可能になる場合がある
優れた JIT は多相的インライン化をサポートする。C++ に関する私の経験は少し古いが、この問題の解決策は PGO だった。ただし広く使われてはいない。代わりに、性能が重要なコードでは動的ディスパッチ自体を避ける傾向がある
より一般的な教訓は、どんな言語でもコードのホットパスでは、コンパイラや JIT がそれを見通せるという強い確信がない限り、不要な動的分岐を避けるべきだということ
https://youtu.be/i5MAXAxp_Tw
高頻度取引が存在すべき十分な理由はあるのか？ 人々は Bitcoin がエネルギーを浪費しているとよく批判するが、これも社会的には明らかに純損失に見えるのに、不思議と見過ごされているように思う
この業界がものすごく親社会的だとは言いにくいが、スプレッドを狭めれば仲介者に渡るお金が減るのは確か
HFT はかなり集中した領域ではあるが、規模自体は小さいほう。エネルギー浪費という点では Bitcoin より数桁小さい
HFT の唯一の肯定的な効果は流動性とより狭いスプレッドだが、それは人々が HFT をどう定義するかにもよる。たとえば Robinhood と手数料無料取引は、おそらくこれなしには存在しなかったはず
彼らは以前ならブローカーや銀行に行っていた取り分を取っている。HFT は「個人投資家」を食い物にするビジネスではない
私の見方では、社会への悪影響はほとんどないか、まったくない。長期的に株式市場に投資する人なら、HFT を気にする理由はほとんどない
いずれにせよ、高頻度取引を必要とする自然な出来事はない。基礎価値が非常に速く変わることはまれで、変わるとしてもボラティリティではなく確定的な転換に近い
HFT は不一致、たとえば3つの通貨ペアが互いにずれている状況や「明白な」ミスプライシングを解消して、金融市場をほんの少しだけ正確にする
何かを取引しようとするとき、反対側には誰かがいる。たいていは、自分が望む価格で HFT 参加者と取引することになる可能性が高い。より良い価格を得られるなら、そのお金は自分が守れたお金
「見過ごされている」という言い方にも同意しにくい。HFT はここでもかなり頻繁に批判されている
プロの開発者なら全体を見る価値がある
https://github.com/CppCon/CppCon2017/tree/master/Presentatio...
そしてその親ディレクトリも
気になる点がある。この分野では、なぜロジックに C ではなく C++ を使う、あるいは使ってきたのだろうか？ この領域で C++ が C より持つ利点は何だろう？ C/アセンブリには習熟しているが HFT の慣行はまったく知らないので、わかりやすく説明してもらえるとうれしい
もちろん、この表現力が言語の途方もない複雑さを受け入れる価値があるかどうかは議論できるが、実際には人々は経験的に C++ を選んできた
この記事の構成とトーンにはLLM っぽさが強く残っている