Yüksek frekanslı işlemler dahil düşük gecikmeli uygulamalar için C++ kalıpları

 (arxiv.org)
1 puan yazan GN⁺ 2024-07-09 | 1 yorum | WhatsApp'ta paylaş
  • Yüksek frekanslı işlem (HFT) gibi gecikmenin doğrudan rekabet avantajı olduğu alanlarda, kamuya açıkta eksik olan C++ optimizasyon bilgisi deney ve uygulama odaklı olarak derleniyor
  • Ortaya çıkan çalışma üç parçaya ayrılıyor: Low-Latency Programming Repository, piyasa nötr pair trading stratejisi optimizasyonu ve C++ Disruptor pattern kütüphanesi
  • Benchmark değerlendirmeleri hız, cache kullanımı ve istatistiksel anlamlılığı birlikte ele alıyor; Cache Warming ve Constexpr gecikmeyi azaltmada büyük kazanım sağlıyor
  • Optimize edilen pair trading stratejisi hem yürütme hızı hem de kârlılık açısından iyileşme gösterirken, Disruptor implementasyonu geleneksel kuyruk yaklaşımından daha iyi performans veriyor
  • Gelecek çalışmalar arasında deponun genişletilmesi, gerçek işlem ortamında testler ve Disruptor ile işlem algoritmalarının entegre edilmesinden sonra tüm sistemin benchmark edilmesi yer alıyor

HFT düşük gecikme optimizasyonunun hedefi

  • Amaç, gecikmeye duyarlı kodu optimize ederek yürütme hızını artırmak
  • Odak, yüksek frekanslı işlemlerde kullanılan programlama stratejileri ve veri yapıları üzerinde
  • Finans sektörü, özellikle açık piyasalarla çalışan buy-side şirketler, gizlilik ve rekabet avantajı nedeniyle bu konudaki bilgileri fazla paylaşmıyor
  • Bu boşluğu azaltmak için çeşitli teknikleri içeren özel bir Low-Latency Programming Repository oluşturuluyor ve istatistiksel benchmark ile doğrulanıyor

Üç çıktı

  • Low-Latency Programming Repository

    • Sadece bir teori derlemesi değil, istatistiksel benchmark içeren pratik bir rehber işlevi görüyor
    • HFT sistemlerinde gecikmeyi azaltmaya yönelik programlama tekniklerini, tasarım kalıplarını ve iyi uygulamaları derliyor

  • Piyasa nötr istatistiksel arbitraj pair trading stratejisi optimizasyonu

    • Gecikme azaltma tekniklerini ve CPU düzeyi optimizasyonlarını entegre ediyor
    • Yürütme hızı ve kârlılıkta iyileşme gösteriyor

  • C++ Disruptor pattern kütüphanesi

    • Geleneksel kuyruk yaklaşımına göre performans artışı sağlıyor
    • HFT sistemlerinin Order Management System (OMS) içinde bu tür veri yapılarının uygulanabileceğini gösteriyor

Açık bilginin neden yetersiz olduğu

  • HFT sistem optimizasyonu bilgisi çoğunlukla sektör profesyonellerinden geliyor; ancak gizlilik ve rekabet avantajı nedeniyle güncel araştırmaların ve implementasyon ayrıntılarının kamuya açılması zor oluyor
  • Gecikme iyileştirmesi, kod verimliliği ve cache optimizasyonu gibi alanlarda açık kaynaklar özellikle sınırlı
  • Ekonomi ve finans perspektifinden HFT araştırmaları ile algoritmik işlem matematik modelleri mevcut olsa da, kod optimizasyonu veya gecikme azaltımının ayrıntılı tekniklerine kadar inen çalışmalar nadir
  • C++ literatürü görece daha fazla olsa da, bunun ultra düşük gecikmeli HFT sistemleri bağlamına doğrudan bağlandığı örnekler sınırlı
  • Çevrimiçi bloglar ve yazılar çoğu zaman ortalama gecikme verilerini yüzeysel biçimde sunuyor; cache erişimi veya komut yürütme gecikmesinin ayrıntılı davranış analizleri ise yetersiz kalıyor

Değerlendirme ve performans iyileştirmesi

  • Değerlendirme ölçütleri arasında hız, cache kullanımı ve istatistiksel anlamlılık bulunuyor
  • Low-Latency Programming Repository içindeki tekniklerden Cache Warming ve Constexpr, gecikme azaltımında en büyük kazancı sağlıyor
  • Disruptor pattern implementasyonu; ring buffer, sequence number ve özel bekleme stratejilerini kullanarak geleneksel kuyruk yaklaşımından gecikme ve hız açısından daha iyi performans üretiyor
  • Piyasa nötr pair trading stratejisi, CPU düzeyi optimizasyonlar ve gecikme azaltma teknikleri sayesinde yürütme hızı ve kârlılıkta iyileşiyor

Açık depo ve gelecek çalışmalar

  • Depo, işlem stratejisi ve Disruptor kütüphanesi https://github.com/0burak/imperial hft adresinde bulunuyor
  • Gelecek çalışmalar arasında deponun genişletilmesi yer alıyor
  • Optimize edilmiş işlem algoritmalarının gerçek işlem ortamında test edilmesi gereken bir sonraki görev olarak duruyor
  • Disruptor pattern'in işlem algoritmalarıyla entegre edilerek tüm sistem düzeyinde benchmark yapılması da planlar arasında

İlgili okumalar

1 yorum

 
GN⁺ 2024-07-09
Hacker News yorumları

  • Bu yazı, konuya oldukça temel bir giriş gibi görünüyor
    Lisans öğrencilerine ders vermiş biri olarak, öğrenciler de genelde bu tür şeyleri zaten biliyor. Bilgisayar mimarisi dersinde dallanma tahmini, önbellek tutarlılığı ve komut önbelleği gibi performansın temel unsurlarını öğreniyorlar
    Klasik performans düşüşü nedenlerinden false sharing konusuna hiç değinmemesi şaşırtıcıydı; daha çok tek iş parçacıklı gecikme süresine odaklanmış gibi. fat LTO, PGO, [[likely]], [[unlikely]] gibi “bedava” optimizasyon ipuçlarının da eksik olması şaşırtıcıydı
    Daha derin performans sorunları, belirli giriş/çıkış API'lerine, senkronizasyon ilkel işlemlerine, süreçler arası iletişime ve anlaşılması zor derleyici yerleşiklerinin kullanım biçimlerine kadar inmeyi gerektirir
    Düşük gecikmeli programcıların en çok eksikliğini çektiği ve öğretmesi en zor şey bir tür paranoyadır. Gereksiz ayırmalara, kopyalamalara ve performans düşürücülere karşı gerçek bir korku ve öfke gerekir. Sıcak döngünün tam ortasında nesne önbelleği ıskalayıp ayırıcıya giden çağrıyı bulmak için callgrind ile benchmark'ları takıntılı biçimde çalıştırma hissidir bu
    Kişisel olarak, düşük gecikmeli bir sunucu geliştirirken vektör G/Ç işlemleri oluşturmaktansa küçük nesneleri ardışık bir arabelleğe kopyalayıp tek bir write yapmanın genel olarak daha hızlı olduğunu fark ettiğim an önemliydi. Bedava kopya yoktur; fat pointer da istisna değildir

    • Öyle olabilir ama düşük gecikmeli C++, başlı başına bir alan olmasına rağmen bilgi açısından neredeyse çöl gibi
      Şu anda elde edilebilecek en iyi kaynaklar bile birkaç C++ konferans konuşmasından ibaret ve oldukça yetersizdi
      Gösteriş yapma dürtüsünü bir kenara bırakırsak, bu belge bu alana mükemmel bir katkı ve belki de ilk yetkin referans olabilir. Başka derslerden benzer bilgilerin bir araya getirilebileceğine dair muğlak sözler katkı değildir ve kimseye yardımcı olmaz
    • Neyse ki artık böyle işler yapmıyorum, ama gerçek paranoya Heisenberg tarzı güvensizlikte. Programın ölçüm yapılırken ve yapılmazken farklı davranıp davranmadığına dair şüpheden kurtulamıyorsunuz
    • Genel olarak önerebileceğiniz kaynaklar var mı, merak ediyorum
    • Ben olsam muhtemelen şöyle yaklaşırdım. Bu alana daha yakın kişilerin geri bildirimini merak ediyorum
      Önce ham hız için ön uç FPGA ile yükü varlık bazında basit veri akışlarına ayırırdım. Ancak yinelemeli geliştirme, insan kaynağı ve tedarik zinciri gibi sürtünmeler çok büyük olduğundan, burada gerçek yürütmeye kadar gitme cazibesinden kaçınırdım. Girdi FIX akışı gibi bir şey olurdu; çıktı ise düşük gecikmeli bir veri yolu boyunca varlık bazında ikili olay akışlarına ayrılır ve düşük maliyetli MCU'lardan oluşan ölçeklenebilir bir kümenin varlık bazlı segmentlerine girerdi
      İkinci olarak, varlık bazlı MCU tabanlı yürütme platformunda genel amaçlı işletim sistemi varsayımlarını kaldırarak, gerçekten temin edilebilen donanım üzerinde insanların yazabileceği düşük seviyeli kodla daha hızlı geçiş mümkün olurdu. Üçüncüsü, kâr? Böyle bir yapıda genel amaçlı işletim sistemi tabanlı bir denetleyici, genel durumu izleyip gerektiğinde tekil öğeleri yeniden programlayarak stratejiyi durdurmalı veya değiştirmelidir
      Asıl mesele gerçek gecikme süresinin ne kadar düşük olduğudur. Bir noktadan sonra mühendisliktense donanımı çekirdeğe daha yakın konumlandırmanın maliyetini ödemek daha mantıklı olabilir gibi geliyor. Bu, ilgili borsa veya havuzun sunduğu kurallara, veri merkezine ve bağlantı altyapısına büyük ölçüde bağlı olacaktır
      Kârlı operasyonların önemli bir kısmı hangi havuza bağlandığını açıklamıyor olabilir; düzenlemeleri veya kullanım şartlarını umursamadan önden işlem yapmayı iş modeli haline getirmiş olma ihtimalleri de var. Böyle durumlarda iki yürütme noktası arasındaki göreli ağ coğrafyası gecikmesi, tek bir noktaya kadar olan mutlak gecikmeden daha güçlüdür
    • PGO yapılıyorsa ipucu öznitelikleri ters etki yaratmaz mı diye düşünüyorum
      Aslında derleyici tarafındaki kişilerin sıkça dile getirdiği genel kanı, PGO olmasa bile çoğu durumda bu tür ipuçlarının ters etki yarattığıdır. Modern derleyiciler bu ipuçlarındansa kendi analiz geçişlerine daha çok güvenir ve genellikle bunları yok sayar
      Bu arada gerçek kodda bu tür ipuçlarını yalnızca derleyicinin kolayca koyabileceği yerlerde gördüm. Örneğin malloc çağrısından sonraki null kontrolü gibi

  • Vurgulamak istediğim kısım şu
    “Bu testin çıktısı test istatistiği (t-statistic) ve ilgili p-value'dur. Skor olarak da adlandırılan t-statistic, artıklar üzerinde birim kök testi sonucudur. Daha negatif bir t-statistic, artıkların durağan olma olasılığının daha yüksek olduğunu gösterir. p-value, testin sıfır hipotezinin, yani eşbütünleşme olmadığı hipotezinin doğru olma olasılığına dair bir ölçü sağlar. Test sonucu yaklaşık 0.0149 p-value ve -3.7684 t-statistic verdi.”
    Bu kısmın LLM ile yazılmış gibi olduğunu düşünüyorum
    Örnek de gerçekten tuhaf. 5 yıl boyunca günde bir kez kapanış fiyatı korelasyonuna bakıyor, sonra 65 mikrosaniye gecikmeyle spread hesaplayan kod yazıyor. Gerçekten yapılacak bir iş olarak hiç mantıklı değil. İç döngüde spread istatistikleri de hesaplamazsınız; 65 mikrosaniye de iç döngü için çok yavaş
    Asıl amaç optimizasyon tekniklerini pratik etmek olabilir, ama optimizasyon hedefi olarak pek temsil edici değil

  • C++ ile LMAX Disruptor deseni kullanan bir borsa uygulaması yaptım
    https://github.com/sneilan/stock-exchange
    LMAX Disruptor’ın temel uygulamasını da birkaç C++ dosyasıyla hazırladım
    https://github.com/sneilan/lmax-disruptor-tutorial
    Ancak bunu Rust ile yeniden yapmayı düşünüyorum. Kendi WebSocket protokolümü, kimlik doğrulama sistemimi, SSL vb. uyguladığım noktaya kadar geldim; ama bellek yönetimi ve bağımlılıklar konusunda Rust’ın çok daha kolay olduğunu fark ettim. Özellikle tek kişilik bir yazılım projesiyse daha da öyle

    • Bu tür bir veri yapısını C++ ile düzgün yapmak kolay değil. Kuyruk uygulamasında birkaç sorun var
      Bellek erişimleri hem derleyici hem de CPU tarafından yeniden sıralanabileceği için, özgün LMAX Disruptor makalesinde açıklanan bariyerleri elde etmek adına üretici ve tüketici konumları için std::atomic kullanmak gerekir
      get metodunda tüketici konumu artırıldıktan, yani slot üreticiye serbest bırakıldıktan sonra kuyruk içindeki öğenin işaretçisi döndürülüyor. Bu yüzden kullanıcı erişirken üzerine yazılabilir
      Ayrıca üretici konumu ile tüketici konumunun aynı cache line’a düşme olasılığı yüksek, bu da false sharing yaratır
    • Böyle bir kod yerine
      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;
      şöyle yapılabilir
      uint64_t mask = slot_count - 1; // ikilikte tamamen 1
      item = &slots[ pos & mask ];
      pos ++;
      Yani bölme/modulo işlemini bit AND ile değiştirerek hesaplamayı biraz azaltabilirsiniz. Ancak ring buffer boyutu 2’nin kuvveti olmalı
      Daha da ileri gidip uint64_t gibi tam aralıklı sıra numaraları kullanılabilir. Wrap etme otomatik olarak halledilir. İki sıra numarasını çıkarmak da wrap durumunu dikkate alarak sorunsuz çalışır. Buffer’ın dolu mu boş mu olduğunu ayırt etmek için bir slotu boş bırakmak zorunda kalma gibi saçma sorun da ortadan kalkar
      Elbette “canlı” sıra numaraları penceresinin ring buffer pencere boyutunu asla aşmamasına dikkat etmek gerekir
    • Borsa koduna kısaca baktım
      Bellek yönetimini std::shared_ptr ile değiştirmeyi düşünmeye değer. Hızı düşürmeden bu kaygıyı tamamen ortadan kaldırır
      Soketler için, kendi yazdığınız koddan daha performanslı olan ve baş ağrıtan uç durumları da azaltan özgür açık kaynak kütüphaneler var. Örneğin FD_ISSET üzerinde dolaşma yöntemi epoll veya kqueue’dan daha yavaştır
      Bağımlılık yönetimi C++’ta diğer dillere göre kesinlikle daha pürüzlü. Hatta yönetmekten çok bulmak daha zor olabilir. Kullanılabilir kütüphane kodları orada burada dağınık duruyor; bazıları internetin unutulmuş köşelerinde saklı. Onları bulmak başlı başına bir beceri ve iyi yapıldığında büyük karşılığı var
    • LMAX Disruptor, thread’leri çekirdeklere sabitlediğinizde ve çoğu ya da tamamı çekişmesiz olduğunda harika bir veri yapısıdır. Bu desen olmazsa tail latency tarafında korkunç patolojik durumlar oluşur. Bir thread kötü bir zamanlamayla zamanlayıcıdan düşerse büyük darbe alırsınız
      Düşündüğünüz sistemde SPSC ring buffer’ı geçmek zor görünüyor; gerekirse eski usul kilitlerle iş çalma da uygulanabilir
    • İlginç bilgi: Asıl LMAX, Java için tasarlanmış ve Java ile yazılmıştı
      https://martinfowler.com/articles/lmax.html

  • Aklıma https://github.com/CppCon/CppCon2017/blob/master/Presentatio... geldi

    • Harika slaytlar
      Sahte bir sunucunun emir verilerini yeniden oynattığı, ikinci bir sunucunun çalışma süresini hesapladığı, test edilen sunucu ve donanım switch’iyle paket sürelerinin ölçüldüğü slayt gerçekten hoş bir şekilde hardcore
      Finans tarafında çalışmak istemem ama sırf kıyaslama için rack ölçeğinde donanım satın almanın ekonomik olarak mümkün olduğu ölçüde performans kritik sistemlerle uğraşmak eğlenceli olabilir

  • LMAX Disruptor’a birçok yönden benzeyen bir C++ logging kütüphanesi yaptım ve HFT topluluğunda da bir ölçüde kullanılıyor gibi görünüyor
    Asıl amacı, üretim ortamında olay sonrası hata ayıklama için performans düşüşü olmadan çok ayrıntılı log bırakılabilmesini sağlamaktı. Sorun çözmede önemli bilgileri log’a koymanın performansı etkileyebileceğinden korkup buna karşı çıkan iş arkadaşlarım vardı; bu kütüphane o tartışmayı bitirdi
    [1] https://github.com/mattiasflodin/reckless

  • Derleme zamanı dispatch’in bir başka avantajı, derleyicinin hangi fonksiyonun çağrıldığını statik olarak belirleyebildiğinde çağrılan fonksiyonun kodunu çağrı noktasına doğrudan inline edebilmesidir.
    Böylece fonksiyon çağrısı ek yükü tamamen ortadan kalkar; ölü kod eliminasyonu, sabit yayılımı gibi ek optimizasyonlar da mümkün olabilir.

    • Bildiğim kadarıyla hız artışının nedeni nadiren fonksiyon çağrısı ek yüküdür. Sonda söylendiği gibi asıl mesele, derleyici optimizasyonunun dinamik dallanmanın ötesini görüp göremediğidir.
      İyi bir JIT polimorfik inline etmeyi destekler. C++ konusundaki deneyimim biraz eski ama bu sorunun çözümü PGO idi. Ancak yaygın kullanılmıyor. Bunun yerine performansa duyarlı kodlarda dinamik dispatch’in kendisinden kaçınma eğilimi var.
      Daha genel ders şu: Hangi dil olursa olsun, kodun sıcak bölgelerinde, derleyicinin ya da JIT’in bunu içini görebildiğine dair güçlü bir güveniniz yoksa gereksiz dinamik dallanmalardan kaçının.
    • Gerçek performans yalnızca derleyici optimizasyonlarına değil, makinenin çalışma zamanı davranışına da bağlıdır. Bu konuda şu konuşma çok ilginçti:
      https://youtu.be/i5MAXAxp_Tw
    • Öte yandan sınır komut önbelleği ise gecikme açısından net zarar olabilir. Elbette erişim örüntülerine vb. bağlı.

  • Yüksek frekanslı alım satımın var olması için iyi bir neden var mı? İnsanlar Bitcoin’i enerji israf ettiği için sık sık eleştiriyor, ama bu da toplumsal açıdan açıkça net kayıp gibi görünüyor; nedense üstünden geçiliyor gibi.

    • Alış/satış spread’leri eskisine göre çok daha daraldı. HFT sektörünün tamamının kârına bakarsanız o kadar büyük değil; birkaç on milyar dolar düzeyinde, işlem hacmi ise trilyonlarca dolar.
      Bu sektörün inanılmaz derecede toplum yararına olduğunu söylemek zor, ama spread’leri daraltmanın aracılara giden parayı azalttığı doğru.
    • Sanırım açıkça yasaklanmadığı için.
      HFT oldukça yoğunlaşmış bir alan olsa da ölçek olarak küçük sayılır. Enerji israfı açısından Bitcoin’den birkaç mertebe daha küçük.
      HFT’nin tek olumlu etkisi likidite ve daha dar spread’ler; bu da insanların HFT’yi nasıl tanımladığına bağlı. Örneğin Robinhood ve ücretsiz işlem muhtemelen onsuz var olmazdı.
      Bunlar daha önce brokerlara ve bankalara giden payı alıyor. HFT “küçük yatırımcıyı” soyma işi değil.
      Benim açımdan toplum üzerindeki olumsuz etkisi ya yok ya da çok az. Uzun vadede borsaya yatırım yapan biriyseniz HFT’yi önemsemek için pek neden yok.
    • Warren Buffett, borsanın üç ayda bir gibi daha seyrek açılması gerektiğini önermişti. Bu, spekülasyon yerine uzun vadeli yatırımı teşvik edebilir.
      Zaten yüksek frekanslı alım satımı gerektiren doğal bir olay yok. Temel değerin çok hızlı değişmesi nadirdir; değişse bile bu oynaklıktan çok kesin bir geçişe yakındır.
    • Bitcoin dışındaki işlemler, birkaç veritabanına birkaç kayıt yazmaktan ibaret. Bitcoin madenciliği ise yoğun sayısal hesaplama işidir.
      HFT, tutarsızlıkları — örneğin üç döviz çiftinin birbirinden sapması ya da “bariz” yanlış fiyatlama gibi durumları — gidererek finansal piyasaları çok az daha doğru hale getirir.
    • Ne kadar araştırdığınızı ve hiç hisse alıp satıp satmadığınızı merak ediyorum.
      Bir şeyin işlemini yapmak istediğinizde karşı tarafta biri vardır. Genellikle istediğim fiyattan bir HFT katılımcısıyla işlem yapma olasılığım yüksektir. Daha iyi fiyat alırsam, o para bende kalan paradır.
      “Üstünden geçiliyor” ifadesine de katılmak zor. HFT burada da oldukça sık eleştiriliyor.

  • Profesyonel bir geliştiriciyseniz tamamını izlemeye değer.
    https://github.com/CppCon/CppCon2017/tree/master/Presentatio...
    Ve onun üst dizinini de.

  • Merak ettiğim bir şey var. Bu alanda mantık için neden C değil de C++ kullanılıyor ya da kullanılageldi? Bu alanda C++’ın C’ye göre avantajı nedir? C/assembly’ye hâkimim ama HFT pratiklerini hiç bilmiyorum; basitçe açıklarsanız sevinirim.

    • C++ C’den daha ifade gücü yüksek ve çok daha fazla soyutlamaya izin veriyor. Uzun süre C++ hem C düzeyinde performans hem de zengin soyutlamalar sunan tek ana akım dildi; bu yüzden HFT, oyun geliştirme, grafikler gibi karmaşık domain modelleme gerektiren alanlarda popüler oldu.
      Elbette bu ifade gücünün dilin muazzam karmaşıklığına değip değmediği tartışılabilir, ama pratikte insanlar deneyimle C++’ı seçti.

  • Bu yazının yapısı ve tonunda belirgin bir LLM kokusu var