Padrões em C++ para aplicações de baixa latência, incluindo high-frequency trading

• Em áreas como high-frequency trading (HFT), onde a latência é a própria vantagem competitiva, o autor organiza conhecimentos pouco disponíveis publicamente sobre otimização em C++ com foco em experimentos e implementação
• Os resultados são divididos em três partes: o Low-Latency Programming Repository, a otimização de uma estratégia de pair trading neutra ao mercado e uma biblioteca do padrão Disruptor em C++
• O benchmarking avalia velocidade, uso de cache e significância estatística em conjunto, e mostra que Cache Warming e Constexpr trazem grandes ganhos na redução de latência
• A estratégia de pair trading otimizada melhorou a velocidade de execução e a rentabilidade, e a implementação do Disruptor apresentou desempenho superior ao de abordagens tradicionais com filas
• Os próximos passos incluem expandir o repositório, testar em ambiente real de negociação e integrar o Disruptor com o algoritmo de trading para benchmark do sistema completo

---

Objetivo da otimização de baixa latência em HFT

• O objetivo é otimizar código sensível à latência para aumentar a velocidade de execução
• O foco está em estratégias de programação e estruturas de dados usadas em high-frequency trading
• No setor financeiro, especialmente em empresas buy-side que atuam em mercados públicos, muito desse conhecimento não é divulgado por questões de confidencialidade e vantagem competitiva
• Para reduzir essa lacuna, foi criado um Low-Latency Programming Repository personalizado com várias técnicas, validado por benchmarking estatístico

Três resultados

• Low-Latency Programming Repository

  • Não é apenas uma coletânea teórica, mas um guia prático com benchmarking estatístico
  • Faz a curadoria de técnicas de programação, padrões de design e boas práticas para reduzir a latência em sistemas HFT

• Otimização de uma estratégia de pair trading estatística neutra ao mercado

  • Integra técnicas de redução de latência e otimizações em nível de CPU
  • Mostra melhorias na velocidade de execução e na rentabilidade

• Biblioteca do padrão Disruptor em C++

  • Mostra ganho de desempenho em relação a abordagens tradicionais com filas
  • Demonstra que essa estrutura de dados pode ser aplicada ao Order Management System (OMS) de sistemas HFT

Por que há pouca informação pública

• O conhecimento sobre otimização de sistemas HFT vem principalmente de profissionais do setor, mas detalhes de pesquisas recentes e de implementação raramente são divulgados por confidencialidade e vantagem competitiva
• Áreas como melhoria de latência, eficiência de código e otimização de cache têm material público especialmente limitado
• Existem estudos de HFT sob a perspectiva econômica e financeira, assim como modelos matemáticos de algorithmic trading, mas é raro que entrem nos detalhes técnicos de otimização de código ou redução de latência
• Mesmo havendo relativamente bastante literatura sobre C++, há poucas conexões diretas com o contexto de sistemas HFT de ultrabaixa latência
• Blogs e posts online frequentemente apresentam apenas dados superficiais de latência média, sem análise detalhada de acesso a cache ou atraso na execução de instruções

Avaliação e melhorias de desempenho

• As métricas de avaliação incluem velocidade, uso de cache e significância estatística
• Entre as técnicas do Low-Latency Programming Repository, Cache Warming e Constexpr mostraram os maiores ganhos na redução de latência
• A implementação do padrão Disruptor usa ring buffer, números de sequência e estratégias de espera especializadas para superar abordagens tradicionais com filas em latência e velocidade
• A estratégia de pair trading neutra ao mercado melhorou velocidade de execução e rentabilidade por meio de otimizações em nível de CPU e técnicas de redução de latência

Repositório público e trabalho futuro

• O repositório, a estratégia de trading e a biblioteca Disruptor estão em https://github.com/0burak/imperial hft
• O trabalho futuro inclui a expansão do repositório
• Ainda resta testar o algoritmo de trading otimizado em ambiente real de negociação
• Também inclui integrar o padrão Disruptor ao algoritmo de trading para realizar benchmarking no nível do sistema completo

[GN⁺]

Opiniões no Hacker News

• Este artigo parece uma introdução bastante básica ao tema.
  Pela minha experiência ensinando alunos de graduação, eles em geral já sabem esse tipo de coisa. Em aulas de arquitetura de computadores, aprendem os fundamentos de desempenho, como predição de desvios, coerência de cache e cache de instruções.
  Achei surpreendente que ele não trate em nada de falso compartilhamento (false sharing), um fator clássico de queda de desempenho, e parece se concentrar principalmente na latência em single thread. Também me surpreendeu a ausência de dicas de otimização “gratuitas” como fat LTO, PGO, [[likely]] e [[unlikely]].
  Problemas de desempenho mais profundos exigem entrar em APIs específicas de entrada/saída, primitivas de sincronização, comunicação entre processos e formas de uso de recursos internos obscuros do compilador.
  O que mais falta a programadores de baixa latência, e o mais difícil de ensinar, é uma espécie de paranoia. É preciso ter medo e raiva reais de alocações desnecessárias, cópias e fatores que degradam o desempenho. É aquela sensação de rodar benchmarks compulsivamente no callgrind para encontrar, no meio de um hot loop, uma chamada que vai parar no alocador porque o cache de objetos falhou.
  Para mim, ao criar um servidor de baixa latência, foi importante o momento em que percebi que, em vez de montar operações de E/S vetorizadas, copiar pequenos objetos para um buffer contíguo e fazer um único write era mais rápido no geral. Não existe cópia grátis, e fat pointer não é exceção.

  • Pode ser, mas C++ de baixa latência é uma área independente e, ainda assim, as informações são quase um deserto.
    O melhor material disponível hoje se resume a algumas palestras de conferências de C++, e elas deixam bastante a desejar.
    Deixando de lado a tentação de se exibir, este documento é uma contribuição excelente para a área e talvez seja a primeira referência de autoridade. Dizer vagamente que dá para juntar informações parecidas em outras aulas não é uma contribuição e não ajuda ninguém.
  • Ainda bem que hoje não faço esse tipo de coisa, mas a verdadeira paranoia está na desconfiança heisenberguiana. Não dá para se livrar da suspeita de que o programa se comporta de forma diferente quando está sendo medido e quando não está.
  • Fico curioso se há alguma literatura geralmente recomendável.
  • Acho que eu abordaria assim. Gostaria de ouvir o feedback de pessoas mais próximas dessa área.
    Primeiro, para obter velocidade bruta, eu usaria um FPGA no front-end para dividir a carga em fluxos de dados simples por ativo. Mas evitaria a tentação de executar a lógica ali de fato, porque o atrito de iteração de desenvolvimento, equipe, cadeia de suprimentos etc. é grande demais. A entrada seria algo como um fluxo FIX, e a saída seria dividida, por um barramento de baixa latência, em fluxos de eventos binários por ativo, entrando em segmentos por ativo de um cluster escalável composto por MCUs de baixo custo.
    Em segundo lugar, na plataforma de execução baseada em MCU por ativo, eu removeria as suposições de um sistema operacional de propósito geral, permitindo uma transição mais rápida com código de baixo nível que as pessoas conseguem escrever sobre hardware realmente disponível. Terceiro, lucro? Nessa arquitetura, um supervisor baseado em sistema operacional de propósito geral teria de monitorar o estado global e, quando necessário, reprogramar elementos individuais para interromper ou alterar a estratégia.
    A questão é quão baixa é a latência real. A partir de certo ponto, acho que pode valer mais a pena pagar o custo de colocar o hardware mais perto do núcleo do que continuar investindo em engenharia. Isso dependeria muito das regras, do data center e da infraestrutura de links oferecidos pela bolsa ou pool em questão.
    Muitas operações lucrativas provavelmente não revelam a quais pools se conectam e talvez façam de front-running um negócio, ignorando regulações ou termos de uso. Nesses casos, a latência geográfica relativa de rede entre dois pontos de execução é mais poderosa do que a latência absoluta até um único ponto.
  • Se você usa PGO, os atributos de dica não seriam contraproducentes?
    De fato, o senso comum que o pessoal de compiladores costuma mencionar é que, mesmo sem PGO, na maioria dos casos essas dicas são contraproducentes. Compiladores modernos confiam mais em seus próprios passes de análise do que nessas dicas e normalmente as ignoram.
    A propósito, os únicos lugares em que vi essas dicas em código real foram aqueles em que o compilador poderia inseri-las facilmente. Por exemplo, uma verificação de nulo depois de uma chamada a malloc.

• A parte que eu quero destacar é esta:
  “A saída deste teste é a estatística do teste (t-statistic) e o p-value associado. A t-statistic, também chamada de pontuação, é o resultado do teste de raiz unitária sobre os resíduos. Uma t-statistic mais negativa sugere maior probabilidade de que os resíduos sejam estacionários. O p-value fornece uma medida da probabilidade de que a hipótese nula do teste, isto é, a hipótese de ausência de cointegração, seja verdadeira. O resultado do teste produziu um p-value de aproximadamente 0,0149 e uma t-statistic de -3,7684.”
  Essa parte parece ter sido escrita por um LLM.
  O exemplo também é realmente estranho. Ele observa a correlação dos preços de fechamento uma vez por dia durante 5 anos e depois escreve código para calcular o spread com latência de 65 microssegundos. Isso não faz sentido como algo que você faria de verdade. Você também não calcularia estatísticas de spread no loop interno, e 65 microssegundos é lento demais para um loop interno.
  A ideia pode ser praticar técnicas de otimização, mas, como alvo de otimização, é bem pouco representativo.

• Implementei em C++ uma bolsa de valores usando o padrão LMAX Disruptor
  https://github.com/sneilan/stock-exchange
  Também deixei uma implementação básica do LMAX Disruptor em alguns arquivos C++
  https://github.com/sneilan/lmax-disruptor-tutorial
  Só que estou pensando em refazer isso em Rust. Cheguei ao ponto de implementar um protocolo WebSocket próprio, sistema de autenticação, SSL etc., mas percebi que gerenciamento de memória e dependências são muito mais fáceis em Rust. Especialmente em um projeto de software de uma pessoa só

  • Não é fácil fazer esse tipo de estrutura de dados direito em C++. Há alguns problemas na implementação da fila
    O acesso à memória pode ser reordenado tanto pelo compilador quanto pela CPU, então é preciso usar std::atomic nas posições do produtor e do consumidor para obter as barreiras descritas no artigo original do LMAX Disruptor
    No método get, a posição do consumidor é incrementada e, portanto, o slot é liberado para o produtor, antes de retornar um ponteiro para o elemento interno da fila. Assim, ele pode ser sobrescrito enquanto o usuário está acessando
    Além disso, é provável que as posições do produtor e do consumidor fiquem na mesma linha de cache, causando false sharing
  • Em vez deste código
    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;
    dá para fazer assim
    uint64_t mask = slot_count - 1; // todos 1 em binário
item = &slots[ pos & mask ];
pos ++;
    Ou seja, dá para reduzir um pouco o cálculo trocando divisão/módulo por AND bit a bit. Mas o tamanho do ring buffer precisa ser uma potência de 2
    Indo além, dá para usar um número de sequência com intervalo completo, como uint64_t. O wraparound é tratado automaticamente. Subtrair dois números de sequência também funciona sem problemas levando o wraparound em conta. Também desaparece aquele problema idiota de ter que deixar um slot vazio para distinguir se o buffer está cheio ou vazio
    Claro, é preciso tomar cuidado para que a janela de números de sequência “vivos” nunca ultrapasse o tamanho da janela do ring buffer
  • Dei uma olhada rápida no código da bolsa de valores
    Para gerenciamento de memória, vale considerar trocar para std::shared_ptr. Isso elimina completamente essa preocupação sem reduzir a velocidade
    Para sockets, existem bibliotecas livres e open source que têm desempenho melhor e reduzem os casos excepcionais chatos em comparação com código escrito do zero. Por exemplo, iterar com FD_ISSET é mais lento do que epoll ou kqueue
    O gerenciamento de dependências em C++ é definitivamente mais bruto do que em outras linguagens. Encontrar dependências também pode ser mais difícil do que gerenciá-las. Código de biblioteca útil está espalhado por aí, e parte dele fica escondida em cantos esquecidos da internet. Encontrar isso já é uma habilidade por si só, e quando você é bom nisso, a recompensa é grande
  • O LMAX Disruptor é uma excelente estrutura de dados quando as threads são fixadas a cores e a maioria, ou todas, não está competindo por recursos. Sem esse padrão, aparecem patologias horríveis na latência de cauda. Se uma thread for retirada do escalonamento no momento errado, o impacto é grande
    No sistema que você está considerando, acho que vai ser difícil superar um ring buffer SPSC e, se necessário, também dá para implementar work stealing com locks à moda antiga
  • Curiosidade: o LMAX foi originalmente projetado para Java e escrito em Java
    https://martinfowler.com/articles/lmax.html

• Isso me lembrou https://github.com/CppCon/CppCon2017/blob/master/Presentatio...

  • Slides excelentes
    O slide em que um servidor falso reproduz dados de ordens, um segundo servidor calcula o tempo de execução e um servidor em teste, junto com um switch de hardware, mede o tempo dos pacotes é deliciosamente hardcore
    Não tenho vontade de trabalhar no setor financeiro, mas deve ser divertido lidar com sistemas críticos de desempenho em um nível em que é economicamente viável comprar hardware em racks só para benchmarking

• Criei uma biblioteca de logging em C++ que tem muitos pontos em comum com o LMAX Disruptor e que parece ser usada em certa medida pela comunidade de HFT
  O objetivo original era permitir logs extremamente detalhados em produção para depuração post-mortem, sem degradação de desempenho. Eu tinha colegas que relutavam em colocar nos logs informações importantes para solucionar problemas por medo de impactar a performance, mas esta biblioteca encerrou essa discussão
  [1] https://github.com/mattiasflodin/reckless

• Outra vantagem do despacho em tempo de compilação é que, quando o compilador consegue determinar estaticamente qual função será chamada, ele pode inlinear o código da função chamada diretamente no ponto de chamada
  Isso elimina todo o overhead da chamada de função e também pode permitir otimizações adicionais, como eliminação de código morto e propagação de constantes

  • Pelo que sei, raramente a causa do ganho de velocidade é o overhead de chamada de função. Como foi dito no final, o ponto principal é se a otimização do compilador consegue enxergar além da ramificação dinâmica
    Um bom JIT oferece suporte a inline polimórfico. Minha experiência com C++ já é um pouco antiga, mas a solução para esse problema era PGO. Só que não é algo amplamente usado. Em vez disso, em código sensível a desempenho, a tendência é evitar o despacho dinâmico em si
    A lição mais geral é: em qualquer linguagem, nos trechos quentes do código, evite ramificações dinâmicas desnecessárias, a menos que você tenha forte convicção de que o compilador ou o JIT consegue atravessá-las
  • O desempenho real depende não só das otimizações do compilador, mas também do comportamento em runtime da máquina. Sobre esse tema, esta palestra foi muito interessante
    https://youtu.be/i5MAXAxp_Tw
  • Por outro lado, se o limite for o cache de instruções, isso pode ser uma perda líquida em termos de latência. Claro, depende do padrão de acesso e de outros fatores

• Há algum bom motivo para a existência de negociação de alta frequência? As pessoas criticam bastante o Bitcoin por desperdiçar energia, mas isso também parece claramente uma perda líquida para a sociedade e, curiosamente, parece passar batido

  • Os spreads de compra/venda ficaram muito mais estreitos do que antes. Se olhar para o lucro de toda a indústria de HFT, ele não é tão grande assim, fica na casa de dezenas de bilhões de dólares, enquanto o volume negociado é de trilhões
    É difícil dizer que esse setor seja extremamente pró-social, mas é verdade que estreitar os spreads reduz o dinheiro que vai para intermediários
  • Imagino que seja porque não é explicitamente proibido
    HFT é uma área bastante concentrada, mas seu tamanho em si é relativamente pequeno. Em termos de desperdício de energia, é várias ordens de grandeza menor que o Bitcoin
    O único efeito positivo do HFT é a liquidez e spreads mais estreitos, mas isso também depende de como as pessoas definem HFT. Por exemplo, a Robinhood e as negociações gratuitas provavelmente não existiriam sem isso
    Eles estão tomando uma fatia que antes ia para corretoras e bancos. HFT não é um negócio de passar a perna no “investidor pessoa física”
    Do meu ponto de vista, o impacto negativo sobre a sociedade é quase inexistente, ou inexistente. Para quem investe no mercado de ações no longo prazo, há pouquíssimos motivos para se preocupar com HFT
  • Warren Buffett sugeriu que o mercado de ações deveria abrir com menos frequência, como uma vez por trimestre. Isso poderia incentivar investimento de longo prazo, e não especulação
    De todo modo, não há nenhum evento natural que exija negociação de alta frequência. É raro que o valor fundamental mude muito rapidamente e, mesmo quando muda, está mais para uma transição definida do que para volatilidade
  • Transações que não são Bitcoin são apenas escrever alguns registros em vários bancos de dados. Mineração de Bitcoin é uma carga pesada de computação numérica
    HFT torna os mercados financeiros um pouquinho mais precisos ao resolver inconsistências, por exemplo quando três pares de moedas ficam desalinhados entre si, ou corrigindo uma precificação “óbvia” errada
  • Fico curioso sobre até onde você pesquisou e se já comprou e vendeu ações
    Quando você tenta negociar algo, há alguém do outro lado. Em geral, é bem provável que você acabe negociando com um participante de HFT no preço que deseja. Se você recebe um preço melhor, esse é dinheiro que fica com você
    Também é difícil concordar com a ideia de que isso “passa batido”. HFT também é criticado com bastante frequência por aqui

• Se você é um desenvolvedor profissional, vale a pena ver tudo
  https://github.com/CppCon/CppCon2017/tree/master/Presentatio...
  E também o diretório acima dele

• Tenho uma dúvida. Por que, nessa área, usariam ou teriam usado C++ para a lógica, em vez de C? Quais vantagens o C++ tem sobre C nesse domínio? Sou fluente em C/assembly, mas não conheço nada das práticas de HFT, então uma explicação simples seria bem-vinda

  • C++ é mais expressivo que C e permite muito mais abstrações. Por muito tempo, C++ foi a única linguagem mainstream que oferecia desempenho no nível de C junto com abstrações ricas, e por isso ganhou popularidade em áreas que exigem modelagem de domínios complexos, como HFT, desenvolvimento de jogos e gráficos
    Claro, dá para discutir se essa expressividade vale a enorme complexidade da linguagem, mas, na prática, as pessoas têm escolhido C++ empiricamente

• A estrutura e o tom deste texto deixam um forte cheiro de LLM