1 अरब पंक्तियों की चुनौती

 (morling.dev)
2 पॉइंट द्वारा GN⁺ 2024-01-05 | 2 टिप्पणियां | WhatsApp पर शेयर करें
  • जनवरी 2024 के पूरे महीने चली One Billion Row Challenge(1BRC) एक performance challenge थी, जिसमें 1 अरब पंक्तियों वाली text file को process करके यह देखा गया कि Java कितनी तेज़ हो सकती है
  • input station;temperature format का साधारण text है, लेकिन हर observation station के लिए न्यूनतम·औसत·अधिकतम तापमान calculate करके नाम के क्रम में बिल्कुल सही output देना होता है
  • implementation में सिर्फ Java की अनुमति है; SDKMan distributions और openjdk.net Early Access builds इस्तेमाल किए जा सकते हैं, लेकिन external dependencies प्रतिबंधित हैं
  • प्रतिभागी GitHub के 1brc repository में pull request के जरिए submit करते हैं, और दिए गए baseline implementation से answer format और performance की तुलना कर सकते हैं
  • evaluation समान Hetzner Cloud CCX33 environment में 5 बार run करने के बाद सबसे कम और सबसे ज्यादा records हटाकर बाकी 3 runs के average से leaderboard ranking तय करता है

1 अरब पंक्तियों को सबसे तेज़ aggregate करने वाला Java task

  • One Billion Row Challenge 1 जनवरी 2024 से 31 जनवरी 2024 तक चली Java performance challenge थी
  • प्रतिभागी एक Java program लिखते हैं जो text file से temperature measurements पढ़कर प्रत्येक weather observation station के लिए न्यूनतम·औसत·अधिकतम तापमान calculate करता है
  • difficulty का मुख्य बिंदु यह है कि input file में 1,000,000,000 पंक्तियां हैं
  • input एक simple structure है, जिसमें एक line में एक measurement होता है
    • उदाहरण: Hamburg;12.0
    • उदाहरण: Bulawayo;8.9
    • उदाहरण: Palembang;38.8
  • output में observation station names को alphabetical order में sort करना और हर station के min/mean/max values दिखाने होते हैं
    • उदाहरण: {Abha=5.0/18.0/27.4, Abidjan=15.7/26.0/34.1, ...}

Submission rules और execution environment

  • लक्ष्य वही काम करने वाला सबसे तेज़ Java implementation बनाना है
  • optimization में virtual threads, Vector API और SIMD, GC optimization, AOT compilation आदि का उपयोग किया जा सकता है
  • basic rules इस प्रकार हैं
    • submission Java में लिखा होना चाहिए
    • SDKMan द्वारा प्रदान किए गए Java distributions और openjdk.net के Early Access builds इस्तेमाल किए जा सकते हैं
    • Valhalla जैसे OpenJDK projects के EA builds भी allowed हैं
    • external dependencies इस्तेमाल नहीं की जा सकतीं
  • प्रतिभागी 1brc repository clone करके README instructions के अनुसार implementation submit करते हैं
  • baseline implementation comparison baseline और answer format check करने के लिए दिया गया है
  • submission upstream repository में pull request खोलकर किया जाता है

Leaderboard calculation method और community sharing

  • evaluation Hetzner Cloud CCX33 instance पर किया जाता है
    • specification 8 dedicated vCPU, 32 GB RAM है
    • time program से end-to-end execution time measure किया जाता है
    • हर submission लगातार 5 बार run किया जाता है
    • सबसे धीमा run और सबसे तेज़ run exclude किए जाते हैं
    • बचे हुए 3 runs के execution time का average उस submission का result बनता है
    • results leaderboard में जोड़े जाते हैं
  • optimization techniques पर चर्चा GitHub repository के discussion में जारी रहती है
  • Java के अलावा दूसरी languages के implementations share करने के लिए Show & Tell भी उपलब्ध है, जहां Rust, Go, C++ आदि के 1BRC implementations share किए गए हैं

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

2 टिप्पणियां

 
GN⁺ 2024-01-05
Hacker News की राय

  • अभी सबसे बेहतर प्रदर्शन करने वाला दिख रहा समाधान [0] hash collision को ध्यान में नहीं रखता, इसलिए अगर dataset में अलग-अलग शहरों की संख्या काफी ज़्यादा हो, तो यह गलत परिणाम दे सकता है
    सोच रहा हूँ कि कहीं मैं कुछ मिस तो नहीं कर रहा
    [0] https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...

    • सही है। यह समस्या कल सामने आई थी, और सच में दो समाधानों ने किसी खास dataset के हिसाब से बने hash function पर निर्भर होकर उस नियम का उल्लंघन किया था कि यह सभी station names पर काम करना चाहिए, लेकिन evaluation के दौरान यह छूट गया
      फिलहाल उन entries को leaderboard से हटा दिया गया है, और दोनों लेखक अपनी submissions ठीक कर रहे हैं, इसलिए बाद में उन्हें फिर जोड़ा जाएगा
      [0] https://twitter.com/mtopolnik/status/1742652716919251052

  • मुझे लगता है कि इस तरीके से पूरी चीज़ को 0.3 सेकंड के अंदर प्रोसेस किया जा सकता है
    तापमान में दशमलव का सिर्फ एक अंक है, इसलिए सामान्य स्थिति में लगभग 400 values काफ़ी हैं, और place names भी लगभग 400 तक सीमित हैं, तो temperature × place name के लगभग 1.6 लाख combinations की lookup table बनाई जा सकती है
    फिर एक state machine auto-generate की जा सकती है, जो इन 1.6 लाख combinations को, चाहे वे 4-byte register में किसी भी rotation position पर हों, hash table के unique bucket से map करे, और 32-bit state register में हर cycle state-transition table lookup तथा अगले 4 bytes के साथ XOR करे
    पूरे data को memory speed पर scan करते हुए state के हिसाब से counters बढ़ाए जा सकते हैं, और state केवल 65K हैं इसलिए counters cache में आ जाएंगे
    AVX512 के साथ, प्रति core ऐसी 32-bit state machines को 512 parallel में चलाया जा सकता है, इसलिए computation bottleneck नहीं होगा
    जो बहुत ऊँचे/नीचे तापमान या अनजान place names valid buckets पर map नहीं होते, उन्हें slow code path पर भेजा जा सकता है, और min/max handling भी ऐसे ही escape के ज़रिए की जा सकती है, जो सिर्फ कुछ हज़ार बार होगा
    मेरा मानना है कि यह तरीका सिर्फ एक AVX512 single core पर memory speed से चल सकता है, इसलिए इसे कई cores में बाँटने का खास फायदा नहीं होगा

    • lookup table की ज़रूरत नहीं है। चाहिए सिर्फ min/average/max, इसलिए data को store किए बिना एक ही pass में सब कुछ निकाला जा सकता है
      ज़रूरत सिर्फ 400 entries वाली hash table, running min/average/max के 3 floating-point values, और average update के लिए एक count integer की है
      नामों पर 16 bytes भी खर्च करें, तब भी सब कुछ 16KB के अंदर आ जाएगा
      runtime पर I/O हावी होगा, और उसके बाद JSON parsing
    • एक single core memory bandwidth को saturate नहीं कर सकता। core memory parallelism और latency से सीमित होता है
      ज़्यादातर modern x86 server chips प्रति clock 2 SIMD loads retire कर सकते हैं, इसलिए AVX2 के हिसाब से 1GHz पर लगभग 32GB/s संभव है, यानी per-core bandwidth को maximize करने के लिए AVX-512 अनिवार्य नहीं है
      लेकिन अगर DRAM से पढ़ रहे हैं, तो bottleneck इससे बहुत पहले, आम तौर पर servers में 10~16GB/s के आसपास आ सकता है
      जब तक ज़्यादातर data RAM तक spill हो रहा है, single-core throughput काफ़ी गिर जाएगा, और बड़े streaming workloads में multi-core parallelism लगभग हमेशा फ़ायदेमंद होती है
      L3 cache से बहुत बड़ा memory block allocate करके, pages को पहले से fault-in कराकर, फिर tight loop में unrolled vector loads (AVX2/AVX-512) चलाकर इसे आसानी से verify किया जा सकता है
    • अगला state हमेशा पिछले state पर निर्भर है, इसलिए समझ नहीं आ रहा कि state machine को parallel में कैसे चलाया जा सकता है
      और state register को interpret कैसे करेंगे, यह भी सवाल है। input के 4 bytes के साथ XOR करने पर, किसी अनपेक्षित place name के लिए यह वास्तव में 4.7 अरब संभावित values में से कुछ भी बन सकता है
      और अपेक्षित place name के मामले में भी, अगर वह 4 bytes से लंबा है, तो common prefix वाले दूसरे नामों से अलग करने के लिए क्या हर नाम के लिए कई states नहीं चाहिए होंगे?
    • लगता है नियमों की व्याख्या दोबारा जाँचनी होगी। ज्ञात 400 place names के लिए optimized code, लेकिन अतिरिक्त names को slow path से support करना वैध है या नहीं, यह स्पष्ट नहीं है
      नियम कहते हैं कि भले ही data generator station names के fixed set का उपयोग करे, कोई भी समाधान arbitrary UTF-8 station names पर काम करना चाहिए
    • place names ढूँढने के लिए आखिरकार पूरी file पढ़कर parse करनी ही पड़ेगी

  • सबसे धीमे और सबसे तेज़ run को हटाकर बाकी तीन का average लेने की बजाय, मेरा मानना है कि या तो दो सबसे धीमे runs हटाने चाहिए, या बस सबसे तेज़ value को मान लेना चाहिए
    मुझे नहीं लगता कि अच्छे run result को फेंकने की कोई ठोस वजह है

    • यह trimmed mean नाम की काफ़ी standard measurement technique है: https://statisticsbyjim.com/basics/trimmed-mean/
    • सबसे अच्छे run को हटाने की वजह हो सकती है। अगर आप मानें कि system predictably चलता है और सिर्फ background tasks की वजह से कभी-कभी slow होता है, तो best run लेना उचित लग सकता है
      लेकिन अगर program के अंदर non-determinism का थोड़ा भी कारण हो, जो सोचे से ज़्यादा आम है, तो best time representative न होने की पूरी संभावना है
      इस बारे में https://tratt.net/laurie/blog/2019/minimum_times_tend_to_mis... एक अच्छी पोस्ट है
    • अगर सबसे तेज़ run को हटाना स्वीकार्य नहीं लगता, तो फिर सबसे धीमे run को हटाने का समर्थन क्यों है, यह समझ नहीं आता

  • नियमों को सख्ती से मानने वाले नज़रिए से देखें तो पहली रन पर background daemon उठाकर पूरी फ़ाइल को मेमोरी में लोड करके pin कर देना, फिर बाद की runs को लगभग सिर्फ़ linear scan तक सीमित कर देना, और cache भी पहले से warm कर लेना आकर्षक लगता है
    पहली रन में result पहले से precompute करना भी, नियमों की व्याख्या को कितना खींचा जाए इस पर निर्भर करते हुए, संभव लगता है; और संख्याओं को पहले से अधिक सघन format में parse करके रखना और बाद की runs में उन्हें सीधे cumulative sum की तरह पढ़ना भी संभव लग सकता है
    यह प्रतियोगिता के उद्देश्य के बिल्कुल विपरीत है, लेकिन दिखने वाले नियमों के हिसाब से शायद स्पष्ट रूप से मना नहीं है
    अगर precomputation पसंद नहीं है, तो input को पहले से sort करना, pre-parse करना, या compression·sorting·sorted memory layout जैसी तरकीबें भी संभव हैं
    चरम स्थिति में calculate_time स्क्रिप्ट को patch करके अपने लिए 0 सेकंड और प्रतियोगी के लिए 9999 लौटाया जा सकता है

    • अगर प्रतिभागियों को वही सटीक फ़ाइल दे दी जाए जो प्रतियोगिता में वास्तव में इस्तेमाल होगी, तो सच में समस्या पैदा होगी
      input पढ़े बिना answer को एक लाइन में hardcode करने से लेकर, फ़ाइल की सामग्री नहीं जानते मानकर process करने तक, precomputation का gray area लगभग 1 अरब चरणों जितना बड़ा है
      यह एक ऐसी प्रतियोगिता बन सकती है जिसमें तय करना पड़े कि कौन-सा precomputation निष्पक्ष है और कौन-सा नहीं
      इसी वजह से machine learning प्रतियोगिताएँ प्रतिभागियों को final data नहीं दिखातीं
    • लगता है यह नियम का उल्लंघन करेगा
      लिखा है कि computation application run के समय होनी चाहिए, और build समय पर measurement फ़ाइल को process करके result को binary में bake नहीं करना चाहिए
    • नियमों के अनुसार हर run को अलग tmpfs में चलाना चाहिए, और runs के बीच सभी processes और page cache को साफ़ करने की बात स्पष्ट रूप से लिखी जानी चाहिए

  • मुझे लगता है यह बस disk speed से बँधी हुई समस्या नहीं है क्या। SIMD या multithreading जैसी optimizations का कितना मतलब होगा, इस पर संदेह है
    अलग-अलग stations की संख्या और hash lookup के तरीके पर यह निर्भर करेगा, लेकिन I/O की तुलना में यह मापने लायक असर डालेगा या नहीं, इस पर शंका है

    • disk access को parallelize किया जा सकता है और NVMe बहुत तेज़ है, इसलिए bottleneck disk की बजाय CPU भी हो सकता है
      आधुनिक hardware को ध्यान में रखकर डिज़ाइन किए गए systems इसी बात का फायदा उठाते हैं, और जहाँ मैं काम करता हूँ, redpanda.com, वह भी ऐसा ही एक उदाहरण है
      parsing computation time का बड़ा हिस्सा लेती है, और delimiter ढूँढने की SWAR जैसी SIMD techniques मददगार हो सकती हैं
      अगर ऐसे algorithms की साफ़-सुथरी implementation देखनी हो तो Stringzilla अच्छा है: https://github.com/ashvardanian/StringZilla
      पहली run के बाद फ़ाइल पूरी तरह मेमोरी में cache हो जाती है, इस बिंदु पर यहाँ जवाब दिया गया है: https://news.ycombinator.com/item?id=38864034
    • यह पूरी तरह workload और hardware पर निर्भर करता है। साधारण consumer SSD भी 2TB में से सिर्फ़ 700GB इस्तेमाल होने पर 7GB/s (56Gbps) आसानी से बनाए रख सकता है
      आम तौर पर servers में ऐसे 15 SSD लगाने के लिए पर्याप्त PCIe lanes होते हैं, इसलिए server I/O bandwidth मेमोरी bandwidth के काफ़ी करीब पहुँच जाती है
      अधिक महँगे servers में PCIe 5.0 जैसी तेज़ lanes और उनकी अधिक संख्या होती है
      यह फ़ाइल 1 अरब rows की है और compress होने पर लगभग 1GB की है, और पहली discarded run के बाद मेमोरी में आ जाती है, इसलिए इस scenario में I/O bandwidth महत्वपूर्ण नहीं है
      GitHub repository में इसे uncompressed 12GB बताया गया है, और यह भी इसी बात की पुष्टि करता है कि I/O bandwidth यहाँ महत्वपूर्ण नहीं है
    • Daniel Lemire की यह talk दिलचस्प है: https://www.youtube.com/watch?v=wlvKAT7SZIQ
      मुख्य बात यह है कि disk का bottleneck होना दुर्लभ है
    • यह operating system और file system पर निर्भर करता है। input फ़ाइल लगभग 12GB है और 32GB मेमोरी वाली machine पर 5 बार चलती है, इसलिए पहली run के बाद पूरी फ़ाइल मेमोरी में cache हो सकती है
      उदाहरण के लिए Linux पर ext2 इस्तेमाल हो तो पहली run के बाद पूरी फ़ाइल cache होने की संभावना ज़्यादा है, लेकिन ZFS पर ऐसा ज़रूरी नहीं
    • सबसे तेज़ parsing के लिए सब कुछ RAM में लाकर अंत से उल्टी दिशा में process करना स्पष्ट रूप से सही लगता है
      तब संख्या के digit low place से high place के क्रम में मिलेंगे, फिर delimiter और string आएँगे, और EOF या newline मिलने तक आगे बढ़ा जा सकता है

  • नियमों के अनुसार submission को हर input पर सही काम करना चाहिए, लेकिन ऐसा लगता है कि create_measurements.sh से बनने वाले खास input के लिए tune करना allowed है, और शायद अपेक्षित भी
    उदाहरण के लिए दिए गए station set के लिए अनुकूलित perfect hash function इस्तेमाल करने वाली submission की कल्पना की जा सकती है

    • अगर यह requirement है, तो test data को example data से अलग बनाना समझदारी होगी
      इससे overfitting optimization रोकी जा सकेगी
    • UTF-8 की वजह से यह बहुत कठिन हो जाता है। लेकिन अगर नियमों की भावना नहीं बल्कि सिर्फ़ शब्दशः पालन किया जाए, तो 127 से बड़े byte दिखते ही slow implementation पर switch किया जा सकता है
      127 से बड़े byte multi-byte UTF-8 characters को दर्शाते हैं

  • मज़े के लिए awk बनाम Java speed comparison किया गया
    यह awk -F';' से station के हिसाब से sum, count, min, max जमा करता है और END में average निकालकर प्रिंट करने वाला script है

    • PostgreSQL के file foreign data wrapper के साथ speed comparison देखना चाहूँगा: https://www.postgresql.org/docs/current/file-fdw.html
      इसमें file_fdw से CSV फ़ाइल को external table बनाकर GROUP BY station_name के साथ MIN, AVG, MAX निकाले जाते हैं
    • ClickHouse local में चलाने पर लगभग 15.2 सेकंड आते हैं
      clickhouse local में file('measurements.txt', 'CSV', 'station String, t Float32') पढ़कर station के हिसाब से min, max, avg group किया जाता है, और max_threads = 8 के साथ चलाया जाता है
      ज़्यादातर समय फ़ाइल parsing में जाता है
    • sum variable काफ़ी बड़ा हो सकता है, इसलिए streaming average इस्तेमाल करना बेहतर है
      उदाहरण के लिए new_mean = ((n*old_mean)+temp)/(n+1) जैसा तरीका

  • दिलचस्प challenge है, लेकिन सिर्फ Java तक सीमित होना अफ़सोस की बात है। लोग जब खुद JVM bytecode हाथ से बनाना शुरू करेंगे, उसका इंतज़ार है

    • चर्चा देखने पर लगता है कि कई भाषाओं में submissions हैं। Go, Rust, Python, C++ आदि हैं
      [0] https://github.com/gunnarmorling/1brc/discussions
    • या फिर “इसे Java में लिखा होना चाहिए” का मतलब “रन शुरू करने के लिए JVM का इस्तेमाल होना चाहिए” भी निकाला जा सकता है, और Java से दूसरा process चलाना तो निश्चित रूप से संभव है

  • मज़ेदार है। Advent of Code के बाद की अनौपचारिक मस्ती जैसा लगता है
    अगर भाषाओं के बीच निष्पक्ष तुलना करनी है, तो make और build time भी शामिल होना चाहिए। Java/Maven को मैंने कुछ सालों से इस्तेमाल नहीं किया, लेकिन ./mvnw clean verify का download 2 मिनट से चलता देख कर वजह फिर याद आ गई

    • Java build time बहुत तेज़ होता है। अभी जो मापा जा रहा है, वह internet speed है
      और incremental compile build tool के तौर पर Gradle ज़्यादा तेज़ है
    • अगर build time शामिल करना है, तो programming time भी शामिल करना चाहिए, और दोनों को उस संख्या से भाग देना चाहिए जितनी बार code अपने पूरे जीवनकाल में चलेगा
      programming सीखने में लगा समय का उचित अनुपात भी जोड़ना चाहिए
      ऐसे challenge में बहुत naïve version के जीतने की संभावना काफ़ी ज़्यादा होगी, और यह न सिर्फ अवास्तविक है बल्कि challenge के उद्देश्य के भी ख़िलाफ़ है
    • समझ नहीं आता clean क्यों किया जा रहा है
      cache फेंक कर फिर उसे slow कहना जैसी बात है
    • Maven की ज़रूरत नहीं है
      लिखा है कि external dependencies इस्तेमाल नहीं की जा सकतीं

  • Czech Technical University के C course में बिल्कुल ऐसा ही एक assignment था
    सभी छात्रों की submissions का लगातार leaderboard पर मूल्यांकन होता था, और बेहतर grade के लिए extra points, यानी लगभग status points, पाने के लिए कई छात्र optimization पर दर्जनों घंटे खर्च करते थे
 
dlehals2 2024-01-10

पहला स्थान 6 सेकंड है.. वाकई हैरान करने वाला है।