เทคนิคชื่อ branchless binary search ทำให้โค้ดค้นหาข้อมูลสุดพื้นฐานอย่าง binary search เร็วขึ้นราว 6 เท่า หัวใจของมันไม่ใช่การให้ CPU (สมองประมวลผลของคอมพิวเตอร์) ทำงานน้อยลง แต่คือการเลิกบังคับให้มันต้องเดาทาง ตัว binary search เองเป็นวิธีค้นหาแบบเดียวกับที่เราเปิดพจนานุกรม เปิดกลางเล่มก่อน ถ้าคำที่หาอยู่ค่อนไปทางท้ายเล่ม ก็ทิ้งครึ่งแรกไปทั้งครึ่ง แล้วแบ่งครึ่งที่เหลือแบบนี้ไปเรื่อยๆ จนเจอ วิธีนี้เป็นบทเรียนแรกๆ ของคนหัดเขียนโปรแกรม และฝังอยู่ในซอฟต์แวร์แทบทุกตัวที่เราใช้กันทุกวัน

คนที่พิสูจน์ตัวเลขนี้คือ Itamar Turner-Trauring เจ้าของบล็อก Python⇒Speed เขาหยิบงานจริงชิ้นหนึ่งมาเป็นโจทย์ งานนั้นมาจากขั้นตอนเทรนโมเดลของ scikit-learn ไลบรารี machine learning ที่คนใช้กันทั้งโลก ตัวงานคือการนำค่าทศนิยมนับล้านค่ามาจัดลงถัง 255 ใบตามช่วงของค่า ซึ่งเดิมใช้ binary search ธรรมดาแบบในตำรา เขาเขียนโค้ดนี้ใหม่ด้วยภาษา Rust แล้วไล่ปรับทีละขั้น วัดผลทุกขั้นด้วยตัวนับที่อยู่ใน CPU โดยไม่เพิ่มคอร์ และไม่เปลี่ยนเครื่อง

ขั้นแรกแค่เอาทางแยกออกจากโค้ด ก็เร็วขึ้น 3.5 เท่าทันที ส่วนอีกสองขั้นที่เหลือเป็นการขัดเกลาโค้ดต่ออีกชั้น ช่วยดันความเร็วไปถึง 6 เท่า แต่เวอร์ชันที่เร็วขึ้น 3.5 เท่ากลับไม่ได้ทำงานน้อยลงเลย มันสั่งงาน CPU ทั้งหมด 188.1 ล้านคำสั่ง มากกว่าโค้ดเดิมที่สั่ง 184.9 ล้านคำสั่งด้วยซ้ำ สิ่งเดียวที่หายไปคือการเดาผิดของ CPU ตามปกติ CPU จะเดาล่วงหน้าว่าโค้ดจะไปทางไหน แล้วลงมือทำไปก่อนโดยไม่รอ โค้ดเวอร์ชันเดิมทำให้มันเดาผิดถึง 16.6% ส่วนเวอร์ชันใหม่เขียนแบบไม่เหลือทางแยกให้เดา ตรงตามชื่อ branchless ที่แปลว่าไม่มีทางแยก ตัวเลขเดาผิดจึงเหลือ 0%

CPU ไม่ได้รอคำตอบ มันเดาไปก่อน

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

ฝั่ง CPU เวลาเจอ if มันไม่ได้หยุดรอให้เงื่อนไขได้คำตอบก่อน แต่จะเดาล่วงหน้าว่าน่าจะไปทางไหน แล้วเริ่มประมวลผลทางนั้นทันทีควบคู่กับงานอื่นที่ค้างอยู่ ตัวที่รับหน้าที่เดาคือ branch predictor หรือตัวเดาทางของ CPU ซึ่งเดาจากสถิติของคำตอบครั้งก่อนๆ

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

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

แต่โจทย์จัดค่าลงถังไม่ใช่แบบนั้น ขอบของถังทั้ง 255 ใบวางห่างเท่าๆ กัน และข้อมูลที่ไหลเข้ามาก็กระจายทั่วช่วง ทุกครั้งที่โค้ดถามว่าซ้ายหรือขวา โอกาสไปแต่ละทางจึงพอๆ กันเหมือนโยนหัวก้อย ตัวเดาทางเลยไม่มีแนวโน้มอะไรให้ใช้คาดการณ์ ผลที่วัดได้คือโค้ดเวอร์ชันเดิมเจอทางแยกทั้งหมด 27 ล้านครั้ง เฉลี่ยราว 27 ครั้งต่อหนึ่งค่า และเดาผิดไป 16.6%

ผลรวมของการเดาผิดไปปรากฏที่ค่า IPC ซึ่งคือจำนวนคำสั่งที่ CPU ทำเสร็จในหนึ่งรอบสัญญาณนาฬิกา ซีพียูสมัยนี้ทำได้หลายคำสั่งต่อรอบสบายๆ แต่โค้ดเวอร์ชันเดิมทำได้แค่ 1.1 เพราะเวลาส่วนใหญ่หมดไปกับการทิ้งงานแล้วเริ่มใหม่

เอา if ออกจากลูป แล้วการเดาผิดก็เหลือ 0%

เวอร์ชัน branchless แก้โค้ดเดิมแค่สองจุด

จุดแรกคือทำจำนวนรอบของลูปให้ตายตัว ของเดิมวนไปเรื่อยๆ จนกว่าจะเจอถังที่ใช่ จำนวนรอบจึงขึ้นกับข้อมูลแต่ละค่า ของใหม่สั่งวน 8 รอบเท่ากันทุกครั้ง เพราะการแบ่งครึ่งจากถัง 255 ใบ ยังไงก็เหลือใบเดียวภายใน 8 ครั้งเสมอ

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

พอไม่มีทางแยก ก็ไม่มีอะไรให้เดา และไม่มีอะไรให้เดาผิด การเดาผิดที่วัดได้เหลือ 0.0% เวลาทำงานลดจากราว 45.9 มิลลิวินาที เหลือ 13.2 มิลลิวินาที คือเร็วขึ้น 3.5 เท่าจากการแก้สองจุดนี้เท่านั้น

ค่า IPC ยืนยันเรื่องเดียวกัน มันพุ่งจาก 1.1 ขึ้นเป็น 4.0 ซีพียูตัวเดิมและเครื่องเดิมประมวลผลคำสั่งต่อรอบได้เกือบสี่เท่าของเดิม เพราะไม่ต้องทิ้งงานกลางทางอีกแล้ว

ข้อเสียของวิธีนี้ก็มี คือ CPU ต้องคำนวณทั้งสองทางทุกรอบ และต้องรอให้ค่าที่ใช้ตัดสินพร้อมก่อนจึงจะเลือกได้ จึงต้องรอสั้นๆ เท่ากันทุกรอบ แต่ก็ยังเสียเวลาน้อยกว่าการเดาผิดแล้วทิ้งงานทั้งกองอยู่มาก

อีกสองขั้นที่พา binary search ไปถึง 6 เท่า

ขั้นที่สองคือตัดการทำงานที่ซ่อนอยู่ออก ปกติ Rust จะแอบเช็คให้ทุกครั้งที่โค้ดหยิบข้อมูลจากชุดข้อมูลที่เรียงลำดับไว้ ว่าตำแหน่งที่ขอเลยขอบไปหรือเปล่า การเช็คแบบนี้ก็คือ if ที่ซ่อนอยู่อีกชุดหนึ่ง เวอร์ชันนี้จึงเปิดโหมด unsafe ของ Rust เพื่อข้ามการเช็คขอบทั้งหมดไป และยังทำอีกอย่างควบคู่กัน คือค่าไหนที่ต้องใช้ซ้ำทุกรอบ ก็คำนวณเตรียมไว้ล่วงหน้าครั้งเดียว ไม่ต้องคำนวณใหม่ทุกค่า

ขั้นสุดท้ายคือจัดลูปใหม่ทั้งชุด เดิมโค้ดไล่จบทีละค่า ค่าใครค่ามัน ของใหม่เปลี่ยนมาจับข้อมูลเป็นชุด ชุดละ 16 ค่า แล้วพาทั้งชุดเดินหน้าไปพร้อมกันทีละขั้นของการแบ่งครึ่ง ทุกค่าในชุดจึงทำงานขั้นเดียวกันเป๊ะๆ เสมอ จากนั้นกำหนดตัวเลือก target-cpu=x86-64-v3 ให้คอมไพเลอร์สร้างคำสั่งสำหรับซีพียูรุ่นใหม่โดยเฉพาะ คอมไพเลอร์ก็แปลงลูปนี้ให้กลายเป็นคำสั่งชนิดที่ประมวลผลข้อมูลหลายค่าได้ในคำสั่งเดียว ซึ่งเรียกกันว่า SIMD

โค้ดทั้งสี่เวอร์ชันในตารางเขียนด้วย Rust เหมือนกันหมด ความเร็วที่เพิ่มขึ้นจึงไม่ได้มาจากการเปลี่ยนภาษา จริงอยู่ การย้ายไปใช้ภาษาที่เร็วกว่าช่วยได้มาก เหมือนที่ Astro 7.0 ยกเครื่องเครื่องมือเบื้องหลังใหม่ด้วย Rust แล้วงานเบื้องหลังเร็วขึ้น 15-61% แต่เคสนี้บอกอีกด้านหนึ่งด้วยว่า ต่อให้ย้ายภาษาเสร็จแล้ว โค้ดก็ยังเร็วขึ้นได้อีกหลายเท่า แค่ปรับให้เข้ากับวิธีทำงานจริงของ CPU

ความเร็วที่เพิ่มขึ้นต้องแลกกับอะไรบ้าง

ข้อแรก โค้ดอ่านยากขึ้นชัดเจน binary search แบบมาตรฐานอ่านสิบวินาทีก็เข้าใจ ส่วนเวอร์ชันสุดท้ายที่วน 8 รอบตายตัว เลือกค่าแบบไม่มีทางแยก และไล่ข้อมูลทีละ 16 ค่า ต้องนั่งอ่านกันพักใหญ่กว่าจะเห็นว่ามันคือการค้นหาแบบแบ่งครึ่งตัวเดิม

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

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

ควรใช้ branchless เมื่อไหร่ และเมื่อไหร่ที่ไม่ต้องใช้

เทคนิคนี้คุ้มก็ต่อเมื่อเข้าเงื่อนไขสองข้อพร้อมกัน เงื่อนไขแรกคือลูปนั้นวนหนักจริง ระดับล้านรอบขึ้นไปจนกินเวลาส่วนใหญ่ของโปรแกรม เงื่อนไขที่สองคือ if ในลูปนั้นเดาทางไม่ได้จริงๆ เพราะข้อมูลกระจายแบบสุ่ม ขาดข้อใดข้อหนึ่งเมื่อไหร่ ผลที่ได้จะไม่คุ้มความยุ่งยากที่ตามมา

ถ้า if ตัวไหนให้คำตอบทางเดิมเกือบทุกรอบ อย่าไปยุ่งกับมัน ตัวเดาทางของ CPU จัดการเคสแบบนั้นได้ดีอยู่แล้ว ถ้าฝืนเขียนแบบไม่มีทางแยก มีแต่จะช้าลง เพราะต้องคำนวณทั้งสองทางทุกรอบทั้งที่รู้คำตอบอยู่แล้ว คอมไพเลอร์เองก็คิดแบบเดียวกัน มันจะเลือกใช้คำสั่งเลือกค่าแบบไม่มีทางแยกก็ต่อเมื่อประเมินว่าโอกาสเดาถูกต่ำกว่าราว 75% เท่านั้น

โค้ดสองแบบนี้ยังมีพฤติกรรมต่างกันอีกเรื่อง ความเร็วของโค้ดที่มีทางแยกขึ้นกับว่าข้อมูลเดาง่ายแค่ไหน ข้อมูลเปลี่ยน ความเร็วก็เปลี่ยนตาม ส่วนโค้ดแบบไม่มีทางแยกใช้เวลาเท่าเดิมทุกครั้งไม่ว่าข้อมูลหน้าตาเป็นแบบไหน งานบางประเภทต้องการความนิ่งแบบนี้มากกว่าความเร็วดิบเสียอีก

และก่อนจะแก้โค้ดสักบรรทัด ให้วัดก่อนเสมอ ไม่ใช่เดาเอา ตัวนับใน CPU บอกได้ตรงๆ ว่าระหว่างรันเกิดอะไรขึ้นบ้าง ทั้งจำนวนคำสั่ง จำนวนทางแยก และเปอร์เซ็นต์การเดาผิด ตัวเลขพวกนี้เครื่องมือวัดความเร็วโค้ดทั่วไปไม่แสดง บทความต้นทางอ่านค่าพวกนี้ผ่าน Python ด้วยเครื่องมือชื่อ py-perf-event

ตัวเลข 16.6% ของเคสนี้ไม่ได้มาจากการเดา แต่มาจากการเปิดตัวนับใน CPU ดู โค้ดช้าๆ ในเครื่องของเราเองก็มีตัวเลขแบบเดียวกันรออยู่ ต่างกันแค่ยังไม่มีใครเปิดดู

---

ที่มา:

• บทความ 6× faster binary search: from compiled code to mechanical sympathy จาก Python⇒Speed
• บทความ Branchless Programming จาก Algorithmica