इसे binary search से भी तेज़ बनाया जा सकता है
(lemire.me)- sorted array में किसी मान को खोजने के लिए आमतौर पर इस्तेमाल होने वाला binary search एक बार में सिर्फ एक मान की तुलना करता है, लेकिन आधुनिक CPU एक ही instruction से कई मानों की एक साथ तुलना कर सकते हैं, और इस क्षमता का उपयोग करने पर खोज की गति काफ़ी बढ़ाई जा सकती है
- SIMD Quad एक hierarchical search algorithm है जो array को 16-16 के ब्लॉकों में बाँटता है, फिर ब्लॉक की स्थिति को quaternary interpolation search से तेज़ी से सीमित करता है, और ब्लॉक के भीतर SIMD instructions से 16 elements की एक साथ तुलना करता है
- benchmark में Intel warm cache के आधार पर इसने binary search की तुलना में 2x से अधिक तेज़ प्रदर्शन दिखाया, और Apple cold cache पर भी 2x से अधिक तेज़ था; सभी measurement conditions में
std::binary_searchसे बेहतर रहा - array को आधा बाँटने के बजाय चार भागों में बाँटने पर instructions थोड़ी बढ़ती हैं, लेकिन Intel के बड़े arrays में memory-level parallelism का बेहतर उपयोग होता है, जिससे cold cache performance सुधरती है
- क्योंकि textbook algorithms आज के CPU की data parallelism और memory parallelism को ध्यान में रखकर नहीं बनाए गए थे, इसलिए hardware characteristics को प्रतिबिंबित करने वाले redesign से वास्तविक performance gains संभव हैं
मुख्य विचार
- binary search की संरचना एक बार में एक ही मान की तुलना करती है, लेकिन आधुनिक 64-bit ARM और x64 processors एक instruction में 8 16-bit integers की साथ में तुलना कर सकते हैं
- इस hardware क्षमता का उपयोग करने पर search unit को individual elements के बजाय block level पर बदला जा सकता है, जिससे comparisons की संख्या काफ़ी घटती है
- array को आधा बाँटने के बजाय 4-way split (quaternary search) करने पर instructions कुछ बढ़ सकती हैं, लेकिन bottleneck संभव है कि instruction count न हो, और memory-level parallelism का उपयोग भी बेहतर हो सकता है
sorted array membership check का बुनियादी तरीका
- sorted array में कोई मान मौजूद है या नहीं, यह जाँचने का सबसे सरल तरीका linear search है, जिसमें मानों को एक-एक करके देखा जाता है; C++ में
std::findसे यही प्रभाव मिलता है - बड़े arrays में binary search अधिक तेज़ होता है, और यह search range के मध्य मान के आधार पर ऊपरी या निचले आधे हिस्से को बार-बार हटाता है
- C++ का
std::binary_searchमान की मौजूदगी को boolean के रूप में लौटाता है - Roaring Bitmap format आकार 1~4096 के 16-bit integer arrays का उपयोग करता है, और मान की मौजूदगी जाँचने के लिए binary search का उपयोग करता है
SIMD Quad algorithm की संरचना
- 16-bit unsigned integers की sorted array को 16-element fixed-size blocks में विभाजित किया जाता है
- हर block के आख़िरी element को interpolation key की तरह इस्तेमाल करके लक्ष्य मान के होने की सबसे संभावित एकल block तक range को सीमित किया जाता है, फिर उस block के 16 elements को SIMD से एक साथ जाँचा जाता है
- संचालन के चरण:
- अगर elements की संख्या 16 से कम हो, तो पूरे हिस्से पर साधारण linear search
- array को लगातार 16-element blocks में बाँटा जाता है, और कुल block count
num_blocks = cardinality / 16 - block के आख़िरी element को key बनाकर current search range के 1/4 points को target value से compare किया जाता है और
baseको adjust किया जाता है - अगर block valid हो, तो ARM पर NEON और x64 पर SSE2 से 16 elements load करके parallel equality comparison किया जाता है
- जो बचे हुए elements पूरे block में शामिल नहीं होते, उन पर linear search किया जाता है
benchmark का तरीका
- array size 2~4096 के लिए 16-bit unsigned integers की sorted arrays 100,000 बनाई गईं
- हर size पर membership queries 10 million बार दो modes में चलाई गईं
- cold mode: हर query अलग array पर search करती है, जिससे cache miss का simulation होता है
- warm mode: एक ही array पर लगातार 100 बार search करके cache hit का simulation किया जाता है
- measurement target था average query time, और comparison targets थे linear search (
std::find), binary search (std::binary_search), और SIMD Quad - measurement systems थे Apple M4 (Apple LLVM) और Intel Emerald Rapids (GCC)
measurement results
- array बड़े होने पर binary search, linear search को स्पष्ट रूप से पीछे छोड़ देता है, और cold cache में data access अधिक होने से linear search और भी नुकसान में रहता है
- Intel platform: warm cache में SIMD Quad, binary search से 2x से अधिक तेज़ था; cold cache में लाभ अपेक्षाकृत कम था
- Apple platform: cold cache में SIMD Quad 2x से अधिक तेज़ था; warm cache में लाभ अधिक सीमित था
- हर स्थिति में SIMD Quad,
std::binary_searchसे तेज़ था - SIMD हिस्सा special instructions से काम कम करता है, और instructions व branches दोनों कम होने से speedup का कारण स्पष्ट है
4-way search का प्रभाव
- SIMD optimization को बनाए रखते हुए 4-way interpolation search को binary search से बदलने वाला SIMD binary version भी तुलना में शामिल था
- Apple platform पर 4-way approach का असर छोटा था
- Intel platform पर बड़े arrays की cold cache स्थिति में 4-way approach एक meaningful optimization साबित हुआ
- Intel servers पर 4-way search ने memory-level parallelism का बेहतर उपयोग किया
implementation के मुख्य बिंदु
simd_quadfunction,uint16_tarray, element countcardinality, और खोजे जाने वाले मानposको लेकर boolean लौटाता हैgapको 16 पर fixed रखा गया है;cardinality < gapहोने पर simple loop से search की जाती है- block search loop,
n > 3रहने तक 1/4, 2/4, 3/4 points पर block के आख़िरी मान को पढ़कर compare करता है, और तीन comparisons के योग सेbaseको आगे बढ़ाता है - चुने गए block में ARM NEON का
vceqq_u16या x64 SSE2 का_mm_cmpeq_epi16इस्तेमाल करके 16 elements की दो समूहों में parallel comparison की जाती है - बचे हुए elements के हिस्से में
v >= posहोने वाले बिंदु परv == posका परिणाम लौटाया जाता है
निष्कर्ष
- textbook binary search एक ठीक algorithm है, लेकिन वास्तविक performance के लिहाज़ से इसे अर्थपूर्ण तरीके से और तेज़ बनाया जा सकता है
- standard algorithms अक्सर आज के computers की ऊँची parallelism को आधार मानकर डिज़ाइन नहीं किए गए थे
- SIMD Quad, memory-level parallelism और data parallelism दोनों का लाभ उठाने की कोशिश है
- इससे भी बेहतर algorithms संभव हो सकते हैं, और अधिक रचनात्मक approaches की ज़रूरत है
- source code
- Faster intersections between sorted arrays with shotgun
1 टिप्पणियां
Hacker News टिप्पणियाँ
Daniel Lemire ने जिस low-level hardware optimization की बात की, उससे अलग मुद्दा यह है कि binary search या उसके implementation variants तब ही सबसे अच्छे होते हैं जब sorted/monotonic होने के अलावा data के बारे में कुछ भी पता न हो।
अगर data distribution के बारे में पहले से जानकारी हो, तो उस जानकारी का इस्तेमाल करके कहीं ज़्यादा तेज़ algorithm बनाया जा सकता है। कागज़ के dictionary में इंसान का शुद्ध binary search से तेज़ी से सही page range तक पहुँच जाना इसका उदाहरण है।
गणितीय रूप से sorted list search, closed-loop control algorithm से monotonic function के inverse को खोजने के ज़्यादा क़रीब है, और cost function बनाकर gradient descent या उसके accelerated variants भी इस्तेमाल किए जा सकते हैं। और सामान्य रूप से भी, ज़रूरत से ज़्यादा abstract formulation का solution लाने से बेहतर है कि जिस specific problem को सुलझाना है उसके बारे में ज़्यादा जानकारी इस्तेमाल की जाए; यह हमेशा अधिक efficient होता है और hardware को बेहतर इस्तेमाल करके मिलने वाले constant-factor improvement से कहीं बड़ी scalable speedup दे सकता है।
fixed iteration count branch predictor के लिए अच्छा है, और core loop भी target hardware के हिसाब से multiplication से बचते हुए काफ़ी tightly optimized है। इसे और चतुर बनाने की कोशिशों ने loop को और खराब ही किया, कोई फ़ायदा नहीं मिला। struct array format में size 12 है, और आम तौर पर N छोटा होता है, इसलिए और भी मुश्किल है।
मैंने bookmark नहीं किया था, इसलिए साल में लगभग दो बार उसे फिर से खोजता हूँ। किंवदंती है कि मैं अभी भी उसे खोज ही रहा हूँ।
इसी वजह से databases में B-tree standard है। Data कुछ भी हो सकता है, और अगर नई rows bulk में आ जाएँ तो उसकी characteristics कभी भी काफ़ी बदल सकती हैं।
gradient descent जैसी किसी चीज़ से lookup को तेज़ करने वाला algorithm बनाया जा सकता है, लेकिन B-tree पहले से ही बहुत तेज़ है और worst-case performance, I/O requirements की predictability, range scan, sorted traversal, prefix condition support जैसे कई फ़ायदे भी देता है।
किसी खास data distribution पर अधिक efficient lookup algorithm बनाया जा सकता है, लेकिन अक्सर उसकी कुछ महत्वपूर्ण properties खो जाती हैं। कोई दूसरा algorithm बेहतर initial estimate दे दे, फिर भी आख़िरी item खोजने में धीमा हो सकता है, या average तेज़ हो लेकिन worst-case इतना खराब हो कि इस्तेमाल लायक न रहे।
कागज़ के dictionary में भी पहली estimate के बाद लगभग binary search ही इस्तेमाल होता था, और उस initial estimate से कम होने वाले steps बहुत ज़्यादा नहीं होते। सही page range तक पहुँचने के बाद, ज़रूरत से ज़्यादा सख़्ती से binary search करने के बजाय थोड़ा linear scan करना ही व्यावहारिक होता है, हालाँकि सख़्त binary search तेज़ भी हो सकता है; लेकिन page पलटने के समय के साथ उसका संतुलन भी बैठाना पड़ता है।
Ed Kmett ने उस विचार को Haskell के discrimination[2] library में तराशा, और उससे जुड़ी talk[3] भी बहुत दिलचस्प है।
[1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220
[2]: https://hackage.haskell.org/package/discrimination
[3]: https://www.youtube.com/watch?v=cB8DapKQz-I
“4-way search” क्या आख़िरकार binary search loop को एक level unroll करना ही नहीं है? जिस interval में item है उसे ढूँढ़ने के लिए comparisons की संख्या लगभग वैसी ही लगती है, बस ऐसा दिखता है कि हर बार 2 की जगह 4 चीज़ें process हो रही हैं। loop unrolling से भी शायद वही असर मिल सकता है।
व्यावहारिक रूप से processor के नज़रिए से सभी loops पहले से कुछ हद तक unrolled ही होते हैं, और loop का सिर्फ़ थोड़ा सा overhead बचता है। Binary search में मुख्य cost memory या cache से data लाना है, इसलिए असली लड़ाई यह है कि बाद में जिन data की ज़रूरत पड़ेगी उन्हें जितनी जल्दी हो सके request करा दी जाए ताकि उनके आने का इंतज़ार कम करना पड़े।
4-way search जैसे algorithms का फ़र्क यह है कि वे हर branch की सिर्फ़ एक side को गहराई तक prefetch करने के बजाय, हर possible case को उथले स्तर पर prefetch करते हैं। इससे आख़िरकार जो prefetch ज़रूरी होगा वह ज़रूर issue हो जाता है, और actual execution path में इस्तेमाल न होने वाले data पर bandwidth भी अपेक्षाकृत कम खर्च होती है।
search algorithm की असली performance predict करने में “comparison count” लगभग बेकार metric है। Bottleneck यह नहीं है कि comparisons कितने किए जा सकते हैं, बल्कि यह है कि memory और cache bandwidth का कितना अच्छा उपयोग हो रहा है। अगर आधुनिक processor के branch behavior को भीतर तक ध्यान में रखें, तो इसे loop unrolling जैसा कहा भी जा सकता है।
वैसे दोनों searches अलग constants वाले O(log N) हैं। Algorithms की class में constants ज़्यादा मायने नहीं रखते, लेकिन वास्तविक दुनिया में ये काफ़ी असर डाल सकते हैं।
मैंने हाल में exponential search[2] पर भी एक लेख[1] लिखा है। यह ऐसा algorithm है जिसे तब इस्तेमाल किया जा सकता है जब जिन elements को ढूँढ़ना है वे खुद sorted हों और array में बार-बार binary search करनी हो; हमारे workload में इससे 8x speedup मिला।
[1] https://lalitm.com/post/exponential-search/
[2] https://en.wikipedia.org/wiki/Exponential_search
HEAD /users/1 -> 200 OK
HEAD /users/2 -> 200 OK
HEAD /users/4 -> 200 OK
...
HEAD /users/2048 -> 200 OK
HEAD /users/4096 -> 404 Not Found
इसके बाद 2048 और 4096 के बीच binary search करके सबसे हाल का user और साथ ही user count भी पता किया जा सकता है। प्रतिस्पर्धी SaaS कंपनियों की जाँच करते समय यह काम की जानकारी हो सकती है।
CPU हमेशा पूरी cache line, आम तौर पर 64 bytes, एक साथ access करता है, इसलिए पूरी cache line को search करना बेहतर होना चाहिए। Data के CPU में आ जाने के बाद वह लगभग मुफ़्त जैसा होता है।
इसलिए “binary” search में बीच वाली cache line के सभी values को check करके, अगर match न मिले तो left/right जाना, ऐसा कुछ आज़माना दिलचस्प होगा। Cache line search एक 512-bit SIMD instruction से हो सकती है। 64-byte cache line में 16-bit integers के 32 values होते हैं, इसलिए यह साधारण binary search से लगभग 32 गुना तेज़ भी हो सकती है, या कम से कम memory accesses 32 गुना घटा सकती है, जो ज़्यादातर वास्तविक programs में हावी कारक होगा।
अगर 4-byte key और 4-byte child pointer, या array index, इस्तेमाल करें तो internal node में 7 keys, 8 child pointers, और 1 next pointer रखकर 64-byte cache line पूरी भरी जा सकती है। 10 लाख items पर tree depth लगभग 20 से घटकर लगभग 7 हो जाती है, और ऊपर के कुछ levels cache में टिके रहने की संभावना भी ज़्यादा होती है।
थोड़ा विचार करें तो SIMD से B-tree node के अंदर search तेज़ की जा सकती है, लेकिन data dependency बहुत अधिक रहती है।
छोटे arrays के लिए, अंत में sentinel value के साथ linear search को हराना पहले से ही मुश्किल है। बस यह दावा थोड़ा धुंधला इसलिए लगता है क्योंकि “छोटा” कितना छोटा है, यह बहुत अस्पष्ट शर्त है और सहज समझ में नहीं आता।
कुल मिलाकर यह लेख मुझे पसंद आया। जिस बात को मैं लंबे समय से सोच रहा था, उसे उपयोगी elimination experiments के साथ बहुत अच्छी तरह explore किया गया है।
छोटे arrays, 16~32 items पर मैंने कुछ search experiments किए थे, और binary search branches ज़्यादा होने की वजह से सबसे खराब तरीकों में से एक निकली। छोटे arrays में सबसे तेज़ तरीका branchless linear search था।
इसमें loop को बीच में रोका नहीं जाता, बल्कि सभी elements को scan किया जाता है। उदाहरण के लिए, अगर पता करना हो कि array में कोई number है या नहीं, तो सभी items के test results को logical OR से जोड़ देते हैं। मैंने SIMD नहीं इस्तेमाल किया, लेकिन छोटे arrays में branches बहुत महँगी होती हैं, इसलिए बिना branch के हर element को बस check कर लेना ज़्यादा तेज़ था।
algorithm की व्याख्या थोड़ी उलझाने वाली लगी।
SIMD वाला हिस्सा सिर्फ़ आख़िरी चरण में, यानी अंतिम 16 elements search करते समय इस्तेमाल होता है।
4-way search वाला हिस्सा 3 points check करके 4 paths बनाता है, लेकिन वह सिर्फ़ सही key नहीं बल्कि सही block ढूँढ़ रहा है।
details दिलचस्प हैं; लेखक हर block के आख़िरी element को 4-way search में इस्तेमाल करता है। अगर पहला element या कोई भी arbitrary element लिया जाए तो algorithm कैसे बदलेगा, यह जानने की जिज्ञासा है।
यहाँ की मुख्य intuition, यानी SIMD multi-compare, आख़िरी चरण से बड़े scale पर भी लागू होती दिखती है।
रूपरेखा कुछ ऐसी है: a) gather से समान अंतराल वाले 16 स्थानों से कई elements लाओ b) SIMD instruction से parallel comparison करो c) सही block पर फ़ोकस करो d) block छोटा हो जाए तो linear search पर switch करो, नहीं तो gather/compare cycle दोहराओ।
gather instruction non-contiguous memory से पढ़ती है, और binary search की तुलना में ज़रूरत से ज़्यादा पढ़ लेती है। फिर भी अगर multi-way comparison संभव हो और binary search के 4 steps समेटे जा सकें, तो बड़े tables पर यह जीत सकती है।
सभी data types में पूरी 16-way comparison भी संभव नहीं है। float64 search AVX-512 पर भी 8-way comparison तक सीमित है, लेकिन int32 और float32 में 16-way comparison हो सकती है।
मुझे लगता है कि gather-based approach से binary search वास्तव में तेज़ निकलेगी।
पारंपरिक computer science algorithms असल में लगभग बिना parallelism वाले CPU को ध्यान में रखकर “design” किए गए थे। न कई cores, न Hyper-threading, न SIMD instructions जैसी parallelism; सभी memory accesses का समय समान माना गया, L1/L2/L3 cache latency जैसी कोई अवधारणा नहीं, और data सामान्य/यादृच्छिक होने का अनुमान।
इन मान्यताओं में से एक भी टूट जाए तो performance बढ़ाने के लिए बहुत सारे adjustments संभव हो जाते हैं।
पारंपरिक algorithms एक बहुत अच्छा starting point देते हैं, जिसके बाद किसी विशेष data shape या किसी खास CPU की characteristics/features को बेहतर समझकर और optimized solution विकसित किया जा सकता है।
optimization के नुकीले सिरे तक पहुँचने पर बात अक्सर इस पर आ जाती है कि data memory में कैसे रखा और access किया जा रहा है, और क्या उसे सुधारने वाले बदलाव बाद के stages को नुकसान तो नहीं पहुँचा रहे। बहुत पहले मेरी नौकरी में किसी ने code के एक हिस्से को बहुत ज़्यादा optimize कर दिया था, लेकिन उस optimization की वजह से बाद में ज़रूरी बहुत-सी जानकारी cache से बाहर धकेल दी गई और पूरी application और धीमी हो गई।
यह शायद Rob Pike के programming के पाँचवें नियम का ही एक रूप है, या यूँ कहें कि The Mythical Man Month में Fred Brooks की बात का पुनर्वचन। संदर्भ: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...
किशोरावस्था में मैंने एक पूरा वीकेंड इस सोच में बिताया था कि अगर binary search हर step में search space को आधा करके अच्छी है, तो ternary search हर बार एक-तिहाई करके और बेहतर क्यों नहीं होगी।
बीच के एक value से compare करने के बजाय 1/3 position के value से compare करना, और अगर वह बहुत छोटा हो तो 2/3 position के value से compare करना — यही विचार था।
लेकिन मैंने सोचा कि हर step में binary search के 1/2 की जगह 1/3 तक घटता है, पर comparisons औसतन 3/2 गुना लगती हैं, इसलिए कुल मिलाकर बात बराबर ही होगी।
सुधार: zamadatix के जवाब को देखकर समझ आया कि वास्तव में 2/3 cases में 2 comparisons लगती हैं, इसलिए औसत 5/3 गुना है।
पहला 1/3: 1 comparison
दूसरा 1/3: 2 comparisons
तीसरा 1/3: 2 comparisons
(1+2+2)/3 = औसतन 5/3 comparisons। “1 या 2 comparisons” वाली भावना के कारण 50% समझ लेना आसान है, लेकिन वास्तव में पहली comparison में hit होने की संभावना 1/3 है और 2 comparisons करने की संभावना 2/3 है।
इसलिए कुल average comparison count में ternary search को थोड़ा बदतर दिखाया जा सकता है: 5/3*Log_3[n] = 1.052... * Log_2[n]
यानी steps कम होते हैं, लेकिन अंत तक पहुँचने के लिए औसतन ज़्यादा comparisons करनी पड़ती हैं। इस तरह के लगभग सभी searches में, यानी जहाँ branching factor 2 से बड़ा हो, यही बात सामान्यतः सही रहती है। बेशक इसमें कुछ मान्यताएँ हैं — जैसे कि खोजी जाने वाली value का uniform distribution होना और operation cost का idealized होना — और ठीक यहीं इस लेख की चर्चा शुरू होती है।
binary search algorithm के ternary version के रूप में नहीं, क्योंकि वह असली ternary search से ज़्यादा एक biased binary search के क़रीब है। Comparison मूल रूप से binary ही होता है, इसलिए comparisons शामिल करने वाले सभी search algorithms किसी न किसी रूप में binary search ही हैं, और बीच वाले element के अलावा कुछ और चुनना algorithmic complexity के लिहाज़ से कम efficient होता है। हालाँकि वास्तविक hardware पर कुछ परिस्थितियों में वह बेहतर भी हो सकता है। असली ternary search के लिए मूल operation के रूप में 3-way comparison चाहिए।
यह तब दिलचस्प होता है जब “radix efficiency”[1] पर विचार किया जाए। सबसे अच्छा विकल्प 3 है, जो e के सबसे क़रीब natural number है। इसका tree search से भी संबंध है, इसलिए ternary tree कभी-कभी binary tree से बेहतर हो सकती है।
[1] https://en.wikipedia.org/wiki/Optimal_radix_choice
इसलिए वह विचार उस समय के CPU पर व्यावहारिक नहीं रहा होगा, लेकिन आज के CPU पर शायद कहीं ज़्यादा संभव हो।