GitHub mở mã nguồn casefold: Tối ưu hóa xử lý chữ hoa/thường đạt tốc độ băng thông bộ nhớ

Cách một vòng lặp không nhánh (branch-free loop) và thuật toán trên không gian byte cho phép GitHub thực hiện case-fold (chuẩn hóa chữ hoa/thường) cho mọi byte trong tìm kiếm mã nguồn với tốc độ >45 GiB/s trên một nhân duy nhất.

Ngày 31 tháng 7 năm 2026

16 phút

Giả sử người dùng tìm kiếm "café" và kho dữ liệu của bạn chứa "CAFÉ", hoặc họ gõ "straße" và bạn đã lưu trữ "STRASSE". Để những từ này được coi là khớp nhau, bạn cần một dạng chuẩn hóa loại bỏ sự khác biệt giữa chữ hoa và chữ thường, sao cho hai chuỗi chỉ khác nhau về kiểu chữ sẽ được so sánh là bằng nhau. Dạng đó chính là case folding, và nó xuất hiện ở bất cứ nơi nào văn bản được so khớp thay vì hiển thị: công cụ tìm kiếm, cờ regex (?i), tên người dùng và tên máy chủ không phân biệt chữ hoa chữ thường.

Đây là một thao tác cơ bản, nhưng tại GitHub, chúng tôi thực hiện nó rất nhiều. Blackbird, công cụ tìm kiếm mã nguồn của GitHub, lập chỉ mục hơn 180 triệu kho lưu trữ—hơn 480TB mã nguồn. Mỗi byte đều được case-folded trước khi chúng tôi trích xuất n-gram và xây dựng chỉ mục, và đối với mỗi kết quả truy vấn tiềm năng, một thao tác case folding khác (ngầm định hoặc tường minh) lại cần thiết để xác định vị trí khớp. Ở quy mô đó, tốc độ của ngay cả một thao tác cơ bản cũng bắt đầu trở nên quan trọng.

Bài viết này nói về cách chúng tôi làm cho nó trở nên nhanh chóng, và nó bắt đầu từ một nơi khá phản trực giác: thành tựu lớn nhất trong đường dẫn nhanh (fast path) ASCII đến từ việc loại bỏ một tối ưu hóa, chứ không phải thêm vào. Hóa ra, việc quét toàn bộ bộ đệm mà không có nhánh (branch) lại nhanh hơn là dừng sớm tại byte không phải ASCII đầu tiên. Chúng tôi đã mã nguồn mở kết quả này dưới dạng một Rust crate có tên là casefold.

Folding không phải là chuyển sang chữ thường (lowercasing)

Thật dễ để nghĩ đến việc dùng str::to_lowercase, nhưng chuyển sang chữ thường và folding là hai thao tác khác nhau với các mục tiêu khác nhau:

Chuyển sang chữ thường là để hiển thị, và nó phụ thuộc vào ngôn ngữ (locale) và ngữ cảnh: chữ sigma cuối từ trong tiếng Hy Lạp sẽ chuyển thành ς ở cuối từ và σ ở các vị trí khác, và chữ I trong tiếng Thổ Nhĩ Kỳ chuyển đổi khác với chữ I trong tiếng Anh. Case folding là để so sánh, và nó được thiết kế để không phụ thuộc vào ngữ cảnh và ngôn ngữ. Mục đích là tạo ra một mối quan hệ ổn định và đối xứng, sao cho nếu A fold để khớp với B, thì B cũng fold để khớp với A trong bất kỳ ngôn ngữ nào. Unicode Character Database cung cấp một tệp CaseFolding.txt tường minh chính xác cho việc đó.

Hai thao tác này khác biệt trên các ký tự thực tế—ß, İ, sigma cuối từ—đó là lý do tại sao việc dùng chuyển sang chữ thường làm thay thế sẽ tạo ra các kết quả khớp sai một cách âm thầm. Crate này chỉ triển khai các kiểu fold đơn giản (1-đối-1)—trạng thái C và S trong CaseFolding.txt—chứ không phải các kiểu fold "đầy đủ" nhiều ký tự (ß → ss) hay kiểu fold theo ngôn ngữ Turkic (chữ İ có dấu chấm). Đây không phải là một lựa chọn bất thường: các công cụ phổ biến và công cụ regex như ripgrep cũng áp dụng hạn chế tương tự, và việc nhất quán giữa các công cụ là rất quan trọng.

Cốt lõi phản trực giác: Đừng dừng sớm

Chúng tôi chủ yếu xử lý mã nguồn, vì vậy văn bản chúng tôi fold phần lớn là ASCII và việc làm cho nó chạy ở tốc độ bộ nhớ là điều quan trọng nhất chúng tôi có thể làm. Mọi thứ khác chỉ cần đảm bảo đường dẫn không phải ASCII hiếm gặp không làm ảnh hưởng đến hiệu suất.

Việc fold một chữ cái ASCII rất đơn giản—A..=Z ánh xạ thành a..=z, mọi thứ khác không thay đổi—vì vậy bước ASCII thực chất chỉ là "quét bộ đệm, chuyển sang chữ thường tại chỗ". Nếu bạn hỏi bất kỳ LLM nào về điều này, bạn có thể nhận được kết quả như sau:

Nó trông có vẻ lý tưởng: thực hiện công việc trên byte giá rẻ, và ngay khi gặp byte không phải ASCII, hãy ngắt vòng lặp và để đường dẫn Unicode "thực sự" tiếp quản: "chỉ làm công việc giá rẻ cho đến khi bắt buộc phải dừng". Trên chip Apple M4, cách này chạy ở tốc độ khoảng 3 GiB/s. Nghe có vẻ ổn khi đứng độc lập, nhưng nó chậm hơn 15 lần so với mức "tối ưu" do các nhánh if.

Hãy xóa mọi nhánh, từng dòng một:

Những gì còn lại không có nhánh trong thân vòng lặp và không có lối thoát sớm:

Một vòng lặp không có luồng điều khiển phụ thuộc vào dữ liệu thì có thể vector hóa một cách dễ dàng: LLVM phát ra các lệnh NEON xử lý 16 byte mỗi lần và toàn bộ quá trình chạy ở tốc độ > 45 GiB/s—về cơ bản là đạt tới băng thông bộ nhớ. Và chúng tôi thoát khỏi bước này khi đã biết, từ high_bit_acc, liệu còn công việc nào liên quan đến ký tự không phải ASCII cần thực hiện hay không.

Mỗi bước quan trọng đến mức nào? Đo lường sự tích lũy trên ASCII thuần túy (Apple M4, bộ đệm 5.7 KB):

Lối thoát sớm (early-exit) chính là thứ ngăn cản việc vector hóa: giữ lệnh break nhưng làm cho thân vòng lặp hoàn toàn không nhánh thì bạn vẫn nhận được kết quả là không có lệnh vector nào (~2.6 GiB/s); một lối thoát vòng lặp phụ thuộc vào dữ liệu là đủ để giữ cho vòng lặp ở dạng vô hướng (scalar). Chỉ khi lệnh break bị loại bỏ, trình biên dịch mới có thể vector hóa. Bước cuối cùng—làm cho việc fold chữ hoa trở nên không nhánh—sau đó biến một vòng lặp được vector hóa một phần (vẫn biên dịch lệnh lưu có điều kiện thành compare-blend-masked-store, ~7.6 GiB/s) thành các phép tính thẳng hàng đạt tới băng thông bộ nhớ.

Lưu ý: Không nhánh (branchless) là một sự tối ưu hóa ngược trong mã vô hướng. Hãy nhìn lại bảng: làm cho thân vòng lặp không nhánh trong khi vẫn giữ lệnh break (2.6 GiB/s) thực tế còn chậm hơn vòng lặp có nhánh thông thường (3.1 GiB/s). Mã assembly giải thích lý do tại sao. Phiên bản có nhánh chỉ lưu một byte khi nó thực sự thay đổi; lệnh lưu có điều kiện của nó bị bỏ qua đối với mọi chữ cái thường, chữ số và khoảng trắng (phần lớn văn bản thực tế), và nhánh được dự đoán tốt bảo vệ nó gần như không tốn chi phí. Phiên bản không nhánh thay thế lệnh lưu hiếm khi thực hiện đó bằng một lệnh lưu không điều kiện trong mỗi lần lặp, ghi lại toàn bộ ~5,700 byte thay vì chỉ một vài byte chữ hoa. Lưu lượng ghi dư thừa mà không mang lại lợi ích. Ghi không nhánh chỉ thắng khi vòng lặp được vector hóa, vì khi đó lệnh lưu trở thành một lệnh ghi vector 16-byte duy nhất bất kể nội dung, và chi phí trên mỗi byte biến mất. Bài học: thân vòng lặp không nhánh chỉ đáng giá khi nó là yếu tố kích hoạt vector hóa. Nếu đứng một mình trong mã vô hướng, nó có thể gây tốn kém.

Ngoài ra còn có một giải pháp trung gian, và đó là những gì các thư viện tiêu chuẩn sử dụng. Thay vì kiểm tra từng byte một, [u8]::is_ascii quét một từ máy (machine word) mỗi lần—trên mục tiêu 64-bit, nó kiểm tra 16 byte mỗi lần lặp bằng cách thực hiện phép OR trên hai làn u64 và kiểm tra tất cả các bit cao của chúng với một mặt nạ & 0x8080_8080_8080_8080 duy nhất. Bạn có thể xây dựng đường dẫn nhanh ASCII dựa trên đó: quét theo khối để tìm tiền tố ASCII, sau đó chạy chuyển đổi không nhánh (có thể vector hóa) trên đó. Điều đó giữ được khả năng thoát sớm—nó vẫn dừng ở khối không phải ASCII đầu tiên—trong khi vẫn cho phép cả hai nửa chạy nhanh. Điểm hạn chế là nó đọc dữ liệu hai lần (một lần để quét, một lần để chuyển đổi), đạt khoảng 23 GiB/s—xấp xỉ một nửa so với quét không nhánh một lần, và gấp ~7 lần vòng lặp có lệnh break thông thường. Một mặc định vững chắc, đa năng; chỉ là không phải mức trần tuyệt đối khi bạn kiểm soát toàn bộ vòng lặp và có thể gộp việc phát hiện và chuyển đổi vào một đường dẫn không nhánh duy nhất.

Liệu việc hợp nhất hai bước có nhanh hơn không? Đó là suy nghĩ tiếp theo hiển nhiên: giữ lối thoát sớm theo khối nhưng chuyển đổi mỗi khối 16-byte ngay sau khi xác nhận đó là ASCII, chỉ đọc dữ liệu một lần. Khi đo lường, nó chậm hơn ~2.6 lần—8.7 GiB/s so với 23 GiB/s của phương pháp hai bước. Việc chuyển đổi khối bên trong vẫn vector hóa thành một thao tác 16-byte duy nhất, nhưng bây giờ có một nhánh thoát sớm phụ thuộc vào dữ liệu sau mỗi 16 byte, và nhánh đó ghim vòng lặp vào từng khối một: trình biên dịch không thể unroll hoặc pipeline phần mềm qua các khối, và mỗi lần lặp phải trả giá cho toàn bộ độ trễ load→test→branch→convert→store mà không có gì để che giấu nó. Chia thành hai bước, mỗi bước đều sạch sẽ: bước quét là một bước quét từ máy không nhánh, không lưu, chạy nhanh qua bộ nhớ, và bước chuyển đổi là bước quét không nhánh được vector hóa hoàn toàn ở tốc độ >45 GiB/s. Hai bước nhanh, không nhánh đánh bại một bước hợp nhất có nhánh—mặc dù phiên bản hợp nhất truy cập dữ liệu ít hơn một nửa. Đó vẫn là bài học cũ: trong vòng lặp nóng (hot loop), nhánh là kẻ thù.

Tránh sử dụng heap

45 GiB/s cũng có nghĩa là không thực hiện bất kỳ cấp phát không cần thiết nào. simple_fold nhận đầu vào String theo giá trị, sở hữu bộ đệm heap mà nó có thể thay đổi và trả về. Nếu bit cao của bộ tích lũy OR bằng 0, đầu vào là ASCII thuần túy đã được fold tại chỗ. Chúng tôi trả lại chính cấp phát đó, không cần bộ đệm thứ hai và không cần sao chép. Nếu không, chúng tôi dùng memchr để tìm byte không phải ASCII đầu tiên và quét phần đuôi từ đó, để bộ đệm đầu ra chưa được cấp phát (một con trỏ ghi null) cho đến khi chúng tôi gặp một ký tự fold thành các byte khác. Văn bản có nội dung đa byte không bao giờ fold—CJK, Hangul, Kana, Ả Rập, Do Thái, ký hiệu—cũng trả về cấp phát gốc mà không thay đổi, không bao giờ sao chép một byte nào.

Tại sao lại dùng bộ đệm thứ hai thay vì ghi đè tại chỗ như bước ASCII? Bởi vì folding có thể làm chuỗi dài ra: hầu như mọi kiểu fold đều bảo toàn độ dài UTF-8 hoặc làm nó ngắn đi, nhưng có hai trường hợp ngoại lệ làm nó dài ra—U+023A (Ⱥ) và U+023E (Ɀ) là 2 byte mỗi ký tự nhưng fold thành các ký tự 3 byte (ⱥ, ɀ). Khi một trong số chúng xuất hiện, đầu ra không còn vừa với các byte đầu vào, và chúng tôi cần một nơi mới để ghi.

Chúng tôi cấp phát bộ đệm đó một lần, với kích thước cho trường hợp xấu nhất, thay vì tăng dần khi có thêm các kiểu fold xuất hiện. Các lệnh reserve tăng dần sẽ có nghĩa là phải kiểm tra lại dung lượng, thỉnh thoảng cấp phát lại, sao chép mọi thứ đã ghi cho đến nay, và quản lý việc ghi chép độ dài/dung lượng bổ sung; một lần cấp phát duy nhất ngay từ đầu cho phép con trỏ ghi thô chạy thẳng đến cuối mà không cần những thứ đó. Và vì con trỏ là null cho đến khi kiểu fold thay đổi/tăng trưởng đầu tiên xuất hiện, nó đóng vai trò kép là cờ "chúng ta đã cấp phát bộ đệm bổ sung chưa?".

Việc xác định kích thước cần một giới hạn về sự tăng trưởng, và chính hai trường hợp ngoại lệ đó cung cấp giới hạn đó: cứ mỗi 2 byte đầu vào tạo ra tối đa 3 byte đầu ra, giới hạn đầu ra ở mức 1.5 lần đầu vào—chính xác là dung lượng chúng tôi dự trữ:

Sau đó, vòng lặp ghi qua một con trỏ thô mà không cần kiểm tra dung lượng và gọi set_len một lần ở cuối. Hai chi tiết nữa giúp giữ cho nó ít nhánh. Chuỗi các byte không thay đổi giữa hai lần fold được di chuyển bằng một lệnh copy_nonoverlapping duy nhất thay vì từng byte một. Và mỗi kiểu fold ghi không điều kiện tất cả 4 byte của một từ little-endian trước khi tăng con trỏ chỉ theo độ dài đã fold (1–4)—loại bỏ một nhánh về độ dài đầu ra khỏi đường dẫn nóng, với + 4 trong phần dự trữ là khoảng trống giúp việc ghi đè ký tự cuối cùng trở nên an toàn.

Làm cho Unicode cũng trở nên rẻ

Khi một ký tự thực sự fold, chúng tôi vẫn không muốn rơi vào tình trạng tồi tệ—giải mã UTF-8, tra cứu hash, mã hóa lại. Unicode 16.0 có 1484 ánh xạ fold đơn giản, nhưng chúng là một mối quan hệ rất thưa thớt và rất có cấu trúc. Bốn quan sát thu nhỏ chúng xuống còn 1776 byte và cho phép quá trình fold chạy mà không bao giờ phải giải mã toàn bộ ký tự.

Ngay cả trên đường dẫn không phải ASCII, đại đa số các ký tự không fold. Thao tác nóng thực sự không phải là "fold ký tự này", mà là "ký tự này có fold không?". Hầu như luôn luôn là không. Bảng phải làm cho bài kiểm tra phủ định đó rẻ nhất có thể; việc folding thực tế là trường hợp hiếm gặp trên một đường dẫn vốn đã hiếm. Sự ưu tiên đó là thứ định hình bố cục bên dưới—bitmap trang tồn tại chính xác để một ký tự không fold bị từ chối trong một lần kiểm tra bit duy nhất, ngay từ các byte UTF-8 dẫn đầu của nó, mà không cần giải mã hay quét bất cứ thứ gì.

Đây chính xác là lý do tại sao HashMap<u32, u32> là cấu trúc sai cho công việc này, không chỉ vì nó lớn hơn. Một hash map được tối ưu hóa cho trường hợp tìm thấy: nó tìm thấy một khóa hiện có trong khoảng một lần dò, và chỉ tốn thêm công sức (dò thêm, so sánh khóa đầy đủ) khi hệ số tải hoặc va chạm xảy ra. Nhưng khối lượng công việc của chúng tôi bị chi phối bởi các trường hợp không tìm thấy—các ký tự không có trong bảng—và không tìm thấy là truy vấn mà hash map ghét nhất: nó vẫn phải hash khóa, nhảy đến một bucket, và đi theo chuỗi dò đủ xa để chứng minh sự vắng mặt.

Các điểm mã (code point) có thể fold tập trung thành các "trang" 64 điểm mã

Các điểm mã có thể fold tập hợp lại với nhau. Chia không gian mã thành các "trang" 64 điểm mã và ~1484 kiểu fold chỉ chạm đến 59 trong số ~1960 trang có thể. Một bitmap sự hiện diện với một bit cho mỗi trang tự trả lời bài kiểm tra phủ định: một bit bằng 0 là một câu trả lời "không fold" dứt khoát—sao chép qua, xong—đó là điều làm cho các tập lệnh không có fold trở nên rẻ. Chỉ khi bit được đặt (bằng 1), chúng tôi mới tham khảo cấu trúc thứ hai, một bảng phụ cumulative-popcount xếp hạng trang (có bao nhiêu trang đã được điền đứng trước nó) để tìm lát cắt mục nhập của nó, không lưu trữ gì cho ~1900 trang trống.

Vì word_idx chỉ phụ thuộc vào byte dẫn đầu (và, đối với các chuỗi bốn byte, byte tiếp theo đầu tiên), việc tải bitmap có thể được thực hiện sớm.

Trong một trang, các kiểu fold xuất hiện theo chuỗi

Một bit trang được đặt cho chúng ta biết có thứ gì đó trên trang này fold, nhưng không biết là điểm mã nào hoặc fold thành cái gì. Cách mã hóa hiển nhiên là một mục nhập cho mỗi điểm mã có thể fold—nhưng cách đó vừa cồng kềnh vừa chậm để tìm kiếm: một trang có thể chứa hàng chục kiểu fold, và chúng tôi sẽ phải quét tất cả chúng để tìm cái khớp với điểm mã hiện tại. Cấu trúc của dữ liệu lại cứu chúng ta. Các điểm mã liền kề phần lớn chia sẻ cùng một độ lệch (delta) để fold: A–Z đều ánh xạ +32, và Latin Extended đầy các chuỗi xen kẽ như 0x0100, 0x0102, 0x0104, … nơi cứ mỗi điểm mã thứ hai lại fold. Thay vì các mục nhập cho mỗi điểm mã, chúng tôi lưu trữ các chuỗi (runs)—bắt đầu, kết thúc, bước nhảy (stride), độ lệch—và một cờ bước nhảy 1-bit bao gồm cả trường hợp liên tục và trường hợp cách quãng. Việc nén khoảng này thu gọn ~1484 kiểu fold riêng lẻ thành chỉ 238 chuỗi trên 59 trang (≈bốn chuỗi mỗi trang), để lại việc tìm kiếm trong trang chỉ cần xem xét một vài mục nhập thay vì hàng chục. Cách mã hóa phạm vi-với-độ lệch này (bao gồm cả thủ thuật bước nhảy) được mượn từ gói unicode của Go, nơi các bản ghi CaseRange lưu trữ một phạm vi Lo/Hi cộng với các độ lệch cho mỗi trường hợp, với một sentinel UpperLower đánh dấu các khối xen kẽ. Các chuỗi được chia tại ranh giới trang để một chuỗi không bao giờ nằm vắt qua hai trang.

Một bản ghi chuỗi là hai byte sạch sẽ

Với cả hai điểm cuối nằm trong một trang, chúng vừa vặn trong 6 bit, chia thành hai mảng: RUN_END_LOW[i] = end & 0x3F (khóa quét) và RUN_START_STRIDE[i] = (start & 0x3F) | ((stride − 1) << 6) (chỉ đọc khi có kết quả khớp). Vì mỗi khóa là một byte sạch, việc tìm kiếm trong trang có thể thực hiện rộng: thay vì so sánh cp & 0x3F với các chuỗi từng cái một, chúng tôi tải 8 byte end_low vào một u64 duy nhất và kiểm tra tất cả chúng cùng lúc với một bước SWAR không nhánh—(chunk | 0x80…80) − broadcast(low) & 0x80…80 đặt bit cao của mọi làn có khóa ≥ cp & 0x3F. Một lần quét bit duy nhất của mặt nạ đó (các khóa đã được sắp xếp, vì vậy làn được đặt đầu tiên là chuỗi chúng tôi muốn) tìm thấy vị trí. Một trang chứa trung bình ~4 chuỗi; phép so sánh rộng 8 đó hầu như luôn giải quyết toàn bộ tìm kiếm trong một bước duy nhất. Một trang không may mắn chứa 30 chuỗi, điều này đặt phép so sánh vào bên trong một vòng lặp ngắn bước qua tám khóa mỗi lần—nhưng vòng lặp đó chỉ chạy tối đa một vài lần trên đúng một trang trong toàn bộ Unicode, và không bao giờ trên các trang phổ biến. Dù thế nào đi nữa: không có nhánh cho mỗi chuỗi, và không có việc tái tạo điểm mã ở bất cứ đâu.

Folding là một phép cộng byte little-endian