بهینه‌سازی افراطی الگوریتم آنگرام؛ رسیدن به سرعت ۱۱ نانوثانیه به ازای هر کلمه در Rust — 11 Nanoseconds per Word: Over-Optimizing Anagrams
خلاصه
این مقاله نگاهی فنی به بهینه‌سازی افراطی یک حل‌کننده بازی کلمات دارد. نویسنده با جایگزینی ساختارهای داده، استفاده از عددگذاری گودل (Gödel numbering) با اعداد اول سفارشی و تکنیک‌های سخت‌افزاری مانند موازی‌سازی در سطح دستورالعمل (ILP)، سرعت پردازش واژه‌نامه اسکرابل را تا ۱۵ برابر افزایش می‌دهد.
زمینه و پیش‌زمینه
در برخی بازی‌های کلمات و معماها، پیدا کردن مسیر تغییر کلمات (مانند تبدیل یک کلمه به کلمه‌ای دیگر از طریق تغییر، حذف، اضافه کردن حروف یا ساختن آنگرام) یک چالش جذاب الگوریتمی است. نویسنده پس از برخورد با این بازی، تصمیم گرفت یک حل‌کننده (Solver) برای آن به زبان Rust بنویسد. اجرای اولیه کد روی یک واژه‌نامه حدود ۱۷۸ هزار کلمه‌ای، رقمی در حدود ۳۱ میلی‌ثانیه زمان برد که برای یک مهندس نرم‌افزارِ به‌دنبال بهینه‌سازی، «به‌طور دیوانه‌کننده‌ای کند» محسوب می‌شود! این مقاله داستان سفر او برای کاهش این زمان به زیر ۲ میلی‌ثانیه است.
گام‌های بهینه‌سازی فنی
برای درک این بهینه‌سازی، مسیر طی‌شده توسط نویسنده از نسخه کند اولیه تا نسخه نهایی فوق‌سریع به این شکل است:
- نسخه پایه (مرتب‌سازی رشته‌ها): در رویکرد سنتی، حروف هر کلمه مرتب شده و به عنوان کلید در یک
HashMapذخیره می‌شوند. این کار به دلیل ایجاد تخصیص‌های حافظه (Allocations) مکررVecو تبدیل رشته‌ها بسیار کند بود و ۱۷۳ نانوثانیه به ازای هر کلمه زمان می‌برد. - حذف تخصیص‌های
Vec: با استفاده از یک ساختار داده سفارشی شبیه به لیست پیوندی مبتنی بر آرایه‌ها، از تخصیص‌های پویای حافظه جلوگیری شد تا سربار کاهش یابد. - بسته‌بندی شمارش حروف در
u128: به جای دستکاری رشته‌ها، شمارش حروف الفبا در قالب یک عدد ۱۲۸ بیتی ذخیره شد. این کار رشته‌ها را حذف کرد و زمان را به ۳۱ نانوثانیه رساند. - تغییر هش‌مپ: جایگزینی هش‌مپ پیش‌فرض با
rustc_hash(نسخه‌ای که برای سرعت بالا و بدون نگرانی از ورودی‌های مخرب طراحی شده) عملکرد را باز هم بهتر کرد. - شماره‌گذاری گودل با اعداد اول سفارشی: این جذاب‌ترین بخش مقاله است. استفاده از حاصل‌ضرب اعداد اول برای شناسایی یکتا (Canonical Identifier) حروف یک کلمه (Gödel Numbering). به جای اعداد اول ساده که باعث سرریز شدن عدد ۶۴ بیتی می‌شدند، نویسنده با تحلیل طولانی‌ترین و پرتکرارترین کلمات واژه‌نامه اسکرابل، جدول ویژه‌ای از اعداد اول را به حروف الفبا اختصاص داد تا هیچ کلمه‌ای از حد
u64تجاوز نکند. - بسته‌بندی نهایی و بهره‌برداری از ILP: کلمات در ساختارهای فشرده ۵ بیتی خوانده شدند و با استفاده از دو انباشتگر مستقل (Accumulators)، موازی‌سازی در سطح دستورالعمل (Instruction-Level Parallelism) برای کامپایلر فراهم شد تا محاسبات ریاضی به موازات هم انجام گیرند.
چرا این مطلب برای مهندسان نرم‌افزار اهمیت دارد؟
این مقاله نمونه‌ای کلاسیک و آموزشی از پروفایل کردن و بهینه‌سازی سطح‌پایین است که نشان می‌دهد چگونه شناخت عمیق از مدل‌سازی داده‌ها، محدودیت‌های سخت‌افزاری پردازنده‌ها و ساختار حافظه می‌تواند کارایی را به شدت دگرگون کند. استفاده خلاقانه از عددگذاری گودل برای فشرده‌سازی حالت‌ها در یک عدد ۶۴ بیتی و پرهیز از تخصیص‌های غیرضروری حافظه، درس‌های ارزنده‌ای برای توسعه‌دهندگان سیستم‌های با کارایی بالا دارد.
دیدگاه کاربران هکرنیوز
در بحث‌های هکرنیوز، برخی کاربران به این نکته اشاره کردند که اگر واژه‌نامه ثابت است، ساختن هش‌مپ در زمان اجرا اصلاً چه ضرورتی دارد و می‌توان از پیش آن را پردازش و ذخیره کرد. با این حال، ایده عددگذاری گودل با اعداد اول سفارشی به عنوان یک ترفند هوشمندانه برای محاسبات سریع آنگرام‌ها تحسین شد.
این مطلب به‌صورت کاملاً خودکار و با هوش مصنوعی از مقالهٔ اصلی و بحث هکرنیوز تهیه شده و ممکن است خطا داشته باشد. حقوق مطلب اصلی متعلق به نویسندهٔ آن است. قوانین و گزارش مشکل