सबसे तेज़ branchless binary search

• यह लेख मानक std::lower_bound फ़ंक्शन से दोगुना तेज़ और छोटा एक सामान्य binary search C++ implementation पर चर्चा करता है.
• नई implementation "branchless" है क्योंकि यह branch/conditional jump की बजाय conditional move instructions में compile होती है.
• Binary search इस तरह काम करता है कि sorted list को बीच के item पर दो भागों में बाँटा जाता है, और बीच के मान की दिए गए मान से तुलना की जाती है. तुलना के परिणाम के आधार पर तय किया जाता है कि खोज दो सूचियों में से किसमें जारी रखनी है.
• यह लेख branch prediction की अवधारणा पर भी चर्चा करता है. यह एक ऐसी तकनीक है जिसमें processor instructions को parallel में चलाकर गति बढ़ाता है. लेकिन binary search अनुमान लगाना कठिन होने के कारण branch prediction इसके लिए आदर्श नहीं है.
• लेखक standard implementation और branchless_lower_bound version से भी तेज़ नई binary search implementation, sb_lower_bound, प्रस्तुत करते हैं. यह तेज़ है क्योंकि loop के भीतर instructions कहीं कम हैं.
• लेखक एक और तेज़ version, bb_lower_bound, भी प्रस्तुत करते हैं, जो search list को विभाजित करने का अलग तरीका इस्तेमाल करता है.
• लेख के अंत में सुझाव दिया गया है कि यदि किसी program का सबसे धीमा हिस्सा ऐसे search और/या comparison शामिल करता है जिनका processor अनुमान नहीं लगा सकता, तो clang को -mllvm -x86-cmov-converter=false के साथ आज़माएँ. और यदि आपको और तेज़ binary search चाहिए, तो sb_lower_bound आज़माएँ.
• लेखक नई binary search implementations के लिए code भी देते हैं और हर एक के performance पर विस्तार से चर्चा करते हैं.
• यह लेख sb_lower_bound के एक refactored version के साथ update किया गया है, जो hot loop में assembly instructions की संख्या 9 से घटाकर 8 कर देता है, जिससे गति में थोड़ा सुधार हुआ है.
• लेखक prefetching की अवधारणा पर भी चर्चा करते हैं. यह एक तकनीक है जिसमें memory के किसी खास हिस्से को cache में पहले से लाया जाता है, ताकि prefetch किया गया data वास्तव में ज़रूरत पड़ने पर केवल L1/L2 cache latency ही हो. 256KB+ के लिए prefetching जोड़े गए sb_lower_bound version भी दिया गया है.
• यह लेख Mihail Dumitrescu ने लिखा है और 24 जून 2023 को प्रकाशित हुआ था.

[GN⁺]

Hacker News राय

• लेख branchless binary search की अवधारणा और इसके संभावित फ़ायदों पर चर्चा करता है।
• एक टिप्पणी branch हटाने की आवश्यकता पर सवाल उठाती है और सुझाती है कि branch prediction failure से होने वाला pipeline stall आर्किटेक्चर का मूलभूत हिस्सा नहीं है।
• टिप्पणी आगे समझाती है कि हर काम मूल रूप से एक branch है, और ये branch performance को इसलिए नुकसान नहीं पहुँचाते क्योंकि ये main pipeline के branch नहीं हैं।
• एक अन्य टिप्पणी lowerBound को implement करने के लिए Nim भाषा के उपयोग का सुझाव देती है, जिसे "bare-metal" भाषा में compile किया जाता है।
• इस पर चर्चा है कि code पहला match लौटाता है या कोई भी match, और code के काम करने के तरीके को समझने के महत्व पर ज़ोर दिया गया है।
• एक टिप्पणी ब्लॉग पोस्ट की सहज परिचयात्मक शैली की प्रशंसा करती है, जो सबसे तेज़ सामान्य binary search C++ implementation को जल्दी प्रस्तुत करती है।
• टिप्पणियों में कहा गया है कि Zig stdlib binary search के लिए C++ को call नहीं करता, और Zig stdlib के binary search का लिंक दिया गया है।
• binary search और branch की समस्या पर चर्चा में सुझाव दिया गया है कि समस्या branch में नहीं, बल्कि उस data dependency में है जहाँ comparison पूरा होने तक अगला memory location पता नहीं चलता।
• टिप्पणियों में Cascade Lake processor पर binary search performance के परिणाम साझा किए गए हैं, और सुझाव दिया गया है कि इस विशेष code को optimize करने में clang, gcc से खराब है।
• एक टिप्पणी "BUT RUST" लिंक के गंतव्य पर सवाल उठाती है और कहती है कि यह लिंक पुराना लगता है।
• टिप्पणियों में कहा गया है कि परिणाम अधिक जटिल comparison function के साथ कायम नहीं रहते, और सबसे अच्छा performance primitive type के लिए sb_lower_bound और अन्य मामलों में std::lower_bound का उपयोग करके मिल सकता है।
• आख़िरी टिप्पणी में कहा गया है कि unpredictable property अब cmov conversion pass को प्रभावित करती है, और अतिरिक्त जानकारी के लिए एक लिंक दिया गया है।