Static Search Trees: เร็วกว่า binary search 40 เท่า

• ใช้ต้นไม้ค้นหาแบบสถิตที่ติดตั้งใช้งานแล้ว "S+ tree" เพื่อค้นหาข้อมูลที่เรียงลำดับแล้วได้อย่างรวดเร็วมาก
• เริ่มจากโค้ดที่เสนอในโพสต์ของ Algorithmica แล้วทำการปรับแต่งเพิ่มเติม พร้อมนำไอเดียและการปรับปรุงที่เสนอไว้มาทำเป็นโค้ด
• วิเคราะห์โค้ดแอสเซมบลีแล้วปรับแต่งคำสั่งที่เป็นไปได้ทั้งหมดเพื่อดึงประสิทธิภาพออกมาสูงสุด
• นำ batching มาใช้เพื่อเพิ่ม throughput โดยประมวลผลหลายคิวรีแบบขนาน
• เป้าหมายคือใช้ S+ tree เพื่อให้คิวรีทำงานได้อย่างมีประสิทธิภาพพร้อมรักษา throughput สูงบนข้อมูลที่เรียงลำดับแล้ว

1. บทนำและแรงจูงใจ

• นิยามปัญหา:

  • อินพุต: รายการจำนวนเต็มไม่ติดลบ 32 บิตที่เรียงลำดับแล้ว vals: Vec<u32>
  • เอาต์พุต: โครงสร้างข้อมูลขนาดกะทัดรัดที่สามารถคืนค่าซึ่งมีค่ามากกว่าหรือเท่ากับคิวรี (q)
  • เมตริก: จำนวนคิวรีอิสระที่ประมวลผลได้ต่อวินาที

• วัตถุประสงค์:

  • สร้างโครงสร้างข้อมูลที่มีประสิทธิภาพสำหรับชีวสารสนเทศ โดยเฉพาะการเร่งความเร็วการค้นหา suffix array สำหรับการทำดัชนีลำดับ DNA
  • มุ่งดึงประสิทธิภาพสูงสุดจาก CPU และชุดคำสั่ง SIMD

• เอกสารแนะนำ:

  • งานวิจัยเรื่อง binary search และ array layout (“Array Layouts for Comparison-Based Searching”)
  • เอกสารแนะนำ S+ tree และ static B-tree

2. S+ tree และการปรับแต่งประสิทธิภาพ

2.1 Binary search และ Eytzinger layout

• Binary search ในไลบรารีมาตรฐานของ Rust ใช้แคชได้ไม่ดี และประสิทธิภาพลดลงเมื่อขนาดข้อมูลเพิ่มขึ้น
• Eytzinger layout:
  • จัดเก็บ binary search tree ในรูปแบบอาร์เรย์เพื่อใช้ประโยชน์จากแคชให้สูงสุด
  • ประสิทธิภาพ: เร็วกว่า binary search ได้สูงสุด 4 เท่าสำหรับข้อมูลที่มีขนาดเกิน L3 cache

2.2 แนวคิดของ S+ tree

• S-tree:
  • โครงสร้างต้นไม้ฐาน 16 ที่มีค่าเรียงลำดับ 15 ค่าในแต่ละโหนด
  • มีประสิทธิภาพกว่า B-tree และบีบอัดได้ดีกว่า Eytzinger layout
• S+ tree:
  • เก็บข้อมูลทั้งหมดไว้ใน leaf node และมีการเก็บค่าซ้ำไว้ในโหนดชั้นบน
  • ให้โครงสร้างที่เรียบง่ายและค้นหาได้อย่างมีประสิทธิภาพ

2.3 การปรับแต่งฟังก์ชัน find

• การค้นหาเชิงเส้นแบบพื้นฐาน:
  • วนดูข้อมูลแล้วคืนค่าที่ตรงเงื่อนไข (ไม่มีประสิทธิภาพ)
• การทำ vectorization อัตโนมัติ:
  • แปลงเป็นโค้ดแบบไม่มี branch และใช้คำสั่ง SIMD ทำให้ประสิทธิภาพดีขึ้น 2 เท่า
• การทำ SIMD แบบเขียนเอง:
  • ปรับแต่งด้วยการใช้คำสั่ง SIMD ด้วยตนเอง และดึงประสิทธิภาพสูงสุดด้วยคำสั่งเพียง 5 คำสั่ง

3. Batching และ prefetching

3.1 Batching

• ประมวลผลหลายคิวรีแบบขนานเพื่อชดเชยเวลาในการรอหน่วยความจำ
• เพิ่มขนาดแบตช์แล้ว throughput ดีขึ้น และเริ่มอิ่มตัวที่ขนาดแบตช์สูงสุด 16

3.2 Prefetching

• ดึงโหนดถัดไปเข้าหน่วยความจำล่วงหน้าเพื่อเพิ่มประสิทธิภาพสำหรับข้อมูลที่มีขนาดเกิน L3 cache
• เมื่อใช้ร่วมกับ batching เวลาประมวลผลลดลงจาก 45ns/query เหลือ 30ns/query

4. การปรับแต่ง data layout และโครงสร้าง

4.1 การเปลี่ยนขนาดโหนด

• ลดจำนวนค่าต่อโหนดเหลือ 15 ค่า เพื่อลดความซับซ้อนของการคูณและเพิ่มประสิทธิภาพการใช้แคช
• ช่วยเพิ่มประสิทธิภาพเล็กน้อยสำหรับข้อมูลที่อยู่ใน L3 cache

4.2 การเปลี่ยน memory layout

• ทดลองจัดเก็บ layout แบบย้อนลำดับ หรือจัดวางให้มี padding น้อยที่สุด
• ทั้ง layout แบบย้อนลำดับและแบบลด padding แทบไม่มีผลต่อประสิทธิภาพมากนัก

5. การแบ่งพาร์ทิชันข้อมูล

5.1 การแบ่งพาร์ทิชันตาม prefix

• แยกพาร์ตตามบิตด้านบนของข้อมูล
• ช่วยเพิ่มประสิทธิภาพกับข้อมูลขนาดเล็ก แต่มี memory overhead

5.2 Subtree แบบบีบอัด

• แพ็กแต่ละ subtree เพื่อเพิ่มประสิทธิภาพด้านพื้นที่
• ต้องติดตามขนาดของแต่ละพาร์ต และความเร็วคิวรีลดลงเล็กน้อย

6. การเปรียบเทียบแบบหลายเธรด

• เมื่อใช้ 6 เธรด เวลาคิวรีลดลงจาก 27ns เป็น 7ns
• คอขวดกลายเป็นข้อจำกัดด้านแบนด์วิดท์ของ RAM

7. บทสรุปและงานวิจัยต่อไป

• ประสิทธิภาพดีขึ้นมากกว่า 40 เท่าเมื่อเทียบกับ binary search (1150ns/query → 27ns/query)
• งานต่อไป:
  • ปรับสมดุลข้อมูลให้เหมาะสมและลดการเข้าถึง RAM
  • รองรับ range query และ sorted query
  • ผสานเข้ากับการค้นหา suffix array

[beenzinozino]

ว้าว... ถ้านำไปใช้กับไลบรารีมาตรฐานที่มีมาให้ในหลายภาษาได้จริง ผลกระทบที่ตามมาคงมหาศาลทีเดียวครับ

[GN⁺]

ความคิดเห็นจาก Hacker News

• สังเกตว่า Rust ถูกใช้มากขึ้นเรื่อย ๆ ในคอนเทนต์ระดับล่างที่เกี่ยวกับอัลกอริทึม ในอดีตคอนเทนต์ลักษณะนี้มักเขียนด้วย C(++) หรือ pseudocode เชิงวิทยาศาสตร์เป็นหลัก มองว่าการใช้ Rust เพิ่มขึ้นเป็นเรื่องดี

  • แม้จะไม่ได้รู้จัก Rust ดีมาก แต่ก็ยังเข้าใจคอนเทนต์ที่เขียนด้วย Rust ได้ คล้ายกับที่โปรแกรมเมอร์ Rust สามารถเข้าใจตัวอย่างอัลกอริทึมที่เขียนด้วย C ได้
  • อยากให้ Rust กลายเป็นมาตรฐาน และคิดว่าถ้ามี Zig ใช้ร่วมกันด้วยก็น่าจะดี

• ยังไม่มีการสำรวจวิธีแบ่ง query เป็น batch ต้นทุนหลักคือการ lookup ในตารางที่อยู่นอกแคช

  • ถ้ามี query มากพอ ก็สามารถประมวลผลหลายชั้นของ tree ได้พร้อมกันในครั้งเดียว
  • แต่อาจเกิดปัญหาว่าต้องจัดเรียงผลลัพธ์กลับไปตามลำดับ output ที่ถูกต้อง

• จำนวนค่า int32 ไม่ได้มากนัก และ bitset ทั้งหมดมีขนาด 512MB สำหรับโครงสร้างข้อมูลทั่วไป แนะนำให้ใช้ Roaring Bitmaps

  • ถ้าต้องการแค่ lookup อย่างเดียว ก็ควรพิจารณา minimal perfect hash function

• รู้สึกทึ่งกับวิธีเพิ่มประสิทธิภาพระดับล่างใน Rust อยากเห็นการเปรียบเทียบกับ implementation ฝั่ง C++

• ข้อดีของ Eytzinger tree คือมีสูตรสำหรับแปลงดัชนีของโหนดเป็นตำแหน่งแบบ inorder traversal

  • มีประโยชน์เมื่อที่เก็บคีย์พื้นฐานเป็นชุดคีย์ที่เรียงลำดับแล้ว
  • การใช้ Eytzinger ทำให้สามารถคาดเดาการวนลูปหลายรอบล่วงหน้าได้

• น่าประหลาดใจที่การค้นหา u32 ในหน่วยความจำ 4GB มี overhead ราว ~27ns

  • สงสัยว่าการ optimize ทำงานอย่างไรเมื่อ batch size เป็น 8
  • ผลลัพธ์แบบ multithreading ก็น่าสนใจเช่นกัน เมื่อเปลี่ยนจาก 1 เป็น 6 threads overhead ดีขึ้น 4 เท่า

• มีการพูดถึง Rust และ C++ มาก แต่กำลังคิดว่าจะ implement สิ่งนี้ใน Common Lisp โดยยังคง SIMD ไว้ได้อย่างไร

• ทุกครั้งที่อ่านบทความเกี่ยวกับการ optimize ระดับล่าง ก็รู้สึกขอบคุณที่ผู้เขียนสละเวลาเพื่อช่วยประหยัดเวลาในระดับนาโนวินาที

  • สงสัยว่าถ้าเอา optimization แบบนี้มาสะสมรวมกันแล้ว มนุษยชาติประหยัดเวลาไปได้มากแค่ไหน

• คิดว่ารูป 3 ในหัวข้อ 1.7 มีข้อผิดพลาด และเสนอว่า label แกน y ของรูป 1 ในหัวข้อ 1.3 ควรเป็น "ปริมาณการย้อนกลับ"

• หากบางครั้งจำเป็นต้องรองรับการเขียน ก็อาจใช้ static search tree ขนาดใหญ่ร่วมกับ tree ขนาดเล็กที่เขียนได้

  • เมื่อมีการเปลี่ยนแปลงมากพอ ก็สามารถย้ายการเปลี่ยนแปลงไปยัง static tree เวอร์ชันใหม่ได้