Static Search Trees : बाइनरी सर्च से 40 गुना तेज

• "S+ ट्री" नाम के एक static search tree को implement करके sorted data पर high-speed search किया जाता है
• Algorithmica पोस्ट में प्रस्तावित code को शुरुआती आधार बनाकर optimize किया गया, और सुझाए गए अतिरिक्त ideas व improvements को code में बदला गया
• Assembly code का analysis करने के बाद संभव सभी instructions को optimize कर performance को अधिकतम किया गया
• कई queries को parallel में process करके throughput बढ़ाने के लिए batching जोड़ी गई
• लक्ष्य यह है कि S+ tree के जरिए sorted data पर high throughput बनाए रखते हुए queries को efficiently execute किया जाए

1. परिचय और प्रेरणा

• समस्या की परिभाषा:

  • इनपुट: sorted 32-bit unsigned integer list vals: Vec<u32>
  • आउटपुट: न्यूनतम आकार वाला ऐसा data structure जो किसी query (q) से बड़ा या उसके बराबर मान लौटाए
  • metric: प्रति सेकंड process की जा सकने वाली independent queries की संख्या

• उद्देश्य:

  • bioinformatics में efficient data structure बनाना, खासकर DNA sequence indexing के लिए suffix array search की speed बढ़ाना
  • CPU performance और SIMD instructions का उपयोग करके performance को अधिकतम करना

• अनुशंसित सामग्री:

  • binary search और array layout पर शोध (“Array Layouts for Comparison-Based Searching”)
  • S+ tree और static B-tree का परिचय

2. S+ tree और optimization

2.1 binary search और Eytzinger layout

• Rust standard library की binary search cache-efficient नहीं है, और data size बढ़ने पर performance गिरती है
• Eytzinger layout:
  • binary search tree को array form में store करके cache utilization को अधिकतम करता है
  • performance: L3 cache से बड़े data पर binary search से अधिकतम 4 गुना तेज

2.2 S+ tree की अवधारणा

• S-tree:
  • प्रति node 15 sorted values वाला hexadecimal tree form
  • B-tree से अधिक efficient और Eytzinger layout से अधिक compact
• S+ tree:
  • सभी data को leaf nodes में store करता है, और upper nodes में duplicate रूप से रखता है
  • सरल search और efficient structure प्रदान करता है

2.3 find function optimization

• मूल linear search:
  • data को traverse करके condition से मेल खाने वाला value लौटाता है (inefficient)
• automatic vectorization:
  • branchless code में बदलकर SIMD instructions से performance 2 गुना बेहतर
• manual SIMD implementation:
  • SIMD instructions का manually उपयोग कर optimization, 5 instructions के साथ performance को अधिकतम किया गया

3. batching और prefetching

3.1 batching

• कई queries को parallel में process करके memory latency को offset किया जाता है
• batch size बढ़ाने पर throughput बेहतर हुआ, और अधिकतम batch size 16 पर saturation आया

3.2 prefetching

• अगले node को पहले से memory में लाकर L3 cache से बड़े data पर performance सुधरती है
• batching के साथ मिलाकर processing time 45ns/query से 30ns/query तक घटा

4. data layout और structure optimization

4.1 node size बदलना

• प्रति node values को 15 तक घटाकर multiplication operation को सरल बनाया गया और cache efficiency बढ़ी
• L3 cache के अंदर के data पर थोड़ा performance improvement मिला

4.2 memory layout बदलना

• layout को reverse order में store करने या padding को कम करने वाली configurations का परीक्षण किया गया
• reverse और reduced-padding layouts दोनों का performance पर बड़ा असर नहीं पड़ा

5. data partitioning

5.1 prefix-based partitioning

• data के upper bits के आधार पर parts अलग किए गए
• छोटे data पर performance बेहतर हुई, लेकिन memory overhead आया

5.2 compressed subtrees

• हर subtree को pack करके space efficiency बढ़ाई गई
• parts के size को track करना पड़ता है, और query speed थोड़ी घटती है

6. multi-thread तुलना

• 6 threads उपयोग करने पर query time 27ns → 7ns तक घटा
• RAM bandwidth limit bottleneck बन गई

7. निष्कर्ष और आगे का शोध

• binary search की तुलना में 40 गुना से अधिक performance improvement (1150ns/query → 27ns/query)
• आगे के कार्य:
  • data balancing optimization और RAM access कम करना
  • range queries और sorted queries को handle करना
  • suffix array search integration

[beenzinozino]

वाह... अगर इसे विभिन्न भाषाओं की built-in libraries में लागू किया जाए, तो इसका प्रभाव काफ़ी बड़ा हो सकता है।

[GN⁺]

Hacker News टिप्पणियाँ

• देखा कि एल्गोरिथ्म से जुड़े low-level कंटेंट में Rust का इस्तेमाल धीरे-धीरे बढ़ रहा है। पहले ऐसे कंटेंट ज़्यादातर C(++) या वैज्ञानिक pseudocode में लिखे जाते थे। Rust का बढ़ता उपयोग सकारात्मक लगता है

  • Rust अच्छी तरह नहीं जानता, फिर भी Rust में लिखा कंटेंट समझ सका। यह वैसा ही है जैसे C में लिखे एल्गोरिथ्म उदाहरणों को Rust प्रोग्रामर समझ सकते हैं
  • Rust का standard बनना पसंद है, और Zig भी साथ में इस्तेमाल हो तो अच्छा लगेगा

• queries को batch में बाँटने के तरीके की खोज नहीं की गई। cache के बाहर की table में lookup करना मुख्य लागत है

  • अगर queries पर्याप्त संख्या में हों, तो tree की कई levels को एक साथ हल किया जा सकता है
  • इससे results को सही output order में sort करने की समस्या आ सकती है

• int32 values की संख्या बहुत बड़ी नहीं है, और पूरा bitset 512MB है। सामान्य data structure के रूप में Roaring Bitmaps की सिफारिश है

  • अगर सिर्फ simple lookup चाहिए, तो minimal perfect hash function पर विचार करना उचित हो सकता है

• Rust में low-level efficiency बढ़ाने के तरीकों को देखकर हैरानी हुई। इसे C++ implementation से तुलना करके देखना चाहूँगा

• Eytzinger tree का फ़ायदा यह है कि node index को inorder traversal position in बदलने का एक formula होता है

  • जब underlying key storage sorted key set हो, तब यह उपयोगी है
  • Eytzinger का उपयोग करने पर loop की कई iterations का पहले से अनुमान लगाया जा सकता है

• 4GB memory में u32 खोजने पर ~27ns overhead आना आश्चर्यजनक है

  • batch size 8 पर optimization कैसे आगे बढ़ती है, यह जानने की उत्सुकता है
  • multithreading के नतीजे भी दिलचस्प हैं। 1 से 6 threads पर जाने से overhead में 4 गुना सुधार होता है

• Rust और C++ पर बहुत चर्चा है, लेकिन यह सोच रहा हूँ कि Common Lisp में SIMD बनाए रखते हुए इसे कैसे implement किया जाए

• low-level optimization पर लेख पढ़ते समय हर बार यह महसूस होता है कि लेखक ने nanoseconds बचाने के लिए समय लगाया, उसके लिए आभार

  • सोचता हूँ कि ऐसी optimizations जुड़कर मानवता का कुल कितना समय बचा चुकी होंगी

• लगता है कि 1.7 के figure 3 में त्रुटि है। 1.3 के figure 1 में y-axis label को "inversion throughput" की जगह सही किया जाना चाहिए, ऐसा सुझाव है

• अगर कभी-कभी writes को support करना हो, तो एक बड़ा static search tree और एक छोटा writable tree इस्तेमाल किया जा सकता है

  • जब पर्याप्त बदलाव इकट्ठा हो जाएँ, तो उन changes को static tree के नए version में भेजा जा सकता है