การค้นหาแบบไบนารีไร้การแตกแขนงที่เร็วที่สุด

• บทความนี้กล่าวถึงอิมพลีเมนเทชันการค้นหาแบบไบนารีทั่วไปใน C++ ที่สั้นกว่าและเร็วกว่า std::lower_bound มาตรฐานถึงสองเท่า
• อิมพลีเมนเทชันใหม่นี้เป็นแบบ "ไร้การแตกแขนง" เพราะถูกคอมไพล์เป็นคำสั่งย้ายข้อมูลแบบมีเงื่อนไขแทนการแตกแขนง/การกระโดดแบบมีเงื่อนไข
• การค้นหาแบบไบนารีทำงานโดยแบ่งรายการที่เรียงลำดับแล้วออกเป็นสองส่วนที่ตำแหน่งกึ่งกลาง และเปรียบเทียบค่ากลางกับค่าที่กำหนด จากผลการเปรียบเทียบจึงตัดสินใจว่าจะค้นหาต่อในรายการย่อยฝั่งใด
• บทความนี้ยังกล่าวถึงแนวคิดเรื่องการทำนายการแตกแขนง ซึ่งเป็นเทคนิคที่โปรเซสเซอร์ใช้รันคำสั่งแบบขนานเพื่อเพิ่มความเร็ว อย่างไรก็ตาม การค้นหาแบบไบนารีคาดเดาได้ยาก จึงไม่เหมาะกับการทำนายการแตกแขนงนัก
• ผู้เขียนแนะนำอิมพลีเมนเทชันการค้นหาแบบไบนารีใหม่ชื่อ sb_lower_bound ที่เร็วกว่าเวอร์ชันมาตรฐานและเวอร์ชัน branchless_lower_bound เนื่องจากมีจำนวนคำสั่งภายในลูปน้อยกว่ามาก
• ผู้เขียนยังนำเสนอเวอร์ชันที่เร็วกว่าอีกแบบคือ bb_lower_bound ซึ่งใช้วิธีแบ่งรายการค้นหาที่แตกต่างออกไป
• บทความนี้ปิดท้ายด้วยข้อเสนอแนะว่า หากส่วนที่ช้าที่สุดของโปรแกรมมีการค้นหาและ/หรือการเปรียบเทียบที่โปรเซสเซอร์คาดเดาไม่ได้ ให้ลองใช้ clang พร้อมออปชัน -mllvm -x86-cmov-converter=false และหากต้องการการค้นหาแบบไบนารีที่เร็วขึ้น ให้ลอง sb_lower_bound
• ผู้เขียนยังให้โค้ดของอิมพลีเมนเทชันการค้นหาแบบไบนารีใหม่ และอภิปรายประสิทธิภาพของแต่ละแบบอย่างละเอียด
• บทความนี้ได้รับการอัปเดตด้วยเวอร์ชันรีแฟกเตอร์ของ sb_lower_bound ที่ลดจำนวนคำสั่งแอสเซมบลีใน hot loop จาก 9 เหลือ 8 ส่งผลให้เร็วขึ้นเล็กน้อย
• ผู้เขียนยังกล่าวถึงแนวคิดเรื่องการพรีเฟตช์ ซึ่งเป็นการดึงหน่วยความจำบางส่วนเข้าสู่แคชล่วงหน้า เพื่อให้เมื่อจำเป็นต้องใช้ข้อมูลที่พรีเฟตช์ไว้จริง จะเกิดเพียงดีเลย์ของแคช L1/L2 เท่านั้น นอกจากนี้ยังมีเวอร์ชัน sb_lower_bound ที่เพิ่มการพรีเฟตช์สำหรับขนาด 256KB+
• บทความนี้เขียนโดย Mihail Dumitrescu และเผยแพร่เมื่อวันที่ 24 มิถุนายน 2023

[GN⁺]

ความเห็นบน Hacker News

• บทความกล่าวถึงแนวคิดและข้อดีที่อาจเกิดขึ้นของการค้นหาแบบไบนารีที่ไม่มี branch
• ความเห็นหนึ่งตั้งคำถามถึงความจำเป็นของการกำจัด branch โดยเสนอว่าการค้างของ pipeline จากการทำนาย branch พลาดไม่ใช่ส่วนที่เป็นแก่นแท้ของสถาปัตยกรรม
• ความเห็นดังกล่าวอธิบายเพิ่มเติมว่าการทำงานทั้งหมดโดยเนื้อแท้แล้วคือ branch และเหตุผลที่ branch เหล่านี้ไม่ทำให้ประสิทธิภาพเสียหายก็เพราะมันไม่ใช่ branch บน pipeline หลัก
• อีกความเห็นหนึ่งเสนอให้ใช้ภาษา Nim ที่คอมไพล์เป็นภาษาแบบ "bare-metal" เพื่อใช้งาน lowerBound
• มีการถกเถียงกันว่าโค้ดคืนค่าตัวที่ตรงกันตัวแรกหรือคืนค่าตัวที่ตรงกันตัวใดก็ได้ พร้อมเน้นย้ำความสำคัญของการทำความเข้าใจการทำงานของโค้ด
• ความเห็นหนึ่งชื่นชมบทนำที่เข้าใจง่ายของบล็อกโพสต์นี้ ซึ่งนำเสนอ implementation ของการค้นหาแบบไบนารีทั่วไปที่เร็วที่สุดใน C++ ได้อย่างรวดเร็ว
• มีความเห็นชี้ว่า Zig stdlib ไม่ได้เรียก C++ สำหรับการค้นหาแบบไบนารี และให้ลิงก์ไปยังการค้นหาแบบไบนารีใน Zig stdlib
• มีการอภิปรายเรื่องปัญหาของการค้นหาแบบไบนารีและ branch โดยเสนอว่าปัญหาไม่ได้อยู่ที่ branch เอง แต่อยู่ที่ data dependency ซึ่งทำให้ไม่รู้ว่าต้องดึงตำแหน่งหน่วยความจำถัดไปจากที่ใดจนกว่าการเปรียบเทียบจะเสร็จสิ้น
• ความเห็นหนึ่งแชร์ผลลัพธ์ประสิทธิภาพของการค้นหาแบบไบนารีบนโปรเซสเซอร์ Cascade Lake และเสนอว่า clang แย่กว่า gcc ในการ optimize โค้ดเฉพาะกรณีนี้
• ความเห็นหนึ่งตั้งคำถามถึงปลายทางของลิงก์ "BUT RUST" โดยบอกว่าลิงก์นี้ดูเก่าแล้ว
• มีความเห็นชี้ว่าผลลัพธ์ดังกล่าวใช้ไม่ได้กับฟังก์ชันเปรียบเทียบที่ซับซ้อนขึ้น และเสนอว่าวิธีที่ให้ประสิทธิภาพดีที่สุดคือใช้ sb_lower_bound กับชนิดข้อมูลพื้นฐาน และใช้ std::lower_bound ในกรณีอื่น
• ความเห็นสุดท้ายระบุว่าคุณสมบัติที่คาดเดาไม่ได้ตอนนี้ส่งผลต่อ cmov transformation pass แล้ว พร้อมให้ลิงก์สำหรับข้อมูลเพิ่มเติม