सबसे तेज़ branchless binary search

(mhdm.dev)

1 पॉइंट द्वारा GN⁺ 2023-08-13 | 1 टिप्पणियां | WhatsApp पर शेयर करें

sb_lower_bound std::lower_bound जैसा ही interface बनाए रखता है, लेकिन जब comparison branch conditional move (cmov) में compile होती है, तब यह सामान्य binary search से अधिकतम 2 गुना तेज़ दिखता है
binary search के comparison result में search position पहले से पता नहीं होती, इसलिए branch prediction miss बार-बार होते हैं, और x86 पर clang -mllvm -x86-cmov-converter=false option इसे कम करने में मदद करता है
यह implementation हर loop में length को आधा करती है और comparison result के आधार पर केवल first को update करती है, जिससे instruction count कम होता है, और 2^k <= n < 2^(k+1) range में हमेशा k+1 comparisons करती है
clang -cmov benchmark में average execution time std::lower_bound के लिए 61.30ns, sb_lower_bound के लिए 33.24ns, और bb_lower_bound के लिए 32.73ns था, जबकि geometric mean भी क्रमशः 39.17ns, 19.81ns, 21.33ns था
8-byte string search जैसे मामलों में जहाँ comparison function धीमा था, std::lower_bound कभी-कभी थोड़ा आगे रहा, और बड़े arrays में prefetching जोड़ने वाला variant std::lower_bound से average में लगभग 2.3 गुना तेज़ था

`sb_lower_bound` की बुनियादी संरचना

sb_lower_bound std::lower_bound जैसी ही C++ function है
- input हैं first, last, value, comp
- return value वह iterator है जहाँ comparison पहली बार fail होती है, और अगर सभी elements condition satisfy करते हैं तो last लौटाया जाता है
core loop length को आधा करती है, और केवल तब first को आगे बढ़ाती है जब comp(first[length], value) true हो
यहाँ “branchless” का मतलब यह नहीं कि if गायब हो जाता है, बल्कि यह कि संबंधित if conditional jump की जगह cmov जैसी conditional move instruction में compile होता है
clang में -mllvm -x86-cmov-converter=false option देने पर यह form conditional move में compile हो सकता है

जहाँ `std::lower_bound` धीमा पड़ता है

सामान्य binary search middle element और value की तुलना करके left या right interval चुनती है
जब target की position पता नहीं होती, तब if (comp(first[half], value)) अक्सर predict करना मुश्किल branch बन जाती है
CPU branch prediction से अगला instruction पहले चलाने की कोशिश करती है, लेकिन prediction गलत होने पर किया गया काम फेंकना पड़ता है
conditional move का उपयोग comparison result के आधार पर value चुनते हुए conditional jumps को कम कर सकता है
clang -cmov std::lower_bound के कुछ if/else को भी conditional move में बदल सकता है, जिससे यह लगभग 25% तेज़ हुआ
gcc में ऐसी स्थिति में conditional move force करने का अच्छा option नहीं है, और sb_lower_bound भी अभी optimization level की परवाह किए बिना branchless code emit नहीं करता

comparison count के नज़रिए से “optimal” search

यहाँ “optimal” का मतलब सबसे कम comparisons वाली binary search है
size n की list में std::lower_bound के possible results element positions n और end position 1 मिलाकर कुल n+1 होते हैं
अगर list size 2^k - 1 हो, तो possible results 2^k होते हैं, और हर comparison true/false के रूप में 1 bit information देती है, इसलिए optimal comparison count k है
length 2^k - 1 जैसे “nice” case में बहुत छोटे loop से optimal search संभव है
अगर length मेल नहीं खाती, तो [0, 1, 2, 3, 4, 5] में value 4 होने जैसी स्थिति में out-of-range access हो सकता है

`sb_lower_bound` की performance और सीमाएँ

sb_lower_bound जब even length वाले interval को बाँटता है, तब comparison true होने पर भी कुछ मामलों में पर्याप्त elements skip नहीं करता
2^k <= n < 2^(k+1) range में यह हमेशा k+1 comparisons करता है
उसी range में std::lower_bound k या k+1 comparisons करता है, और average में लगभग log2(n+1) comparisons करता है
comparisons ज़्यादा हो सकती हैं, लेकिन loop के अंदर instructions बहुत कम होने से कुल execution time फिर भी तेज़ आता है
अगर comparison function बहुत धीमा हो, तो k+1 और log2(n+1) comparisons का फर्क performance पर असर डाल सकता है
gcc में conditional move force करने के लिए x86-specific inline assembly से cmov इस्तेमाल किया जा सकता है, लेकिन सरल तरीका instruction count बढ़ा देता है और दूसरे तरीके में type-specific assembly अलग से लिखनी पड़ती है

और तेज़ variant `bb_lower_bound`

bb_lower_bound पहले interval को अलग तरीके से बाँटता है जब तक length 2^k - 1 form तक नहीं पहुँच जाती, फिर तेज़ दूसरे loop से search करता है
length & (length + 1) का उपयोग यह पहचानने के लिए होता है कि length 11..1, यानी 2^k - 1, form में है या नहीं
non-ideal lengths में auto step = length / 8 * 6 + 1 जैसा MAGIC value इस्तेमाल होता है ताकि जल्दी “nice” interval के पास पहुँचा जा सके
step आम तौर पर length / 2 से कम नहीं होना चाहिए ताकि तेज़ loop में जल्दी प्रवेश हो, लेकिन अगर यह length के बहुत पास हो जाए तो binary search का फायदा खो जाता है
break की वजह से bb_lower_bound branch वाला form बन जाता है
सभी lengths के लिए सबसे तेज़ step की precomputed table का तरीका अभी तक explore नहीं किया गया है

पूरी तरह branchless implementation ज़रूरी नहीं कि तेज़ हो

64-bit machine पर sb_lower_bound का loop अधिकतम 64 बार चलता है, इसलिए switch और जानबूझकर fall-through का उपयोग करके length check भी हटाने वाला “पूरी तरह branchless” version बनाया जा सकता है
इस तरीके में std::bit_width(length) के जरिए जितनी comparisons चाहिए उतने code position पर jump किया जाता है
वास्तविक performance इससे बेहतर नहीं हुई
आधुनिक x86 CPUs loop condition जैसी predictable branches को अच्छी तरह handle करती हैं, इसलिए length check हटाने का लाभ नहीं मिला
templates, macros, और 64 cases की copy-editing से बचने के लिहाज़ से भी सामान्य loop बेहतर माना गया

benchmark results

average execution time (ns) में clang -cmov के आधार पर results इस प्रकार थे
- std::lower_: 61.30
- branchless_lower_: 43.43
- asm_lower_: 54.32
- sb_lower_: 33.24
- sbm_lower_: 35.54
- bb_lower_: 32.73
geometric mean execution time (ns) में भी sb_lower_ सबसे कम था
- std::lower_: 39.17
- branchless_lower_: 25.14
- asm_lower_: 31.21
- sb_lower_: 19.81
- sbm_lower_: 20.91
- bb_lower_: 21.33
sbm_lower_bound वह variant है जो if की जगह first += comp(first[length], value) * (length + rem) form का उपयोग करके gcc को conditional move generate करने की ओर धकेलता है
यह optimization अगले gcc version में गायब हो सकती है, इसलिए comment और सावधानी ज़रूरी है
benchmark command में g++-10, clang++-10, clang++-10 -mllvm -x86-cmov-converter=false का उपयोग हुआ, और -march=haswell भी जोड़ा गया
-march=native या -march न देने से ranking पर बड़ा असर नहीं पड़ा, और test Intel i7 Kaby Lake पर किया गया

branch prediction miss की माप

perf से मापे गए सामान्य clang run में लगभग 6.94 अरब branches और लगभग 1.20 अरब branch-misses दर्ज हुए, और branch-misses ratio 17.34% था
clang -cmov run में लगभग 4.07 अरब branches और लगभग 3.595 करोड़ branch-misses दर्ज हुए, और branch-misses ratio घटकर 0.88% रह गया
-cmov ने लगभग 2.9 अरब branches और लगभग 1.2 अरब branch failures हटा दिए
हटाई गई branches में prediction miss की संभावना लगभग 41% थी
यह पूरी तरह unpredictable branches के लिए अपेक्षित 50% के काफ़ी करीब है

धीमे comparison function में नतीजे बदल जाते हैं

और धीमे comparison function की स्थिति देखने के लिए 8-byte string search का test किया गया
average execution time (ns) में std::lower_bound sb_lower_bound से थोड़ा तेज़ या लगभग बराबर था
- gcc: std::lower_ 160.01, sb_lower_ 165.66
- clang: std::lower_ 157.71, sb_lower_ 162.68, bb_lower_ 157.22
- clang -cmov: std::lower_ 156.06, sb_lower_ 164.71, bb_lower_ 157.48
इस case में std::lower_bound, sb_lower_bound से बहुत थोड़ा लेकिन लगातार तेज़ रहा
library सर्वोत्तम performance के लिए primitive types पर सीधे sb_lower_bound और बाकी मामलों में std::lower_bound का उपयोग कर सकती है

assembly में दिखने वाला अंतर

std::lower_bound का clang -cmov hot loop cmova, cmovbe जैसी conditional moves शामिल करता है, लेकिन length और position update के लिए कई instructions इस्तेमाल करता है
sb_lower_bound का hot loop half length, remainder, और move होने वाला pointer calculate करके cmova से first update करता है
branchless_lower_bound की assembly बहुत छोटी और साफ़ है, लेकिन performance test में sb_lower_bound ने कम overhead के साथ बेहतर result दिया

update: और छोटा हुआ `sb_lower_bound`

orlp.net author की comment के बाद sb_lower_bound को इस तरह refactor किया जा सकता है कि hot loop assembly instructions 9 से घटकर 8 रह जाएँ
मुख्य बात यह है कि length - half, half + length % 2 के बराबर होता है
refactored form half = length / 2 calculate करता है, comparison true होने पर first += length - half करता है, और फिर length = half से update करता है
clang -cmov में average execution time लगभग 33ns से घटकर लगभग 32ns हो गया

बड़े arrays में prefetching असरदार रही

comments में सुझाया गया prefetching ज़रूरी memory को पहले से L1/L2 cache में लाने का तरीका है ताकि वास्तविक access के समय delay कम हो
उदाहरण latency: L1 लगभग 4 cycles, L2 लगभग 12 cycles, L3 लगभग 40 cycles, memory लगभग 200 cycles
gcc और clang दोनों __builtin_prefetch() को support करते हैं
length / 4 position prefetch करने पर 2 में से 1 व्यर्थ जाता है, और length / 8 तक जोड़ने पर 6 में से 5 व्यर्थ होते हैं
prefetch position calculation और call का खुद का भी overhead है, और छोटे किए गए hot loop में यह cost महत्वपूर्ण हो जाती है
कई prefetch strategies 256KB से छोटे arrays में मददगार नहीं थीं
256KB से बड़े arrays में prefetching जोड़ने वाला sbp_lower_bound लगभग 40 लाख entries, यानी 16MB तक के test में average execution time लगभग 32ns से घटकर लगभग 26ns तक ले आया
इसके बाद लगभग 12.8 करोड़ entries, यानी 512MB तक बढ़ाए गए test में prefetch version average time के हिसाब से std::lower_bound से लगभग 2.3 गुना तेज़ था
- तुलना के लिए std::lower_bound लगभग 161ns और prefetch version लगभग 71ns था

बड़े datasets में observations और alternatives

बहुत बड़े sizes पर clang -cmov से बना branchless std::lower_bound, branch वाले version से धीमा था
आधुनिक CPUs predicted branch का पीछा करते हुए memory load और speculative execution आगे बढ़ा सकती हैं, जो व्यवहार में prefetching जैसा काम कर सकता है
sbpm_lower_bound, sbm_lower_bound में prefetching जोड़ने वाला version है, और boolean multiplication से gcc को branchless code generate करने की ओर धकेलता है
10 लाख से 1 करोड़ elements के बीच performance graph में उछाल दिखा, इसलिए सिद्धांततः इससे भी तेज़ implementation की गुंजाइश है
लेकिन prefetching code धीरे-धीरे जटिल होता जाता है और magic constants बढ़ते जाते हैं, इसलिए gcc/libstdc++ या llvm/libc++ में contribution की संभावना complexity बढ़ने के साथ कम होती दिखी
std::lower_bound की सीमाओं को तोड़ने वाले alternatives में Eytzinger Binary Search शामिल है, जो input array को binary median heap form में rearrange करके cache-friendly lookup देता है
Sergey Slotin at CppCon 2022 के int 16-ary tree test में यह std::lower_bound से 7x से 15x तक तेज़ निकला

code और उपयोग की शर्तें

अगर search या comparison आपके program का सबसे धीमा हिस्सा है, और processor comparison result को predict नहीं कर पाता, तो x86 पर clang का -mllvm -x86-cmov-converter=false option आज़माया जा सकता है
और तेज़ binary search चाहिए तो sb_lower_bound आज़माया जा सकता है, और gcc में sbm_lower_bound भी एक विकल्प है
code MIT license के तहत जारी किया गया है
code और benchmark github.com/mh-dm/sb_lower_bound/ पर देखे जा सकते हैं

1 टिप्पणियां

GN⁺ 2023-08-13

Hacker News की राय

जब भी लोगों को branches हटाने की कोशिश करते देखता हूँ, तो सोचता हूँ कि क्या वे जानते हैं कि branch prediction failure से लंबी pipeline का रुक जाना CPU architecture का अनिवार्य हिस्सा नहीं है
pipeline लंबी इसलिए होती है क्योंकि execution से ठीक पहले बहुत सारा analysis और transformation किया जाता है, जबकि यह कोई ऐसा algorithm नहीं है जिसमें state dependency बहुत ज़्यादा हो, इसलिए इसका अधिकांश हिस्सा पहले से किया जा सकता है
Transmeta Crusoe CPU इसी तरह काम करता था, और ऐसी दुनिया की कल्पना की जा सकती है जहाँ branches की चिंता न करनी पड़े
और गहराई से देखें तो हर operation, bit state को देखकर result बदलने वाली एक branch ही है, लेकिन ALU के अंदर की ये local branches main pipeline पर मौजूद branches नहीं होतीं, इसलिए performance को बहुत नुकसान नहीं पहुँचातीं
- क्या आप Dave हैं? :-) पहले superscalar CISC और uniscalar RISC की तुलना hourly throughput और instructions per clock के लिहाज़ से करने वाला एक paper था
  मुझे याद है कि उस समय srk से भी कहा था कि IPC और throughput में से कौन-सा metric चुनते हैं, यह इस बात को प्रभावित करता है कि आप किसे अच्छा और बुरा मानते हैं
  IPC वाला पक्ष मानता है कि अगर higher IPC बनाया जाए तो process technology clock बढ़ा देगी और सब जीतेंगे; throughput वाला पक्ष ज्यादा व्यावहारिक approach लेता है कि Moore's law मर चुका है और silicon को और तेज़ चलाने पर वह पिघल जाएगा, इसलिए ISA को smart तरीके से design करने वाला पक्ष जीतेगा
  पिछले 20 वर्षों में दोनों पक्षों ने सफलता और निराशा दोनों देखी हैं, और आजकल RISC-V का CPU architecture में फिर से इसी सवाल पर लौटना दिलचस्प है
  instruction set की flexibility के आधार पर modern superscalar ideas कैसे जोड़े जाते हैं, यह follow करने के लिए भी यह अच्छी जगह है, और लंबे समय में मुझे लगता है कि यही पक्ष जीतेगा
- यह पूरी तरह गलत सोच है
  Transmeta का translation branch cost को खत्म नहीं करता था
  मुझे याद है कि Transmeta में काम करने वाले Linus ने comp.arch thread में कुछ ऐसा कहा था कि “CPU का काम cache misses को जितनी जल्दी हो सके पैदा करना है”
  compulsory cache misses मौजूद होते हैं, और कोई भी JIT उन्हें हटा नहीं सकता
  असली दुनिया में, आज जैसे बड़े caches होने पर भी capacity misses से बचा नहीं जा सकता
  Itanium ने भी माना था कि static analysis से branch cost खत्म की जा सकती है; बस याद कर लें कि उसका नतीजा क्या हुआ
  programmer आत्मविश्वास से यह निष्कर्ष निकालने से पहले कि वे modern processors से बेहतर चीज़ आसानी से बना सकते हैं, काश कुछ computer architecture की किताबें पढ़ लें
  मेरे हिसाब से वे current processors में लगी बौद्धिक मेहनत के पैमाने को कम से कम 7 अंकों जितना कम आँक रहे हैं
- state न भी हो सकती हो, फिर भी यह compile time पर अज्ञात factors पर बहुत निर्भर करता है
  उनमें से एक है process किया जाने वाला input data
  binary search इसका बिल्कुल सही उदाहरण है, क्योंकि compiler को पता नहीं होता कि result किस position पर मिलेगा
  दूसरा है microarchitecture, खासकर cache hierarchy और execution units की configuration
  अगर ISA को ऐसे instructions वाला बना दें जो current CPU के micro-operations जैसे हों, तो हर microarchitecture के लिए फिर से compile करना पड़ेगा
  हालांकि इसे तकनीकी रूप से OS JIT से हल किया जा सकता है, जैसे आजकल GPU में programs को bytecode format (DXBC, SPIR-V, NVPTX) में distribute किया जाता है और user-mode GPU driver उन्हें actual hardware instructions में recompile करता है
  इससे बड़ा variable यह है कि दूसरे CPU threads ऐसा code चला रहे होते हैं जिसे जाना नहीं जा सकता
  hyperthreading हटाकर cores को independent बना दें, तब भी L3 cache, external memory, I/O bandwidth, power और heat जैसे chip-wide shared resources बने रहते हैं
- मुझे लगता है कि असली मुद्दा branch की definition में है
  अगर हर चीज़ को Branch™ के रूप में redefine कर दें, तो actual branch न होने वाली चीज़ों सहित कुछ Branch™ पहले से compute की जा सकती हैं
  लेकिन आम तौर पर branch removal से मतलब if/else जैसे code में सचमुच calculation path के अलग-अलग हो जाने वाले cases से नहीं होता क्या
  ऐसी दुनिया में भी useful optimization संभव होगी, लेकिन वह कई future results को simultaneously calculate करने की कोशिश करने वाली Branch™ तक सीमित होगी
- pipeline लंबी होने की वजह को इस तरह भी कहा जा सकता है कि processor के अंदर साथ-साथ किए जा सकने वाले independent work बहुत सारे होते हैं
  जब भी independently perform किए जा सकने वाले operations होते हैं, उतनी ही उन्हें simultaneously execute करने की संभावना बनती है
  मैं सिर्फ decode, fetch और execute की बात नहीं कर रहा
  अगर independent ALU और shifter हों, तो add करते समय shift भी किया जा सकता है; और dedicated adder और multiplier हों, तो दोनों को simultaneously try न करने की कोई वजह नहीं है
  इसका मतलब है कि आप कई instructions को एक साथ in-flight रखना चाहेंगे, और processing speed से भी तेज़ instructions fetch और decode कर पाने होंगे
  साथ ही यह स्वाभाविक रूप से ऐसी स्थिति की ओर ले जाता है जहाँ आप reorder करना चाहेंगे ताकि N Add instructions किसी independent Shift को दिखने से न रोकें
  आप सोच सकते हैं कि current structure ज़रूरत से ज़्यादा complex है, और शायद आप गलत भी न हों
  फिर भी current structure बनाने में बहुत भारी engineering लग रही है, इसलिए अगर आपको लगता है कि इस तरीके के बिना कहीं तेज़ बनाया जा सकता है, तो यह दावा कितना सही है, इसे गहराई से खंगालना ज़रूरी है
“काश यह सब लिखने के लिए कोई साफ़ और तेज़ bare-metal language होती…” वाले हिस्से में लेखक ने “BUT RUST..” और “BUT ZIG..” फुटनोट डाले हैं, लेकिन सोच रहा हूँ कि Nim कैसा रहेगा
लगता है lowerBound का native library implementation मौजूद है: https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al...
सख्ती से कहें तो यह “bare-metal” language नहीं है, लेकिन C या C++ में compile होती है, इसलिए यह देखना दिलचस्प होगा कि यहाँ किस तरह के code में compile होती है
और यह भी जानना चाहूँगा कि C में आखिर दिक्कत क्या है
- Zig की binary search यहाँ है, और यह optimized न की गई textbook-style implementation है: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...
  TigerBeetle अपनी branchless implementation इस्तेमाल करता है: https://github.com/tigerbeetle/tigerbeetle/blob/e996abcf7154...
- C में बराबर की generic sort function बनाएं तो, बहुत अच्छा करने पर भी काफी बिखरा हुआ सहायक code चाहिए होगा
  ऐसे use case ही वजह हैं कि C++ templates की जरूरत पड़ती है
- C में, उदाहरण के लिए, undefined behavior बहुत ज्यादा है
  C साफ़-सुथरी नहीं है
मुझे अभी भी पक्का नहीं है कि यह lower_bound है या नहीं
हो सकता है मैं code गलत पढ़ रहा हूँ, लेकिन duplicates होने पर यह सबसे पहला matching item नहीं, बल्कि कोई भी matching item लौटाता हुआ लगता है
अगर comparison function autocomplete के लिए किसी खास string prefix को खोज रहा हो, तो unique list में भी कई items match कर सकते हैं, और उस स्थिति में हमें list का सबसे पहला item चाहिए होता है
- हर match पर बची हुई length आधी कर दी जाती है, और loop सिर्फ length 0 होने पर ही बाहर निकलता है, इसलिए इसे पहला item लौटाना चाहिए
- अगर ज्यादा speed चाहिए और exact कौन-सा matching item है, इसकी परवाह नहीं है, तो ऐसा option होना अच्छा लगता है
- मुझे तो यह सबसे पहला matching item लौटाता दिखता है
  जानना चाहूँगा कि आपको ऐसा क्यों नहीं लगता
काश सभी blog posts इसी तरह शुरू होतीं: “आप व्यस्त होंगे, इसलिए सीधे मुद्दे पर आते हैं। यह रही सबसे तेज़, generic और simple C++ binary search implementation”
Zig standard library binary search के लिए C++ को call नहीं करती
मौजूदा binary search यहाँ है: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...
- Version-pinned link: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...
ठीक से समझ नहीं आ रहा
binary search और branches की समस्या branch खुद नहीं है, बल्कि यह है कि comparison खत्म होने तक आपको नहीं पता होता कि array से अगली कौन-सी memory location fetch करनी है
branch इस्तेमाल करें या कुछ और, फर्क नहीं पड़ता; असली बात यह है कि आप processor से आखिर क्या करवाना चाहते हैं
data dependency है
middle index पढ़ने से पहले आप नहीं जान सकते कि ऊपर वाले range में search करना है या नीचे वाले range में
अनुमान लगाकर दोनों तरफ की reads issue की जा सकती हैं, और तब dependency हल हो जाएगी, लेकिन memory traffic बढ़ जाएगा
यही मुख्य सवाल है कि यह सही trade-off है या नहीं; सिर्फ branch हटाना जवाब नहीं है
- बड़े arrays में prefetching सही trade-off है
  article के अंत में इसे cover किया गया है: https://mhdm.dev/posts/sb_lower_bound/#prefetching
- सही
  इसलिए सच में तेज़ binary search Eytzinger array layout इस्तेमाल करती है: https://algorithmica.org/en/eytzinger
- अगर array पूरी तरह L1 cache में फिट हो जाए, तो क्या branch prediction miss की cost memory fetch से कहीं ज्यादा नहीं होगी?
मेरे Cascade Lake processor पर -mllvm -x86-cmov-converter=false binary search performance को लगभग आधा कर देता है
numbers 100MB uint32 array पर प्रति bsearch nanoseconds में हैं
clang 15.0.7 इस खास code optimization में gcc 13.2.1 से काफी खराब दिखता है
assembly यहाँ देखी जा सकती है: https://godbolt.org/z/cbx5Kdjs6
gcc assembly काफी ज्यादा साफ़ दिखती है

Benchmark gcc clang clang -cmov

slow u32 23.4 46.7 45.8

fast u32 18.1 19.8 31.4
- तो फिर https://mhdm.dev/posts/sb_lower_bound/#prefetching देखना चाहिए
  100MB इतना बड़ा है कि branch वाला version थोड़ा बेहतर निकलता है, लेकिन इसलिए नहीं कि वह बेहतर है, बल्कि x86 की speculative execution characteristics की वजह से
क्या किसी को पता है कि “BUT RUST” link असल में कहाँ जाना था?
version-pinned नहीं था, इसलिए लगता है पहले ही टूट चुका है, और शायद starts_with documentation comment के बीच में जाना था
- article publish होने से ठीक पहले [1] और ठीक बाद [2] के archive.org captures देखें, तो लगता है यह उस code line की ओर इशारा करना चाहता था जो अब line 2779 [3] बन गई है
  let mid = left + size / 2;

Benchmark	gcc	clang	clang -cmov
slow u32	23.4	46.7	45.8
fast u32	18.1	19.8	31.4

[1] https://web.archive.org/web/20230602210213/https://doc.rust-...

[2] [https://web.archive.org/web/20230709221353/https://doc.rust-...](<https://web.archive.org/web/20230709221353/…;)

[3] [https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779](<https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779>;)

Rust के binary search implementation से लिंक करना था
https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#... पर अपडेट किया गया
दिलचस्प है कि ज़्यादा जटिल comp comparison function में परिणाम बरकरार नहीं रहते
लेख में ID, फोन नंबर, account, keyword जैसी स्थितियों की कल्पना की गई थी, यानी कुछ हद तक व्यावहारिक binary search scenario जहां comparison function धीमा होता है, और इसलिए 8-byte string search को test किया गया
इस मामले में std::lower_bound, sb_lower_bound से बहुत थोड़ा, लेकिन लगातार तेज़ है; और हमेशा best performance पाने के लिए library को primitive types को सीधे handle करते समय sb_lower_bound, और बाकी मामलों में std::lower_bound इस्तेमाल करना चाहिए, ऐसा कहा गया है
यहां का analysis देखना चाहता हूं
- मुझे लगता है कि ऐसा branch prediction की वजह से होता है: यह कई comparisons को एक साथ pipeline में डाल सकता है और predictor के गलत होने पर वापस लौट सकता है
  अगर data और input सचमुच random हों, तो prediction लगभग आधी बार गलत होगा
  CMOV approach comparison function के बाद data dependency की वजह से अटक जाती है
  औसतन branch-based approach एक बार में दो comparisons करती है, जबकि CMOV एक करता है, इसलिए जब comparison time branch prediction failure penalty से बड़ा हो जाता है, तो reversal point आने की उम्मीद है
- अगर ऐसा है, तो primitive types के लिए binary search का कहीं बेहतर version होने की पूरी संभावना है
  पहले SIMD से मोटे तौर पर बनाया गया मेरा version memory bandwidth से bottleneck होने से पहले std::lower_bound से 3 गुना तेज़ था: https://github.com/matthewkolbe/ThinkingInSimd/tree/main/alg...
- लेख में input dataset या search keys की content को लेकर “unpredictable” कहने के अलावा कोई guarantee नहीं मिली
  मान लेते हैं कि यह pure random है, लेकिन अगर ये 8-byte strings pure information नहीं हैं, तो modern branch predictors cmov से आसानी से बेहतर performance दे सकते हैं
लगता है कि unpredictable attribute अब cmov conversion pass को प्रभावित करता है
1 जून तक की स्थिति है, इसलिए शायद clang 17/18 में आएगा: https://reviews.llvm.org/D118118

सबसे तेज़ branchless binary search

sb_lower_bound की बुनियादी संरचना

जहाँ std::lower_bound धीमा पड़ता है

comparison count के नज़रिए से “optimal” search

sb_lower_bound की performance और सीमाएँ

और तेज़ variant bb_lower_bound

पूरी तरह branchless implementation ज़रूरी नहीं कि तेज़ हो

benchmark results

branch prediction miss की माप

धीमे comparison function में नतीजे बदल जाते हैं

assembly में दिखने वाला अंतर

update: और छोटा हुआ sb_lower_bound

बड़े arrays में prefetching असरदार रही

बड़े datasets में observations और alternatives

code और उपयोग की शर्तें

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

1 टिप्पणियां

Hacker News की राय

`sb_lower_bound` की बुनियादी संरचना

जहाँ `std::lower_bound` धीमा पड़ता है

`sb_lower_bound` की performance और सीमाएँ

और तेज़ variant `bb_lower_bound`

update: और छोटा हुआ `sb_lower_bound`