คุณเอาชนะ binary search ได้

• การตรวจสอบสมาชิกในอาร์เรย์ที่เรียงลำดับแล้วสามารถทำให้เร็วกว่า binary search แบบตำราได้ และ SIMD Quad เร็วกว่า std::binary_search ในทุกเงื่อนไขการวัด
• SIMD Quad แบ่งอาร์เรย์จำนวนเต็ม unsigned 16 บิตที่เรียงลำดับแล้วออกเป็นบล็อกละ 16 องค์ประกอบ โดยใช้การค้นหาแบบ interpolation 4 ทางที่ขอบบล็อก และใช้การเปรียบเทียบแบบขนานด้วย SIMD ภายในบล็อก
• ARM 64 บิตและ x64 สมัยใหม่ (Intel/AMD) สามารถเปรียบเทียบจำนวนเต็ม 16 บิตได้ 8 ค่าในคำสั่งเดียว ทำให้ไม่จำเป็นต้องยึดโครงสร้าง binary search ที่ตรวจสอบทีละค่าเหมือนเดิมมากนัก
• การทดสอบประสิทธิภาพทำกับอาร์เรย์ที่เรียงลำดับแล้ว 100,000 ชุด ขนาด 2~4096 และคำถาม membership 10 ล้านครั้ง โดยโหมด cold จำลอง cache miss และโหมด warm จำลอง cache hit
• บน Intel นั้น SIMD Quad เร็วกว่า binary search มากกว่า 2 เท่าเมื่อแคช warm ขณะที่บน Apple เร็วกว่า 2 เท่าเมื่อแคช cold และในกรณีอาร์เรย์ใหญ่บน Intel กับแคช cold วิธีแบบ 4 ทางใช้ประโยชน์จาก memory-level parallelism ได้ดีกว่า

---

คอขวดของการตรวจสอบสมาชิกในอาร์เรย์ที่เรียงลำดับแล้ว

• วิธีที่ง่ายที่สุดในการตรวจสอบว่ามีค่าอยู่ในอาร์เรย์ที่เรียงลำดับแล้วหรือไม่ คือ linear search ที่ไล่ดูค่าทีละตัว ซึ่งใน C++ สามารถให้ผลแบบเดียวกันได้ด้วย std::find
• สำหรับอาร์เรย์ขนาดใหญ่ binary search จะเร็วกว่า โดยจะทิ้งครึ่งบนหรือครึ่งล่างตามค่าตรงกลางของช่วงค้นหา และทำซ้ำจนกว่าจะพบค่าหรือช่วงว่างลง
• std::binary_search ของ C++ จะคืนค่าความจริงเป็นบูลีนว่ามีค่านั้นหรือไม่
• ฟอร์แมต Roaring Bitmap ใช้อาร์เรย์จำนวนเต็ม 16 บิตขนาด 1~4096 และใช้ binary search เพื่อตรวจสอบการมีอยู่ของค่า

จุดเริ่มต้นของ SIMD Quad

• โปรเซสเซอร์สมัยใหม่ส่วนใหญ่มีคำสั่ง SIMD สำหรับ data parallelism และ ARM 64 บิตกับ x64 (Intel/AMD) สามารถเปรียบเทียบจำนวนเต็ม 16 บิตได้ 8 ค่าเทียบกับค่าเป้าหมายในคำสั่งเดียว
• ด้วยคุณสมบัตินี้ จึงไม่จำเป็นต้องไล่ binary search ลงไปจนถึงบล็อกที่เล็กกว่า 8 ค่า และยังเปรียบเทียบองค์ประกอบตั้งแต่ 16 ค่าขึ้นไปได้ในต้นทุนต่ำ
• binary search ตรวจสอบทีละค่า แต่โปรเซสเซอร์รุ่นใหม่สามารถโหลดและตรวจสอบหลายค่าได้พร้อมกัน และยังมี memory-level parallelism ที่ดี
• แทนที่จะแบ่งอาร์เรย์ครึ่งหนึ่ง อาจลองใช้ 4-ary search ที่แบ่งเป็น 4 ส่วน ซึ่งแม้จำนวนคำสั่งจะเพิ่มขึ้นเล็กน้อย แต่คอขวดอาจไม่ได้อยู่ที่จำนวนคำสั่ง

โครงสร้างอัลกอริทึม SIMD Quad

• SIMD Quad เป็นอัลกอริทึมค้นหาสำหรับอาร์เรย์จำนวนเต็ม unsigned 16 บิตที่เรียงลำดับแล้ว โดยผสาน 4-ary interpolation search เข้ากับ SIMD
• อาร์เรย์จะถูกแบ่งเป็นบล็อกขนาดคงที่บล็อกละ 16 องค์ประกอบ และบล็อกสุดท้ายอาจเป็นกรณีพิเศษ
• ใช้องค์ประกอบสุดท้ายของแต่ละบล็อกเป็นคีย์สำหรับ interpolation เพื่อลดช่วงไปยังบล็อกเดียวที่มีแนวโน้มจะมีค่าเป้าหมาย จากนั้นตรวจสอบ 16 องค์ประกอบในบล็อกนั้นพร้อมกันด้วย SIMD
• แกนหลักคือการค้นหาแบบลำดับชั้น โดยลดจำนวนการเปรียบเทียบด้วย interpolation search ที่ขอบบล็อก และใช้ SIMD เปรียบเทียบแบบขนานภายในบล็อก
• ขั้นตอนการทำงานมีดังนี้
  • หากมีองค์ประกอบน้อยกว่า 16 ค่า จะใช้ linear search ทั้งหมดแบบง่าย
  • แบ่งอาร์เรย์ขนาด cardinality ออกเป็นบล็อกขององค์ประกอบต่อเนื่อง 16 ค่า และจำนวนบล็อกทั้งหมดคือ num_blocks = cardinality / 16
  • ใช้องค์ประกอบสุดท้ายของบล็อกที่ตำแหน่ง 16-1, 32-1 เป็นต้น เป็นคีย์ แล้วเปรียบเทียบจุด 1/4 ของช่วงค้นหาปัจจุบันกับค่าเป้าหมาย pos เพื่อปรับ base
  • เลือกดัชนีบล็อก lo ที่เหมาะสมตามผลของ interpolation
  • หากเป็นบล็อกที่ใช้ได้ บน ARM จะใช้ NEON และบน x64 จะใช้ SSE2 เพื่อโหลด 16 องค์ประกอบและเปรียบเทียบความเท่ากับค่าเป้าหมายแบบขนาน หากมีค่าตรงกันจะคืน true
  • องค์ประกอบที่เหลือซึ่งไม่อยู่ในบล็อกเต็ม 16 ค่าจะถูกค้นหาแบบเชิงเส้น

วิธีการทำ benchmark

• การทดสอบประสิทธิภาพสร้างอาร์เรย์จำนวนเต็ม unsigned 16 บิตที่เรียงลำดับแล้ว 100,000 ชุด สำหรับทุกขนาดอาร์เรย์ตั้งแต่ 2~4096
• สำหรับแต่ละขนาด มีการทำคำถาม membership 10 ล้านครั้งใน 2 โหมด
  • โหมด cold: แต่ละคำถามค้นหาในอาร์เรย์คนละชุด เพื่อจำลอง cache miss
  • โหมด warm: จัดกลุ่มคำถามตามอาร์เรย์ และค้นหาในอาร์เรย์เดียวกันต่อเนื่อง 100 ครั้ง เพื่อจำลอง cache hit
• ค่าที่วัดคือเวลาเฉลี่ยต่อคำถาม และอัลกอริทึมที่นำมาเทียบคือ linear search (std::find), binary search (std::binary_search) และ SIMD Quad
• ระบบที่ใช้วัดคือ Apple M4 กับ Apple LLVM และโปรเซสเซอร์ Intel Emerald Rapids กับ GCC

ผลการวัด

• เมื่อเทียบ linear search กับ binary search จะพบว่าเมื่ออาร์เรย์ใหญ่ขึ้น binary search จะชนะ linear search
• ในแคชแบบ cold การเข้าถึงข้อมูลที่มากขึ้นทำให้ cache miss เพิ่มขึ้น จึงทำให้ linear search เสียเปรียบยิ่งขึ้น
• หลังจาก binary search เหนือกว่า linear search โดยรวมแล้ว จึงนำไปเปรียบเทียบกับ SIMD Quad
• ผลลัพธ์บนแพลตฟอร์ม Intel และ Apple แตกต่างกันอย่างชัดเจน
  • บนแพลตฟอร์ม Intel นั้น SIMD Quad เร็วกว่า binary search มากกว่า 2 เท่าเมื่อแคช warm
  • บนแพลตฟอร์ม Intel ในแคช cold ข้อได้เปรียบจะเล็กลง
  • บนแพลตฟอร์ม Apple กลับกันคือ SIMD Quad เร็วกว่า 2 เท่าเมื่อแคช cold และข้อได้เปรียบในแคช warm มีจำกัดกว่า
• ในทุกกรณี SIMD Quad เร็วกว่า binary search
• ส่วน SIMD ลดงานลงด้วยคำสั่งเฉพาะทาง และมีจำนวนคำสั่งกับการแตกแขนงน้อยกว่า จึงอธิบายการเพิ่มความเร็วได้ไม่ยาก

ผลของการค้นหาแบบ 4 ทาง

• มีการเปรียบเทียบเวอร์ชัน SIMD binary ด้วย ซึ่งยังคงการปรับแต่งแบบ SIMD ไว้ แต่เปลี่ยน 4-ary interpolation search กลับเป็น binary search มาตรฐาน
• บนแพลตฟอร์ม Apple ผลของแนวทางแบบ 4 ทางมีไม่มาก
• บนแพลตฟอร์ม Intel วิธีแบบ 4 ทางเป็นการปรับแต่งที่มีนัยสำคัญในกรณีอาร์เรย์ใหญ่และแคช cold
• บนเซิร์ฟเวอร์ Intel การค้นหาแบบ 4 ทางใช้ประโยชน์จาก memory-level parallelism ได้ดีกว่า

แกนสำคัญของการ implement

• ฟังก์ชัน simd_quad รับอาร์เรย์ uint16_t, จำนวนองค์ประกอบ cardinality และค่าที่ต้องการหา pos แล้วคืนค่าบูลีน
• gap ถูกกำหนดคงที่เป็น 16 และหาก cardinality < gap จะค้นหาค่าด้วยลูปธรรมดา
• ลูปค้นหาบล็อกจะทำงานขณะ n > 3 โดยอ่านค่าองค์ประกอบสุดท้ายของบล็อกที่ตำแหน่ง 1/4, 2/4, 3/4 แล้วเปรียบเทียบว่าเล็กกว่า pos หรือไม่ จากนั้นเลื่อน base ตามผลรวมของการเปรียบเทียบทั้งสาม
• หลังจากนั้นขณะ n > 1 จะเปรียบเทียบตามครึ่งหนึ่งเพื่อลดช่วงที่เหลือ และสุดท้ายเลือกบล็อก lo
• บล็อกที่เลือกจะถูกเปรียบเทียบ 16 องค์ประกอบเป็น 2 ชุดด้วย vceqq_u16 ของ ARM NEON หรือ _mm_cmpeq_epi16 ของ x64 SSE2
• ช่วงองค์ประกอบที่เหลือจะคืนผล v == pos เมื่อเจอจุดที่ v >= pos และหากไม่พบจนสุดจะคืน false

บทสรุปและข้อมูลอ้างอิง

• binary search แบบตำราเป็นอัลกอริทึมที่ดี แต่ก็สามารถทำให้เร็วขึ้นได้อย่างมีนัยสำคัญในแง่ประสิทธิภาพจริง
• อัลกอริทึมมาตรฐานจำนวนมากไม่ได้ถูกออกแบบโดยตั้งสมมติฐานถึงความขนานระดับสูงของคอมพิวเตอร์ยุคปัจจุบัน
• SIMD Quad เป็นแนวทางที่พยายามใช้ทั้ง memory-level parallelism และ data parallelism
• ยังอาจมีอัลกอริทึมที่ดีกว่านี้ได้ และจำเป็นต้องมีแนวทางที่สร้างสรรค์มากขึ้น
• Source code
• Faster intersections between sorted arrays with shotgun

[GN⁺]

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

• แยกจากประเด็นเรื่องการปรับแต่งฮาร์ดแวร์ระดับล่างของ Daniel Lemire แล้ว binary search หรือรูปแบบดัดแปลงของมันจะเป็นทางเลือกที่ดีที่สุดก็ต่อเมื่อเราไม่รู้อะไรเลยนอกจากข้อเท็จจริงว่าข้อมูลถูกเรียงลำดับ/เป็นโมโนโทนิก
  ถ้ามีความรู้ล่วงหน้าเกี่ยวกับการกระจายตัวของข้อมูล ก็สามารถใช้ข้อมูลนั้นออกแบบอัลกอริทึมที่เร็วกว่าได้มาก ตัวอย่างเช่น ในพจนานุกรมกระดาษ คนสามารถข้ามไปยังชุดหน้าที่น่าจะใช่ได้เร็วกว่าการทำ binary search เชิงอุดมคติแบบล้วน ๆ
  ในเชิงคณิตศาสตร์ การค้นหาในลิสต์ที่เรียงลำดับแล้วค่อนข้างใกล้เคียงกับการแปลงกลับฟังก์ชันโมโนโทนิกด้วยอัลกอริทึมควบคุมแบบวงปิด และหากกำหนด cost function ที่เหมาะสม ก็อาจใช้ gradient descent หรือรูปแบบเร่งความเร็วของมันได้
  โดยทั่วไปแล้ว ถ้าอยากแก้ปัญหาให้มีประสิทธิภาพขึ้น วิธีที่ดีที่สุดคือใช้ข้อมูลเกี่ยวกับปัญหาเฉพาะที่ต้องการแก้ให้มากขึ้น แทนที่จะหยิบวิธีแก้ที่นามธรรมเกินไปมาใช้ ซึ่งอาจให้การเร่งความเร็วระดับหลักจำนวนที่ขยายต่อได้ มากกว่าการปรับปรุงแบบคูณค่าคงที่จากการใช้ฮาร์ดแวร์ให้ดีขึ้น
  • ผมคิดเรื่อง binary search มาพอสมควร แต่ก็ยังเอาชนะ implementation นี้ไม่ได้: https://github.com/protocolbuffers/protobuf/blob/44025909eb7...
    1. ตรวจแบบ O(1) ว่าเป็นลิสต์แบบหนาแน่นหรือไม่ 2) ตรวจขอบบน 3) ใช้ binary search แบบจำนวนรอบคงที่
       จำนวนรอบคงที่เป็นมิตรกับ branch predictor และลูปแกนกลางก็ถูกปรับแต่งค่อนข้างแน่นให้เหมาะกับฮาร์ดแวร์เป้าหมายโดยหลีกเลี่ยงการคูณด้วย ความพยายามจะทำให้ฉลาดกว่านี้ทุกครั้งกลับทำให้ลูปแย่ลงและไม่คุ้มต้นทุน ข้อมูลเป็น array-of-structs ขนาด 12 และ N ก็มักเล็กด้วย เลยยิ่งยาก
  • คำพูดที่ว่า “ใช้ข้อมูลเกี่ยวกับปัญหาเฉพาะที่ต้องการแก้ให้มากขึ้นจะดีกว่า” ฟังดูเหมือนเรื่องชัดเจน แต่ก็ลึกซึ้ง ยิ่งคุณมีข้อมูลอยู่แล้วมากเท่าไร ก็ยิ่งหมายความว่าคุณมีข้อมูลอยู่แล้วมากขึ้นเท่านั้น
  • ผมจำได้ว่าเคยอ่านบทความเกี่ยวกับ treap ที่แทนจะถ่วงสมดุลต้นไม้ ก็ใช้การ Huffman encode ความลึกในการค้นหาด้วยค่าน้ำหนัก เพื่อลดเวลาเข้าถึงเฉลี่ยเมื่อความถี่การเข้าถึงไม่เท่ากัน
    ไม่ได้บุ๊กมาร์กไว้ เลยต้องกลับไปหามันใหม่ประมาณปีละสองครั้ง
  • จริง แต่ประเด็นสำคัญคือบ่อยครั้งเราไม่ได้รู้ข้อมูลมากกว่านั้น
    นั่นจึงเป็นเหตุผลที่ B-tree เป็นมาตรฐานในฐานข้อมูล ข้อมูลอาจเป็นอะไรก็ได้ และถ้าดึง row ใหม่เข้ามาทีละมาก ๆ คุณลักษณะของมันก็อาจเปลี่ยนไปมากเมื่อไรก็ได้
    คุณอาจออกแบบให้ lookup เร็วขึ้นด้วยอัลกอริทึมอย่าง gradient descent ได้ แต่ B-tree นั้นเร็วมากอยู่แล้ว แถมคาดเดาประสิทธิภาพแย่สุดและความต้องการ I/O ได้ และยังมีข้อดีอีกมาก เช่น range scan, ordered traversal, เงื่อนไขแบบ prefix
    ถึงจะสร้างอัลกอริทึม lookup ที่มีประสิทธิภาพกว่ากับการกระจายตัวของข้อมูลเฉพาะแบบได้ แต่มักต้องเสียคุณสมบัติสำคัญบางอย่างไป แม้อัลกอริทึมอื่นจะให้ค่าประมาณเริ่มต้นที่ใกล้กว่า ก็อาจใช้เวลาหา item สุดท้ายช้ากว่า และแม้ค่าเฉลี่ยจะเร็วกว่า แต่ถ้าประสิทธิภาพแย่สุดเลวร้ายมากก็ใช้งานจริงได้ยาก
    แม้แต่ในพจนานุกรมกระดาษ หลังจากเดาครั้งแรกแล้ว คนก็มักใช้ binary search อยู่ดี ซึ่งลดการขยับได้แค่ไม่กี่ครั้ง พอไปถึงหน้าที่ใกล้ถูกแล้วก็มักลงเอยด้วยการไล่เชิงเส้นมากเกินจำเป็น ซึ่งถ้าทำ binary search แบบเคร่งครัดอาจเร็วกว่าก็ได้ แต่ต้องชั่งกับเวลาที่ใช้พลิกหน้า
  • Fritz Henglein เคยทำงานที่น่าสนใจเกี่ยวกับการ sort/group ที่เร็ว แกนหลักน่าจะเป็นงาน Generic Discrimination Sorting and Partitioning Unshared Data in Linear Time[1]
    Ed Kmett ได้นำแนวคิดนั้นมาขัดเกลาเป็นไลบรารี discrimination[2] สำหรับ Haskell และวิดีโอพูดคุยด้านเทคนิคที่เกี่ยวข้อง[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
• ผมรู้สึกว่า “quaternary” น่าจะใกล้เคียงกับการ unrolling ลูปของ binary search ออกมาหนึ่งขั้นมากกว่าไม่ใช่หรือ? สุดท้ายก็ต้องใช้จำนวนการเปรียบเทียบพอ ๆ กันเพื่อหา partition ที่มี item อยู่ เพียงแต่ประมวลผลครั้งละ 4 ส่วนแทน 2 ส่วน จึงน่าจะคล้ายกับ loop unrolling
  • มันซับซ้อนกว่านั้นอีกนิด โปรเซสเซอร์สมัยใหม่ทำ speculative execution จึงเดาผลการเปรียบเทียบแล้วเดินต่อไปตาม branch ด้านหนึ่งเรื่อย ๆ จนกว่าจะรู้ว่าเดาผิดหรือชนข้อจำกัดภายใน
    ถ้าผิดก็ทิ้งงานที่เดาไว้ เสีย penalty ไปไม่กี่ cycle แล้วค่อยเริ่มใหม่จากอีกจุด
    นั่นหมายความว่าในมุมมองของโปรเซสเซอร์ ทุกลูปก็ถูก unroll ไปบางส่วนอยู่แล้ว และต้นทุนหลักของ binary search คือการดึงข้อมูลจากหน่วยความจำหรือ cache ดังนั้นเกมที่แท้จริงคือการออกคำสั่งขอข้อมูลที่จะต้องใช้ในภายหลังให้เร็วที่สุดเพื่อลด latency
    การค้นหาแบบ quad หรือที่มีลำดับสูงกว่านั้น ไม่ได้ prefetch ลึกไปทาง branch ด้านเดียว แต่ prefetch ตื้น ๆ สำหรับทุกความเป็นไปได้แทน จึงมั่นใจได้ว่าจะออกคำสั่ง prefetch สำหรับข้อมูลที่ต้องใช้จริง และยังลด bandwidth ที่เสียไปกับข้อมูลที่ไม่ได้ใช้บนเส้นทางรันจริงลงเล็กน้อย
    “จำนวนครั้งของการเปรียบเทียบ” แทบไม่มีประโยชน์เลยในฐานะตัวชี้วัดเปรียบเทียบอัลกอริทึมค้นหาสำหรับทำนายประสิทธิภาพจริง คอขวดไม่ใช่จำนวนการเปรียบเทียบ แต่คือการใช้ memory และ cache bandwidth ให้เต็มที่ หากคำนึงถึงพฤติกรรม branch ของโปรเซสเซอร์ยุคใหม่ ก็พอมองว่าเป็น loop unrolling ได้
  • จะมองว่าเป็น loop unrolling เล็กน้อยก็ได้ เหตุที่แรงขึ้นไม่ใช่เพราะลดจำนวนคำสั่งหรือจำนวนการอ่านหน่วยความจำลงมากนัก แต่เพราะมันผ่อนคลาย dependency ระหว่างการคำนวณ ทำให้ไม่ใช่การรันแบบอนุกรมล้วน ๆ คล้ายกับการรันทั้งสองด้านของ branch แบบ speculative ด้วย
  • quaternary search ทำการเปรียบเทียบของรอบปัจจุบันพร้อมกับการเปรียบเทียบที่เป็นไปได้สองครั้งของรอบถัดไปแทบจะพร้อมกัน จึงซับซ้อนกว่าการ loop unrolling ธรรมดาเล็กน้อย
    อย่างไรก็ตาม การค้นหาทั้งสองแบบยังเป็น O(log N) และต่างกันแค่ค่าคงที่ ในวิชาอัลกอริทึมค่าคงที่อาจไม่สำคัญมาก แต่ในโลกจริงมันสำคัญได้มากทีเดียว
  • ก็จริงในระดับหนึ่ง แต่ยังลบ data dependency ระหว่างขั้นที่ถูก unroll ออกมาด้วย
  • เพราะโปรเซสเซอร์ไม่ได้ทำงานอย่างที่คนมักจินตนาการแบบง่าย ๆ
• ผมเพิ่งเขียนบทความ[1] เกี่ยวกับ Exponential Search[2] ไปเหมือนกัน เป็นอีกอัลกอริทึมที่ใช้ได้เมื่อคุณต้องทำ binary search ซ้ำ ๆ บนอาร์เรย์ที่ตัว element ที่จะค้นหาเองก็ถูกเรียงลำดับอยู่แล้ว
  สำหรับ workload ของเรา มันทำให้เร็วขึ้น 8 เท่า
  [1] https://lalitm.com/post/exponential-search/
  [2] https://en.wikipedia.org/wiki/Exponential_search
  • Exponential search มีประโยชน์กับ REST API ที่อ้างอิง resource ด้วย ID แบบลำดับต่อเนื่อง เมื่อคุณต้องการ ID ล่าสุดแต่ไม่มี endpoint เฉพาะให้
    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
    จากนั้นก็ทำ binary search ระหว่าง 2048 กับ 4096 เพื่อหา user ล่าสุด และโดยผลพลอยได้ก็รู้จำนวน user ด้วย เป็นข้อมูลที่มีประโยชน์มากเวลาส่องบริษัท SaaS คู่แข่ง
• CPU จะเข้าถึง cache line 64 ไบต์ ทั้งก้อนในครั้งเดียวอยู่แล้ว ดังนั้นจะค้นทั้ง cache line เลยก็ได้ เมื่อข้อมูลเข้ามาอยู่ใน CPU แล้ว ต้นทุนแทบจะใกล้ศูนย์
  เพราะงั้นผมเลยอยากลองทำการค้นหาแบบ ‘binary’ ที่ตรวจทุกค่าภายใน “cache line ตรงกลาง” ก่อน แล้วถ้าไม่พบค่อยไปซ้าย/ขวา การค้นภายใน cache line ทำได้ด้วยคำสั่ง 512bit SIMD เพียงคำสั่งเดียว
  cache line หนึ่งก้อนมี 64 ไบต์ หรือก็คือจำนวนเต็ม 16-bit ได้ 32 ค่า ดังนั้นการค้นหาแบบนี้อาจเร็วกว่า binary search ธรรมดาเกือบ 32 เท่า อย่างน้อยก็ลดการเข้าถึงหน่วยความจำลง 32 เท่า ซึ่งในโปรแกรมจริงส่วนใหญ่สิ่งนี้เป็นตัวครอบงำ
  • ใน binary search tree ที่เก็บเป็น sorted vector การเอา cache line ด้านบนทั้งก้อนมาเทียบกับ target ก็ยังมีโอกาสเจอตรง ๆ ต่ำอยู่ดี สิ่งที่ควรทำคือใช้ข้อมูลเพิ่มเติมภายใน line เพื่อลดการค้นหา ซึ่งสุดท้ายก็นำไปสู่ B-Tree/B+tree
    ถ้าใช้ key 4 ไบต์กับ child pointer หรือ array index 4 ไบต์ internal node หนึ่งอันจะใส่ key ได้ 7 ตัว child pointer 8 ตัว และ next pointer 1 ตัว พอดีเต็ม cache line 64 ไบต์ ทำให้ depth ของ tree สำหรับ 1 ล้าน entries ลดจากราว 20 ลงมาเหลือประมาณ 7 และหลาย level ด้านบนก็น่าจะค้างอยู่ใน cache
    คุณอาจเอา SIMD ไปใช้กับ B-tree node เพื่อเร่งการค้นภายใน node ได้เช่นกัน แต่มี data dependency สูงมาก
• ถ้าเป็นอาร์เรย์ขนาดเล็ก การทำ linear search โดยมี sentinel value ที่ท้ายอาร์เรย์นั้นชนะได้ยากอยู่แล้ว เพียงแต่คำว่า “เล็ก” เป็นคำขยายที่คลุมเครือเกินไป เลยทำให้รู้สึกภาพไม่ออกว่าเล็กแค่ไหน นี่คือจุดอ่อนของคำกล่าวนี้เอง
  • จาก benchmark ที่ยอดเยี่ยมในบทความนี้ linear search เริ่มตามไม่ทันที่ประมาณ 200~400 elements ดังนั้นมันไม่ใช่แค่คำพูดลอย ๆ
    โดยรวมแล้วผมชอบบทความนี้เพราะมันสำรวจสิ่งที่สงสัยมาบ่อย ๆ ได้อย่างครบถ้วนในรูปแบบ ablation study ที่มีประโยชน์
• ผมเคยลองทำการทดลองค้นหากับอาร์เรย์เล็ก ๆ ขนาด 16~32 รายการ แล้วพบว่า binary search เป็นหนึ่งในวิธีที่แย่เกือบสุด เพราะมี branch เยอะ
  วิธีที่เร็วที่สุดสำหรับอาร์เรย์เล็กคือ linear branchless search คือไล่ดูทุก element โดยไม่ออกจากลูปก่อนกลางทาง ตัวอย่างเช่น ถ้าคุณแค่อยากรู้ว่ามีเลขใดเลขหนึ่งอยู่ในอาร์เรย์หรือไม่ ก็แค่เอาผลการตรวจของทุก item มาทำ logical OR รวมกัน
  ไม่ได้ใช้ SIMD แต่ในอาร์เรย์เล็ก ๆ ต้นทุนของ branch แพงมาก การเช็กทุก element แบบไม่มี branch ตรง ๆ จึงเร็วกว่า
  • สงสัยว่าเร็วกว่าเพราะเป็นแพตเทิร์นที่ prefetcher ชอบด้วยหรือเปล่า
• คำอธิบายอัลกอริทึมทำให้ผมงงนิดหน่อย
  ส่วนของ SIMD มีอยู่เฉพาะในขั้นสุดท้ายที่ค้นหา 16 element ท้ายสุดเท่านั้น
  ส่วน Quad คือการตรวจ 3 จุดเพื่อสร้าง 4 เส้นทาง แต่สิ่งที่กำลังหาไม่ใช่แค่ key ที่ตรงกัน แต่เป็น block ที่ถูกต้อง
  รายละเอียดตรงนี้น่าสนใจอยู่บ้าง ผู้เขียนใช้ element สุดท้ายของแต่ละ block ใน quad search เลยสงสัยว่าถ้าใช้ element แรกของแต่ละ block หรือใช้ element แบบสุ่ม อัลกอริทึมจะเปลี่ยนไปอย่างไร
• สัญชาตญาณหลักตรงนี้เรื่องการ SIMD compare หลาย element ดูเหมือนจะนำไปใช้ในสเกลใหญ่กว่าขั้นสุดท้ายได้ด้วย
  ภาพรวมคือ 1) ใช้ gather ดึงหลาย element จากตำแหน่งที่เว้นระยะเท่า ๆ กัน 16 ตำแหน่ง 2) เปรียบเทียบแบบขนานด้วยคำสั่ง SIMD 3) โฟกัสไปที่ block ที่ถูกต้อง 4) ถ้า block เล็กพอให้สลับเป็น linear search ไม่เช่นนั้นก็ทำวงจร gather/compare ซ้ำ
  คำสั่ง gather อ่านหน่วยความจำที่ไม่ต่อเนื่องและอ่านมากกว่า binary sort ปกติ แต่เปิดทางให้เทียบหลายทางพร้อมกัน และเทียบเท่ากับการยุบ 4 ขั้นของ binary search ทิ้งไป จึงอาจคุ้มในตารางขนาดใหญ่
  อย่างไรก็ตาม ไม่ใช่ทุกชนิดข้อมูลที่จะทำการเปรียบเทียบ 16 ทางเต็มรูปแบบได้ การค้นหา float64 ถูกจำกัดที่ 8 ทางแม้บน AVX-512 แต่ int32 และ float32 ทำการเปรียบเทียบ 16 ทางได้
  • gather ช้ามาก คนที่เน้นประสิทธิภาพจะหลีกเลี่ยง gather
    ผมคิดว่าวิธีแบบอิง gather จะช้ากว่า binary search จริง ๆ
• อัลกอริทึมคลาสสิกในวิทยาการคอมพิวเตอร์ถูก “ออกแบบ” มาโดยปริยายสำหรับ CPU ที่แทบไม่มีความขนาน ไม่มีหลายคอร์ ไม่มี Hyper-threading ไม่มีคำสั่งแบบ SIMD และถือว่าเวลาเข้าถึงหน่วยความจำทุกครั้งเท่ากัน จึงไม่มีความต่างของ latency แบบ L1/L2/L3 cache ด้วย อีกทั้งยังสมมติว่าข้อมูลทั่วไปและสุ่ม
  ถ้าสมมติฐานข้อใดข้อหนึ่งนี้ไม่จริง ก็จะมี tweak มากมายเพื่อให้ได้ประสิทธิภาพที่ดีกว่า
  ข้อดีของอัลกอริทึมคลาสสิกคือ เมื่อเรารู้เพิ่มเกี่ยวกับรูปแบบข้อมูลเฉพาะหรือคุณลักษณะ/quirk ของ CPU เฉพาะรุ่น มันเป็นจุดตั้งต้นที่ยอดเยี่ยมสำหรับพัฒนาวิธีแก้ที่เหมาะและมีประสิทธิภาพยิ่งกว่า
  ยิ่งเข้าใกล้ปลายแหลมของการปรับแต่งมากเท่าไร ก็ยิ่งต้องมองว่าข้อมูลถูกเก็บและเข้าถึงในหน่วยความจำอย่างไร และการเปลี่ยนเพื่อปรับปรุงตรงนี้จะไม่ไปทำร้ายขั้นตอนถัดไปหรือไม่ ที่ทำงานเก่าของผมเคยมีคนใช้เวลานานมากปรับแต่งโค้ดส่วนหนึ่ง แต่การปรับแต่งนั้นกลับทำให้ข้อมูลที่ต้องใช้ทีหลังถูกดันหลุดออกจาก cache มากขึ้น จนทั้งแอปพลิเคชันช้าลง
  นี่น่าจะใกล้เคียงกับกฎข้อที่ 5 ของการเขียนโปรแกรมของ Rob Pike หรือถ้าย้อนกลับไปอีกก็คือการกล่าวซ้ำสิ่งที่ Fred Brooks ใน The Mythical Man Month เคยพูดไว้ อ้างอิง: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...
• ตอนเป็นวัยรุ่น ผมเคยคิดอยู่ทั้งสุดสัปดาห์ว่าถ้า binary search ดีเพราะมันลดพื้นที่ค้นหาลงครึ่งหนึ่งทุกขั้น งั้น ternary search ที่แบ่งเป็นสามส่วนทุกขั้นก็น่าจะดีกว่าไหม
  แทนที่จะเทียบกับค่าตรงกลาง ก็เทียบกับค่าที่จุด 1/3 แล้วถ้าต่ำเกินไปค่อยเทียบกับค่าที่จุด 2/3
  แต่ผมคิดว่าในแต่ละขั้น พื้นที่ค้นหาไม่ได้ลดจาก 2/3 เทียบกับ 1/2 เฉย ๆ เพราะมันลดเป็น 1/3 แทน 1/2 แต่ต้องแลกกับการเปรียบเทียบเฉลี่ย 3/2 เท่าเมื่อเทียบกับ binary search เลยสรุปว่าพอ ๆ กัน
  แก้ไข: ตามคำตอบของ zamadatix จริง ๆ แล้วเป็นการเปรียบเทียบ 5/3 เท่า เพราะกรณี 2/3 ต้องเทียบ 2 ครั้ง
  • วิธี ternary นี้ไม่ได้มีจำนวนการเปรียบเทียบเฉลี่ยต่อ level เท่ากับ 3/2
    1/3 แรกใช้เทียบ 1 ครั้ง, 1/3 ที่สองใช้ 2 ครั้ง, และ 1/3 ที่สามก็ใช้ 2 ครั้ง ดังนั้นค่าเฉลี่ยคือ (1+2+2)/3 = 5/3 มันเลยหลอกให้รู้สึกผิดง่ายว่ามี “1 ครั้งหรือ 2 ครั้ง เลยน่าจะ 50% ต่อ 50%” แต่จริง ๆ แล้วความน่าจะเป็นที่จะจบตั้งแต่การเทียบครั้งแรกคือ 1/3 และความน่าจะเป็นที่จะต้องเทียบ 2 ครั้งคือ 2/3
    ดังนั้น ternary จึงแย่กว่าเล็กน้อยในแง่จำนวนการเปรียบเทียบเฉลี่ยรวม 5/3 * Log_3[n] = 1.052... * Log_2[n]
    นั่นคือจำนวน level ลดลง แต่โดยเฉลี่ยต้องเปรียบเทียบมากขึ้นกว่าจะไปถึงปลายทาง ข้อสรุปนี้ใช้ได้กับการค้นหาประเภทที่มีจำนวนการ split มากกว่า 2 โดยทั่วไป ภายใต้สมมติฐานมาตรฐานบางอย่าง เช่น ค่าที่ค้นหามีการกระจายแบบสม่ำเสมอและต้นทุนการคำนวณถูกทำให้อุดมคติ ซึ่งความต่างของฮาร์ดแวร์จริงที่บทความพูดถึงก็เข้ามามีบทบาทตรงจุดนี้พอดี
  • ไอเดียของวัยรุ่นคนนั้นก็มีอะไรบางอย่างอยู่
    แค่ไม่ใช่ในฐานะเวอร์ชัน ternary ของอัลกอริทึม binary search มันไม่ใช่ ternary search จริง แต่ใกล้กับ binary search แบบเอนเอียงมากกว่า เพราะการเปรียบเทียบนั้นเป็น binary โดยเนื้อแท้ ดังนั้นอัลกอริทึมค้นหาที่มีการเปรียบเทียบจึงเป็น binary search ชนิดหนึ่ง และการเลือกตำแหน่งที่ไม่ใช่ element ตรงกลางย่อมมีประสิทธิภาพน้อยกว่าในมุมมองของ complexity แน่นอนว่าในฮาร์ดแวร์จริงมันอาจดีกว่าได้ภายใต้เงื่อนไขบางอย่าง ถ้าจะทำ ternary search จริง ๆ ต้องมี 3-way comparison เป็นปฏิบัติการพื้นฐาน
    ส่วนที่น่าสนใจคือเมื่อคิดเรื่อง radix efficiency[1] ตัวเลือกที่ดีที่สุดคือ 3 ซึ่งเป็นจำนวนเต็มที่ใกล้ e ที่สุด มันเกี่ยวข้องกับ tree search ด้วย จึงเป็นไปได้ว่า ternary tree อาจดีกว่า binary tree
    [1] https://en.wikipedia.org/wiki/Optimal_radix_choice
  • ในที่อย่างดิสก์ที่ seek ได้ไม่เร็ว คุณอาจใช้ 128-way B-tree เป็นต้น เพราะต้นทุนในการดึง key 128 ตัวไม่ได้แพงกว่าการดึง key 1 ตัวมากนัก แต่ช่วยลดจำนวน fetch ลงไปอีก 7 ครั้ง
  • แล้วจากนั้นคุณได้จินตนาการถึง CPU ที่มี ternary comparator ในตัวหรือเปล่า
  • ตั้งแต่สมัยเป็นวัยรุ่น CPU ก็ขยายทั้ง execution width และ vector capability อย่างมหาศาล throughput ที่เพิ่มขึ้นทำให้จุดคุ้มค่าขยับไปทางการเผาการคำนวณมากขึ้นเพื่อลด dependency chain
    ไอเดียนั้นอาจไม่สมจริงบน CPU ในยุคนั้น แต่บน CPU ยุคนี้อาจสมจริงขึ้นมาก