کندترین راه جمعزدن یه آرایه
خلاصهٔ کاملتر
نویسنده تو این پست یه سؤال وارونه میپرسه: اگه یه آرایه داشته باشیم، کندترین راه جمعزدن اعدادش چیه؟ جواب بدیهی «تصادفی بخونشون» ـه، ولی نویسنده میگه میشه خیلی بدتر هم بود — و قدمبهقدم یه الگوی دسترسی میسازه که از سوءاستفادهٔ حسابشده از تلههای حافظه به دست میاد.
قواعد بازی مشخصه: ۲^۲۶ عدد (حدود ۶۷ میلیون) تو ۶۵۵۳۶ صفحهٔ ۴ کیلوبایتی، هیوجپیج خاموش، و تابع تجمیع ثابت. تنها چیزی که اجازه داری عوضش کنی، محتوای آرایهٔ positions ـه؛ یعنی همون ترتیب دسترسی. زمانها هم با شمارش سیکل rdtsc اندازهگیری شدن.
uint32_t accumulator(uint32_t const* data, uint32_t const* positions) {
uint32_t total = 0;
for (uint32_t i = 0; i < ELEMENT_COUNT; ++i) {
uint32_t pos = positions[i];
total += data[pos];
}
return total;
}نقطهٔ شروع، دسترسی خطیه: positions[i] = i. این سریعترین حالته و ۱۳۳ میلیون سیکل طول میکشه، چون CPUها حسابی برای دسترسی ترتیبی بهینه شدن. اگه با Fisher-Yates ترتیب رو تصادفی کنی، پردازنده دیگه نمیتونه حدس بزنه بعدی کجاست و زمان به ۱.۵۷ میلیارد سیکل میپره — بیش از ۱۰ برابر بدتر.
قدم اول برای بدترکردن اوضاع اینه که هر دسترسی رو یه کشلاین جلوتر ببری: هر بار فقط ۴ بایت از یه کشلاین ۶۴ بایتی مصرف میشه و تا وقتی برگردی سراغ همون کشلاین، از کش بیرون انداخته شده. نتیجه ۷۱۹ میلیون سیکل، یعنی حدود ۴ برابر کندتر از خطی. ولی prefetcherهای سختافزاری هنوز الگوی جریانی رو تشخیص میدن و جلوتر میخونن.
اینجاست که نویسنده به یه واقعیت جالب اشاره میکنه: خیلی از prefetcherهای اینتل از مرز صفحهٔ ۴ کیلوبایتی رد نمیشن، چون عبور از مرز صفحه یه ترجمهٔ مجازی-به-فیزیکی جدید میخواد و صفحههای مجازی مجاور لزوماً به صفحههای فیزیکی مجاور نگاشت نمیشن. پس اگه بهجای کشلاین، دسترسیها رو یه صفحه از هم فاصله بدی، افت شدیدتری میگیری: ۱.۴۱ میلیارد سیکل.
ولی داستان فقط prefetch نیست. کش L1d این ماشین ۴۸ کیلوبایته با ۶۴ set و ۱۲ way. چون stride دقیقاً ۴۰۹۶ بایته، همهٔ دسترسیهای حلقهٔ داخلی به یه set مشترک میافتن و برای ۱۲ جای خالیش با هم میجنگن؛ نتیجهش conflict miss پشت conflict miss ـه. ظرفیت اسمی کش ۴۸KB ـه، ولی برای این الگو ظرفیت مفیدش فقط ۷۶۸ بایته (۱۲ way × ۶۴ بایت).
نویسنده بعدش سراغ مفهوم فاصلهٔ استفادهٔ مجدد کشلاین میره و نشون میده وقتی این فاصله از ظرفیت کش خصوصی هسته (اینجا حدود ۴۰ هزار کشلاین برای L1+L2) بیشتر بشه، دیگه عملاً امیدی به hit تو کش خصوصی نیست. با ترکیب همین ایدهها — فاصلهگذاری بر اساس صفحه، کشلاین و بعد stride چند صفحهای — به الگویی میرسه که طبق اسپویلر خودِ پست، بیشتر از ۳۰٪ از دسترسی کاملاً تصادفی هم کندتره.
نکات کلیدی:
- تابع جمع ثابته؛ فقط ترتیب دسترسی عوض میشه، ولی همین ترتیب دهها برابر روی زمان اجرا اثر میذاره.
- خطی: ۱۳۳ میلیون سیکل · تصادفی: ۱.۵۷ میلیارد · فاصله به اندازهٔ یه کشلاین: ۷۱۹ میلیون · فاصله به اندازهٔ یه صفحه: ۱.۴۱ میلیارد.
- prefetcherهای اینتل معمولاً از مرز صفحهٔ ۴KiB رد نمیشن، پس stride صفحهای از کارشون میندازه.
- set-associativity باعث میشه stride ۴۰۹۶ بایتی همهش به یه set بخوره؛ ظرفیت مفید L1d از ۴۸KB به ۷۶۸ بایت میافته.
- با ترکیب این اثرها میشه بیشتر از ۳۰٪ از دسترسی تصادفی هم کندتر شد.
