आप binary search को पछाड़ सकते हैं

 (lemire.me)
1 पॉइंट द्वारा GN⁺ 1 시간 전 | अभी कोई टिप्पणी नहीं है. | WhatsApp पर शेयर करें
  • sorted array में membership check को पाठ्यपुस्तक वाले binary search से भी तेज़ बनाया जा सकता है, और SIMD Quad हर measured condition में std::binary_search से तेज़ था
  • SIMD Quad 16-bit unsigned integer sorted array को 16-element ब्लॉक्स में बाँटता है, block boundaries पर 4-way interpolation search करता है, और block के अंदर SIMD parallel comparison चलाता है
  • आधुनिक 64-bit ARM और x64 (Intel/AMD) एक ही instruction में 8 16-bit integers की तुलना कर सकते हैं, इसलिए एक बार में सिर्फ एक value जाँचने वाले binary search ढाँचे का कड़ाई से पालन करना अब उतना ज़रूरी नहीं रह जाता
  • benchmark 2~4096 आकार के 100,000 sorted arrays और 10 million membership queries के साथ चलाया गया; cold mode cache miss और warm mode cache hit को simulate करता है
  • Intel पर warm cache में SIMD Quad, binary search से 2x से अधिक तेज़ था; Apple पर cold cache में 2x से अधिक तेज़ था; और Intel पर बड़े arrays के cold cache में 4-way approach ने memory-level parallelism का बेहतर उपयोग किया

sorted array membership check की bottleneck

  • sorted array में कोई value मौजूद है या नहीं, इसे जाँचने का सबसे सरल तरीका values को एक-एक करके देखना है, यानी linear search; C++ में std::find से यही प्रभाव मिलता है
  • बड़े arrays में binary search ज़्यादा तेज़ होता है; यह search range के बीच वाले value को आधार बनाकर ऊपरी या निचला आधा हटाता है, और value मिलने या range खाली होने तक यह प्रक्रिया दोहराता है
  • C++ का std::binary_search value मौजूद है या नहीं, इसे boolean के रूप में लौटाता है
  • Roaring Bitmap format 1~4096 आकार के 16-bit integer arrays का उपयोग करता है, और membership check के लिए binary search इस्तेमाल करता है

SIMD Quad की शुरुआत

  • ज़्यादातर आधुनिक processors में data-parallel instructions यानी SIMD होते हैं, और 64-bit ARM तथा x64 (Intel/AMD) एक instruction में 8 16-bit integers की target value से तुलना कर सकते हैं
  • इस वजह से binary search को 8 से छोटे blocks तक नीचे ले जाना ज़रूरी नहीं रहता, और 16 या उससे अधिक elements की तुलना भी सस्ते में की जा सकती है
  • binary search एक बार में एक value जाँचता है, लेकिन आधुनिक processors एक साथ कई values load और check कर सकते हैं, और memory-level parallelism भी अच्छा होता है
  • array को आधा बाँटने की जगह 4 हिस्सों में बाँटने वाला 4-way search आज़माया जा सकता है; instructions थोड़ी बढ़ें तो भी bottleneck शायद instruction count न हो

SIMD Quad algorithm की संरचना

  • SIMD Quad, 16-bit unsigned integer sorted arrays के लिए search algorithm है, जो 4-way interpolation search और SIMD को जोड़ता है
  • array को 16-element fixed-size blocks में बाँटा जाता है, और आख़िरी block अपवाद हो सकता है
  • हर block के आख़िरी element को interpolation key की तरह इस्तेमाल करके range को उस एक block तक सीमित किया जाता है जहाँ target value होने की संभावना सबसे ज़्यादा हो; फिर उस block के 16 elements को SIMD से एक साथ जाँचा जाता है
  • core flow एक hierarchical search है: block boundaries पर interpolation search से comparison count कम करना, और block के अंदर SIMD से parallel comparison चलाना
  • काम करने के चरण इस प्रकार हैं
    • अगर element count 16 से कम है, तो पूरे array पर simple linear search किया जाता है
    • cardinality आकार के array को 16 लगातार elements वाले blocks में बाँटा जाता है, और कुल block count num_blocks = cardinality / 16 होता है
    • 16-1, 32-1 जैसी positions पर block के आख़िरी elements को key की तरह लेकर current search range के 1/4 points की target pos से तुलना की जाती है और base adjust किया जाता है
    • interpolation के नतीजे के अनुसार उपयुक्त block index lo चुना जाता है
    • अगर block valid है, तो ARM पर NEON और x64 पर SSE2 से 16 elements load करके target value के साथ parallel equality comparison किया जाता है; match मिलने पर true लौटाया जाता है
    • पूरे 16-element blocks में शामिल न होने वाले बचे हुए elements पर linear search किया जाता है

benchmark का तरीका

  • benchmark में 2~4096 के हर array size के लिए 16-bit unsigned integers के 100,000 sorted arrays बनाए गए
  • हर size पर membership query 10 million बार, दो modes में चलाई गई
    • cold mode: हर query अलग array में search करती है, जिससे cache miss simulate होता है
    • warm mode: queries को array के हिसाब से group किया जाता है और उसी array को लगातार 100 बार search किया जाता है, जिससे cache hit simulate होता है
  • measurement target average query time था, और comparison algorithms थे linear search (std::find), binary search (std::binary_search), और SIMD Quad
  • measurement systems थे Apple M4 के साथ Apple LLVM, और Intel Emerald Rapids processor के साथ GCC

measurement results

  • linear search और binary search की तुलना में, array बड़ा होने पर binary search, linear search से बेहतर निकला
  • cold cache में अधिक data access के कारण cache failures बढ़ते हैं, इसलिए linear search तुलनात्मक रूप से और कमज़ोर हो जाता है
  • binary search के linear search पर कुल बढ़त दिखने के बाद, इसकी तुलना SIMD Quad से की गई
  • Intel और Apple platforms पर परिणाम साफ़ तौर पर अलग थे
    • Intel platform पर warm cache में SIMD Quad, binary search से 2x से अधिक तेज़ था
    • Intel platform के cold cache में लाभ कम था
    • Apple platform पर इसके उलट cold cache में SIMD Quad, 2x से अधिक तेज़ था, जबकि warm cache में लाभ अपेक्षाकृत सीमित था
  • हर मामले में SIMD Quad, binary search से तेज़ था
  • SIMD वाला हिस्सा special instructions से काम घटाता है, और instructions तथा branches दोनों कम होने से speedup को समझना आसान होता है

4-way search का प्रभाव

  • SIMD optimization को बनाए रखते हुए, 4-way interpolation search को standard binary search से बदलने वाला SIMD binary version भी compare किया गया
  • Apple platform पर 4-way approach का असर छोटा था
  • Intel platform पर बड़े arrays के cold cache scenario में 4-way approach meaningful optimization साबित हुआ
  • Intel server पर 4-way search ने memory-level parallelism का बेहतर उपयोग किया

implementation की मुख्य बातें

  • simd_quad function uint16_t array, element count cardinality, और खोजी जाने वाली value pos लेकर boolean लौटाता है
  • gap को 16 पर fixed रखा गया है; अगर cardinality < gap हो, तो simple loop से value खोजी जाती है
  • block search loop में n > 3 रहने तक 1/4, 2/4, 3/4 points पर block के आख़िरी values पढ़े जाते हैं, pos से तुलना की जाती है, और तीन comparison results के योग से base को आगे बढ़ाया जाता है
  • इसके बाद n > 1 रहने तक half-based comparison करके बाकी range घटाई जाती है, और आख़िर में lo block चुना जाता है
  • चुने गए block में ARM NEON के vceqq_u16 या x64 SSE2 के _mm_cmpeq_epi16 से 16 elements को दो batches में compare किया जाता है
  • बचे हुए elements वाले हिस्से में v >= pos होने वाली जगह पर v == pos लौटाया जाता है, और अंत तक न मिलने पर false लौटाया जाता है

निष्कर्ष और सामग्री

  • पाठ्यपुस्तक वाला binary search ठीक-ठाक algorithm है, लेकिन वास्तविक performance में मायने रखने वाले तरीक़े से इसे और तेज़ बनाया जा सकता है
  • standard algorithms अक्सर आज के computers की उच्च parallelism को ध्यान में रखकर डिज़ाइन नहीं किए गए थे
  • SIMD Quad, memory-level parallelism और data parallelism दोनों का उपयोग करने की कोशिश करने वाला approach है
  • इससे भी बेहतर algorithms संभव हो सकते हैं, और अधिक रचनात्मक approaches की ज़रूरत है
  • source code
  • Faster intersections between sorted arrays with shotgun

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

अभी कोई टिप्पणी नहीं है.

अभी कोई टिप्पणी नहीं है.