Modèles C++ pour les applications à faible latence, y compris le trading haute fréquence

• Dans des domaines comme le trading haute fréquence (HFT), où la latence est un avantage concurrentiel en soi, l’auteur synthétise des connaissances C++ d’optimisation peu documentées publiquement à partir d’expérimentations et d’implémentations concrètes
• Le travail se divise en trois livrables : le Low-Latency Programming Repository, l’optimisation d’une stratégie de pair trading neutre au marché, et une bibliothèque C++ du pattern Disruptor
• L’évaluation prend en compte à la fois la vitesse, l’utilisation du cache et la significativité statistique, avec Cache Warming et Constexpr comme principaux gains de réduction de latence
• La stratégie de pair trading optimisée améliore la vitesse d’exécution et la rentabilité, tandis que l’implémentation de Disruptor surpasse les approches traditionnelles basées sur des files
• Les travaux futurs portent sur l’extension du dépôt, les tests en environnement de trading réel, et l’intégration de Disruptor avec les algorithmes de trading suivie d’un benchmarking système complet

---

Objectif de l’optimisation faible latence pour le HFT

• L’objectif est d’optimiser du code sensible à la latence afin d’augmenter la vitesse d’exécution
• L’accent est mis sur les stratégies de programmation et les structures de données utilisées dans le trading haute fréquence
• L’industrie financière, en particulier les entreprises buy-side opérant sur les marchés publics, publie peu sur le sujet en raison des exigences de confidentialité et des avantages concurrentiels
• Pour réduire ce manque, l’auteur a créé un Low-Latency Programming Repository sur mesure rassemblant diverses techniques, validées par un benchmarking statistique

Trois livrables

• Low-Latency Programming Repository

  • Ce n’est pas seulement une compilation théorique, mais un guide pratique incluant un benchmarking statistique
  • Il rassemble des techniques de programmation, des design patterns et des bonnes pratiques pour réduire la latence dans les systèmes HFT

• Optimisation d’une stratégie de pair trading statistique neutre au marché

  • Elle intègre des techniques de réduction de latence et des optimisations au niveau CPU
  • Elle montre des améliorations en vitesse d’exécution et en rentabilité

• Bibliothèque C++ du pattern Disruptor

  • Elle montre de meilleures performances que les approches traditionnelles basées sur des files
  • Elle montre que ce type de structure de données peut être appliqué à l’Order Management System (OMS) des systèmes HFT

Pourquoi les connaissances publiques sont limitées

• Les connaissances sur l’optimisation des systèmes HFT proviennent principalement des praticiens du secteur, mais la confidentialité et l’avantage concurrentiel rendent difficiles la publication des recherches récentes et des détails d’implémentation
• Les domaines comme l’amélioration de la latence, l’efficacité du code et l’optimisation du cache sont particulièrement peu documentés publiquement
• Il existe des travaux sur le HFT sous l’angle économique et financier, ainsi que des recherches sur les modèles mathématiques du trading algorithmique, mais ils abordent rarement les techniques détaillées d’optimisation de code ou de réduction de latence
• Même si la littérature sur C++ est relativement abondante, les travaux directement reliés au contexte des systèmes HFT ultra-faible latence restent limités
• Les blogs et billets en ligne fournissent souvent de manière superficielle des données de latence moyenne, sans analyser en détail les accès cache ni les délais d’exécution des instructions

Évaluation et amélioration des performances

• Les métriques d’évaluation incluent la vitesse, l’utilisation du cache et la significativité statistique
• Parmi les techniques du Low-Latency Programming Repository, Cache Warming et Constexpr apportent les gains les plus importants en réduction de latence
• L’implémentation du pattern Disruptor, fondée sur un ring buffer, des numéros de séquence et des stratégies d’attente spécialisées, offre de meilleures performances en latence et en vitesse que les approches traditionnelles basées sur des files
• La stratégie de pair trading neutre au marché améliore la vitesse d’exécution et la rentabilité grâce à des optimisations au niveau CPU et à des techniques de réduction de latence

Dépôt public et travaux futurs

• Le dépôt, la stratégie de trading et la bibliothèque Disruptor sont disponibles sur https://github.com/0burak/imperial hft
• Les travaux futurs incluent l’extension du dépôt
• Il reste à tester l’algorithme de trading optimisé dans un environnement de trading réel
• Il est également prévu d’intégrer le pattern Disruptor à l’algorithme de trading afin d’effectuer un benchmarking à l’échelle du système complet

[GN⁺]

Avis sur Hacker News

• Cet article ressemble à une introduction assez élémentaire au sujet.
  D’après mon expérience d’enseignement à des étudiants de premier cycle, ils connaissent déjà en général ce genre de choses. Dans les cours d’architecture des ordinateurs, on apprend les bases des performances comme la prédiction de branchement, la cohérence des caches ou le cache d’instructions.
  J’ai été surpris qu’il ne traite pas du tout d’un facteur classique de dégradation des performances, le faux partage (false sharing), et il semble surtout se concentrer sur la latence en monothread. J’ai aussi été étonné de ne pas voir mentionnés les indices d’optimisation « gratuits » comme fat LTO, PGO, [[likely]] ou [[unlikely]].
  Les problèmes de performance plus profonds obligent à entrer dans le détail d’API d’entrée-sortie spécifiques, de primitives de synchronisation, de communication interprocessus et de l’usage de fonctions intrinsèques obscures du compilateur.
  Ce qui manque le plus aux programmeurs low latency, et ce qui est le plus difficile à enseigner, c’est une forme de paranoïa. Il faut une vraie peur et une vraie colère face aux allocations, copies et sources de ralentissement inutiles. C’est le réflexe de lancer compulsivement des benchmarks avec callgrind pour trouver, au beau milieu d’une hot loop, l’appel qui part vers l’allocateur à cause d’un cache d’objets raté.
  Personnellement, en construisant un serveur low latency, le moment important a été de comprendre qu’il était globalement plus rapide de copier de petits objets dans un tampon contigu puis de faire un seul write, plutôt que de composer des opérations d’E/S vectorisées. Aucune copie n’est gratuite, et les fat pointers ne font pas exception.

  • C’est possible, mais le C++ low latency est un domaine à part entière, et pourtant l’information y est presque un désert.
    Les meilleures ressources disponibles aujourd’hui se résument à quelques conférences C++, et elles m’ont laissé sur ma faim.
    Si l’on met de côté la tentation de se faire valoir, ce document est une excellente contribution au domaine et peut-être la première référence faisant autorité. Dire vaguement qu’on peut recomposer des informations similaires à partir d’autres cours n’est pas une contribution et n’aide personne.
  • Heureusement que je ne fais plus ce genre de choses aujourd’hui, mais la vraie paranoïa tient à une méfiance à la Heisenberg : impossible de se défaire du soupçon que le programme se comporte différemment quand on le mesure et quand on ne le mesure pas.
  • Je me demande s’il existe des références globalement recommandables.
  • Voilà comment je pense que j’aborderais le problème. Je serais curieux d’avoir le retour de personnes plus proches de ce domaine.
    D’abord, pour la vitesse brute, utiliser un FPGA en front-end afin de découper la charge en simples flux de données par actif. Mais comme les frictions liées aux itérations de développement, aux compétences humaines et à la chaîne d’approvisionnement sont trop fortes, j’éviterais la tentation d’y faire aussi l’exécution réelle. L’entrée serait quelque chose comme un flux FIX, et la sortie serait découpée en flux d’événements binaires par actif sur un bus low latency, vers des segments par actif d’un cluster extensible constitué de MCU peu coûteux.
    Ensuite, sur cette plateforme d’exécution par actif basée sur des MCU, supprimer les hypothèses d’un système d’exploitation généraliste permettrait des transitions plus rapides avec du code bas niveau que des humains peuvent écrire sur du matériel réellement disponible. Troisièmement, profit ? Dans une telle architecture, un superviseur basé sur un OS généraliste devrait surveiller l’état global et reprogrammer des éléments individuels si nécessaire pour arrêter ou modifier une stratégie.
    Tout dépend de la latence réellement atteinte. À partir d’un certain point, j’ai l’impression qu’il vaut mieux payer le coût de placer le matériel plus près du cœur que de continuer à faire de l’ingénierie. Cela dépendrait fortement des règles proposées par la bourse ou le pool concerné, du datacenter et de l’infrastructure de liaison.
    Il est aussi possible que beaucoup d’opérations rentables ne révèlent pas à quels pools elles se connectent et fassent du front-running leur activité, en ignorant la réglementation ou les conditions d’utilisation. Dans ce cas, la latence géographique relative du réseau entre deux points d’exécution est plus déterminante que la latence absolue jusqu’à un seul point.
  • Si l’on utilise PGO, j’ai l’impression que les attributs d’indication risquent plutôt d’être contre-productifs.
    En pratique, le bon sens souvent exprimé par les gens côté compilateurs est que, même sans PGO, ces indications sont contre-productives dans la plupart des cas. Les compilateurs modernes font davantage confiance à leurs propres passes d’analyse qu’à ce genre d’indices et les ignorent généralement.
    À titre de remarque, dans du vrai code, je n’ai vu ces indices que là où le compilateur pouvait facilement les insérer lui-même. Par exemple, le test de nullité après un appel à malloc.

• Le passage que je veux souligner est celui-ci :
  « La sortie de ce test est la statistique de test (t-statistic) et la p-value associée. La t-statistic, aussi appelée score, est le résultat d’un test de racine unitaire sur les résidus. Une t-statistic plus négative suggère que les résidus ont davantage de chances d’être stationnaires. La p-value fournit une mesure de la probabilité que l’hypothèse nulle du test, à savoir l’absence de cointégration, soit vraie. Le test a donné une p-value d’environ 0,0149 et une t-statistic de -3,7684. »
  Cette partie donne l’impression d’avoir été écrite par un LLM.
  L’exemple est aussi vraiment étrange. On regarde la corrélation des cours de clôture une fois par jour pendant cinq ans, puis on écrit du code qui calcule le spread avec une latence de 65 microsecondes. Comme cas d’usage réel, ça n’a aucun sens. On ne calculerait pas non plus des statistiques de spread dans la boucle interne, et 65 microsecondes, c’est beaucoup trop lent pour une boucle interne.
  Le but est peut-être de s’entraîner à des techniques d’optimisation, mais comme cible d’optimisation, ce n’est pas très représentatif.

• J’ai créé en C++ une implémentation d’une bourse utilisant le pattern LMAX Disruptor
  https://github.com/sneilan/stock-exchange
  J’ai aussi fait une implémentation de base du LMAX Disruptor en quelques fichiers C++
  https://github.com/sneilan/lmax-disruptor-tutorial
  Cela dit, j’envisage de refaire ça en Rust. J’en suis arrivé au point où j’avais implémenté mon propre protocole WebSocket, un système d’authentification, SSL, etc., mais j’ai réalisé que la gestion mémoire et les dépendances étaient bien plus simples en Rust. Surtout pour un projet logiciel en solo

  • Ce genre de structure de données n’est pas facile à réaliser correctement en C++. L’implémentation de la file présente plusieurs problèmes
    Les accès mémoire peuvent être réordonnés à la fois par le compilateur et par le CPU ; pour obtenir les barrières décrites dans l’article original sur le LMAX Disruptor, il faut donc utiliser std::atomic pour les positions du producteur et du consommateur
    Dans la méthode get, la position du consommateur est incrémentée, autrement dit le slot est libéré pour le producteur, puis un pointeur vers l’élément interne de la file est renvoyé. Il peut donc être écrasé pendant que l’utilisateur y accède
    Par ailleurs, les positions du producteur et du consommateur ont de fortes chances de se retrouver sur la même ligne de cache, ce qui provoque du faux partage
  • Au lieu d’un code comme celui-ci
    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;
    on peut faire ainsi
    uint64_t mask = slot_count - 1; // tous les bits à 1 en binaire
item = &slots[ pos & mask ];
pos ++;
    Autrement dit, on remplace la division/le modulo par un AND bit à bit, ce qui réduit un peu le calcul. En revanche, la taille du ring buffer doit être une puissance de 2
    On peut même aller plus loin et utiliser des numéros de séquence sur toute la plage, par exemple en uint64_t. Le wrapping est alors géré automatiquement. Soustraire deux numéros de séquence fonctionne aussi correctement en tenant compte du wrapping. On évite aussi le problème idiot consistant à devoir laisser un slot vide pour distinguer un buffer plein d’un buffer vide
    Bien sûr, il faut veiller à ce que la fenêtre des numéros de séquence « vivants » ne dépasse jamais la taille de la fenêtre du ring buffer
  • J’ai jeté un rapide coup d’œil au code de la bourse
    Pour la gestion mémoire, ça vaut la peine d’envisager de passer à std::shared_ptr. Cela élimine complètement ce souci sans ralentir le programme
    Pour les sockets, il existe des bibliothèques libres et open source plus performantes que du code maison, et qui réduisent aussi le nombre de cas particuliers pénibles. Par exemple, parcourir FD_ISSET est plus lent que epoll ou kqueue
    La gestion des dépendances en C++ est clairement plus rude que dans d’autres langages. Les trouver peut même être plus difficile que les gérer. Du bon code de bibliothèque est éparpillé un peu partout, et une partie se cache dans des recoins oubliés d’Internet. Savoir le dénicher est une compétence en soi, et elle peut être très payante quand on la maîtrise
  • LMAX Disruptor est une excellente structure de données quand les threads sont épinglés à des cœurs et que la plupart, voire la totalité, ne sont pas en contention. Sans ce pattern, on obtient des pathologies horribles sur la latence de queue. Si un thread est désordonnancé au mauvais moment, l’impact peut être énorme
    Dans le système envisagé, il me semble difficile de battre un ring buffer SPSC, et si nécessaire on pourrait aussi implémenter du vol de travail avec de bons vieux verrous
  • Fait amusant : à l’origine, LMAX a été conçu pour Java et écrit en Java
    https://martinfowler.com/articles/lmax.html

• Ça me fait penser à https://github.com/CppCon/CppCon2017/blob/master/Presentatio...

  • Excellentes slides
    La slide où un faux serveur rejoue les données d’ordres, un deuxième serveur calcule le temps d’exécution, et le serveur testé ainsi qu’un switch matériel mesurent le temps des paquets est vraiment hardcore dans le bon sens du terme
    Je n’ai pas envie de travailler dans la finance, mais ça doit être intéressant de s’attaquer à des systèmes critiques en performance où il est économiquement viable d’acheter des racks entiers de matériel uniquement pour le benchmarking

• J’ai créé une bibliothèque de logging C++ qui a beaucoup de points communs avec LMAX Disruptor, et elle semble aussi être utilisée dans une certaine mesure par la communauté HFT
  L’objectif initial était de pouvoir conserver en production des logs très détaillés pour le débogage post-mortem, sans dégrader les performances. Certains collègues refusaient d’ajouter dans les logs des informations importantes pour le diagnostic par crainte d’un impact sur les performances ; cette bibliothèque a clos le débat
  [1] https://github.com/mattiasflodin/reckless

• Un autre avantage du dispatch à la compilation est que, lorsque le compilateur peut déterminer statiquement quelle fonction est appelée, il peut inliner le code de la fonction appelée directement au point d’appel.
  Cela peut supprimer tout l’overhead de l’appel de fonction et permettre aussi des optimisations supplémentaires comme l’élimination du code mort ou la propagation de constantes.

  • À ma connaissance, les gains de vitesse viennent rarement de l’overhead des appels de fonction. Comme indiqué à la fin, l’essentiel est de savoir si les optimisations du compilateur peuvent voir au-delà d’une branche dynamique.
    Un bon JIT prend en charge l’inlining polymorphe. Mon expérience de C++ commence à dater, mais la solution à ce problème était le PGO. Cela dit, il n’est pas très répandu. À la place, dans le code sensible aux performances, on a tendance à éviter le dispatch dynamique lui-même.
    La leçon plus générale est que, quel que soit le langage, dans les zones chaudes du code, il faut éviter les branches dynamiques inutiles, sauf si l’on a une forte certitude que le compilateur ou le JIT saura les traverser.
  • Les performances réelles dépendent non seulement des optimisations du compilateur, mais aussi du comportement à l’exécution de la machine. Cette conférence sur le sujet était très intéressante :
    https://youtu.be/i5MAXAxp_Tw
  • À l’inverse, si le cache d’instructions est la limite, cela peut être une perte nette en termes de latence. Bien sûr, cela dépend du schéma d’accès, entre autres.

• Y a-t-il une bonne raison pour que le trading haute fréquence existe ? Les gens critiquent souvent Bitcoin pour son gaspillage d’énergie, mais cela aussi semble clairement être une perte nette pour la société, et pourtant on dirait que c’est étrangement accepté.

  • Les spreads achat/vente sont devenus beaucoup plus étroits qu’avant. Si l’on regarde les bénéfices de l’ensemble du secteur HFT, ils ne sont pas si énormes, de l’ordre de dizaines de milliards de dollars, alors que les montants échangés se comptent en milliers de milliards.
    Il est difficile de dire que cette industrie est massivement prosociale, mais réduire les spreads signifie bien que moins d’argent va aux intermédiaires.
  • J’imagine que c’est parce que ce n’est pas explicitement interdit.
    Le HFT est un domaine assez concentré, mais sa taille reste relativement faible. En matière de gaspillage d’énergie, il est plusieurs ordres de grandeur en dessous de Bitcoin.
    Le seul effet positif du HFT est la liquidité et des spreads plus étroits, mais cela dépend aussi de la manière dont les gens définissent le HFT. Par exemple, Robinhood et le trading gratuit n’existeraient probablement pas sans cela.
    Ils captent une part qui allait auparavant aux brokers et aux banques. Le HFT n’est pas une activité qui plume les « petits porteurs ».
    De mon point de vue, son impact négatif sur la société est faible, voire nul. Pour quelqu’un qui investit en Bourse à long terme, il y a très peu de raisons de se soucier du HFT.
  • Warren Buffett a suggéré que les marchés actions devraient ouvrir beaucoup moins souvent, par exemple une fois par trimestre. Cela encouragerait l’investissement à long terme plutôt que la spéculation.
    Quoi qu’il en soit, il n’existe pas d’événements naturels qui nécessitent le trading haute fréquence. Il est rare que la valeur fondamentale change très rapidement, et même quand c’est le cas, cela ressemble davantage à une transition déterministe qu’à de la volatilité.
  • Les transactions qui ne sont pas du Bitcoin ne font qu’écrire quelques entrées dans plusieurs bases de données. Le minage de Bitcoin est un travail intensif de calcul numérique.
    Le HFT rend les marchés financiers très légèrement plus précis en résolvant des incohérences, par exemple lorsque trois paires de devises ne sont pas alignées entre elles, ou des erreurs de prix « évidentes ».
  • Je me demande jusqu’où tu t’es renseigné, et si tu as déjà acheté ou vendu des actions.
    Quand tu essaies de trader quelque chose, il y a quelqu’un en face. La plupart du temps, il est probable que tu traites avec un acteur HFT au prix que tu souhaites. Si tu obtiens un meilleur prix, cet argent reste dans ta poche.
    J’ai aussi du mal à être d’accord avec l’idée que c’est « accepté ». Le HFT est assez souvent critiqué ici aussi.

• Pour un développeur professionnel, cela vaut la peine de tout regarder.
  https://github.com/CppCon/CppCon2017/tree/master/Presentatio...
  Ainsi que le répertoire parent.

• J’ai une question. Pourquoi, dans ce domaine, utilise-t-on, ou a-t-on utilisé, C++ plutôt que C pour la logique ? Quels avantages C++ a-t-il sur C dans ce domaine ? Je maîtrise C/assembleur, mais je ne connais pas du tout les pratiques du HFT, donc une explication simple serait appréciée.

  • C++ est plus expressif que C et permet beaucoup plus d’abstractions. Pendant longtemps, C++ a été le seul langage grand public à offrir à la fois des performances de niveau C et des abstractions riches ; c’est pour cela qu’il est devenu populaire dans des domaines qui nécessitent de modéliser des domaines complexes, comme le HFT, le développement de jeux ou le graphisme.
    On peut bien sûr débattre de la question de savoir si cette expressivité vaut l’énorme complexité du langage, mais dans la pratique, les gens ont choisi C++ de manière empirique.

• La structure et le ton de cet article sentent fortement le LLM