جدول‌های جستجوی یک میلیارد کوئری بر ثانیه در زبان C++ — Billion-query-per-second lookup tables in C++
خلاصه
این مقاله روشی را برای پیاده‌سازی جدول‌های هَش بی‌نقص در زمان کامپایل با C++23 بررسی می‌کند. با حذف سربار مدیریت برخورد در زمان اجرا، این رویکرد به سرعتی فراتر از یک میلیارد جستجو در ثانیه دست می‌یابد و تا ۱۳ برابر سریع‌تر از std::unordered_map استاندارد است.
مقدمه و پس‌زمینه
بسیاری از نرم‌افزارها وقت زیادی را صرف نگاشت رشته‌ها به مقادیر مختلف می‌کنند؛ مانند سرورهای وب که متدهای HTTP یا هدرها را شناسایی می‌کنند، یا کامپایلرهایی که کلمات کلیدی را تشخیص می‌دهند. روش پیش‌فرض در زبان C++ استفاده از کلاس std::unordered_map است. این ساختار داده کار می‌کند، اما یک مشکل اساسی دارد: کلیدها در زمان نوشتن کد کاملاً شناخته‌شده هستند و هرگز تغییر نمی‌کنند، اما در زمان اجرا طوری با آن‌ها برخورد می‌شود که انگار ممکن است هر لحظه تغییر کنند. کل رشته هش می‌شود، یک باکت انتخاب می‌شود، از روی پوینتر عبور صورت می‌گیرد و مقایسه انجام می‌شود.
هَش بی‌نقص (Perfect Hashing)
تابع هش کلیدها را به اسلات‌ها نگاشت می‌کند. وقتی دو کلید در یک اسلات قرار گیرند، برخورد (Collision) رخ می‌دهد و مدیریت آن پیچیده و کند است. اگر کلیدها را از قبل بدانیم، می‌توانیم تابعی بسازیم که هرگز برخورد ایجاد نکند که به آن تابع هش بی‌نقص می‌گویند. این ایده جدیدی نیست و ابزارهایی مثل gperf دهه‌هاست که همین کار را انجام می‌دهند.
در رویکرد جدید معرفی‌شده در C++23، نیازی به ابزار خارجی نیست و همه‌چیز در زمان کامپایل انجام می‌شود:
- کلیدها به عنوان یک ثابت کامپایلی (
constexpr) تعریف می‌شوند. - الگوریتم با استفاده از طول رشته و کاراکترهای انتخابی، یک تابع هش بدون برخورد تولید می‌کند.
- در زمان اجرا، محاسبه هش تنها به چند دستورالعمل ساده محدود می‌شود.
مقایسه سریع رشته‌ها
محاسبه هش بسیار ارزان است، اما همچنان باید بررسی کنیم که رشته ورودی با کلید ذخیره‌شده تطابق دارد یا خیر. مقایسه سنتی رشته‌ها با حلقه‌ها و پرش‌های شرطی (branches) می‌تواند کند باشد. در این روش جدید:
- کلیدها به عنوان بردار (Vector) در نظر گرفته می‌شوند.
- با استفاده از رجیسترهای ۱۶ بایتی (مانند ARM NEON یا x64)، بارگذاری داده‌ها بدون شرط انجام می‌شود.
- بایت‌های اضافی صفر می‌شوند و یک مقایسه برداری واحد کل کلید را بررسی می‌کند.
- برای جلوگیری از خطاهای حافظه، بررسی می‌شود که آیا آدرس به پایان صفحه حافظه نزدیک است یا خیر؛ در این صورت مسیر کندتری طی می‌شود، اما پرش‌های غیرقابل‌پیش‌بینی به شدت کاهش می‌یابند.
معیارهای عملکرد و بنچمارک‌ها
بر اساس بنچمارک‌های انجام‌شده روی تراشه Apple M3 Max، این کتابخانه نتایج شگفت‌انگیزی ثبت کرده است:
- برای هدرهای استاندارد HTTP، هر جستجو حدود ۱.۳ نانوثانیه (حدود ۵ سیکل پردازنده) زمان می‌برد.
- این پیاده‌سازی ۱۳ برابر سریع‌تر از
std::unordered_mapو چندین برابر سریع‌تر ازgperfاست. - روی تراشه Apple M4، برای پروتکل‌های URL، سرعت از یک میلیارد جستجو در ثانیه عبور می‌کند.
دیدگاه کاربران هکرنیوز
در بحث‌های هکرنیوز، برخی کاربران اشاره کردند که این روش برای مواردی که کلیدها ثابت هستند عالی است، اما اگر سرویسی نیاز به افزودن پویای متدها یا مقادیر داشته باشد، کاربرد کمتری دارد. همچنین برخی پرسیدند که آیا می‌توان از تکنیک‌های مشابه برای مقادیری که به ندرت تغییر می‌کنند نیز استفاده کرد.
چرا این موضوع برای مهندسان اهمیت دارد؟
اگر در کدهای خود با مجموعه‌کلیدهای ثابت (مانند پروتکل‌ها، مسیرها، کلیدهای پیکربندی یا دستورات) سر و کار دارید، پرداخت هزینه برای مدیریت برخورد هش در زمان اجرا غیرضروری است. این کتابخانه تک‌هدر (header-only) به شما اجازه می‌دهد از حداکثر توان سخت‌افزار مدرن بهره‌مند شوید.
این مطلب به‌صورت کاملاً خودکار و با هوش مصنوعی از مقالهٔ اصلی و بحث هکرنیوز تهیه شده و ممکن است خطا داشته باشد. حقوق مطلب اصلی متعلق به نویسندهٔ آن است. قوانین و گزارش مشکل