Pola C++ untuk aplikasi latensi rendah termasuk high-frequency trading

 (arxiv.org)
1 poin oleh GN⁺ 2024-07-09 | 1 komentar | Bagikan ke WhatsApp
  • Di bidang seperti high-frequency trading (HFT), di mana latensi langsung menjadi daya saing, pengetahuan optimasi C++ yang masih minim di ruang publik dirangkum dengan fokus pada eksperimen dan implementasi
  • Hasilnya terbagi menjadi tiga: Low-Latency Programming Repository, optimasi strategi market-neutral pair trading, dan library pola Disruptor untuk C++
  • Benchmarking menilai kecepatan, pemanfaatan cache, dan signifikansi statistik secara bersamaan, dan Cache Warming serta Constexpr menunjukkan manfaat besar dalam mengurangi latensi
  • Strategi pair trading yang dioptimalkan meningkatkan kecepatan eksekusi dan profitabilitas, dan implementasi Disruptor menunjukkan performa yang lebih baik dibanding pendekatan queue tradisional
  • Pekerjaan selanjutnya mencakup perluasan repositori, pengujian di lingkungan trading nyata, dan benchmarking seluruh sistem setelah mengintegrasikan Disruptor dengan algoritme trading

Tujuan optimasi latensi rendah untuk HFT

  • Tujuannya adalah mengoptimalkan kode yang sensitif terhadap latensi untuk meningkatkan kecepatan eksekusi
  • Fokusnya diarahkan pada strategi pemrograman dan struktur data yang digunakan dalam high-frequency trading
  • Industri keuangan, khususnya perusahaan buy-side yang menangani pasar publik, tidak banyak membuka pengetahuan terkait karena alasan kerahasiaan dan keunggulan kompetitif
  • Untuk mengurangi kesenjangan ini, dibuat Low-Latency Programming Repository khusus yang memuat berbagai teknik dan divalidasi dengan benchmarking statistik

Tiga hasil utama

  • Low-Latency Programming Repository

    • Bukan sekadar kumpulan teori, tetapi juga berfungsi sebagai panduan praktis yang mencakup benchmarking statistik
    • Mengkurasi teknik pemrograman, design pattern, dan best practice untuk mengurangi latensi pada sistem HFT

  • Optimasi strategi statistical arbitrage pair trading yang market-neutral

    • Mengintegrasikan teknik pengurangan latensi dan optimasi tingkat CPU
    • Menunjukkan peningkatan pada kecepatan eksekusi dan profitabilitas

  • Library pola Disruptor untuk C++

    • Menunjukkan peningkatan performa dibanding pendekatan queue tradisional
    • Menunjukkan bahwa struktur data semacam ini dapat diterapkan pada Order Management System (OMS) di sistem HFT

Alasan minimnya pengetahuan publik

  • Pengetahuan optimasi sistem HFT terutama berasal dari praktisi industri, tetapi karena kerahasiaan dan keunggulan kompetitif, riset terbaru serta detail implementasi sulit dipublikasikan
  • Area seperti peningkatan latensi, efisiensi kode, dan optimasi cache sangat terbatas materi publiknya
  • Memang ada riset HFT dari sudut pandang ekonomi dan keuangan serta model matematika untuk algorithmic trading, tetapi jarang yang membahas hingga detail teknis optimasi kode atau pengurangan latensi
  • Literatur terkait C++ relatif banyak, tetapi yang terhubung langsung dengan konteks sistem HFT ultra-low-latency tetap terbatas
  • Blog dan posting online sering hanya menyajikan data latensi rata-rata secara permukaan, dan kurang menganalisis secara rinci perilaku akses cache atau latensi eksekusi instruksi

Evaluasi dan peningkatan performa

  • Metrik evaluasi mencakup kecepatan, pemanfaatan cache, dan signifikansi statistik
  • Di antara teknik dalam Low-Latency Programming Repository, Cache Warming dan Constexpr memberikan manfaat terbesar dalam pengurangan latensi
  • Implementasi pola Disruptor memanfaatkan ring buffer, sequence number, dan strategi waiting khusus untuk menghasilkan performa yang lebih baik dalam latensi dan kecepatan dibanding pendekatan queue tradisional
  • Strategi market-neutral pair trading mengalami peningkatan kecepatan eksekusi dan profitabilitas melalui optimasi tingkat CPU dan teknik pengurangan latensi

Repositori publik dan pekerjaan lanjutan

  • Repositori, strategi trading, dan library Disruptor tersedia di https://github.com/0burak/imperial hft
  • Pekerjaan selanjutnya mencakup perluasan repositori
  • Masih ada tugas untuk menguji algoritme trading yang telah dioptimalkan di lingkungan trading nyata
  • Arah berikutnya juga mencakup integrasi pola Disruptor dengan algoritme trading untuk melakukan benchmarking pada tingkat keseluruhan sistem

Bacaan terkait

1 komentar

 
GN⁺ 2024-07-09
Komentar Hacker News

  • Tulisan ini tampaknya pengantar yang cukup mendasar tentang topiknya
    Dari pengalaman saya mengajar mahasiswa sarjana, para mahasiswa pun umumnya sudah mengetahui hal-hal seperti ini. Di kelas arsitektur komputer, mereka mempelajari unsur-unsur dasar performa seperti branch prediction, koherensi cache, dan instruction cache
    Agak mengejutkan bahwa faktor klasik penurunan performa, false sharing, sama sekali tidak dibahas, dan tampaknya fokusnya terutama pada latensi single-thread. Saya juga terkejut optimisasi “gratis” seperti fat LTO, PGO, [[likely]], [[unlikely]] tidak disertakan
    Masalah performa yang lebih dalam perlu masuk sampai ke API input/output tertentu, primitive sinkronisasi, komunikasi antarproses, dan cara memakai compiler intrinsic yang rumit
    Hal yang paling kurang dimiliki dan paling sulit diajarkan kepada programmer latensi rendah adalah semacam paranoia. Mereka perlu benar-benar takut dan marah terhadap alokasi, penyalinan, dan faktor penurun performa yang tidak perlu. Ini seperti naluri untuk secara obsesif menjalankan benchmark dengan callgrind demi menemukan panggilan ke allocator akibat object cache miss di tengah hot loop
    Secara pribadi, saat membuat server latensi rendah, momen penting bagi saya adalah ketika menyadari bahwa alih-alih menyusun operasi vectored I/O, menyalin objek-objek kecil ke buffer kontigu lalu melakukan satu write secara keseluruhan lebih cepat. Tidak ada penyalinan yang gratis, dan fat pointer pun bukan pengecualian

    • Bisa jadi, tetapi C++ latensi rendah adalah bidang tersendiri dan informasinya nyaris seperti gurun
      Materi terbaik yang tersedia saat ini pun hanya beberapa presentasi konferensi C++, dan banyak yang terasa kurang memuaskan
      Jika kita kesampingkan godaan untuk pamer, dokumen ini merupakan kontribusi yang sangat bagus untuk bidang ini dan mungkin bisa menjadi referensi otoritatif pertama. Pernyataan samar bahwa informasi serupa bisa dirangkai dari kuliah lain bukanlah kontribusi, dan tidak membantu siapa pun
    • Untung sekarang saya tidak lagi melakukan pekerjaan seperti itu, tetapi paranoia yang sesungguhnya ada pada ketidakpercayaan ala Heisenberg. Sulit menghilangkan kecurigaan bahwa program berperilaku berbeda saat sedang diukur dan saat tidak diukur
    • Saya penasaran apakah ada literatur yang secara umum bisa direkomendasikan
    • Kalau saya, mungkin akan mendekatinya seperti ini. Saya ingin mendengar masukan dari orang-orang yang lebih dekat dengan bidang ini
      Pertama, demi kecepatan mentah, gunakan FPGA front-end untuk membagi beban menjadi stream data sederhana per aset. Namun karena gesekan dalam pengembangan iteratif, SDM, rantai pasok, dan sebagainya terlalu besar, hindari godaan untuk benar-benar melakukan eksekusi di sini. Inputnya semacam stream FIX, dan outputnya dibagi di sepanjang bus latensi rendah menjadi stream event biner per aset, lalu masuk ke segmen per aset dari klaster yang dapat diperluas yang tersusun dari MCU murah
      Kedua, pada platform eksekusi berbasis MCU per aset, hilangkan asumsi sistem operasi umum, sehingga memungkinkan transisi yang lebih cepat dengan kode level rendah yang bisa ditulis orang di atas hardware yang benar-benar tersedia. Ketiga, profit? Dalam struktur seperti ini, supervisor berbasis sistem operasi umum harus memantau keadaan keseluruhan dan, bila perlu, memprogram ulang elemen individual untuk menghentikan atau mengubah strategi
      Yang menentukan adalah seberapa rendah latensi sebenarnya. Pada titik tertentu, rasanya lebih baik membayar biaya untuk menempatkan hardware lebih dekat ke core daripada terus mengandalkan rekayasa. Ini akan sangat bergantung pada aturan, data center, dan infrastruktur link yang disediakan oleh bursa atau pool tersebut
      Tampaknya cukup banyak operasi yang menguntungkan tidak mengungkapkan pool mana yang mereka hubungkan, dan mungkin menjadikan front-running sebagai bisnis sambil mengabaikan regulasi atau ketentuan layanan. Dalam kasus seperti itu, latensi geografis jaringan relatif antara dua titik eksekusi lebih kuat daripada latensi absolut ke satu titik
    • Jika memakai PGO, bukankah atribut hint justru bisa kontraproduktif?
      Seingat saya, pengetahuan umum yang sering dikatakan orang-orang compiler adalah bahwa dalam sebagian besar kasus, hint seperti ini kontraproduktif bahkan tanpa PGO. Compiler modern lebih mempercayai pass analisis mereka sendiri daripada hint seperti ini dan biasanya mengabaikannya
      Sebagai catatan, di kode nyata saya hanya pernah melihat hint semacam ini di tempat yang mudah disisipkan compiler. Misalnya pemeriksaan null setelah pemanggilan malloc

  • Bagian yang ingin saya soroti adalah ini
    “Output dari pengujian ini adalah statistik uji (t-statistic) dan p-value terkait. t-statistic, yang juga disebut skor, adalah hasil uji unit root terhadap residual. t-statistic yang lebih negatif menunjukkan bahwa residual lebih mungkin stasioner. p-value memberikan ukuran probabilitas bahwa hipotesis nol pengujian, yaitu hipotesis tidak adanya kointegrasi, adalah benar. Hasil pengujian menghasilkan p-value sekitar 0,0149 dan t-statistic -3,7684.”
    Bagian ini sepertinya ditulis dengan LLM
    Contohnya juga benar-benar aneh. Setelah melihat korelasi harga penutupan sekali sehari selama 5 tahun, mereka menulis kode yang menghitung spread dengan latensi 65 mikrodetik. Itu tidak masuk akal sebagai sesuatu yang benar-benar akan dilakukan. Orang juga tidak akan menghitung statistik spread di inner loop, dan 65 mikrodetik terlalu lambat untuk inner loop
    Intinya mungkin untuk melatih teknik optimisasi, tetapi sebagai target optimisasi, ini kurang representatif

  • Saya membuat implementasi bursa saham yang menggunakan pola LMAX Disruptor di C++
    https://github.com/sneilan/stock-exchange
    Implementasi dasar LMAX Disruptor juga sudah saya buat dalam beberapa file C++
    https://github.com/sneilan/lmax-disruptor-tutorial
    Namun saya sedang mempertimbangkan untuk membuat ulang ini dengan Rust. Saya sudah sampai pada titik mengimplementasikan protokol WebSocket sendiri, sistem autentikasi, SSL, dan sebagainya, lalu menyadari bahwa manajemen memori dan dependensi jauh lebih mudah di Rust. Terutama jika ini proyek perangkat lunak satu orang

    • Tidak mudah membuat struktur data seperti ini dengan benar di C++. Ada beberapa masalah dalam implementasi queue
      Akses memori dapat di-reorder baik oleh compiler maupun CPU, jadi untuk mendapatkan barrier yang dijelaskan dalam paper LMAX Disruptor asli, posisi producer dan consumer harus menggunakan std::atomic
      Dalam metode get, posisi consumer dinaikkan terlebih dahulu, yaitu slot dilepaskan ke producer, lalu pointer ke elemen internal queue dikembalikan. Akibatnya, elemen itu bisa ditimpa saat pengguna masih mengaksesnya
      Selain itu, posisi producer dan posisi consumer kemungkinan besar berada di cache line yang sama, sehingga terjadi false sharing
    • Alih-alih kode seperti ini
      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;
      Anda bisa melakukannya seperti ini
      uint64_t mask = slot_count - 1; // semua 1 dalam biner
      item = &slots[ pos & mask ];
      pos ++;
      Dengan kata lain, pembagian/modulo bisa diganti dengan bitwise AND untuk sedikit mengurangi perhitungan. Namun, ukuran ring buffer harus berupa pangkat dua
      Lebih jauh lagi, Anda bisa memakai nomor sekuens dengan rentang penuh seperti uint64_t. Wrapping akan ditangani secara otomatis. Mengurangkan dua nomor sekuens juga bekerja tanpa masalah dengan memperhitungkan wrapping. Masalah konyol harus mengosongkan satu slot untuk membedakan apakah buffer penuh atau kosong juga hilang
      Tentu saja, harus berhati-hati agar jendela nomor sekuens yang “aktif” tidak pernah melebihi ukuran jendela ring buffer
    • Saya sempat melihat kode bursa sahamnya
      Untuk manajemen memori, layak mempertimbangkan menggantinya dengan std::shared_ptr. Itu menghilangkan kekhawatiran tersebut sepenuhnya tanpa memperlambat kinerja
      Untuk socket, ada pustaka bebas dan open source yang performanya lebih baik daripada kode buatan sendiri serta mengurangi berbagai kasus khusus yang merepotkan. Misalnya, cara mengiterasi FD_ISSET lebih lambat daripada epoll atau kqueue
      Manajemen dependensi di C++ jelas lebih kasar dibanding bahasa lain. Bahkan menemukan dependensi lebih sulit daripada mengelolanya. Kode pustaka yang layak pakai tersebar di mana-mana, dan sebagian bersembunyi di sudut internet yang terlupakan. Menemukannya sendiri adalah sebuah keterampilan, dan jika dilakukan dengan baik, imbalannya besar
    • LMAX Disruptor adalah struktur data yang luar biasa ketika thread dipatok ke core dan sebagian besar atau semuanya tidak saling berebut. Jika bukan pola ini, akan muncul patologi buruk pada tail latency. Jika thread dikeluarkan dari jadwal pada timing yang buruk, dampaknya bisa besar
      Untuk sistem yang sedang dipikirkan, sepertinya sulit mengalahkan ring buffer SPSC, dan jika diperlukan, work stealing juga bisa diimplementasikan dengan lock gaya lama
    • Fakta menarik: LMAX awalnya dirancang untuk Java dan ditulis dalam Java
      https://martinfowler.com/articles/lmax.html

  • Saya teringat https://github.com/CppCon/CppCon2017/blob/master/Presentatio...

    • Slide yang sangat bagus
      Slide tentang server palsu yang memutar ulang data order, server kedua yang menghitung waktu eksekusi, serta pengukuran waktu paket dengan server yang diuji dan hardware switch benar-benar hardcore dengan cara yang menyenangkan
      Saya tidak punya keinginan bekerja di bidang finansial, tetapi sepertinya menarik menangani sistem yang performanya begitu kritis sampai secara ekonomi masuk akal untuk membeli hardware berskala rak hanya untuk benchmarking

  • Saya membuat pustaka logging C++ yang punya banyak kemiripan dengan LMAX Disruptor, dan tampaknya juga digunakan sampai batas tertentu di komunitas HFT
    Tujuan awalnya adalah memungkinkan pencatatan log yang sangat mendetail di lingkungan produksi untuk debugging pascakejadian tanpa penurunan performa. Ada rekan kerja yang menolak memasukkan informasi penting untuk pemecahan masalah ke log karena khawatir akan berdampak pada performa, dan pustaka ini mengakhiri perdebatan itu
    [1] https://github.com/mattiasflodin/reckless

  • Keuntungan lain dari dispatch pada waktu kompilasi adalah, ketika compiler dapat menentukan secara statis fungsi mana yang dipanggil, kode fungsi yang dipanggil bisa langsung di-inline di titik pemanggilan
    Dengan begitu semua overhead pemanggilan fungsi bisa dihilangkan, dan optimisasi tambahan seperti dead code elimination serta constant propagation juga bisa dimungkinkan

    • Sejauh yang saya tahu, penyebab peningkatan kecepatan hampir tidak pernah karena overhead pemanggilan fungsi. Seperti disebutkan di bagian akhir, kuncinya adalah apakah optimisasi compiler bisa melihat melampaui percabangan dinamis
      JIT yang bagus mendukung inline polimorfik. Pengalaman saya dengan C++ memang agak lama, tetapi solusi untuk masalah ini dulu adalah PGO. Namun itu tidak banyak digunakan. Sebagai gantinya, pada kode yang sensitif terhadap performa, orang cenderung menghindari dynamic dispatch itu sendiri
      Pelajaran yang lebih umum adalah, dalam bahasa apa pun, pada bagian kode yang panas, hindari percabangan dinamis yang tidak perlu kecuali Anda sangat yakin compiler atau JIT dapat menembusnya
    • Performa nyata tidak hanya bergantung pada optimisasi compiler, tetapi juga pada perilaku runtime mesin. Ceramah ini sangat menarik terkait topik tersebut
      https://youtu.be/i5MAXAxp_Tw
    • Sebaliknya, jika instruction cache menjadi batasnya, dari sisi latensi ini bisa menjadi kerugian bersih. Tentu saja tergantung pada pola akses dan sebagainya

  • Apakah ada alasan bagus mengapa perdagangan frekuensi tinggi harus ada? Orang sering mengkritik Bitcoin karena membuang energi, tetapi ini juga tampaknya jelas merupakan kerugian bersih secara sosial, namun anehnya seolah dibiarkan saja

    • Spread bid/ask sudah jauh lebih sempit dibanding dulu. Jika melihat keuntungan seluruh industri HFT, angkanya tidak sebesar itu, hanya di kisaran miliaran dolar, sementara nilai transaksinya triliunan dolar
      Sulit mengatakan industri ini sangat prososial, tetapi benar bahwa mempersempit spread berarti mengurangi uang yang masuk ke perantara
    • Mungkin karena tidak dilarang secara eksplisit
      HFT memang area yang cukup terkonsentrasi, tetapi skalanya sendiri relatif kecil. Dari sisi pemborosan energi, skalanya beberapa orde besaran lebih kecil daripada Bitcoin
      Satu-satunya efek positif HFT adalah likuiditas dan spread yang lebih sempit, meski itu juga bergantung pada bagaimana orang mendefinisikan HFT. Misalnya, Robinhood dan perdagangan gratis mungkin tidak akan ada tanpa ini
      Mereka mengambil bagian yang sebelumnya masuk ke broker dan bank. HFT bukan bisnis yang memeras “investor ritel”
      Dari sudut pandang saya, dampak negatifnya terhadap masyarakat hampir tidak ada atau tidak ada sama sekali. Jika Anda berinvestasi di pasar saham untuk jangka panjang, hampir tidak ada alasan untuk memedulikan HFT
    • Warren Buffett pernah mengusulkan agar pasar saham dibuka lebih jarang, misalnya sekali per kuartal. Dengan begitu, investasi jangka panjang bisa didorong, bukan spekulasi
      Bagaimanapun, tidak ada peristiwa alamiah yang membutuhkan perdagangan frekuensi tinggi. Nilai fundamental jarang berubah sangat cepat, dan kalaupun berubah, itu lebih mendekati transisi yang pasti daripada volatilitas
    • Perdagangan non-Bitcoin hanyalah menulis beberapa entri ke sejumlah database. Penambangan Bitcoin adalah pekerjaan komputasi numerik yang berat
      HFT membuat pasar keuangan sedikit lebih akurat dengan menyelesaikan ketidaksesuaian, misalnya ketika tiga pasangan mata uang saling tidak selaras, atau mengoreksi harga yang “jelas” salah
    • Saya penasaran sejauh mana Anda sudah mencari tahu, dan apakah Anda pernah membeli atau menjual saham
      Saat Anda mencoba memperdagangkan sesuatu, ada seseorang di sisi lain. Biasanya besar kemungkinan Anda akan bertransaksi dengan pelaku HFT pada harga yang Anda inginkan. Jika Anda mendapat harga yang lebih baik, uang itu adalah uang yang Anda pertahankan
      Saya juga sulit setuju dengan ungkapan “dibiarkan saja”. HFT juga cukup sering dikritik di sini

  • Jika Anda pengembang profesional, keseluruhannya layak ditonton
    https://github.com/CppCon/CppCon2017/tree/master/Presentatio...
    Dan juga direktori induknya

  • Ada yang membuat saya penasaran. Di bidang ini, mengapa logikanya menggunakan atau selama ini menggunakan C++, bukan C? Apa keunggulan C++ dibanding C di area ini? Saya cukup mahir C/assembly, tetapi sama sekali tidak tahu praktik HFT, jadi akan bagus kalau ada yang bisa menjelaskannya dengan sederhana

    • C++ lebih ekspresif daripada C dan memungkinkan jauh lebih banyak abstraksi. Untuk waktu yang lama, C++ adalah satu-satunya bahasa arus utama yang menyediakan performa setingkat C sekaligus abstraksi yang kaya, sehingga menjadi populer di bidang yang membutuhkan pemodelan domain kompleks seperti HFT, pengembangan gim, dan grafis
      Tentu saja bisa diperdebatkan apakah ekspresivitas semacam ini sepadan dengan kompleksitas bahasa yang luar biasa besar, tetapi dalam praktiknya orang-orang secara empiris memilih C++

  • Dari struktur dan nada tulisan ini, bau LLM terasa kuat