เบื้องหลัง GitHub Case-folding: เทคนิคการสแกนโค้ดความเร็วสูง 45 GiB/s

เมื่อผู้ใช้ค้นหาคำว่า "café" แต่ในคลังข้อมูลเก็บเป็น "CAFÉ" หรือพิมพ์ "straße" แต่ข้อมูลคือ "STRASSE" ระบบค้นหาจำเป็นต้องมีรูปแบบมาตรฐาน (Canonical form) เพื่อให้การจับคู่ถูกต้องโดยไม่ขึ้นกับตัวพิมพ์ รูปแบบนี้เรียกว่า Case folding ซึ่งถูกใช้งานในทุกที่ที่มีการเปรียบเทียบข้อความ ตั้งแต่ Search Engine ไปจนถึงชื่อโฮสต์ที่ไม่แยกแยะตัวพิมพ์

ที่ GitHub การทำงานพื้นฐานนี้มีความสำคัญอย่างยิ่ง เนื่องจาก Blackbird ซึ่งเป็นเอนจินค้นหาโค้ดต้องทำดัชนีซอร์สโค้ดมากกว่า 480TB จากคลังเก็บข้อมูล 180 ล้านแห่ง ทุกไบต์จะถูกทำ Case-folded ก่อนสร้างดัชนี และในทุกผลลัพธ์การค้นหาต้องมีการทำซ้ำเพื่อระบุตำแหน่งที่ตรงกัน ในสเกลขนาดนี้ แม้แต่ความเร็วในการประมวลผลพื้นฐานก็ส่งผลกระทบอย่างมหาศาล

บทความนี้จะอธิบายถึงวิธีการเพิ่มความเร็วในระดับที่เหนือความคาดหมาย โดยเริ่มต้นจากการเอาการเพิ่มประสิทธิภาพแบบเดิมๆ ออกไป เพราะการกวาดข้อมูลทั้งบัฟเฟอร์โดยไม่มีกิ่งก้านเงื่อนไข (Branch-free) นั้นเร็วกว่าการหยุดเมื่อเจออักขระที่ไม่ใช่ ASCII ซึ่ง GitHub ได้เปิดซอร์สเทคนิคนี้ในรูปแบบ Rust crate ชื่อว่า casefold

Folding ต่างจากการทำ Lowercasing อย่างไร

การใช้ str::to_lowercase อาจดูเป็นทางเลือกที่ง่าย แต่การทำ Lowercasing และ Folding มีวัตถุประสงค์ต่างกัน โดย Lowercasing ออกแบบมาเพื่อการแสดงผลซึ่งขึ้นอยู่กับท้องถิ่น (Locale) และบริบท เช่น อักษร Greek Sigma ที่เปลี่ยนรูปตามตำแหน่งในคำ หรือตัว I ในภาษาตุรกี

ในขณะที่ Case folding ถูกออกแบบมาเพื่อการเปรียบเทียบโดยเฉพาะ จึงต้องปราศจากบริบทและไม่ขึ้นกับท้องถิ่น เพื่อให้มั่นใจว่าหาก A ตรงกับ B แล้ว B จะต้องตรงกับ A เสมอไม่ว่าจะอยู่ในท้องถิ่นใด โดยอ้างอิงตามมาตรฐาน CaseFolding.txt ของ Unicode ซึ่ง crate นี้เลือกใช้การ fold แบบ 1 ต่อ 1 เพื่อความสอดคล้องกับเครื่องมืออย่าง ripgrep

อย่าหยุดก่อนกำหนด: เคล็ดลับความเร็วระดับหน่วยความจำ เนื่องจากซอร์สโค้ดส่วนใหญ่เป็น ASCII การทำให้ประมวลผลได้เร็วเท่าความเร็วหน่วยความจำคือเป้าหมายสูงสุด โค้ดที่เขียนกันทั่วไปมักใช้ if เพื่อตรวจสอบและหยุดเมื่อเจออักขระที่ไม่ใช่ ASCII เพื่อส่งต่อให้ Unicode path ทำงานต่อ ซึ่งบน Apple M4 โค้ดลักษณะนี้จะทำงานได้ประมาณ 3 GiB/s ซึ่งช้ากว่าจุดที่เหมาะสมที่สุดถึง 15 เท่าเพราะมีกิ่งก้านเงื่อนไข (Branches)

GitHub แก้ปัญหานี้ด้วยการลบกิ่งก้านออกทั้งหมด โดยใช้การคำนวณทางคณิตศาสตร์และ Masking แทนการใช้ if เช่น การใช้ high_bit_acc |= *b เพื่อสะสมสถานะอักขระที่ไม่ใช่ ASCII และทดสอบเพียงครั้งเดียวหลังจบลูป สิ่งที่เหลืออยู่คือลูปที่ไม่มีการควบคุมการไหลตามข้อมูล ทำให้คอมไพเลอร์สามารถเปลี่ยนเป็นเวกเตอร์ (Vectorizable) และใช้คำสั่ง NEON ประมวลผลได้ครั้งละ 16 ไบต์ จนทำความเร็วได้สูงถึง >45 GiB/s

การออกก่อนกำหนด (Break) คืออุปสรรคสำคัญของการทำเวกเตอร์ แม้จะทำให้ตัวลูปปราศจากกิ่งก้านแต่ถ้ายังคง Break ไว้ คอมไพเลอร์ก็ยังคงทำงานแบบสเกลาร์ (Scalar) ต่อไป บทเรียนสำคัญคือ ลูปที่ไร้กิ่งก้านจะมีค่าก็ต่อเมื่อมันเปิดทางให้คอมไพเลอร์ทำเวกเตอร์ได้เท่านั้น

การจัดการหน่วยความจำและ Unicode ที่มีประสิทธิภาพ

นอกจากการเพิ่มความเร็วลูปแล้ว GitHub ยังเน้นการหลีกเลี่ยงการจัดสรรฮีป (Heap Allocation) ที่ไม่จำเป็น โดย simple_fold จะพยายามแก้ไขข้อมูลในตำแหน่งเดิม (In-place) หากเป็น ASCII บริสุทธิ์ และจะจองบัฟเฟอร์ใหม่เพียงครั้งเดียวในขนาด 1.5 เท่าของอินพุตเฉพาะเมื่อจำเป็น เนื่องจากอักขระ Unicode บางตัวเมื่อ fold แล้วอาจมีความยาวเพิ่มขึ้นจาก 2 ไบต์เป็น 3 ไบต์

สำหรับการจัดการ Unicode ที่ซับซ้อน GitHub ใช้โครงสร้างตารางขนาดเล็กเพียง 1,776 ไบต์ ซึ่งรวมเอา Bitmap และการบีบอัดช่วง (Packed runs) เข้าด้วยกัน ทำให้สามารถตรวจสอบได้ในบิตเดียวว่าอักขระนั้นต้อง fold หรือไม่ โดยไม่ต้องเสียเวลาถอดรหัส UTF-8 เต็มรูปแบบ ซึ่งเร็วกว่าการใช้ HashMap ที่ต้องเสียเวลาแฮชคีย์และจัดการการชนกันของข้อมูล

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