Tối ưu hóa Case-folding: Đạt tốc độ xử lý bộ nhớ trên 45 GiB/s

Trong quá trình phát triển công cụ tìm kiếm mã nguồn Blackbird, GitHub đối mặt với thách thức xử lý hơn 480TB dữ liệu. Một trong những thao tác cơ bản nhưng tiêu tốn tài nguyên nhất là case-folding (chuyển đổi ký tự về dạng chuẩn để so sánh không phân biệt hoa thường). Bài viết này chia sẻ cách đội ngũ kỹ sư GitHub đạt được tốc độ xử lý hơn 45 GiB/s trên một nhân CPU bằng cách thay đổi tư duy lập trình truyền thống.

Tại sao không nên dừng sớm (Don’t stop early)?

Thông thường, khi xử lý chuỗi, các lập trình viên thường sử dụng vòng lặp kiểm tra từng byte và dừng lại ngay khi gặp ký tự không phải ASCII. Tuy nhiên, cách tiếp cận này vô tình ngăn cản trình biên dịch thực hiện vectorization (tối ưu hóa bằng tập lệnh SIMD). Bằng cách loại bỏ các nhánh điều kiện (branchless) và sử dụng các phép toán số học thay vì kiểm tra phạm vi if, GitHub đã cho phép trình biên dịch tối ưu hóa vòng lặp triệt để.

Kết quả đo đạc cho thấy, việc loại bỏ hoàn toàn lệnh break giúp tăng tốc độ xử lý từ 3.1 GiB/s lên hơn 45 GiB/s. Bài học rút ra là: trong các vòng lặp nóng (hot loop), các nhánh điều kiện (branch) chính là rào cản lớn nhất đối với hiệu năng.

Chiến lược tối ưu hóa

• Vectorization: Việc loại bỏ các nhánh điều kiện giúp mã nguồn được chuyển đổi thành các lệnh vector, tận dụng tối đa băng thông bộ nhớ.
• Tránh cấp phát bộ nhớ (Heap allocation): GitHub tối ưu hóa bằng cách kiểm tra xem chuỗi có cần thay đổi hay không trước khi cấp phát bộ nhớ mới. Nếu chuỗi là ASCII thuần túy, dữ liệu được xử lý tại chỗ (in-place) mà không tốn thêm chi phí cấp phát.
• Cấu trúc dữ liệu cho Unicode: Thay vì sử dụng HashMap vốn không hiệu quả với các trường hợp không tìm thấy (miss), GitHub sử dụng bitmap để kiểm tra nhanh sự tồn tại của các ký tự cần fold. Các điểm mã (code point) được nhóm thành các “trang” 64-bit, giúp việc tra cứu trở nên cực kỳ nhanh chóng và tiết kiệm bộ nhớ.

Kết quả của quá trình nghiên cứu này đã được GitHub đóng góp dưới dạng một crate Rust mã nguồn mở có tên là casefold, cho phép cộng đồng áp dụng kỹ thuật tối ưu hóa này vào các dự án cần xử lý văn bản quy mô lớn.

Nguồn tham khảo: GitHub Blog