1BRC प्रतियोगिता का परिचय
- 1BRC प्रतियोगिता में यह अनुमान लगाया गया था कि "usual suspects" को प्रोसेस करने के बाद CSV फ़ाइल से तापमान parse करना bottleneck बन जाएगा.
- तापमान चार रूपों में आ सकता है:
-XX.X, -X.X, X.X, XX.X; शुरुआत में Double.parseDouble() लाइब्रेरी कॉल का उपयोग किया गया था.
- लेकिन जल्द ही custom solutions सामने आए, और उनमें से एक बिना loop के केवल दो branches वाला optimized तरीका लगा.
- फिर Quân Anh Mai(@merykitty) के प्रस्तुत solution ने Twitter पर #1BRC हैशटैग को गरमा दिया. इस solution में
if statement के बिना सिर्फ एक ही file read का उपयोग किया गया था.
merykitty के जादुई SWAR का विश्लेषण
- merykitty का कोड केवल 18 ALU operations से बना है और इसमें
numberOfTrailingZeros() नाम की एक low-level function call शामिल है.
- इनपुट
long संख्या में CSV से 8 bytes आते हैं, और आउटपुट में integer रूप का तापमान मिलता है (वास्तविक तापमान का 10 गुना).
- इस तकनीक को "SIMD Within A Register"(SWAR) कहा जाता है, और यह मानक CPU registers और instructions का उपयोग करती है.
- कोड में यह चरण शामिल हैं: संख्या negative है या नहीं, इसका पता लगाना; sign character हटाना; decimal point की position ढूँढना; content को template के अनुसार align करना; ASCII characters को numeric values में बदलना; हर digit पर weight लागू करके सबको जोड़ना; और अंत में sign लागू करना.
- ये सभी चरण केवल ALU operations का उपयोग करके किए जाते हैं.
निष्कर्ष
- merykitty ने कुछ ही दिनों में यह सब अकेले कैसे कर लिया, यही असली रहस्य है, जिसे किसी blog post में समझाया नहीं जा सकता.
- QuestDB open source है और Apache 2.0 license के तहत तेज़ data insertion और SQL analytics capabilities प्रदान करता है.
GN⁺ की राय
- यह लेख सिर्फ तापमान parsing की समस्या को हल करने के लिए बनाई गई SWAR तकनीक की जटिलता और रचनात्मकता को दिखाता है. यह programming में bit operations की ताकत और optimization के महत्व को रेखांकित करता है.
- ऐसा approach खासकर उन शुरुआती software engineers के लिए दिलचस्प case बन सकता है, जो system programming या performance-sensitive applications के development में रुचि रखते हैं.
- bit operations और optimization की समझ बढ़ाने के लिए ऐसे संबंधित topics या problems को कवर करने वाली online coding competitions या tutorials देखना उपयोगी होगा.
- इस तकनीक को वास्तविक industrial environments में कैसे लागू किया जा सकता है, और क्या अन्य databases या systems भी इसी तरह की optimization techniques का उपयोग करते हैं, इस पर आगे और research की ज़रूरत है.
- QuestDB जैसे systems अपनाते समय सिर्फ performance improvement ही नहीं, बल्कि maintainability, code readability, और long-term technical support जैसे अन्य factors पर भी विचार करना चाहिए.
1 टिप्पणियां
Hacker News राय
simdjson पेपर से संबंधित Hacker News टिप्पणियों का सार:
कोड कॉन्टेक्स्ट की व्याख्या: प्रस्तुत समाधान शानदार है, लेकिन इसके लिए यह मानना पड़ता है कि डेटा अच्छी तरह संरचित है। कुशल error checking और recovery फीचर अनुभवी parser में बहुत मूल्यवान होते हैं।
नंबर parsing तकनीक: संख्या bitfield को 10 की अलग-अलग powers से गुणा करना और MUL के जरिए shift/जोड़ करना एक जानी-पहचानी तकनीक है। Lemire के ब्लॉग का संदर्भ दिया गया है।
SWAR(SIMD Within A Register) पर व्याख्या: Java/Scala में byte array view var handle का उपयोग करके efficient SWAR routine लागू करने के कई उदाहरण हैं।
SWAR की सरल परिभाषा: "SIMD Within A Register" का मतलब है एक ही register के भीतर SIMD operations करना।
BRC(Branchless Ray Casting) के I/O bottleneck पर सवाल: यह समझ में नहीं आता कि bottleneck CPU कैसे हो सकता है।
68000 पर SWAR इस्तेमाल का अनुभव: एक बार में 4 bytes को parallel process करना संभव था, लेकिन overflow handling मुश्किल था। संबंधित लेख बहुत पसंद आया।
state space और superoptimizer: state space छोटा होने की वजह से, क्या ऐसा कोई superoptimizer मौजूद है जो इसी तरह के नतीजे दे सके?
AVX instructions और Java का SIMD support: यह algorithm AVX instructions का उपयोग करके 32x parallel चल सकता है, लेकिन Java कुछ खास मामलों को छोड़कर SIMD CPU usage को ठीक से support नहीं करता, यह अफसोस की बात है।
bit manipulation की समझ: इस लेख ने bit manipulation को पहले की किसी भी चीज़ से बेहतर समझने में मदद की, और 1BRC challenge के लिए Java solution प्रस्तुत करने वाले लेखक को धन्यवाद।