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

 (mhdm.dev)
1 คะแนน โดย GN⁺ 2023-08-13 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • sb_lower_bound คงอินเทอร์เฟซแบบเดียวกับ std::lower_bound ไว้ และเมื่อสาขาการเปรียบเทียบถูกคอมไพล์เป็น conditional move (cmov) จะแสดงผลลัพธ์ที่เร็วกว่า binary search ทั่วไปได้สูงสุด 2 เท่า
  • ผลลัพธ์การเปรียบเทียบของ binary search มักเกิด branch prediction miss บ่อย เพราะไม่สามารถรู้ตำแหน่งที่จะค้นหาได้ล่วงหน้า และบน x86 ตัวเลือก clang -mllvm -x86-cmov-converter=false ช่วยลดปัญหานี้ได้
  • การใช้งานนี้ลด length ลงครึ่งหนึ่งในแต่ละลูป และอัปเดตเฉพาะ first ตามผลการเปรียบเทียบ จึงลดจำนวนคำสั่งลง โดยในช่วง 2^k <= n < 2^(k+1) จะเปรียบเทียบ k+1 ครั้งเสมอ
  • ใน benchmark ของ clang -cmov เวลาเฉลี่ยในการรันคือ std::lower_bound 61.30ns, sb_lower_bound 33.24ns, bb_lower_bound 32.73ns และค่า geometric mean ก็แตกต่างมากเช่นกัน คือ 39.17ns, 19.81ns, 21.33ns ตามลำดับ
  • ในการค้นหาสตริง 8 ไบต์ที่ฟังก์ชันเปรียบเทียบช้า มีบางกรณีที่ std::lower_bound นำอยู่เล็กน้อย และสำหรับอาร์เรย์ขนาดใหญ่ เวอร์ชันดัดแปลงที่เพิ่ม prefetching เร็วกว่า std::lower_bound โดยเฉลี่ยประมาณ 2.3 เท่า

โครงสร้างพื้นฐานของ sb_lower_bound

  • sb_lower_bound เป็นฟังก์ชัน C++ ในรูปแบบเดียวกับ std::lower_bound
    • อินพุตคือ first, last, value, comp
    • ค่าที่คืนคือ iterator ของตำแหน่งแรกที่การเปรียบเทียบล้มเหลว และถ้าองค์ประกอบทั้งหมดตรงตามเงื่อนไขจะคืน last
  • ลูปหลักลด length ลงครึ่งหนึ่ง และเลื่อน first ไปข้างหน้าเฉพาะเมื่อ comp(first[length], value) เป็นจริง
  • ในที่นี้ “branchless” ไม่ได้หมายความว่า if หายไป แต่หมายถึงกรณีที่ if นั้นถูกคอมไพล์เป็นคำสั่ง conditional move เช่น cmov แทน conditional jump
  • ใน clang หากใช้ตัวเลือก -mllvm -x86-cmov-converter=false รูปแบบนี้อาจถูกคอมไพล์เป็น conditional move ได้

จุดที่ std::lower_bound ช้าลง

  • binary search ทั่วไปจะเปรียบเทียบองค์ประกอบตรงกลางกับ value แล้วเลือกช่วงซ้ายหรือขวา
  • ในสถานการณ์ที่ไม่รู้ตำแหน่งของเป้าหมายการค้นหา if (comp(first[half], value)) มักกลายเป็น สาขาที่คาดเดายาก
  • CPU ใช้ branch prediction เพื่อรันคำสั่งถัดไปล่วงหน้า แต่ถ้าคาดเดาผิดก็ต้องทิ้งงานที่ทำไปแล้ว
  • หากใช้ conditional move จะเลือกค่าตามผลการเปรียบเทียบได้ พร้อมลด conditional jump
  • clang -cmov สามารถเปลี่ยน if/else บางส่วนของ std::lower_bound ให้เป็น conditional move ได้เช่นกัน ทำให้เร็วขึ้นประมาณ 25%
  • gcc ไม่มีตัวเลือกที่ดีในการบังคับ conditional move ในสถานการณ์เดียวกัน และปัจจุบัน sb_lower_bound ก็ไม่ได้ปล่อยโค้ดแบบ branchless โดยไม่ขึ้นกับระดับการปรับแต่ง

การค้นหา “ที่เหมาะที่สุด” ในมุมมองจำนวนครั้งการเปรียบเทียบ

  • “ที่เหมาะที่สุด” ในที่นี้หมายถึง binary search ที่มี จำนวนครั้งการเปรียบเทียบ น้อยที่สุด
  • ในลิสต์ขนาด n ผลลัพธ์ที่เป็นไปได้ของ std::lower_bound มี n+1 แบบ คือ ตำแหน่งองค์ประกอบ n ตำแหน่งรวมกับตำแหน่งท้ายอีก 1 ตำแหน่ง
  • หากขนาดลิสต์เป็น 2^k - 1 ผลลัพธ์ที่เป็นไปได้คือ 2^k แบบ และการเปรียบเทียบแต่ละครั้งให้ข้อมูล 1 บิตจริง/เท็จ ดังนั้นจำนวนครั้งการเปรียบเทียบที่เหมาะที่สุดคือ k ครั้ง
  • ในกรณี “nice” ที่ความยาวเป็น 2^k - 1 สามารถค้นหาแบบเหมาะที่สุดได้ด้วยลูปที่สั้นมาก
  • หากความยาวไม่ตรง อาจเกิด การเข้าถึงนอกช่วง ได้ เช่น เมื่อ value เป็น 4 ใน [0, 1, 2, 3, 4, 5]

ลักษณะประสิทธิภาพและข้อจำกัดของ sb_lower_bound

  • เมื่อ sb_lower_bound แบ่งช่วงที่มีความยาวเป็นจำนวนคู่ แม้ผลการเปรียบเทียบจะเป็นจริง แต่ในบางกรณีอาจข้ามองค์ประกอบไปไม่มากพอ
  • ในช่วง 2^k <= n < 2^(k+1) จะเปรียบเทียบ k+1 ครั้งเสมอ
  • ในช่วงเดียวกัน std::lower_bound จะเปรียบเทียบ k ครั้งหรือ k+1 ครั้ง และโดยเฉลี่ยประมาณ log2(n+1) ครั้ง
  • จำนวนครั้งการเปรียบเทียบอาจมากกว่า แต่จำนวนคำสั่งในลูปน้อยกว่ามาก ทำให้เวลาในการรันโดยรวมเร็วกว่า
  • หากฟังก์ชันเปรียบเทียบช้ามาก ความแตกต่างระหว่าง k+1 ครั้งกับ log2(n+1) ครั้งอาจส่งผลต่อประสิทธิภาพได้
  • หากต้องการบังคับ conditional move ใน gcc มีวิธีใช้ inline assembly เฉพาะ x86 เพื่อใช้ cmov แต่แบบเรียบง่ายจะเพิ่มจำนวนคำสั่ง และทางเลือกอื่นต้องเขียน assembly แยกตามชนิดข้อมูล

เวอร์ชันดัดแปลงที่เร็วกว่า bb_lower_bound

  • bb_lower_bound แบ่งช่วงด้วยวิธีอื่นจนกว่าความยาวจะอยู่ในรูป 2^k - 1 จากนั้นจึงค้นหาด้วยลูปที่สองซึ่งเร็วกว่า
  • length & (length + 1) ใช้ตรวจว่าความยาวอยู่ในรูป 11..1 หรือก็คือ 2^k - 1 หรือไม่
  • สำหรับความยาวที่ไม่ปกติ จะใช้ค่า MAGIC อย่าง auto step = length / 8 * 6 + 1 เพื่อเข้าใกล้ช่วง “nice” อย่างรวดเร็ว
  • โดยทั่วไป step ควรมากกว่าหรือเท่ากับ length / 2 เพื่อให้เข้าสู่ลูปเร็วได้บ่อย แต่ถ้าใกล้ length มากเกินไปก็จะเสียข้อดีของ binary search
  • เพราะมี break ทำให้ bb_lower_bound กลายเป็นรูปแบบที่มีสาขา
  • วิธีใช้ตารางที่คำนวณ step ที่เร็วที่สุดสำหรับทุกความยาวไว้ล่วงหน้า ยังเป็นเส้นทางที่ยังไม่ได้สำรวจ

การใช้งานแบบ branchless สมบูรณ์ไม่ได้เร็วกว่า

  • บนเครื่อง 64 บิต ลูปของ sb_lower_bound ทำซ้ำสูงสุด 64 ครั้ง ดังนั้นสามารถสร้างเวอร์ชัน “branchless สมบูรณ์” ที่ตัดแม้แต่การตรวจ length ออก โดยใช้ switch และ fall-through ที่ตั้งใจไว้
  • วิธีนี้มีโครงสร้างเป็นการกระโดดไปยังตำแหน่งโค้ดตามจำนวนครั้งการเปรียบเทียบที่ต้องใช้ด้วย std::bit_width(length)
  • ประสิทธิภาพจริงไม่ได้เร็วกว่า
  • CPU x86 รุ่นใหม่จัดการสาขาที่คาดเดาได้ เช่น เงื่อนไขลูป ได้ดี ดังนั้นจึงไม่มีประโยชน์จากการตัดการตรวจ length
  • ยังตัดสินว่าลูปทั่วไปดีกว่าในแง่ที่หลีกเลี่ยง template, macro และการคัดลอก-แก้ไข 64 เคสได้ด้วย

ผล benchmark

  • ผลลัพธ์ตาม clang -cmov ในเวลาเฉลี่ยในการรัน (ns) มีดังนี้
    • std::lower_: 61.30
    • branchless_lower_: 43.43
    • asm_lower_: 54.32
    • sb_lower_: 33.24
    • sbm_lower_: 35.54
    • bb_lower_: 32.73
  • ค่า geometric mean ของเวลาในการรัน (ns) ก็ต่ำที่สุดที่ sb_lower_
    • std::lower_: 39.17
    • branchless_lower_: 25.14
    • asm_lower_: 31.21
    • sb_lower_: 19.81
    • sbm_lower_: 20.91
    • bb_lower_: 21.33
  • sbm_lower_bound เป็นเวอร์ชันดัดแปลงที่ใช้รูปแบบ first += comp(first[length], value) * (length + rem) แทน if เพื่อชักนำให้ gcc สร้าง conditional move
  • การปรับแต่งนี้อาจหายไปใน gcc เวอร์ชันถัดไป จึงต้องมีคอมเมนต์และความระมัดระวัง
  • คำสั่ง benchmark ใช้ g++-10, clang++-10, clang++-10 -mllvm -x86-cmov-converter=false และเพิ่ม -march=haswell
  • การใช้ -march=native หรือไม่ระบุ -march ไม่ได้ส่งผลต่ออันดับมากนัก และการทดสอบทำบน Intel i7 Kaby Lake

การวัด branch prediction miss

  • การรัน clang ปกติที่วัดด้วย perf บันทึก branches ประมาณ 6.94 พันล้านครั้ง และ branch-misses ประมาณ 1.20 พันล้านครั้ง โดยอัตรา branch-misses อยู่ที่ 17.34%
  • การรัน clang -cmov บันทึก branches ประมาณ 4.07 พันล้านครั้ง และ branch-misses ประมาณ 35.95 ล้านครั้ง โดยอัตรา branch-misses ลดลงเหลือ 0.88%
  • -cmov กำจัดสาขาประมาณ 2.9 พันล้านรายการและ branch miss ประมาณ 1.2 พันล้านรายการ
  • สาขาที่ถูกกำจัดเป็นสาขาที่เคยคาดเดาพลาดด้วยความน่าจะเป็นประมาณ 41%
  • ค่านี้ใกล้กับ 50% ที่คาดได้จากสาขาที่คาดเดาไม่ได้โดยสิ้นเชิง

เมื่อฟังก์ชันเปรียบเทียบช้า ผลลัพธ์จะต่างออกไป

  • เพื่อดูสถานการณ์ที่ฟังก์ชันเปรียบเทียบช้ากว่า จึงทดสอบการค้นหาสตริง 8 ไบต์
  • ในเวลาเฉลี่ยในการรัน (ns) std::lower_bound เร็วกว่า sb_lower_bound เล็กน้อยหรือใกล้เคียงกัน
    • gcc: std::lower_ 160.01, sb_lower_ 165.66
    • clang: std::lower_ 157.71, sb_lower_ 162.68, bb_lower_ 157.22
    • clang -cmov: std::lower_ 156.06, sb_lower_ 164.71, bb_lower_ 157.48
  • ในกรณีนี้ std::lower_bound เร็วกว่า sb_lower_bound เพียงเล็กน้อยแต่สม่ำเสมอ
  • ไลบรารีอาจมุ่งให้ได้ประสิทธิภาพดีที่สุดด้วยการใช้ sb_lower_bound เมื่อทำงานกับ primitive type โดยตรง และใช้ std::lower_bound ในกรณีอื่น

ความแตกต่างที่เห็นใน assembly

  • hot loop ของ std::lower_bound ใน clang -cmov มี conditional move เช่น cmova, cmovbe แต่ใช้หลายคำสั่งในการอัปเดตความยาวและตำแหน่ง
  • hot loop ของ sb_lower_bound คำนวณความยาวครึ่งหนึ่ง เศษ และพอยน์เตอร์ที่จะเลื่อน จากนั้นอัปเดต first ด้วย cmova
  • assembly ของ branchless_lower_bound สั้นและสะอาดมาก แต่ในการทดสอบประสิทธิภาพ sb_lower_bound ให้ผลดีกว่าด้วย overhead ที่ต่ำกว่า

อัปเดต: sb_lower_bound ที่สั้นลง

  • หลังจากคอมเมนต์ของ ผู้เขียน orlp.net สามารถ refactor sb_lower_bound เพื่อลดจำนวนคำสั่ง assembly ใน hot loop จาก 9 คำสั่งเหลือ 8 คำสั่งได้
  • แก่นสำคัญคือ length - half เท่ากับ half + length % 2
  • รูปแบบที่ refactor แล้วจะคำนวณ half = length / 2 และถ้าการเปรียบเทียบเป็นจริงจะทำ first += length - half จากนั้นอัปเดต length = half
  • ใน clang -cmov เวลาเฉลี่ยในการรันดีขึ้นเล็กน้อยจากประมาณ 33ns เป็นประมาณ 32ns

สำหรับอาร์เรย์ขนาดใหญ่ prefetching ได้ผล

  • prefetching ที่เสนอในคอมเมนต์เป็นวิธีนำหน่วยความจำที่ต้องใช้เข้ามาในแคช L1/L2 ล่วงหน้า เพื่อลด latency เมื่อเข้าถึงจริง
  • ตัวอย่าง latency คือ L1 ประมาณ 4 cycles, L2 ประมาณ 12 cycles, L3 ประมาณ 40 cycles, หน่วยความจำประมาณ 200 cycles
  • ทั้ง gcc และ clang รองรับ __builtin_prefetch()
  • หาก prefetch ตำแหน่ง length / 4 จะมี 1 ใน 2 รายการที่สูญเปล่า และหากเพิ่มจนถึง length / 8 จะมี 5 ใน 6 รายการที่สูญเปล่า
  • การคำนวณตำแหน่ง prefetch และการเรียกเองก็มี overhead และใน hot loop ที่ทำให้สั้นแล้ว ต้นทุนนี้มีความสำคัญ
  • กลยุทธ์ prefetch หลายแบบไม่ได้ช่วยสำหรับอาร์เรย์ต่ำกว่า 256KB
  • ตั้งแต่ 256KB ขึ้นไป sbp_lower_bound ที่เพิ่ม prefetching ปรับปรุงเวลาเฉลี่ยในการรันจากประมาณ 32ns เป็นประมาณ 26ns ในการทดสอบสูงสุดประมาณ 4 ล้าน entry หรือ 16MB
  • ในการทดสอบที่ขยายภายหลังไปถึงประมาณ 128 ล้าน entry หรือ 512MB เวอร์ชัน prefetch เร็วกว่า std::lower_bound ตามเวลาเฉลี่ยประมาณ 2.3 เท่า
    • เกณฑ์เปรียบเทียบคือ std::lower_bound ประมาณ 161ns และเวอร์ชัน prefetch ประมาณ 71ns

ข้อสังเกตและทางเลือกสำหรับชุดข้อมูลขนาดใหญ่

  • เมื่อมีขนาดใหญ่มาก std::lower_bound แบบ branchless ที่ clang -cmov สร้างขึ้นช้ากว่าเวอร์ชันที่มีสาขา
  • CPU รุ่นใหม่สามารถตามสาขาที่คาดเดาไว้ พร้อมโหลดหน่วยความจำและทำ speculative execution ซึ่งทำหน้าที่คล้าย prefetch ได้ในทางปฏิบัติ
  • sbpm_lower_bound เป็นเวอร์ชันที่เพิ่ม prefetching ให้กับ sbm_lower_bound และชักนำให้ gcc สร้างโค้ด branchless ด้วยการคูณบูลีน
  • มีการกระโดดของกราฟประสิทธิภาพในช่วง 1 ล้านถึง 10 ล้านองค์ประกอบ จึงมีช่องให้สร้างการใช้งานที่เร็วกว่าในเชิงทฤษฎี
  • อย่างไรก็ตาม โค้ด prefetching ซับซ้อนขึ้นเรื่อย ๆ และมี magic constant เพิ่มขึ้น จึงประเมินว่ายิ่งซับซ้อนมาก โอกาสที่จะ contribute เข้า gcc/libstdc++ หรือ llvm/libc++ ก็ยิ่งต่ำ
  • ทางเลือกที่ฝ่าข้อจำกัดของ std::lower_bound คือ Eytzinger Binary Search ซึ่งจัดเรียงอาร์เรย์อินพุตใหม่เป็นรูป heap ของค่ากลางแบบไบนารี เพื่อให้การค้นหาเป็นมิตรต่อแคช
  • ในการทดสอบ int 16-ary tree ของ Sergey Slotin at CppCon 2022 ได้ผลลัพธ์เร็วกว่า std::lower_bound 7 ถึง 15 เท่า

โค้ดและเงื่อนไขการใช้งาน

  • หากการค้นหาหรือการเปรียบเทียบเป็นส่วนที่ช้าที่สุดของโปรแกรม และโปรเซสเซอร์คาดเดาผลการเปรียบเทียบได้ยาก สามารถลองใช้ตัวเลือก -mllvm -x86-cmov-converter=false ของ clang บน x86 ได้
  • หากต้องการ binary search ที่เร็วขึ้น สามารถลองใช้ sb_lower_bound ได้ และใน gcc sbm_lower_bound ก็เป็นอีกตัวเลือกหนึ่ง
  • โค้ดเผยแพร่ภายใต้ไลเซนส์ MIT
  • สามารถดูโค้ดและ benchmark ได้ที่ github.com/mh-dm/sb_lower_bound/

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2023-08-13
ความคิดเห็นจาก Hacker News

  • ทุกครั้งที่เห็นคนพยายาม ตัด branch ออก ผมก็สงสัยว่าพวกเขารู้ไหมว่าโครงสร้างที่ branch prediction ผิดพลาดแล้วทำให้ pipeline ยาว ๆ หยุดชะงักนั้นไม่ใช่องค์ประกอบที่จำเป็นของสถาปัตยกรรม CPU
    เหตุผลที่ pipeline ยาวก็เพราะมีการวิเคราะห์และแปลงจำนวนมากก่อนการ execute ทันที ซึ่งส่วนใหญ่สามารถทำไว้ล่วงหน้าได้ เพราะไม่ได้เป็นอัลกอริทึมที่มี dependency ของ state สูงนัก
    CPU Transmeta Crusoe ทำงานในลักษณะนี้ และเราสามารถจินตนาการถึงโลกที่ไม่ต้องกังวลเรื่อง branch ได้
    ถ้ามองให้ลึกขึ้น ทุก operation ก็คือ branch ที่ดูสถานะของบิตแล้วเปลี่ยนผลลัพธ์ แต่ branch เฉพาะที่ภายใน ALU แบบนี้ไม่ใช่ branch บน pipeline หลัก จึงไม่ทำร้ายประสิทธิภาพมากนัก

    • Dave ใช่ไหม? :-) สมัยก่อนมี paper ที่เปรียบเทียบ superscalar CISC กับ uniscalar RISC ในมุมมอง throughput ต่อเวลาและจำนวน instruction ต่อ clock
      จำได้ว่าตอนนั้นเคยบอก srk ด้วยว่า การเลือกใช้ metric ระหว่าง IPC กับ throughput มีผลต่อการมองว่าอะไรดีหรือไม่ดี
      ฝั่ง IPC มองว่าถ้าทำ IPC ให้สูงขึ้น ฝั่ง process ก็จะเพิ่ม clock ให้ ทุกคนก็ชนะ ส่วนฝั่ง throughput ใช้วิธีคิดที่สมจริงกว่า คือกฎของ Moore ตายแล้ว และถ้าหมุน silicon ให้เร็วขึ้นมันก็ละลาย ดังนั้นฝ่ายที่ออกแบบ ISA อย่างชาญฉลาดจะชนะ
      ตลอด 20 ปีที่ผ่านมา ทั้งสองฝั่งต่างก็มีทั้งความสำเร็จและความผิดหวัง และน่าสนใจที่ช่วงนี้ RISC-V กำลังพาเรากลับมาตั้งคำถามแบบนี้ในสถาปัตยกรรม CPU อีกครั้ง
      ยังเป็นจุดที่ดีในการติดตามว่าแนวคิด superscalar สมัยใหม่ถูกเพิ่มเข้ามาอย่างไรบนฐานความยืดหยุ่นของ instruction set และระยะยาวผมคิดว่าฝั่งนี้น่าจะชนะ
    • นี่เป็นความคิดที่ผิดอย่างสิ้นเชิง
      การแปลงของ Transmeta ไม่ได้ทำให้ต้นทุนของ branch หายไป
      ผมจำได้ว่า Linus ที่เคยทำงานที่ Transmeta พูดไว้ในเธรด comp.arch ทำนองว่า “หน้าที่ของ CPU คือทำให้เกิด cache miss ให้เร็วที่สุดเท่าที่จะทำได้”
      forced cache miss นั้นมีอยู่จริง และไม่มี JIT ใดลบมันได้
      ในโลกจริง แม้จะมี cache ขนาดมหึมาอย่างตอนนี้ ก็ยังหลีกเลี่ยง capacity miss ไม่ได้
      Itanium เองก็มองว่าสามารถกำจัดต้นทุนของ branch ได้ด้วย static analysis แต่ลองนึกดูว่าผลลัพธ์เป็นอย่างไร
      อยากให้โปรแกรมเมอร์อ่านหนังสือสถาปัตยกรรมคอมพิวเตอร์สักหน่อย ก่อนจะสรุปอย่างมั่นใจว่าสามารถทำสิ่งที่ดีกว่า processor ยุคใหม่ได้ง่าย ๆ
      ผมคิดว่าพวกเขาประเมินขนาดของความพยายามทางปัญญาที่ใส่ไว้ใน processor ปัจจุบันต่ำไปอย่างน้อยประมาณ 7 หลัก
    • ถึงจะไม่มี state ก็ได้ แต่ก็ยังพึ่งพา ปัจจัยที่ไม่รู้ในเวลา compile อยู่มาก
      หนึ่งในนั้นคือ input data ที่ถูกประมวลผล
      binary search เป็นกรณีแบบนั้นพอดี เพราะ compiler ไม่รู้ว่าผลลัพธ์จะถูกพบที่ตำแหน่งไหน
      อีกอย่างคือ microarchitecture โดยเฉพาะลำดับชั้น cache และการจัดวาง execution unit
      ถ้าเปลี่ยนไปใช้ ISA ที่มีคำสั่งคล้าย micro-operation ของ CPU ปัจจุบัน ก็ต้อง compile ใหม่สำหรับทุก microarchitecture
      แต่ประเด็นนี้ในทางเทคนิคแก้ได้ด้วย OS JIT แบบที่ GPU ปัจจุบันทำ คือแจกจ่ายโปรแกรมเป็นรูปแบบ bytecode (DXBC, SPIR-V, NVPTX) แล้วให้ user-mode GPU driver recompile เป็นคำสั่ง hardware จริง
      ตัวแปรที่ใหญ่กว่านั้นคือ CPU thread อื่น ๆ กำลังรันโค้ดที่ไม่อาจรู้ได้
      แม้จะตัด hyperthreading ออกเพื่อทำให้ core เป็นอิสระต่อกัน ก็ยังเหลือทรัพยากรที่แชร์กันทั้งชิปอยู่ดี เช่น L3 cache, หน่วยความจำภายนอก, bandwidth ของ I/O, พลังงาน และความร้อน
    • ผมคิดว่าประเด็นหลักอยู่ที่ นิยามของคำว่า branch
      ถ้านิยามทุกอย่างใหม่ว่าเป็น Branch™ ก็จะรวมสิ่งที่ไม่ใช่ branch จริง ๆ เข้าไปด้วย และ Branch™ บางส่วนก็สามารถคำนวณล่วงหน้าได้
      แต่ branch removal ที่พูดกันทั่วไปน่าจะหมายถึงกรณีที่เส้นทางการคำนวณแยกออกจริง ๆ ในโค้ดอย่าง if/else ไม่ใช่หรือ
      แม้ในโลกแบบนั้น การ optimize ที่มีประโยชน์ก็ยังเป็นไปได้ แต่จะจำกัดอยู่กับ Branch™ ที่พยายามคำนวณผลลัพธ์หลายอนาคตพร้อมกัน
    • อีกวิธีพูดคือ เหตุผลที่ pipeline ยาวก็เพราะมี งานอิสระ จำนวนมากที่ทำพร้อมกันได้ภายใน processor
      ทุกครั้งที่มี operation ที่ทำได้อย่างอิสระ ก็เกิดโอกาสที่จะ execute พร้อมกันได้เท่านั้น
      ไม่ได้หมายถึงแค่ decode, fetch, execute
      ถ้ามี ALU กับ shifter ที่เป็นอิสระกัน ก็สามารถ shift ระหว่างที่กำลัง add ได้ และถ้ามี adder กับ multiplier เฉพาะทาง ก็ไม่มีเหตุผลที่จะลองทำทั้งสองอย่างพร้อมกันไม่ได้
      นั่นหมายความว่าเราจะอยากให้หลาย instruction อยู่ระหว่างดำเนินการพร้อมกัน และต้องสามารถ fetch กับ decode instruction ได้เร็วกว่าอัตราการประมวลผล
      อีกทั้งยังนำไปสู่สถานการณ์ตามธรรมชาติที่อยาก reorder เพื่อไม่ให้คำสั่ง Add จำนวน N คำสั่งไปบดบัง Shift ที่เป็นอิสระ
      คุณอาจคิดว่าโครงสร้างปัจจุบันซับซ้อนเกินความจำเป็น และอาจไม่ได้ผิดก็ได้
      แต่ก็มีงานวิศวกรรมมหาศาลถูกทุ่มลงไปเพื่อสร้างโครงสร้างปัจจุบัน ดังนั้นถ้าคิดว่าหากไม่ใช้วิธีนี้จะทำให้เร็วขึ้นได้มาก ก็ควรขุดลึกลงไปดูว่าข้ออ้างนั้นแม่นยำแค่ไหน

  • ตรงส่วนที่ว่า “ถ้ามี ภาษา bare-metal ที่สะอาดและเร็วสำหรับเขียนทั้งหมดนี้ก็คงดี…” ผู้เขียนใส่เชิงอรรถ “BUT RUST..” และ “BUT ZIG..” ไว้ แต่ก็สงสัยว่า Nim จะเป็นอย่างไร
    ดูเหมือนจะมีการใช้งาน lowerBound ในไลบรารีเนทีฟ: https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al...
    ถ้าพูดอย่างเคร่งครัด มันไม่ใช่ภาษา “bare-metal” แต่คอมไพล์เป็น C หรือ C++ ได้ ดังนั้นน่าจะน่าสนใจถ้าดูว่ามันคอมไพล์ออกมาเป็นโค้ดแบบไหนที่นี่
    และก็สงสัยด้วยว่า C มีปัญหาอะไร

    • binary search ของ Zig อยู่ที่นี่ และเป็นการใช้งานแบบตำราเรียนที่ไม่ได้ปรับให้เหมาะสม: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...
      TigerBeetle ใช้ การใช้งานแบบไม่มี branch ของตัวเอง: https://github.com/tigerbeetle/tigerbeetle/blob/e996abcf7154...
    • ถ้าสร้าง ฟังก์ชันจัดเรียงแบบ generic ที่เทียบเท่าใน C ต่อให้ทำดีแค่ไหนก็ต้องมีโค้ดประกอบที่รกอยู่มาก
      นี่แหละคือกรณีใช้งานที่ทำให้ต้องมี C++ templates
    • ใน C มี พฤติกรรมที่ไม่ได้กำหนด มากเกินไป เช่น
      C ไม่สะอาด

  • ยังไม่แน่ใจว่านี่ใช่ lower_bound อยู่หรือเปล่า
    อาจเป็นเพราะอ่านโค้ดผิดก็ได้ แต่ดูเหมือนว่าเมื่อมีค่าซ้ำ มันจะคืนรายการที่ตรงกันรายการใดก็ได้ ไม่ใช่รายการแรกสุดที่ตรงกัน
    ถ้าฟังก์ชันเปรียบเทียบกำลังมองหาคำนำหน้าของสตริงหนึ่ง ๆ เพื่อทำ autocomplete แม้ในลิสต์ที่ไม่มีค่าซ้ำ ก็อาจมีหลายรายการที่ตรงกันได้ และตอนนั้นเราต้องการรายการแรกสุดในลิสต์

    • ทุกครั้งที่ตรงกัน มันจะลดความยาวที่เหลือลงครึ่งหนึ่ง และออกจากลูปก็ต่อเมื่อความยาวเป็น 0 ดังนั้นควรคืน รายการแรก
    • ก็ดูดีนะที่มีตัวเลือกสำหรับความเร็วที่สูงขึ้นโดยไม่สนใจว่ารายการที่ตรงกันเป็นรายการไหนแน่
    • จากที่ผมดู มันคืนรายการที่ตรงกันรายการแรกสุด
      อยากรู้ว่าทำไมถึงมองว่าไม่ใช่

  • อยากให้บล็อกทุกบทความเริ่มแบบบทความนี้: “คุณคงยุ่งอยู่ งั้นเข้าเรื่องเลยครับ นี่คือ การใช้งาน binary search ใน C++ ที่เร็วที่สุด ทั่วไปที่สุด และเรียบง่ายที่สุด”

  • ไลบรารีมาตรฐานของ Zig ไม่ได้เรียก C++ เพื่อทำ binary search
    binary search ปัจจุบันอยู่ที่นี่: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...

  • ยังไม่ค่อยเข้าใจ
    ปัญหาของ binary search กับ branch ไม่ใช่ ตัว branch เอง แต่คือก่อนจะเปรียบเทียบเสร็จ เรายังไม่รู้ว่าควรดึงตำแหน่งหน่วยความจำถัดไปตรงไหนในอาร์เรย์
    ไม่ว่าจะใช้ branch หรือใช้อะไรอย่างอื่น ประเด็นสุดท้ายคือเราต้องการให้โปรเซสเซอร์ทำอะไร
    มันมี data dependency
    ก่อนจะอ่านดัชนีกลาง เราไม่รู้ว่าจะค้นหาช่วงบนหรือช่วงล่าง
    เราอาจเดาแล้วออกคำสั่งอ่านทั้งสองฝั่งได้ ซึ่งจะช่วยแก้ dependency แต่ก็เพิ่มทราฟฟิกหน่วยความจำ
    ประเด็นสำคัญคือการแลกเปลี่ยนแบบนี้คุ้มไหม และการแค่ลบ branch ออกไม่ใช่คำตอบ

    • สำหรับอาร์เรย์ขนาดใหญ่ prefetching คือการแลกเปลี่ยนที่เหมาะสม
      มีพูดถึงตอนท้ายบทความ: https://mhdm.dev/posts/sb_lower_bound/#prefetching
    • ใช่
      ดังนั้น binary search ที่เร็วขึ้นจริง ๆ จึงใช้ การจัดวางอาร์เรย์แบบ Eytzinger: https://algorithmica.org/en/eytzinger
    • ถ้าอาร์เรย์ทั้งหมดอยู่ในแคช L1 ได้ครบ ต้นทุนของการทำนาย branch ผิดไม่น่าจะสูงกว่าการดึงข้อมูลจากหน่วยความจำมากหรือ?

  • บนโปรเซสเซอร์ Cascade Lake ของผม -mllvm -x86-cmov-converter=false ทำให้ประสิทธิภาพของ binary search ลดลงเกือบครึ่ง
    ตัวเลขคือจำนวน nanosecond ต่อ bsearch บนอาร์เรย์ uint32 ขนาด 100MB
    clang 15.0.7 ดูเหมือนจะแย่กว่า gcc 13.2.1 มากในการปรับโค้ดเฉพาะกรณีนี้ให้เหมาะสม
    ดู assembly ได้ที่นี่: https://godbolt.org/z/cbx5Kdjs6
    assembly ของ gcc ดูสะอาดกว่ามาก

    Benchmark gcc clang clang -cmov
    slow u32 23.4 46.7 45.8
    fast u32 18.1 19.8 31.4
    • ถ้าอย่างนั้นก็ดู https://mhdm.dev/posts/sb_lower_bound/#prefetching ได้
      100MB ใหญ่พอที่เวอร์ชันมี branch จะออกมาดีกว่าเล็กน้อย แต่ไม่ใช่เพราะมันดีกว่า หากเป็นเพราะลักษณะของ speculative execution บน x86

  • มีใครรู้ไหมว่าลิงก์ “BUT RUST” เดิมควรจะไปที่ไหน?
    ดูเหมือนมันจะพังไปแล้วเพราะไม่ได้ตรึงเวอร์ชันไว้ และไม่แน่ว่าอาจตั้งใจจะลิงก์ไปกลางคอมเมนต์เอกสารของ starts_with หรือเปล่า

    • จาก snapshot ของ archive.org ก่อนบทความเผยแพร่ไม่นาน [1] และหลังเผยแพร่ไม่นาน [2] ดูเหมือนว่าตั้งใจจะชี้ไปที่บรรทัดโค้ดนี้ ซึ่งตอนนี้กลายเป็นบรรทัดที่ 2779 [3]
      let mid = left + size / 2;

[1] https://web.archive.org/web/20230602210213/https://doc.rust-...

[2] [https://web.archive.org/web/20230709221353/https://doc.rust-...](<https://web.archive.org/web/20230709221353/…;)

[3] [https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779](<https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779>;)

  • ตั้งใจจะลิงก์ไปยัง อิมพลีเมนเทชันการค้นหาแบบไบนารี ของ Rust
    อัปเดตเป็น https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#... แล้ว

  • น่าสนใจที่ผลลัพธ์ไม่คงเดิมเมื่อใช้ฟังก์ชันเปรียบเทียบ comp ที่ซับซ้อนกว่า
    ในบทความ ผู้เขียนนึกถึงสถานการณ์การค้นหาแบบไบนารีที่ค่อนข้างสมจริง ซึ่งฟังก์ชันเปรียบเทียบช้า เช่น ID, หมายเลขโทรศัพท์, บัญชี, คีย์เวิร์ด จึงทดสอบการค้นหาสตริงขนาด 8 ไบต์
    ในกรณีนี้ std::lower_bound เร็วกว่า sb_lower_bound เพียงเล็กน้อยแต่สม่ำเสมอ และบอกว่าหากต้องการให้ได้ประสิทธิภาพดีที่สุดเสมอ ไลบรารีควรใช้ sb_lower_bound เมื่อจัดการชนิดข้อมูลพื้นฐานโดยตรง และใช้ std::lower_bound ในกรณีอื่น
    อยากเห็นการวิเคราะห์ตรงนี้

    • ผมคิดว่าสิ่งนี้เกิดขึ้นได้เพราะ branch prediction ช่วยให้ส่งการเปรียบเทียบหลายรายการเข้า pipeline พร้อมกันได้ และย้อนกลับได้เมื่อตัวทำนายทายผิด
      ถ้าเป็นข้อมูลและอินพุตแบบสุ่มจริง ๆ การทำนายน่าจะผิดประมาณครึ่งหนึ่ง
      วิธีแบบ CMOV จะติดอยู่เพราะมี data dependency หลังฟังก์ชันเปรียบเทียบ
      โดยเฉลี่ยแล้ว วิธีแบบมี branch จะทำการเปรียบเทียบได้สองครั้งพร้อมกัน ส่วน CMOV ทำได้ครั้งเดียว ดังนั้นเมื่อเวลาที่ใช้ในการเปรียบเทียบมากกว่า penalty จากการทำนาย branch ผิด ก็น่าจะมีจุดที่ผลพลิกกลับ
    • ถ้าเป็นกรณีนี้ ก็น่าจะมีเวอร์ชันการค้นหาแบบไบนารีที่ดีกว่านี้มากสำหรับชนิดข้อมูลพื้นฐาน
      สิ่งที่เคยลองทำแบบคร่าว ๆ ด้วย SIMD เมื่อก่อน เร็วกว่า std::lower_bound 3 เท่า จนกว่าจะไปติดที่แบนด์วิดท์หน่วยความจำ: https://github.com/matthewkolbe/ThinkingInSimd/tree/main/alg...
    • ในบทความ ผมหาการรับประกันใด ๆ เกี่ยวกับชุดข้อมูลอินพุตหรือเนื้อหาของคีย์ค้นหาไม่เจอ นอกจากคำว่า “คาดเดาไม่ได้”
      สมมติว่าเป็นสุ่มล้วน ๆ แต่ถ้าสตริง 8 ไบต์เหล่านี้ไม่ใช่ข้อมูลบริสุทธิ์ ตัว branch predictor สมัยใหม่ก็อาจทำผลงานได้ดีกว่า cmov ได้ง่าย ๆ

  • ดูเหมือนว่าแอตทริบิวต์ unpredictable ตอนนี้จะมีผลต่อ cmov transformation pass แล้ว
    อ้างอิง ณ วันที่ 1 มิถุนายน ดังนั้นน่าจะเข้าไปอยู่ใน clang 17/18: https://reviews.llvm.org/D118118