زود متوقف نشوید: تبدیل حالت حروف (Case-folding) در سورس‌کد با سرعت حافظه

فرض کنید کاربری واژه «café» را جستجو می‌کند و مجموعه داده شما شامل «CAFÉ» است، یا عبارت «straße» را تایپ می‌کند و شما «STRASSE» را ذخیره کرده‌اید. برای اینکه این موارد به عنوان تطابق در نظر گرفته شوند، به یک فرم استاندارد (Canonical form) نیاز دارید که تمایز بین حروف بزرگ و کوچک را از بین ببرد؛ به‌طوری که دو رشته که فقط در حالت حروف متفاوت هستند، برابر مقایسه شوند. این فرم همان «تبدیل حالت حروف» (Case folding) است و در هر جایی که متن به‌جای نمایش داده شدن، تطبیق داده می‌شود کاربرد دارد: موتورهای جستجو، پرچم‌های (?i) در عبارت‌های باقاعده (Regex)، و نام‌های کاربری و نام‌های میزبان غیرحساس به حالت حروف.

این یک عملیات پایه است، اما ما در گیت‌هاب (GitHub) آن را به مقدار بسیار زیادی اجرا می‌کنیم. بلک‌برد (Blackbird)، موتور جستجوی کد گیت‌هاب، بیش از ۱۸۰ میلیون مخزن — یعنی بیش از ۴۸۰ ترابایت سورس‌کد — را شاخص‌گذاری می‌کند. هر بایت قبل از استخراج n-gramها و ساخت نمایه، تحت عملیات Case-folding قرار می‌گیرد و برای هر نتیجه جستجوی احتمالی، یک عملیات Case-folding دیگر (صریح یا ضمنی) برای یافتن تطابق‌ها لازم است. در چنین مقیاسی، حتی سرعت یک عملیات پایه نیز اهمیت حیاتی پیدا می‌کند.

این مطلب درباره نحوه سریع‌تر کردن این عملیات است و از نقطه‌ای غیرمنتظره شروع می‌شود: بزرگ‌ترین موفقیت در مسیر سریع ASCII از حذف یک بهینه‌سازی به دست آمد، نه اضافه کردن آن! مشخص شد که پیمایش کل بافر بدون هیچ انشعابی (Branch)، بسیار سریع‌تر از توقف زودهنگام در اولین بایت غیر ASCII است. ما نتیجه این تلاش را به عنوان یک کریت (Crate) در زبان راست (Rust) به نام casefold به‌صورت متن‌باز منتشر کردیم.

تفاوت Case-folding با کوچک‌سازی حروف (Lowercasing)

وسوسه‌انگیز است که از str::to_lowercase استفاده کنیم، اما کوچک‌سازی حروف و Case-folding دو عملیات متفاوت با اهداف گوناگون هستند:

کوچک‌سازی حروف برای «نمایش» است و به محلی‌سازی (Locale) و بافت متن وابسته است: سیگمای پایانی یونانی در انتها کلمه به «ς» و در نقاط دیگر به «σ» تبدیل می‌شود، و حرف «I» در ترکی با انگلیسی متفاوت کوچک می‌شود. اما Case-folding برای «مقایسه» است و تعمداً بدون بافت و مستقل از محلی‌سازی طراحی شده است. هدف، ایجاد رابطه‌ای پایدار و متقارن است؛ به‌طوری که اگر A به B نگاشت شود، B نیز در هر محلی‌سازی به A نگاشت گردد. پایگاه داده کاراکترهای یونیکد (UCD) فایل مشخصی به نام CaseFolding.txt را دقیقاً برای همین منظور ارائه می‌دهد.

این دو عملیات در کاراکترهای واقعی مانند «ß»، «İ» و سیگمای پایانی از هم فاصله می‌گیرند؛ به همین دلیل استفاده از کوچک‌سازی حروف به‌جای folding، بی‌سروصدا منجر به تطابق‌های نادرست می‌شود. این کریت صرفاً تبدیل‌های ساده (۱ به ۱) — یعنی وضعیت‌های C و S در فایل CaseFolding.txt — را پیاده‌سازی می‌کند و شامل تبدیل‌های چندکاراکتری کامل (مانند ß → ss) یا تبدیل‌های محلی ترکی نمی‌شود. این یک انتخاب غیرمعمول نیست: ابزارهای رایج و موتورهای عبارت باقاعده مانند ripgrep نیز همین محدودیت را اعمال می‌کنند و یکپارچگی میان ابزارها اهمیت زیادی دارد.

هسته دور از انتظار: زود متوقف نشوید

ما بیشتر با سورس‌کد سروکار داریم، بنابراین متنی که تبدیل می‌کنیم به‌شدت متکی بر ASCII است و اجرای آن با سرعت حافظه (Memory speed)، مهم‌ترین کاری است که می‌توانیم انجام دهیم. سایر بخش‌ها فقط باید جلوی کند شدن این مسیر توسط بایت‌های نادر غیر ASCII را بگیرند.

تبدیل یک حرف ASCII بسیار ساده است — محدوده A..=Z به a..=z نگاشت می‌شود و بقیه بدون تغییر می‌مانند — بنابراین مسیر ASCII صرفاً «پیمایش بافر و کوچک‌سازی در محل» است. اگر از هر مدل زبانی (LLM) برای آن کد بخواهید، ممکن است کدی شبیه به این به شما بدهد:

blockquote>

let bytes = s.as_bytes_mut();
for (i, b) in bytes.iter_mut().enumerate() {
    if *b >= 0x80 {
        break; // non-ASCII at index i: hand the rest to the Unicode path
    }
    if b.is_ascii_uppercase() {
        *b += 32; // ‘A’..=’Z’ → ‘a’..=’z’
    }
}

این کد ایده‌آل به نظر می‌رسد: پردازش ارزان بایت‌ها را انجام بده و به محض برخورد با بایت غیر ASCII، متوقف شو و بقیه کار را به مسیر «واقعی» یونیکد بسپار: «تنها تا زمانی که مجبور نشده‌ای کار ارزان را انجام بده.» روی پردازنده Apple M4 این کد با سرعت حدود ۳ GiB/s اجرا می‌شود. این سرعت به خودی خود خوب به نظر می‌رسد، اما به دلیل وجود شرط‌های if (انشعاب‌ها یا Branches)، بیش از ۱۵ برابر از حد «بهینه» کندتر است.

بیایید تمام انشعاب‌ها را خط به خط حذف کنیم:

• حذف شرط خروج زودهنگام: به هیچ وجه متوقف نشوید. تمام بایت‌ها را با یک انباره (Accumulator) عملیات OR منطقی کنید و فقط یک‌بار پس از حلقه آن را تست کنید: high_bit_acc |= *b. همان اطلاعات با صفر انشعاب در بدنه حلقه به دست می‌آید.
• تست محدوده A..=Z: آن را محاسباتی کنید. عبارت b.wrapping_sub(b’A’) < 26 دقیقاً برای A..=Z درست است و یک ماسک ۰ یا ۱ بدون انشعاب تولید می‌کند.
• نوشتن شرطی: ماسک را در ذخیره‌سازی ادغام کنید. عبارت | (is_upper << 5) بیت ۵ را تنظیم می‌کند که حرف بزرگ را کوچک کرده و روی بقیه بی‌تاثیر است. بایت همیشه نوشته می‌شود و هرگز انشعابی روی آن رخ نمی‌دهد.

آنچه باقی می‌ماند، هیچ انشعابی در بدنه و هیچ خروج زودهنگامی ندارد:

blockquote>

let mut high_bit_acc: u8 = 0;
for b in &mut bytes {
    high_bit_acc |= *b; // detect any non-ASCII byte
    let is_upper = b.wrapping_sub(b’A’) < 26; // branchless A..=Z test
    *b |= u8::from(is_upper) << 5; // set bit 5 → lowercase, else no-op
}
if high_bit_acc & 0x80 == 0 {
    return bytes; // pure ASCII: already folded in place, no second buffer
}

حلقه‌ای بدون جریان کنترل وابسته به داده، به‌راحتی قابل بردارسازی (Vectorizable) است: کامپایلر LLVM دستورات ۱۶ بایتی NEON صادر می‌کند و کل فرآیند با سرعت بیش از ۴۵ GiB/s — در حد پهنای باند حافظه — اجرا می‌شود. بعلاوه، پس از پایان حلقه، از طریق high_bit_acc می‌دانیم آیا کار غیر ASCII باقی مانده است یا خیر.

میزان تاثیر هر مرحله در تست روی ASCII خالص (Apple M4، بافر ۵.۷ کیلوبایتی):

• نسخه ساده (خروج زودهنگام + تست انشعابی): سرعت ۳.۱ GiB/s — بردارسازی نشده (۰ دستور برداری)
• تست و نوشتن بدون انشعاب + حفظ خروج زودهنگام: سرعت ۲.۶ GiB/s — بردارسازی نشده (۰ دستور برداری)
• حذف خروج زودهنگام (break): سرعت ۷.۶ GiB/s — بردارسازی جزئی (۲۵ دستور برداری)
• تست و نوشتن بدون انشعاب (حلقه نهایی): بیش از ۴۵ GiB/s — بردارسازی کامل (۴۱ دستور برداری)

نکته: کد بدون انشعاب (Branchless) در کدهای اسکالر (غیربرداری) باعث کاهش کارایی می‌شود. همان‌طور که در نتایج دیده می‌شود، بدون انشعاب کردن بدنه با حفظ break (سرعت ۲.۶ GiB/s) کندتر از حلقه ساده انشعابی (۳.۱ GiB/s) است. کد اسمبلی علت آن را نشان می‌دهد: نسخه انشعابی فقط زمانی بایت را ذخیره می‌کند که تغییر کند، اما نسخه بدون انشعاب در هر تکرار عمل نوشتن را انجام می‌دهد. نوشتن بدون انشعاب تنها زمانی برنده می‌شود که حلقه بردارسازی شود؛ زیرا هزینه به‌ازای هر بایت ناپدید می‌شود. درس اصلی: بدنه بدون انشعاب تنها به عنوان زمینه‌ساز بردارسازی ارزشمند است.

یک راه میانبر نیز وجود دارد که کتابخانه‌های استاندارد استفاده می‌کنند. تابع [u8]::is_ascii کلمات ماشینی (Machine words) را اسکن می‌کند و در هر تکرار ۶۴ بیتی ۱۶ بایت را بررسی می‌کند. اما داده‌ها دو بار خوانده می‌شوند (یک‌بار اسکن و یک‌بار تبدیل) و به سرعت حدود ۲۳ GiB/s می‌رسد. این یک روش عمومی خوب است، اما سقف مطلق کارایی نیست.

آیا ادغام این دو مرحله سریع‌تر نیست؟ ادغام خروج زودهنگام با تبدیل فوری هر بلوک، در عمل ۲.۶ برابر کندتر است (۸.۷ GiB/s در مقابل ۲۳ GiB/s). انشعاب خروج زودهنگام مانع بهینه‌سازی کامپایلر می‌شود. دو گذر ساده و بدون انشعاب بر یک گذر ادغام‌شده انشعاب‌دار پیروز می‌شوند. بار دیگر همان درس: در حلقه‌های داغ، انشعاب دشمن اصلی است.

اجتناب از تخصیص حافظه هیپ (Heap)

سرعت ۴۵ گیگابایت بر ثانیه به معنای عدم انجام هیچ‌گونه تخصیص حافظه اضافی است. تابع simple_fold ورودی String را با مالکیت دریافت کرده و بافر هیپ آن را در محل تغییر می‌دهد. اگر تمام متون ASCII باشند، همان بافر بدون تخصیص مجدد یا کپی بازگردانده می‌شود. در غیر این صورت، با memchr به اولین بایت غیر ASCII رفته و ادامه متن اسکن می‌شود.

چرا به جای بازنویسی در محل، از بافر دوم استفاده می‌شود؟ زیرا عملیات folding می‌تواند رشته را طولانی‌تر کند؛ مثلاً کاراکترهای U+023A (Ⱥ) و U+023E (Ⱦ) هرکدام ۲ بایت هستند اما به کاراکترهای ۳ بایتی نگاشت می‌شوند.

ما آن بافر را یک بار و با حد بالای رشد (حداکثر ۱.۵ برابر ورودی) تخصیص می‌دهیم:

blockquote>

out = Vec::with_capacity(bytes.len() + bytes.len() / 2 + 4);

ارزان‌سازی فرآیند برای یونیکد

هنگامی که یک کاراکتر تبدیل می‌شود، باز هم نباید دچار افت شدید کارایی (رمزگشایی UTF-8، جستجوی هش، رمزگذاری مجدد) شد. استاندارد یونیکد 16.0 شامل ۱۴۸۴ نگاشت تبدیل ساده است، اما این نگاشت‌ها رابطه‌ای بسیار پراکنده و ساختاریافته دارند که امکان بهینه‌سازی بالای پردازش را فراهم می‌سازند.