Patrones de C++ para aplicaciones de baja latencia, incluido el trading de alta frecuencia

• En áreas donde la latencia es una ventaja competitiva, como el trading de alta frecuencia (HFT), se recopila conocimiento de optimización en C++ que escasea públicamente, con foco en experimentos e implementación
• Los resultados se dividen en tres partes: Low-Latency Programming Repository, optimización de una estrategia de pair trading de mercado neutral y una biblioteca del patrón Disruptor en C++
• El benchmarking considera en conjunto velocidad, uso de caché y significancia estadística; Cache Warming y Constexpr muestran grandes beneficios en la reducción de latencia
• La estrategia optimizada de pair trading mejoró en velocidad de ejecución y rentabilidad, y la implementación de Disruptor muestra mejor rendimiento que los enfoques tradicionales basados en colas
• Las tareas futuras incluyen ampliar el repositorio, probar en entornos reales de trading e integrar Disruptor con algoritmos de trading para luego hacer benchmarking del sistema completo

---

Objetivo de la optimización de baja latencia para HFT

• El objetivo es aumentar la velocidad de ejecución optimizando código sensible a la latencia
• El foco está puesto en estrategias de programación y estructuras de datos usadas en trading de alta frecuencia
• En la industria financiera, especialmente las empresas buy-side que operan en mercados públicos, no se divulga mucho conocimiento relacionado debido a la confidencialidad y a la ventaja competitiva
• Para reducir esa brecha, se crea un Low-Latency Programming Repository personalizado con diversas técnicas y se valida mediante benchmarking estadístico

Tres resultados

• Low-Latency Programming Repository

  • No se limita a una recopilación teórica, sino que funciona como una guía práctica con benchmarking estadístico
  • Curaduría de técnicas de programación, patrones de diseño y buenas prácticas para reducir la latencia en sistemas HFT

• Optimización de una estrategia de pair trading de arbitraje estadístico de mercado neutral

  • Integra técnicas de reducción de latencia y optimizaciones a nivel de CPU
  • Muestra mejoras en velocidad de ejecución y rentabilidad

• Biblioteca del patrón Disruptor en C++

  • Muestra una mejora de rendimiento frente a los enfoques tradicionales basados en colas
  • Demuestra que este tipo de estructura de datos puede aplicarse al Order Management System (OMS) de sistemas HFT

Por qué falta conocimiento público

• El conocimiento sobre optimización de sistemas HFT proviene principalmente de profesionales de la industria, pero la confidencialidad y la ventaja competitiva dificultan la publicación de investigaciones recientes y detalles de implementación
• Áreas como mejoras de latencia, eficiencia del código y optimización de caché tienen material público especialmente limitado
• Existen investigaciones sobre HFT desde una perspectiva económica y financiera, así como estudios de modelos matemáticos para trading algorítmico, pero rara vez cubren técnicas detalladas de optimización de código o reducción de latencia
• Aunque la literatura sobre C++ es relativamente abundante, son limitados los casos que se conectan directamente con el contexto de sistemas HFT de latencia ultrabaja
• Los blogs y publicaciones en línea suelen ofrecer datos superficiales de latencia promedio, pero carecen de análisis detallados sobre el comportamiento del acceso a caché o la latencia de ejecución de instrucciones

Evaluación y mejoras de rendimiento

• Las métricas de evaluación incluyen velocidad, uso de caché y significancia estadística, entre otras
• Entre las técnicas del Low-Latency Programming Repository, Cache Warming y Constexpr muestran los mayores beneficios en reducción de latencia
• La implementación del patrón Disruptor usa un búfer en anillo, números de secuencia y estrategias especiales de espera para ofrecer mejor rendimiento en latencia y velocidad que los enfoques tradicionales basados en colas
• La estrategia de pair trading de mercado neutral mejora su velocidad de ejecución y rentabilidad mediante optimizaciones a nivel de CPU y técnicas de reducción de latencia

Repositorio público y trabajo futuro

• El repositorio, la estrategia de trading y la biblioteca Disruptor están en https://github.com/0burak/imperial hft
• El trabajo futuro incluye ampliar el repositorio
• Queda pendiente probar los algoritmos de trading optimizados en entornos reales de trading
• También se contempla integrar el patrón Disruptor con algoritmos de trading y realizar benchmarking a nivel del sistema completo

[GN⁺]

Opiniones de Hacker News

• Este artículo parece una introducción bastante básica al tema.
  Por mi experiencia enseñando a estudiantes de licenciatura, ellos también suelen saber ya estas cosas. En clases de arquitectura de computadoras aprenden los fundamentos del rendimiento, como la predicción de ramas, la coherencia de caché y la caché de instrucciones.
  Me sorprendió que no trate en absoluto un factor clásico de degradación del rendimiento como la compartición falsa (false sharing), y parece centrarse sobre todo en la latencia de un solo hilo. También me sorprendió que falten pistas de optimización “gratis” como fat LTO, PGO, [[likely]] y [[unlikely]].
  Para problemas de rendimiento más profundos hay que meterse hasta en APIs específicas de entrada/salida, primitivas de sincronización, comunicación entre procesos y formas de usar intrínsecos oscuros del compilador.
  Lo que más le falta a un programador de baja latencia, y lo más difícil de enseñar, es una especie de paranoia. Se necesita miedo y enojo reales ante asignaciones, copias y factores de degradación del rendimiento innecesarios. Es esa sensación de correr benchmarks obsesivamente con callgrind para encontrar, en medio de un hot loop, una llamada al asignador provocada por un fallo en la caché de objetos.
  En lo personal, al construir un servidor de baja latencia, fue importante el momento en que me di cuenta de que, en vez de armar operaciones de entrada/salida vectorizada, resultaba más rápido en conjunto copiar objetos pequeños a un búfer contiguo y hacer un único write. No hay copias gratis, y los fat pointers no son la excepción.

  • Puede ser, pero C++ de baja latencia es un campo independiente y aun así la información disponible es casi un desierto.
    El mejor material que se puede conseguir hoy son apenas algunas charlas de conferencias de C++, y dejan bastante que desear.
    Dejando de lado la tentación de presumir, este documento es una contribución excelente al área y quizá sea la primera referencia autorizada. Decir vagamente que se puede armar información parecida a partir de otras conferencias no es una contribución y no ayuda a nadie.
  • Por suerte ya no hago ese tipo de trabajo, pero la verdadera paranoia está en la desconfianza heisenbergiana. No puedes sacarte de la cabeza la sospecha de que el programa se comporta distinto cuando lo estás midiendo que cuando no.
  • Me pregunto si hay bibliografía generalmente recomendable.
  • Yo creo que lo abordaría así. Me interesa la retroalimentación de gente más cercana a este campo.
    Primero, por velocidad bruta, usaría un FPGA en el front-end para dividir la carga en flujos de datos simples por activo. Pero evitaría la tentación de ejecutar ahí mismo, porque la fricción de iteración, personal y cadena de suministro es demasiado alta. La entrada sería algo como un flujo FIX, y la salida se dividiría, a lo largo de un bus de baja latencia, en flujos de eventos binarios por activo que entrarían en segmentos por activo de un clúster escalable compuesto por MCU de bajo costo.
    Segundo, en la plataforma de ejecución basada en MCU por activo eliminaría las suposiciones de un sistema operativo de propósito general, para permitir transiciones más rápidas con código de bajo nivel que la gente pueda escribir sobre hardware realmente disponible. Tercero, ¿ganancias? En una estructura así, un supervisor basado en un sistema operativo de propósito general tendría que monitorear el estado global y, cuando fuera necesario, reprogramar elementos individuales para detener o cambiar la estrategia.
    La cuestión es qué tan baja es la latencia real. A partir de cierto punto, me parece que quizá conviene más pagar el costo de poner el hardware más cerca del core que seguir haciendo ingeniería. Eso dependerá mucho de las reglas que ofrezca la bolsa o el pool correspondiente, del centro de datos y de la infraestructura de enlaces.
    Muchas operaciones rentables probablemente no revelen a qué pool se conectan, y puede que conviertan el front-running en un negocio ignorando regulaciones o términos de servicio. En esos casos, la latencia geográfica relativa de red entre dos puntos de ejecución es más poderosa que la latencia absoluta hasta un punto.
  • Si se usa PGO, me parece que los atributos de pista más bien podrían ser contraproducentes.
    De hecho, la sabiduría común que suele mencionar la gente de compiladores es que, incluso sin PGO, en la mayoría de los casos estas pistas son contraproducentes. Los compiladores modernos confían más en sus propios pases de análisis que en estas pistas y normalmente las ignoran.
    Como referencia, en código real solo he visto estas pistas en lugares donde el compilador podría ponerlas fácilmente, por ejemplo en una comprobación de nulo después de una llamada a malloc.

• La parte que quiero destacar es esta:
  “La salida de esta prueba es el estadístico de prueba (t-statistic) y el p-value asociado. El t-statistic, también llamado puntuación, es el resultado de una prueba de raíz unitaria sobre los residuos. Un t-statistic más negativo sugiere que es más probable que los residuos sean estacionarios. El p-value proporciona una medida de la probabilidad de que la hipótesis nula de la prueba, es decir, la hipótesis de que no hay cointegración, sea verdadera. Los resultados de la prueba arrojaron un p-value de aproximadamente 0.0149 y un t-statistic de -3.7684.”
  Esta parte parece escrita con un LLM.
  El ejemplo también es realmente raro. Mira la correlación de precios de cierre una vez al día durante 5 años y luego escribe código para calcular el spread con una latencia de 65 microsegundos. No tiene sentido como algo que se haría en la práctica. Tampoco se calcularían estadísticas del spread dentro del bucle interno, y 65 microsegundos es demasiado lento para un bucle interno.
  La idea puede ser practicar técnicas de optimización, pero como objetivo de optimización es bastante poco representativo.

• Implementé en C++ una bolsa de valores que usa el patrón LMAX Disruptor
  https://github.com/sneilan/stock-exchange
  También dejé hecha una implementación básica de LMAX Disruptor en unos cuantos archivos C++
  https://github.com/sneilan/lmax-disruptor-tutorial
  Sin embargo, estoy viendo cómo rehacerlo en Rust. Llegué hasta el punto de implementar un protocolo propio de WebSocket, un sistema de autenticación, SSL, etc., pero me di cuenta de que la gestión de memoria y las dependencias son mucho más fáciles en Rust. Sobre todo si es un proyecto de software de una sola persona

  • No es fácil hacer bien este tipo de estructura de datos en C++. La implementación de la cola tiene varios problemas
    Como los accesos a memoria pueden reordenarse tanto del lado del compilador como del CPU, para obtener las barreras descritas en el artículo original de LMAX Disruptor hay que usar std::atomic en las posiciones del productor y del consumidor
    En el método get, primero se incrementa la posición del consumidor, es decir, se libera el slot para el productor, y después se devuelve un puntero al elemento interno de la cola. Por eso podría sobrescribirse mientras el usuario lo está accediendo
    Además, es muy probable que las posiciones del productor y del consumidor queden en la misma línea de caché, lo que provoca false sharing
  • En lugar de código como este
    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;
    se puede hacer esto
    uint64_t mask = slot_count - 1; // todos 1 en binario
item = &slots[ pos & mask ];
pos ++;
    Es decir, se puede reducir un poco el cálculo reemplazando la división/módulo por un AND bit a bit. Eso sí, el tamaño del ring buffer debe ser una potencia de 2
    Más aún, se puede usar un número de secuencia de rango completo, como uint64_t. El wrap-around se maneja automáticamente. Incluso al restar dos números de secuencia, funciona sin problemas teniendo en cuenta el wrap-around. También desaparece el problema tonto de tener que dejar un slot vacío para distinguir si el buffer está lleno o vacío
    Claro que hay que tener cuidado de que la ventana de números de secuencia “vivos” nunca supere el tamaño de la ventana del ring buffer
  • Le eché un vistazo rápido al código de la bolsa de valores
    Para la gestión de memoria, valdría la pena considerar cambiar a std::shared_ptr. Elimina por completo esa preocupación sin volverlo más lento
    Para sockets, hay bibliotecas libres y open source que rinden mejor que el código escrito a mano y reducen los casos especiales molestos. Por ejemplo, recorrer FD_ISSET es más lento que epoll o kqueue
    La gestión de dependencias en C++ definitivamente es más áspera que en otros lenguajes. Incluso encontrarlas es más difícil que gestionarlas. Hay código de bibliotecas útil repartido por todas partes, y parte está escondido en rincones olvidados de internet. Encontrarlo ya es una habilidad en sí misma, y si se hace bien puede tener una gran recompensa
  • LMAX Disruptor es una estructura de datos excelente cuando fijas los threads a cores y la mayoría, o todos, no compiten entre sí. Si no se usa este patrón, aparecen patologías horribles en la latencia de cola. Si un thread queda desplazado del scheduler en un mal momento, el golpe es fuerte
    En el sistema que estás pensando, creo que será difícil superar un ring buffer SPSC, y si hace falta también se podría implementar work stealing con locks a la vieja usanza
  • Dato curioso: originalmente LMAX fue diseñado para Java y escrito en Java
    https://martinfowler.com/articles/lmax.html

• Me hizo pensar en https://github.com/CppCon/CppCon2017/blob/master/Presentatio...

  • Son excelentes diapositivas
    La diapositiva donde un servidor falso reproduce datos de órdenes, un segundo servidor calcula el tiempo de ejecución, y un servidor bajo prueba junto con un switch de hardware miden el tiempo de los paquetes es deliciosamente hardcore
    No tengo ganas de trabajar en finanzas, pero suena divertido lidiar con sistemas críticos de rendimiento donde sea económicamente viable comprar hardware por racks solo para benchmarking

• Creé una biblioteca de logging en C++ que tiene muchas similitudes con LMAX Disruptor, y parece que también se usa en cierta medida en la comunidad de HFT
  El objetivo original era permitir logs muy detallados en producción para depuración post mortem sin degradar el rendimiento. Algunos colegas se negaban a poner en los logs información importante para resolver problemas por miedo a afectar el rendimiento, pero con esta biblioteca se terminó esa discusión
  [1] https://github.com/mattiasflodin/reckless

• Otra ventaja del dispatch en tiempo de compilación es que, cuando el compilador puede determinar estáticamente qué función se llama, puede inlinear el código de la función llamada directamente en el punto de llamada.
  Eso elimina todo el overhead de la llamada a función y también puede habilitar optimizaciones adicionales como eliminación de código muerto y propagación de constantes.

  • Hasta donde sé, casi nunca la mejora de velocidad se debe al overhead de la llamada a función. Como se dijo hacia el final, la clave está en si la optimización del compilador puede ver más allá de una rama dinámica.
    Un buen JIT soporta inline polimórfico. Mi experiencia con C++ ya es algo vieja, pero la solución a este problema era PGO. Aunque no se usa ampliamente. En cambio, en código sensible al rendimiento se tiende a evitar directamente el dispatch dinámico.
    La lección más general es que, en cualquier lenguaje, en las zonas calientes del código conviene evitar ramas dinámicas innecesarias, salvo que tengas una fuerte certeza de que el compilador o el JIT pueden atravesarlas.
  • El rendimiento real depende no solo de las optimizaciones del compilador, sino también del comportamiento en runtime de la máquina. Sobre este tema, esta charla me pareció muy interesante:
    https://youtu.be/i5MAXAxp_Tw
  • Por el contrario, si el límite es la caché de instrucciones, puede ser una pérdida neta en términos de latencia. Claro que depende del patrón de acceso y otros factores.

• ¿Hay alguna buena razón para que exista el trading de alta frecuencia? La gente suele criticar a Bitcoin por desperdiciar energía, pero esto también parece claramente una pérdida neta para la sociedad, y sin embargo da la impresión de que se deja pasar sin más.

  • Los spreads de compra/venta se han vuelto mucho más estrechos que antes. Si se miran las ganancias de toda la industria de HFT, no son tan grandes: están en el orden de decenas de miles de millones de dólares, mientras que el monto transado está en billones.
    Es difícil decir que esta industria sea enormemente prosocial, pero sí es cierto que estrechar los spreads reduce el dinero que va a los intermediarios.
  • Supongo que es porque no está prohibido explícitamente.
    Aunque HFT es un ámbito bastante concentrado, su escala en sí es más bien pequeña. En términos de desperdicio de energía, es varios órdenes de magnitud menor que Bitcoin.
    El único efecto positivo de HFT es la liquidez y spreads más estrechos, aunque también depende de cómo la gente defina HFT. Por ejemplo, Robinhood y las operaciones gratuitas probablemente no existirían sin esto.
    Están capturando una parte que antes iba a brokers y bancos. HFT no es un negocio de desplumar al “inversionista minorista”.
    Desde mi punto de vista, tiene poco o ningún impacto negativo sobre la sociedad. Si inviertes en el mercado accionario a largo plazo, casi no hay motivo para preocuparte por HFT.
  • Warren Buffett propuso que el mercado accionario debería abrir con menos frecuencia, por ejemplo una vez por trimestre. Eso podría fomentar la inversión a largo plazo en lugar de la especulación.
    En cualquier caso, no hay eventos naturales que requieran trading de alta frecuencia. Es raro que el valor fundamental cambie muy rápido y, aun cuando cambia, suele parecerse más a una transición definitiva que a volatilidad.
  • Las transacciones que no son Bitcoin consisten solo en escribir algunas entradas en varias bases de datos. La minería de Bitcoin es trabajo intensivo de cómputo numérico.
    HFT resuelve inconsistencias —por ejemplo, situaciones en las que tres pares de divisas no cuadran entre sí— o precios “obviamente” incorrectos, haciendo que los mercados financieros sean apenas un poco más precisos.
  • Me da curiosidad cuánto investigaste y si alguna vez compraste o vendiste acciones.
    Cuando intentas operar algo, hay alguien del otro lado. Normalmente es bastante probable que termines operando con un participante de HFT al precio que querías. Si recibes un mejor precio, ese dinero es dinero que conservas.
    Tampoco estoy de acuerdo con eso de que “se deja pasar”. HFT también se critica bastante seguido por aquí.

• Si eres desarrollador profesional, vale la pena verlo completo:
  https://github.com/CppCon/CppCon2017/tree/master/Presentatio...
  Y también el directorio superior.

• Tengo una duda. En este campo, ¿por qué se usa, o se ha usado, C++ para la lógica en lugar de C? ¿Qué ventajas tiene C++ sobre C en esta área? Soy hábil con C/ensamblador, pero no sé nada de las prácticas de HFT, así que agradecería una explicación sencilla.

  • C++ es más expresivo que C y permite muchas más abstracciones. Durante mucho tiempo, C++ fue el único lenguaje mainstream que ofrecía rendimiento a nivel de C junto con abstracciones ricas, y por eso se volvió popular en áreas que requieren modelar dominios complejos, como HFT, desarrollo de videojuegos y gráficos.
    Por supuesto, se puede discutir si esa expresividad vale la pena frente a la enorme complejidad del lenguaje, pero en la práctica la gente ha elegido C++ empíricamente.

• La estructura y el tono de este artículo tienen un fuerte olor a LLM