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

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

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

โจทย์ทดสอบนี้มาจากงานจริง ในขั้นตอนเทรนโมเดลของ scikit-learn ซึ่งเป็นไลบรารี machine learning ที่คนใช้กันทั้งโลก ต้องนำค่าทศนิยมเป็นล้านค่ามาจัดลงถัง 255 ถัง โค้ดที่ทำงานนี้คือ binary search แบบมาตรฐานที่เรียนกันในวิชาแรกๆ

ตัวเลขข้างบนมาจากการทดลองของ Itamar Turner-Trauring เจ้าของบล็อก Python⇒Speed เขานำโจทย์เดียวกันนี้มาเขียนใหม่ด้วย Rust ภาษาที่คอมไพล์เป็นโค้ดเครื่องโดยตรง แล้วไล่แก้ทีละขั้นและวัดผลด้วยตัวนับใน CPU จนทำให้โค้ดเร็วขึ้นราว 6 เท่า โดยไม่เปลี่ยนอัลกอริทึม ไม่เพิ่มคอร์ และไม่เปลี่ยนเครื่อง

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

เมื่อโค้ดเจอ if CPU ไม่ได้หยุดรอดูว่าเงื่อนไขจะพาโค้ดไปทางไหน แต่มันจะเดาล่วงหน้าแล้วเริ่มประมวลผลตามทางนั้นไปก่อน พร้อมกับงานอื่นที่ค้างอยู่ ตัวที่ทำหน้าที่นี้เรียกว่า branch predictor (ตัวเดาทางของ CPU) โดยอาศัยสถิติจากสิ่งที่เคยเจอ

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

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

ปัญหาของเคสนี้คือขอบถังทั้ง 255 ใบวางห่างกันเท่าๆ กัน และข้อมูลที่ไหลเข้ามาก็กระจายทั่วช่วง ทุกครั้งที่ binary search ถามว่าจะไปซ้ายหรือขวา โอกาสไปแต่ละทางจึงพอๆ กันเหมือนโยนหัวก้อย ตัวเดาทางไม่มีสถิติอะไรให้เกาะ ผลที่วัดได้คือโค้ดเดิมเดาผิด 16.6% จากการเจอทางแยกในโค้ดทั้งหมด 27 ล้านครั้ง หรือราว 27 ครั้งต่อหนึ่งค่า ส่วน IPC (จำนวนคำสั่งที่ CPU ทำเสร็จได้ในหนึ่งรอบสัญญาณนาฬิกา) ร่วงไปอยู่ที่ 1.1 ทั้งที่ซีพียูสมัยนี้ทำได้หลายคำสั่งต่อรอบสบายๆ

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

เวอร์ชัน branchless เปลี่ยนโค้ดแค่สองจุด

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

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

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

ตัวเลขที่อธิบายเหตุผลได้ชัดที่สุดคือ 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 แล้ว build เร็วขึ้น 15-61% แต่หลังจากย้ายเสร็จแล้ว การปรับโค้ดที่คอมไพล์แล้วก็ยังทำให้เร็วขึ้นได้อีก 6 เท่า

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

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

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

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

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

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

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

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

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

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

---

ที่มา:

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