HFT सहित low-latency applications के लिए C++ patterns

 (arxiv.org)
1 पॉइंट द्वारा GN⁺ 2024-07-09 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • High-frequency trading (HFT) जैसे क्षेत्रों में, जहाँ latency ही प्रतिस्पर्धात्मक बढ़त होती है, सार्वजनिक रूप से कम उपलब्ध C++ optimization ज्ञान को प्रयोग और implementation-केंद्रित रूप में व्यवस्थित किया गया है
  • परिणाम तीन हिस्सों में बँटा है: Low-Latency Programming Repository, market-neutral pair trading strategy optimization, और C++ Disruptor pattern library
  • Benchmarking में speed, cache utilization, और statistical significance को साथ देखा गया, और Cache Warming तथा Constexpr ने latency कम करने में बड़ा लाभ दिखाया
  • Optimized pair trading strategy में execution speed और profitability बेहतर हुई, और Disruptor implementation ने पारंपरिक queue-based तरीकों से बेहतर performance दिखाया
  • आगे के काम में repository expansion, वास्तविक trading environment में testing, और Disruptor को trading algorithm के साथ integrate करने के बाद पूरे system का benchmarking शामिल है

HFT low-latency optimization का लक्ष्य

  • लक्ष्य latency-sensitive code को optimize करके execution speed बढ़ाना है
  • फोकस high-frequency trading में इस्तेमाल होने वाली programming strategies और data structures पर है
  • वित्तीय उद्योग, खासकर public markets को संभालने वाली buy-side firms, गोपनीयता और प्रतिस्पर्धात्मक बढ़त के कारण इस विषय का ज्ञान ज़्यादा सार्वजनिक नहीं करतीं
  • इस कमी को कम करने के लिए विभिन्न techniques वाला एक custom Low-Latency Programming Repository बनाया गया और statistical benchmarking से उसकी पुष्टि की गई

तीन परिणाम

  • Low-Latency Programming Repository

    • यह केवल theory collection नहीं है, बल्कि statistical benchmarking के साथ एक practical guide की तरह काम करता है
    • यह HFT systems में latency घटाने के लिए programming techniques, design patterns, और best practices को curate करता है

  • Market-neutral statistical arbitrage pair trading strategy optimization

    • इसमें latency reduction techniques और CPU-level optimization को integrate किया गया है
    • इससे execution speed और profitability में सुधार दिखा

  • C++ Disruptor pattern library

    • इसने पारंपरिक queue-based तरीकों की तुलना में performance improvement दिखाया
    • यह दिखाता है कि HFT systems के Order Management System(OMS) में ऐसे data structures लागू किए जा सकते हैं

सार्वजनिक ज्ञान कम होने के कारण

  • HFT system optimization का ज्ञान मुख्य रूप से industry practitioners से आता है, लेकिन गोपनीयता और प्रतिस्पर्धात्मक बढ़त के कारण नवीनतम research और implementation details को सार्वजनिक करना कठिन होता है
  • latency improvement, code efficiency, और cache optimization जैसे क्षेत्रों में सार्वजनिक सामग्री विशेष रूप से सीमित है
  • HFT पर आर्थिक और वित्तीय दृष्टिकोण से research, और algorithmic trading के mathematical models पर काम मौजूद है, लेकिन code optimization या latency reduction की विस्तृत तकनीकों तक पहुँचना दुर्लभ है
  • C++ से जुड़ा साहित्य अपेक्षाकृत अधिक है, फिर भी उसे ultra-low-latency HFT systems के संदर्भ से सीधे जोड़ने वाले स्रोत सीमित हैं
  • online blogs और posts अक्सर average latency data को सतही तौर पर देते हैं, लेकिन cache access या instruction execution latency के सूक्ष्म व्यवहार का विश्लेषण कम मिलता है

मूल्यांकन और performance improvement

  • evaluation metrics में speed, cache utilization, और statistical significance आदि शामिल हैं
  • Low-Latency Programming Repository की techniques में Cache Warming और Constexpr ने latency reduction में सबसे बड़ा लाभ दिया
  • Disruptor pattern implementation ने ring buffer, sequence numbers, और विशेष wait strategies का उपयोग करके पारंपरिक queue-based तरीकों की तुलना में latency और speed दोनों में बेहतर performance दी
  • market-neutral pair trading strategy ने CPU-level optimization और latency reduction techniques के जरिए execution speed और profitability में सुधार किया

सार्वजनिक repository और आगे का काम

  • repository, trading strategy, और Disruptor library https://github.com/0burak/imperial hft पर उपलब्ध हैं
  • आगे के काम में repository expansion शामिल है
  • optimized trading algorithm को वास्तविक trading environment में test करना अभी बाकी है
  • इसमें Disruptor pattern को trading algorithm के साथ integrate करके पूरे system level पर benchmarking करना भी शामिल है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-07-09
Hacker News की टिप्पणियाँ

  • यह लेख विषय का काफ़ी बुनियादी परिचय लगता है
    स्नातक छात्रों को पढ़ाने के मेरे अनुभव में, छात्र भी आम तौर पर यह सब पहले से जानते हैं। Computer architecture की कक्षाओं में वे performance के बुनियादी तत्व जैसे branch prediction, cache coherence, और instruction cache सीखते हैं
    performance खराब होने के एक क्लासिक कारण false sharing को बिल्कुल न छूना हैरान करने वाला था, और ऐसा लगा कि ध्यान मुख्य रूप से single-thread latency पर था। fat LTO, PGO, [[likely]], [[unlikely]] जैसे “मुफ़्त” optimization hints भी गायब थे, यह भी चौंकाने वाला था
    performance की और गहरी समस्याओं में specific I/O API, synchronization primitives, inter-process communication, और पेचीदा compiler built-ins का इस्तेमाल कैसे किया जाता है, यह सब शामिल होना चाहिए
    low-latency programmer के लिए सबसे कम मिलने वाली और सिखाने में सबसे कठिन चीज़ एक तरह की paranoia है। बेकार allocations, copies, और performance regressions के प्रति असली डर और गुस्सा होना चाहिए। hot loop के बीचोंबीच object cache miss होकर allocator तक जाने वाली call को ढूँढने के लिए callgrind के साथ benchmark को जुनून की हद तक चलाते रहने वाली संवेदना
    व्यक्तिगत रूप से, low-latency server बनाते समय मेरे लिए एक अहम पल वह था जब समझ आया कि vector I/O operations तैयार करने की बजाय, छोटे objects को एक contiguous buffer में copy करके एक ही write करना कुल मिलाकर ज़्यादा तेज़ था। कोई copy मुफ़्त नहीं होती, और fat pointer भी इसका अपवाद नहीं है

    • ऐसा हो सकता है, लेकिन low-latency C++ अपने आप में एक स्वतंत्र क्षेत्र है और इसके बारे में जानकारी लगभग रेगिस्तान जैसी दुर्लभ है
      इस समय जो सबसे अच्छे resources मिलते हैं, वे बस कुछ C++ conference talks हैं, और वे भी काफ़ी अधूरे लगे
      दिखावा करने की इच्छा को अलग रखकर देखें तो, यह दस्तावेज़ इस क्षेत्र के लिए एक शानदार योगदान है और शायद पहला authoritative reference भी हो सकता है। यह कहना कि ऐसी जानकारी किसी और lecture से जोड़-तोड़कर निकाली जा सकती है, कोई योगदान नहीं है और किसी की मदद नहीं करता
    • अब मैं ऐसा काम नहीं करता, यह राहत की बात है, लेकिन असली paranoia तो Heisenberg-जैसे अविश्वास में होती है। यह शक दिमाग़ से निकलता ही नहीं कि कहीं program measurement के दौरान और बिना measurement के अलग तरह से तो व्यवहार नहीं कर रहा
    • जानना चाहूँगा कि क्या आम तौर पर recommend करने लायक कोई literature है
    • मैं शायद इसे इस तरह approach करता। इस क्षेत्र के ज़्यादा क़रीब लोगों की feedback जानना चाहूँगा
      पहले, raw speed के लिए front-end FPGA से load को साधारण asset-wise data streams में बाँटता। लेकिन iterative development, staffing, supply chain जैसी friction बहुत ज़्यादा है, इसलिए यहीं से actual execution तक जाने के प्रलोभन से बचता। input कोई FIX stream जैसी चीज़ होगी, और output low-latency bus के साथ asset-wise binary event streams में बँटकर low-cost MCU से बने scalable cluster के asset-specific segments में जाएगा
      दूसरे, asset-specific MCU-based execution platform पर general-purpose OS की धारणाएँ हटा दी जाएँ, ताकि वास्तव में उपलब्ध hardware पर लोग जो low-level code लिख सकें उससे तेज़ transition संभव हो। तीसरा, profit? ऐसी architecture में general-purpose OS-आधारित supervisor को global state monitor करनी होगी और ज़रूरत पड़ने पर individual elements को reprogram करके strategy को रोकना या बदलना होगा
      असली सवाल यह है कि वास्तविक latency कितनी नीचे लाई जा सकती है। एक बिंदु के बाद शायद engineering की जगह hardware को core के और क़रीब रखने की लागत चुकाना ज़्यादा सही हो। यह बहुत हद तक उस exchange या pool के rules, data center, और link infrastructure पर निर्भर करेगा
      काफ़ी से profitable operations यह भी नहीं बताते कि वे किस pool से जुड़े हैं, और संभव है कि वे regulation या terms को नज़रअंदाज़ करके front-running को business बना रहे हों। ऐसे मामलों में दो execution points के बीच की relative network-geographic latency, किसी एक point तक की absolute latency से भी ज़्यादा ताकतवर होती है
    • अगर PGO किया जा रहा है, तो क्या hint attributes उल्टा नुकसान नहीं करेंगे?
      दरअसल compiler पक्ष के लोग अक्सर जो conventional wisdom बताते हैं, वह यही है कि PGO न भी हो तो ज़्यादातर मामलों में ऐसे hints उल्टा असर करते हैं। modern compilers ऐसे hints से ज़्यादा अपनी analysis passes पर भरोसा करते हैं और आम तौर पर इन्हें नज़रअंदाज़ कर देते हैं
      वैसे, मैंने वास्तविक code में ऐसे hints सिर्फ वहीं देखे हैं जहाँ compiler उन्हें आसानी से डाल सकता है। उदाहरण के लिए malloc call के बाद null check जैसी जगहों पर

  • मैं जिस हिस्से पर ज़ोर देना चाहता हूँ, वह यह है
    “इस test का output test statistic (t-statistic) और संबंधित p-value है। t-statistic, जिसे score भी कहा जाता है, residuals पर unit root test का परिणाम है। ज़्यादा negative t-statistic यह संकेत देता है कि residuals के stationary होने की संभावना अधिक है। p-value test की null hypothesis, यानी cointegration न होने की परिकल्पना, के true होने की संभावना का माप देती है। test result ने लगभग 0.0149 का p-value और -3.7684 का t-statistic दिया।”
    यह हिस्सा LLM से लिखा हुआ लगता है
    उदाहरण भी सचमुच अजीब है। 5 साल तक रोज़ाना एक बार के closing-price correlation को देखकर, फिर 65 microsecond latency पर spread निकालने वाला code लिखना। यह किसी असली काम जैसा नहीं लगता। न तो कोई inner loop में spread statistics निकालेगा, और 65 microsecond inner loop के हिसाब से बहुत धीमा है
    बात शायद optimization techniques की practice कराने की हो, लेकिन optimization target के रूप में यह काफ़ी कम representative है

  • C++ में LMAX Disruptor पैटर्न का इस्तेमाल करके एक stock exchange implementation बनाया था
    https://github.com/sneilan/stock-exchange
    LMAX Disruptor का एक basic implementation भी कुछ C++ files में बनाया हुआ है
    https://github.com/sneilan/lmax-disruptor-tutorial
    लेकिन अब इसे Rust में फिर से बनाने का सोच रहा हूँ। custom websocket protocol, authentication system, SSL वगैरह implement करने तक पहुँच चुका था, लेकिन तब समझ आया कि memory management और dependencies के मामले में Rust बहुत आसान है। खासकर अगर यह one-person software project हो तो और भी ज़्यादा

    • ऐसी data structures को C++ में ठीक से बनाना आसान नहीं है। queue implementation में कुछ समस्याएँ हैं
      memory access को compiler और CPU दोनों तरफ से reorder किया जा सकता है, इसलिए मूल LMAX Disruptor paper में बताए गए barrier पाने के लिए producer और consumer positions पर std::atomic का इस्तेमाल करना चाहिए
      get method में consumer position बढ़ाने के बाद, यानी producer के लिए slot खाली करने के बाद, queue के अंदर के element का pointer लौटाया जा रहा है। इसलिए user के access करते समय वह overwrite हो सकता है
      और producer position और consumer position के एक ही cache line में आने की संभावना ज़्यादा है, जिससे false sharing होता है
    • ऐसे code के बजाय
      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;
      ऐसा किया जा सकता है
      uint64_t mask = slot_count - 1; // बाइनरी में सभी 1
      item = &slots[ pos & mask ];
      pos ++;
      यानी division/modulo को bitwise AND से बदलकर computation थोड़ा कम किया जा सकता है। लेकिन ring buffer का size 2 की power होना चाहिए
      इससे आगे uint64_t जैसी full-range sequence numbers का इस्तेमाल भी किया जा सकता है। wrapping अपने-आप संभल जाता है। दो sequence numbers को subtract करने पर भी wrapping को ध्यान में रखते हुए बिना समस्या काम करता है। buffer भरा है या खाली, यह अलग करने के लिए एक slot खाली छोड़ने जैसी बेवकूफी भी नहीं करनी पड़ती
      हाँ, यह ज़रूर ध्यान रखना होगा कि “live” sequence numbers की window कभी भी ring buffer window size से ज़्यादा न हो
    • stock exchange code को थोड़ी देर देखा
      memory management के लिए std::shared_ptr में बदलने पर विचार किया जा सकता है। इससे speed धीमी किए बिना वह चिंता पूरी तरह खत्म हो जाती है
      sockets के लिए self-written code से बेहतर performance देने वाली और परेशान करने वाले edge cases कम करने वाली free open source libraries मौजूद हैं। उदाहरण के लिए FD_ISSET को iterate करने का तरीका epoll या kqueue से धीमा है
      dependency management में C++ सचमुच दूसरी भाषाओं की तुलना में ज़्यादा rough है। manage करने से भी ज़्यादा मुश्किल उन्हें ढूँढना होता है। काम की library code इधर-उधर बिखरी हुई है, और कुछ तो इंटरनेट के भूले-बिसरे कोनों में छिपी होती हैं। उन्हें ढूँढ निकालना अपने-आप में एक skill है, और अगर ठीक से कर लिया जाए तो बड़ा reward मिलता है
    • LMAX Disruptor एक शानदार data structure है जब threads को cores पर pin किया गया हो और ज़्यादातर या पूरी तरह contention न हो। अगर यह pattern न हो, तो tail latency में भयानक pathology पैदा होती है। अगर thread बुरे timing पर scheduler से बाहर हो जाए तो बड़ा नुकसान होता है
      जिस system के बारे में सोच रहा हूँ, उसमें SPSC ring buffer को हराना मुश्किल होगा, और अगर ज़रूरत पड़ी तो पुराने ढंग के locks के साथ work stealing भी implement किया जा सकता है
    • मज़ेदार बात: मूल LMAX को Java के लिए design किया गया था और Java में ही लिखा गया था
      https://martinfowler.com/articles/lmax.html

  • https://github.com/CppCon/CppCon2017/blob/master/Presentatio... याद आ गया

    • शानदार slides हैं
      वह slides, जिनमें fake server order data replay करता है, दूसरा server execution time calculate करता है, और test target server तथा hardware switch के जरिए packet timing मापी जाती है, सच में सुखद रूप से hardcore हैं
      finance में काम करने का खास मन नहीं है, लेकिन ऐसी performance-critical systems पर काम करना मज़ेदार लगता है जहाँ rack-scale hardware सिर्फ benchmarking के लिए खरीदना आर्थिक रूप से संभव हो

  • मैंने एक C++ logging library बनाई थी जिसमें LMAX Disruptor से काफ़ी समानताएँ हैं, और लगता है HFT community में उसका कुछ इस्तेमाल भी होता है
    मूल उद्देश्य यह था कि production environment में post-mortem debugging के लिए बहुत detailed logs बिना performance hit के छोड़े जा सकें। कुछ सहकर्मी इस डर से ज़रूरी जानकारी log में डालने से मना करते थे कि performance पर असर पड़ेगा, लेकिन इस library ने वह बहस खत्म कर दी
    [1] https://github.com/mattiasflodin/reckless

  • compile-time dispatch का एक और फ़ायदा यह है कि जब compiler स्थिर रूप से तय कर सकता है कि कौन-सा function call होगा, तो वह उस function के code को call site पर सीधे inline कर सकता है
    इससे function call overhead पूरी तरह हट सकता है, और dead code elimination, constant propagation जैसी अतिरिक्त optimizations भी संभव हो सकती हैं

    • जहाँ तक मुझे पता है, speedup का कारण function call overhead होना बहुत कम होता है। जैसा कि अंत में कहा गया है, असली बात यह है कि compiler optimization dynamic branch के पार देख सकती है या नहीं
      अच्छे JIT polymorphic inlining को support करते हैं। C++ के बारे में मेरा अनुभव थोड़ा पुराना है, लेकिन इस समस्या का समाधान PGO था। हालाँकि इसका व्यापक उपयोग नहीं होता। इसके बजाय performance-sensitive code में dynamic dispatch से ही बचने की प्रवृत्ति रहती है
      इससे मिलने वाला ज़्यादा सामान्य सबक यह है कि किसी भी भाषा में code के hot path पर अनावश्यक dynamic branch से बचें, जब तक आपको इस बात का मज़बूत भरोसा न हो कि compiler या JIT इसे भेदकर देख लेगा
    • वास्तविक performance सिर्फ compiler optimization पर नहीं, बल्कि मशीन के runtime behavior पर भी निर्भर करती है। इस विषय पर यह talk बहुत दिलचस्प थी
      https://youtu.be/i5MAXAxp_Tw
    • उल्टा, अगर instruction cache ही bottleneck हो, तो latency के लिहाज़ से यह कुल मिलाकर नुकसानदेह हो सकता है। बेशक यह access pattern वगैरह पर निर्भर करता है

  • क्या high-frequency trading के अस्तित्व का कोई अच्छा कारण है? लोग अक्सर Bitcoin की ऊर्जा बर्बादी की आलोचना करते हैं, लेकिन यह भी सामाजिक रूप से साफ़ तौर पर शुद्ध नुकसान जैसा लगता है, फिर भी अजीब तरह से इसे नज़रअंदाज़ कर दिया जाता है

    • bid/ask spread पहले की तुलना में काफ़ी संकरा हो गया है। पूरे HFT उद्योग के मुनाफ़े को देखें तो वह इतना बड़ा नहीं है, बस कई अरब डॉलर के स्तर का है, जबकि trade amount कई trillion dollar है
      यह कहना मुश्किल है कि यह industry बेहद pro-social है, लेकिन spread संकरा होने से middlemen के पास जाने वाला पैसा कम होता है, यह सही है
    • शायद इसलिए क्योंकि इसे स्पष्ट रूप से प्रतिबंधित नहीं किया गया है
      HFT काफ़ी concentrated क्षेत्र है, लेकिन इसका कुल आकार छोटा है। ऊर्जा बर्बादी के हिसाब से यह Bitcoin से कई orders of magnitude छोटा है
      HFT का एकमात्र सकारात्मक प्रभाव liquidity और संकरा spread है, और यह इस पर भी निर्भर करता है कि लोग HFT को कैसे define करते हैं। उदाहरण के लिए Robinhood और free trading शायद इसके बिना मौजूद नहीं होते
      ये पहले broker और bank के पास जाने वाले हिस्से को ले रहे हैं। HFT “retail investors” को ठगने का business नहीं है
      मेरी नज़र में समाज पर इसका नकारात्मक प्रभाव बहुत कम है या है ही नहीं। अगर आप लंबे समय के लिए stock market में निवेश करते हैं, तो HFT की चिंता करने की लगभग कोई वजह नहीं है
    • Warren Buffett ने सुझाव दिया था कि stock market को और कम बार, जैसे हर quarter में एक बार, खुलना चाहिए। इससे speculation की बजाय long-term investment को बढ़ावा मिल सकता है
      वैसे भी high-frequency trading की ज़रूरत पैदा करने वाली कोई प्राकृतिक घटना नहीं है। आधारभूत value का बहुत तेज़ी से बदलना दुर्लभ है, और अगर बदलता भी है तो वह volatility से ज़्यादा किसी निश्चित बदलाव के जैसा होता है
    • Bitcoin के अलावा trading में बस कुछ databases में कुछ entries लिखी जाती हैं। Bitcoin mining भारी numerical computation का काम है
      HFT असंगतियों को, जैसे तीन currency pairs का एक-दूसरे से mismatch होना या “स्पष्ट” mispricing, दूर करके financial market को बहुत थोड़ा अधिक सटीक बनाता है
    • जानना चाहूँगा कि आपने इस बारे में कितना पढ़ा है, और क्या आपने कभी shares खरीदे-बेचे हैं
      जब आप कुछ trade करने की कोशिश करते हैं, तो दूसरी तरफ कोई न कोई होता है। अक्सर संभावना यही होती है कि मुझे अपनी मनचाही price पर किसी HFT participant से trade मिलेगा। अगर मुझे बेहतर price मिलती है, तो वह पैसा मेरे पास बचता है
      “इसे बस नज़रअंदाज़ कर दिया जाता है” वाली बात से भी सहमत होना मुश्किल है। HFT की यहाँ भी काफ़ी आलोचना होती है

  • अगर आप professional developer हैं, तो पूरा material देखने लायक है
    https://github.com/CppCon/CppCon2017/tree/master/Presentatio...
    और उसका parent directory भी

  • एक सवाल है। इस क्षेत्र में logic के लिए C की जगह C++ का उपयोग क्यों किया जाता है या किया जाता रहा है? इस domain में C++ को C पर क्या बढ़त मिलती है? मैं C/assembly में काफ़ी सहज हूँ, लेकिन HFT की practices बिल्कुल नहीं जानता, इसलिए आसान भाषा में समझाएँ तो अच्छा होगा

    • C++ , C की तुलना में अधिक expressive है और बहुत अधिक abstractions की अनुमति देता है। लंबे समय तक C++ ही एकमात्र mainstream language थी जो C-level performance और समृद्ध abstractions दोनों देती थी, इसलिए HFT, game development, graphics जैसे उन क्षेत्रों में यह लोकप्रिय हुई जहाँ जटिल domain modeling की ज़रूरत होती है
      बेशक इस expressive power के लिए language की भारी complexity झेलना वाजिब है या नहीं, इस पर बहस हो सकती है, लेकिन व्यवहार में लोगों ने अनुभव के आधार पर C++ को चुना है

  • इस लेख की संरचना और tone में LLM जैसी गंध काफ़ी मज़बूती से आती है