55 GiB/s FizzBuzz (2021)

 (codegolf.stackexchange.com)
5 पॉइंट द्वारा GN⁺ 2023-07-04 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Code Golf Stack Exchange का High throughput Fizz Buzz एक performance experiment है, जिसमें यह मुकाबला होता है कि FizzBuzz output को कितनी तेज़ी से generate करके pipe में बहाया जा सकता है, और स्कोर <program> | pv > /dev/null throughput से तय होता है
  • वैध output के लिए साधारण ASCII, \n line break, बिल्कुल सही Fizz/Buzz/FizzBuzz, कम-से-कम 2^58 तक या व्यावहारिक रूप से अनंत output ज़रूरी है, और सिर्फ pv में दिखने वाली null byte trick प्रतिबंधित है
  • शीर्ष implementations % 3, % 5, printf loops को छोड़कर 15-line pattern unrolling, fixed-width number handling, बड़े buffers, parallelization, और zero-copy output से bottleneck कम करती हैं
  • दिखाई गई x86-64+AVX2 assembly answer Linux और AVX2 को मानकर vmsplice, L2 cache, huge page, और FizzBuzz bytecode interpreter को मिलाकर लगभग 61GiB/s दर्ज करती है
  • नतीजे CPU, pipe buffer, pv version, CPU affinity, mitigation settings से काफी बदलते हैं, और प्रश्नकर्ता की मशीन के हिसाब से सर्वोच्च स्कोर David Frank के C++ implementation का लगभग 1.7Tb/s बताया गया है

FizzBuzz से throughput की सीमा तक धक्का

  • मूल बात FizzBuzz समस्या नहीं है, बल्कि यह देखना है कि बहुत सरल text generation में CPU computation, memory copy, pipe I/O, kernel boundary में से bottleneck सबसे पहले कहाँ आता है
  • baseline के तौर पर एक naive C implementation % 3, % 5, printf का उपयोग करती है और औसत मशीन पर लगभग 170MiB/s देती है
  • प्रश्नकर्ता ने उसी मशीन पर 3GiB/s से ऊपर की implementations पहले देखी थीं और चाहता था कि community throughput की इससे ऊँची सीमा तलाशे
  • स्कोर प्रश्नकर्ता के desktop पर मापा गया
    • AMD 5950x, 16C/32T
    • 64GB 3200MHz RAM
    • CPU mitigations disabled
  • भाषा-वार तालिका में asm 60.8GiB/s, C 20.9GiB/s, Julia 15.5GiB/s, Go 6.8GiB/s, Java 5.8GiB/s, Rust 3.4GiB/s, Ruby 1.7GiB/s, Python 0.5GiB/s आदि शामिल हैं
  • ais523 का x86-64+AVX2 assembly answer single-thread maximum performance को लक्ष्य बनाता है, और लेखक की मशीन पर लगभग 31GiB/s तथा प्रश्नकर्ता के संकलन में लगभग 61GiB/s दर्ज करता है
  • David Frank की C++ implementation ने प्रश्न के मुख्य पाठ के अनुसार मौजूदा सर्वोच्च स्कोर के रूप में लगभग 1.7 Terrabit/s दर्ज किया, जबकि एक अलग C++20 implementation ने AMD Ryzen 9 7700X पर 283GB/s देने का दावा किया

Output rules और benchmark conditions

  • वैध output की शर्तें कड़ी हैं
    • output बिल्कुल सही FizzBuzz होना चाहिए
    • हर ASCII character 1 byte होना चाहिए
    • line break के लिए सिर्फ \n मान्य है
    • \r\n मान्य नहीं है
    • output कम-से-कम 2^58 जैसी बहुत बड़ी संख्या तक जारी रहना चाहिए
  • benchmark का तरीका भी throughput पर असर डालता है
    • चर्चा में pv और Linux pipe buffer को डिफ़ॉल्ट रूप से 64K buffer इस्तेमाल करने वाला बताया गया है
    • CPU sibling core placement के अनुसार generator program और consumer program के बीच L2 cache path बदल सकता है
    • taskset से CPU placement को force करके तुलना की जा सकती है

assembly implementation की optimization तकनीक

  • assembly implementation का केंद्र calculation से ज़्यादा output copy cost घटाने पर है
    • write इस्तेमाल करने पर user space से kernel space तक copy का खर्च बड़ा होता है
    • लेखक लिखता है कि write-आधारित रूप में बदलने पर performance पाँचवें हिस्से तक गिर जाती है
    • vmsplice से pipe को program के buffer को reference करने दिया जाता है, जिससे copy कम होती है
  • FizzBuzz calculation को 3 चरणों में बाँटा गया है
    • पहला चरण शुरुआती strings को hardcode करता है
    • दूसरा चरण 2 से 5 digit numbers को अपेक्षाकृत सीधे AVX2 routine से संभालता है
    • तीसरा चरण 6 से 18 digit range को FizzBuzz bytecode interpreter से संभालता है
  • तीसरे चरण का मुख्य loop हर 4 clock cycles पर 64 bytes output का लक्ष्य रखता है
    • bytecode का 1 byte, output का 1 byte बनाता है
    • 32-byte bytecode load करके vpshufb, vpsubb आदि से 32 bytes output बनाई जाती है
    • line numbers को approximate value और bytecode correction से संभाला जाता है, ताकि हर line पर सामान्य number conversion न करनी पड़े
  • यह implementation platform-dependent है
    • अपेक्षाकृत नया Linux चाहिए
    • AVX2 support वाला x86-64 processor चाहिए
    • अगर standard output pipe नहीं है तो यह startup पर error देता है
    • बताया गया है कि splice शामिल होने वाली pipe configuration में कभी-कभी गलत output आ सकता है

दूसरी भाषाओं की implementations में साझा रणनीतियाँ

  • C, Go, Java, Rust, Python, Julia, Ruby, C# implementations भी optimization की मिलती-जुलती दिशा अपनाती हैं
    • 15-line FizzBuzz pattern को unroll करती हैं
    • number string conversion की संख्या घटाती हैं
    • बड़े buffer में इकट्ठा करके लिखती हैं
    • threads या goroutine से generation work को parallelize करती हैं
    • output order बनाए रखने के लिए barrier, channel, queue, mutex का उपयोग करती हैं
  • इस नतीजे को साधारण “language performance” तुलना मानना कठिन है
    • pv version, pipe size, vmsplice availability, CPU affinity, huge page, compiler optimization, memcpy inline होने या न होने से throughput बहुत बदलती है
    • कुछ answers के comments में कहा गया है कि वे किसी खास मशीन पर तेज़ थे, लेकिन दूसरे environments में वही आँकड़े दोहराए नहीं जा सके

शामिल न किया गया दायरा

  • input note में संकेत है कि कुछ source chunks लंबाई और लागत सीमाओं के कारण छोड़े गए थे, इसलिए सभी 46 answers और हर code/comment को पूरी तरह शामिल नहीं किया गया है
  • छोड़े गए हिस्सों में कुछ भाषा-विशिष्ट submissions, लंबे code bodies, विस्तृत tuning logs, और comment discussions शामिल हो सकते हैं

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

1 टिप्पणियां

 
GN⁺ 2023-07-04
Hacker News की राय

  • सबसे प्रभावशाली बात यह लगी कि Linux एक प्रोग्राम से दूसरे प्रोग्राम में pipe किए गए डेटा को सिर्फ L2 cache में ही बनाए रख सकता है और main memory को छुए बिना काम कर सकता है
    आम Linux kernel के कई हिस्सों का एक साथ मिलकर इस तरह का fast path संभव बनाना वाकई कमाल की system architecture design है
    जिज्ञासा है कि क्या Mac OSX के Mach ports या Windows के Named Pipes में भी ऐसा संभव है

    • अगर CPU cache physical address tags का उपयोग करती है, और दोनों processes की page tables एक ही physical page साझा करती हैं, तो जब तक operating system context switch के समय cache को explicitly साफ़ या invalidate नहीं करता, CPU किसी भी process को cache की सामग्री इस्तेमाल करने देगा
    • यही उन कई कारणों में से एक है जिनकी वजह से पूरा high-frequency trading उद्योग Linux पर चलता है

  • “ais523 - high effort answers” नाम के अनुरूप, इस यूज़र ने प्रोग्राम चला न पाने वाले व्यक्ति के लिए भी काफ़ी मेहनत से भरी टिप्पणी छोड़ी, और निष्कर्ष यह था
    “शायद प्रोग्राम किसी तरह ASLR enabled स्थिति में compile हो गया। इस स्थिति में dynamic linker BSS segment की 4MiB alignment का सम्मान नहीं करता, इसलिए मेरी .align निर्देशिका प्रभावी रूप से अनदेखी हो जाती है, और शायद वही bug का कारण है”

    • इतना तो समझ आ गया कि अगर यह व्यक्ति मेरे साथ उसी नौकरी के लिए apply करे, तो मेरी कोई संभावना नहीं। यह ultimate leet coder है

  • यह पोस्ट जब भी फिर से सामने आती है, मैं इस टिप्पणी पर हँस पड़ता हूँ
    “@chx: मेरे पास पहले से master’s thesis है। यह उससे भी ज़्यादा कठिन था। – ais523 - high effort answers Oct 29, 2021 at 1:17”

  • Rust, Python3, और C में optimization के बिना simple implementation करके देखा। सिर्फ साधारण if/else/while और standard output पर print इस्तेमाल किया
    Rust -> 23.2MiB/s
    Python3 -> 28.6MiB/s
    C -> 238MiB/s
    किसी को पता है कि Rust performance Python3 के आसपास क्यों है? मुझे लगा था यह C के कहीं ज़्यादा करीब होगा

    • Rust का print function default रूप से lock लेता है। यह safety के लिए है, जबकि C ऐसा नहीं करता। विवरण के लिए Rust docs देखें: https://doc.rust-lang.org/std/macro.print.html
      C जैसी performance पाने के लिए संभव है कि इस lock को सीधे handle करना पड़े
      let mut lock = stdout().lock();
      write!(lock, "hello world").unwrap();
      और standard output के buffer size को भी C के बराबर करना होगा
    • यह काफ़ी पुरानी पोस्ट है, लेकिन मददगार हो सकती है
      https://ismailmaj.github.io/tinkering-with-fizz-buzz-and-con...
    • C और Python standard output के लिए adaptive buffering का उपयोग करते हैं। अगर output terminal हो तो हर newline पर flush करते हैं, नहीं तो internal buffer भरने पर ही flush करते हैं
      1ms delay के साथ नंबर गिनने वाले C प्रोग्राम में दूसरा कॉलम पिछली read() के बाद बीता समय है
      $ ./out | rtss
      4.7ms 4.7ms | 1
      4.7ms | 2
      4.7ms | 3
      4.7ms | 4
      4.8ms exit status: 0
      देखा जा सकता है कि सब कुछ एक साथ लिखा गया। Terminal allocate करने पर हर लाइन अलग-अलग आती है
      $ rtss --pty ./out
      0.8ms 0.8ms | 1
      1.9ms 1.1ms | 2
      3.0ms 1.1ms | 3
      4.1ms 1.1ms | 4
      4.3ms exit status: 0
      Rust में output के लिए ऐसा adaptive व्यवहार नहीं है, इसलिए terminal हो या न हो, यह हमेशा दूसरे नतीजे की तरह व्यवहार करता है
      तकनीकी रूप से, standard output को हमेशा LineWriter(https://doc.rust-lang.org/std/io/struct.LineWriter.html) में wrap किया जाता है, और newline वाला write दिखते ही हमेशा flush हो जाता है। Throughput को अधिकतम करने के लिए इसे BufWriter से wrap करके कई लाइनों को साथ लिखना चाहिए
    • Rust को --release से, और C को -O3 से compile करना चाहिए
    • लगभग पक्का है कि bottleneck output की वजह से है। संभवतः buffering या lock की समस्या है

  • अगर सब कुछ assembly में लिखा गया होता तो यह कितना तेज़ होता, यह जानने की जिज्ञासा होती है
    audio development में DSP code को assembly में लिखना बहुत आम है

    • यह तेज़ होने की वजह सिर्फ assembly होना नहीं है। इस समाधान के लिए इसकी ज़रूरत है, लेकिन यह बिल्कुल भी पर्याप्त शर्त नहीं है
      इसे संभव बनाने के लिए बेहद गहन algorithm research, Linux system calls की गहरी समझ, और platform-specific optimization का मेल होना चाहिए। लेखक Alex Smith के अपने शब्दों में:
      “@chx: मेरे पास पहले से एक master's thesis है. यह उससे भी ज़्यादा कठिन था.”
      यह उस चीज़ से बिल्कुल अलग स्तर का काम है जिसे बस “assembly में कर दो” कहकर बनाया जा सके
    • अगर यह सब सिर्फ Java में भी लिखा गया होता, तब भी यह आज के उस तरीके से बेहतर होता जिसमें Python instance के अंदर Chrome डालकर JavaScript web server चलाया जाता है ताकि documents render किए जा सकें
    • आखिरकार यह Steve Yegge की Geoworks वाली कहानी जैसा ही बन जाता
      “ठीक है। मैं University of Washington में पढ़ता था, फिर Geoworks नाम की एक कंपनी में नौकरी कर ली और 5 साल तक assembly language programming की। हम Geoworker लोग पूरा operating system, libraries, drivers, apps—यानी पूरा desktop operating system—assembly में लिखते थे। वह 8086 assembly थी! और वह कोई अच्छी assembly भी नहीं थी! उसमें सिर्फ चार registers थे! अगर 386 तक गिनें तो si register भी था। बहुत भयानक था।
      सच कहूँ तो हमें यह काफ़ी पसंद भी था। क्योंकि वह object-oriented assembly थी। इंसान अपने-आप को क्या-क्या पसंद करवाने के लिए मना सकता है, यह हैरान करने वाली बात है, और यही इस पूरी कहानी की असली विडंबना है। हमारे लिए C++ रोमन शैली के पतन की पराकाष्ठा था। जैसे ज़्यादा खाने के लिए उल्टी करने चले जाना। उनके पास IF था! हमारे पास jump CX zero था! उनके पास ‘objects’ थे। हमारे पास भी थे, लेकिन उनके लिए उनके पास syntax था। यह बहुत कमज़ोर लगता था। और उस समय हमें पता था कि हम किसी भी compiler से तेज़ code बना सकते हैं, और हम सचमुच बनाते भी थे!
      तो फिर क्या हुआ? कंपनी दिवालिया हो गई। क्यों? शायद इस बात पर मैं हर Geoworker से असहमत हूँ। मुझे पता है कि शायद यह मानने वाला मैं अकेला ही हूँ। लेकिन वजह यह थी कि हमने 8086 assembly language की 1.5 करोड़ lines लिख डाली थीं। हमारे पास बहुत अच्छे tools थे, world-class tools, यक़ीन मानिए। ऐसे tools ज़रूरी भी होते हैं। लेकिन एक समय ऐसा आता है…
      समस्या यह है: कल्पना कीजिए कि एक चींटी garage के फ़र्श पर सीधी रेखा में चलकर पार जाना चाहती है। वह सीधा नहीं जा सकती। हमें ऊपर से व्यापक नज़र मिलती है, इसलिए हम यह जानते हैं। हम देखते हैं कि चींटी इधर-उधर घूमती है, उस पत्थर के हिसाब से local optimization करती है, फिर उधर मुड़ती है।
      जब हम विशाल assembly language systems लिख रहे थे, तब हम भी बिल्कुल यही कर रहे थे। आखिर में Microsoft ने हमसे कहीं तेज़ mobile device platform निकाल दिया। मैं debugger लेकर अंदर गया और कहा, ‘यह क्या है? ऐसा क्यों हो रहा है? rendering बहुत धीमी है, अटक रही है।’ अंदर जाकर देखा तो हर बार screen refresh होने पर कोई title bar 140 बार render हो रही थी। और सिर्फ title bar ही नहीं—हर चीज़ कई-कई बार call हो रही थी।
      क्योंकि हम अब यह देख ही नहीं पा रहे थे कि system असल में कैसे काम कर रहा है!
      छोटे systems सिर्फ optimize करना आसान नहीं होते, वे सच में optimize किए जा सकते हैं। यानी global optimization संभव होती है.”
      http://steve-yegge.blogspot.com/2008/05/dynamic-languages-st...
    • assembly आज लिखे जाने वाले source code से इतनी दूर जा चुकी है कि उसके बारे में सोचना भी व्यावहारिक नहीं लगता। फिर भी, अगर software बनाने वाली कंपनियाँ सच में performance की परवाह करें, तो कल्पना की जा सकती है कि सब कुछ कितना तेज़ हो सकता है
      आज की websites और software का लगभग 99% सिर्फ application performance पर थोड़ा ध्यान देकर, बुनियादी बदलावों से ही कम-से-कम 50% speed improvement हासिल कर सकता है। जैसे सही caching, asset optimization, फूली हुई third-party libraries को उसी काम के लिए native calls से बदलना, और server व database की सही configuration
      यह भी लगता है कि कुछ सालों में AI repositories के लिए one-click optimization दे सकता है, जो best practices लागू कर दे या मूल code को तेज़ assembly में फिर से लिख दे
    • इस बात में जो अक्सर छूट जाता है कि ज़्यादा primitive languages तेज़ programs देती हैं, वह यह है कि अगर coding के दौरान ज़रा-सी प्रगति भी दर्दनाक हो, तो आप बहुत मेहनत करते हैं कि जितना कम हो सके उतना ही implement करना पड़े
      resource constraints फ़ोकस को स्पष्ट बना सकते हैं

  • यह प्रयोग मज़ेदार और जानकारीपूर्ण तो है, लेकिन इसमें थोड़ी खामी दिखती है। यह इस बात का मूल्यांकन कम करता है कि कोई जटिल समस्या कितनी तेज़ी से हल होती है, और ज़्यादा इस सहायक समस्या को टेस्ट करता है कि एक प्रोसेस से मेमोरी निकालकर दूसरे प्रोसेस को कितनी दक्षता से सौंपी जाती है
    इसलिए ऐसा लगता है कि दूसरा प्रोसेस लगातार console या file में लिख रहा है, लेकिन तकनीकी रूप से ऐसा नहीं है। pv >/dev/null चलाना मूलतः लगभग कुछ भी न करने जैसा है, और write system call लगभग तुरंत return हो जाती है
    vmsplice एक shared memory जैसी सुविधा है, जो एक प्रोसेस के buffer/memory तक दूसरे प्रोसेस को पहुँचने देती है। शुरुआती प्रतियोगिता की requirements शायद अस्पष्ट थीं, इसलिए यह नियमों के हिसाब से ठीक था या नहीं, यह स्पष्ट नहीं लगता

    • यह देखने के लिए ऊपर scroll करके मूल प्रश्न देखा जा सकता है कि शुरुआती requirements अस्पष्ट थीं या नहीं, और edit history से यह भी पता चलता है कि challenge शुरू होने के बाद वे बदली नहीं थीं
      “एक FizzBuzz program लिखिए। उसे चलाइए। output को | pv > /dev/null में pipe कीजिए। throughput जितना ज़्यादा, उतना बेहतर।”
      “Program output बिल्कुल वैध fizzbuzz होना चाहिए। वैध output के बीच null byte घुसाकर cheat नहीं कर सकते। जैसे null byte जो console पर नहीं दिखते लेकिन pv throughput में गिने जाते हैं।”
      और vmsplice(2) वास्तव में standard output pipe में एक byte stream बनाता है, जिसे pv(1) /dev/null में splice कर सकता है या cat(1) terminal पर copy कर सकता है
      सिर्फ इसी submission ने vmsplice(2) का इस्तेमाल नहीं किया। दूसरे submitters ने भी पता लगाया कि यह कोई जादुई समाधान नहीं है। I/O barrier पार करने के बाद भी output pages को जितना संभव हो उतनी तेज़ी से बनाना बाकी रहता है
    • मुझे लगता है “एक प्रोसेस से मेमोरी निकालकर दूसरे प्रोसेस को देने की दक्षता” लगभग हमेशा पूरी समस्या ही होती है
      ज़्यादातर code की bottleneck memory और I/O में होती है। जटिल समस्याएँ भी आम तौर पर data को एक जगह से दूसरी जगह ले जाने की गति से अटकती हैं; data की computation से अटकना दुर्लभ है। GPU assembly optimize करते हुए दिन बिताने वाले व्यक्ति के रूप में भी, जिन दुर्लभ मामलों में computation bottleneck होती है, उसे optimize करने के बाद bottleneck फिर memory बन जाती है
    • मैं सहमत नहीं हूँ। पहले काफ़ी FizzBuzz-विशेष optimization किए बिना bottleneck “एक प्रोसेस से मेमोरी निकालकर दूसरे प्रोसेस को देने की दक्षता” तक पहुँचती ही नहीं
      उदाहरण के लिए, एक चतुर bit representation है जो decimal carry को स्वाभाविक रूप से होने देती है
      शुरुआती प्रतियोगिता requirements भी इस बिंदु पर ख़ास अस्पष्ट नहीं थीं। उसमें साफ़ कहा गया था कि throughput को | pv > /dev/null से मापना है, और यह भी कहा गया था:
      “Architecture-specific optimization / assembly भी स्वीकार्य है। यह कोई असली competition नहीं है। हम बस लोगों को fizz buzz को उसकी सीमा तक धकेलते देखना चाहते हैं, भले ही वह सिर्फ़ किसी special environment/platform पर ही काम करे।”
    • I/O शाब्दिक रूप से हर program को करना ही पड़ता है। आधुनिक hardware पर चलने वाले code का 99% यहीं bottleneck हो सकता है। bytes को एक जगह से दूसरी जगह ले जाना ज़रूरी है और तुलनात्मक रूप से धीमा भी
      memory I/O और file I/O को अच्छी performance के साथ handle करना समझना हर program और programmer के लिए प्रासंगिक कौशल है

  • इसमें fizzbuzz.S नाम से save करने को कहा गया है, तो मैं सोच रहा हूँ कि extension .S और .s में क्या फ़र्क है

    • बड़े S का मतलब है पहले preprocessor चलाया जाएगा
      manual page के अनुसार:
      file.s
      assembler code
      file.S
      file.sx
      preprocessed assembler code
    • जहाँ तक मुझे याद है, पारंपरिक रूप से फ़र्क यही था कि input को preprocessor से गुज़ारा जाता है (.S) या नहीं (.s)
      आधुनिक toolchain में अब भी कोई फ़र्क है या नहीं, यह मुझे पक्का नहीं मालूम
    • जिस convention का मैं आदी हूँ, उसमें .S मानव द्वारा सीधे लिखी गई assembly file के लिए होता है, आम तौर पर git में tracked file, और .s machine-generated assembly के लिए, जिसे ज़रूरत पड़ने पर overwrite किया जा सके
    • GCC आदि .S को overwrite नहीं करते, लेकिन अगर आप assembly generate करने को कहें (जैसे gcc -S xyz.c) तो .s overwrite कर देते हैं

  • पिछली पोस्टें:
    https://news.ycombinator.com/item?id=29031488
    https://news.ycombinator.com/item?id=29413656

  • मैंने पहले इसे 55 GiB/s FritzBox पढ़ लिया था। FritzBox यूरोप के जर्मन-भाषी क्षेत्रों में लोकप्रिय router है
    मेरे ISP ने भी पिछले हफ़्ते ट्वीट किया था कि 60 GiB/s support वाला OPNSense box[1] जल्द उपलब्ध होगा
    [1] https://twitter.com/init7/status/1674920410889043973

    • मैं 16GB memory में upgraded DEC750 इस्तेमाल कर रहा हूँ। 10GbE support वाला, WireGuard 2.3GbE कर सकने वाला यह router शानदार hardware निकला—शांत, और idle power भी cable modem जैसी सिर्फ़ 8W—इसलिए मेरा इसे 2030~2035 से पहले बदलने का कोई इरादा नहीं है
      मैंने एक USB WiFi adapter भी लगाया हुआ है, ताकि cable कटने पर कुछ VLAN fail over हो जाएँ और phone के ज़रिए काम के लिए ज़रूरी connectivity बनी रहे
      यह सस्ता नहीं है, लेकिन अगर आप OPNSense project को आर्थिक रूप से support करते हुए सही hardware चाहते हैं, तो Deciso hardware के ख़िलाफ़ तर्क करना मुश्किल है। यह power-efficient है, durability-focused components इस्तेमाल करता है, और बस ठीक से काम करता है
      commercial lineup को और शक्तिशाली होते देखना अच्छा लगता है