روز هفته رو با فقط سه دستور اسمبلی حساب کن
خلاصهٔ کاملتر
نویسنده این مقاله میگه محاسبهٔ روز هفته از یه rata-die (یعنی شمارهٔ روزها از یه مبدأ ثابت) با روشهای معمولی مثل عملگر % خیلی کند و پر مرحلهست، مخصوصاً وقتی زبونی مثل Rust بخواد باقیماندهی همیشه-مثبت (rem_euclid) رو دربیاره.
قبل از این، الگوریتم هاوارد هیننت (۲۰۱۴) و بعدش نسخهٔ کاسیو نری (۲۰۲۴) استاندارد شده بودن؛ نری با تبدیل عدد بهعلامت به بیعلامت قبل از محاسبه، مشکل سرریز (overflow) رو حل کرد و کل بازهٔ ۳۲ بیتی امضادار رو پوشش داد.
نکتهٔ اصلی مقاله اینه که عدد ۷ یه عدد مرسنـه (یعنی به فرم 2^N - 1 نوشته میشه) و همین باعث میشه باقیماندهگیری بر ۷ بشه با فقط یه ضرب و یه شیفت بهجای چندین مرحله انجام داد. این ترفند تو کتابخونهٔ تاریخ Rust به اسم jiff هم پیاده شده و باعث ۴۰٪ سریعتر شدن بعضی توابعش شده.
نسخهٔ سادهی این الگوریتم فقط بازهٔ محدودی (حدود ۸۹ میلیون سال) رو پوشش میده؛ برای رسیدن به کل بازهٔ ۳۲ بیتی، نویسنده چند تا نسخهٔ دیگه هم ارائه میده که با اضافه کردن جملههای تصحیح یا محاسبات ۶۴ بیتی، بین سرعت تکدرخواستی (latency) و توان عملیاتی (throughput) تعادل برقرار میکنن.
طبق بنچمارکهای نویسنده رو پردازندههای AMD Ryzen 9 و اپل M4 Pro، سریعترین نسخههای این مقاله حدود ۲ تا ۳ برابر از روشهای قبلی (از جمله کار نری) جلوترن. همین تکنیک رو میشه برای باقیماندهگیری بر ۲۴ و ۶۰ هم به کار برد که تو محاسبات ساعت و زمان کاربرد دارن.
یکی از جالبترین نسخهها فقط با سه دستور اسمبلی کل بازهٔ ۳۲ بیتی رو (تقریباً) پوشش میده:
mov eax, 613566756
imul ecx
lea eax, [eax-1828716544+edx*4]
shr eax, 29نکات کلیدی:
- عدد ۷ یه عدد مرسنـه (2^3 - 1) که این ترفند رو ممکن میکنه
- نسخهٔ محدود فقط با یه ضرب و شیفت، بازهٔ حدود ±۸۹ میلیون سال رو پوشش میده
- کتابخونهٔ Rust به اسم jiff با این ترفند ۴۰٪ سریعتر شده
- بنچمارکها رو AMD Ryzen 9 و اپل M4 Pro گرفته شدن
- سریعترین نسخهها ۲ تا ۳ برابر از روش قبلی نری سریعترن
- همین تکنیک برای باقیماندهگیری بر ۲۴ و ۶۰ هم قابل تعمیمه
