‏چرا هر بایت تو ساختار داده مهمه

نویسنده تو این مقاله می‌گه سال‌ها با Java کار کرده و اون‌جا آدم عادت می‌کنه کلاس‌های غول‌پیکر بسازه و هزینهٔ هر فیلد جدید رو در نظر نگیره. مشکل اینه که پرفورمنس معمولاً فقط از منظر کلاسیک علوم کامپیوتر، یعنی تحلیل مجانبی الگوریتم‌ها، دیده می‌شه؛ ولی حتی تو یه حلقهٔ ساده با رشد O(N) هم زمان می‌تونه به‌شدت فرق کنه اگه درک عمیق‌تری از سخت‌افزار زیرین داشته باشیم.

اولین مفهوم کلیدی کش‌لاین هست. روی ماشین نمونهٔ مقاله اندازهٔ کش‌لاین ۶۴ بایته. نکته اینه که وقتی فقط یه بایت از حافظه می‌خونی، سخت‌افزار کل ۶۴ بایت اطرافش رو میاره تو کش‌لاین؛ چون فرض بر اینه که داده‌ها معمولاً از نظر مکانی و زمانی نزدیک هم استفاده می‌شن. نویسنده هم یادآوری می‌کنه که فاصلهٔ زمانی لایه‌های مختلف حافظه چقدر زیاده: از L1 با حدود ۱ تا ۲ نانوثانیه تا DRAM با حدود ۶۰ تا ۱۰۰ نانوثانیه.

مثالی که می‌زنه یه ساختار Monster به اندازهٔ ۶۴ بایته که می‌خوایم روی آرایه‌ای ازش حلقه بزنیم و فقط فیلد is_alive رو برداریم. تو چیدمان «آرایه‌ای از ساختارها» (Array of Structs)، هر کش‌لاین با یه Monster کامل پر می‌شه ولی ما فقط یه بایت is_alive ازش لازم داریم؛ یعنی بیشتر کش‌لاین هدر می‌ره. راه‌حل اینه که داده رو نرمال کنیم و هر فیلد رو تو لیست خودش بذاریم تا کش‌لاین خیلی فشرده‌تر پر شه:

struct Monsters {
    uint32_t *ids;
    float    *xs, *ys, *zs;
    int32_t  *hps;
    uint8_t  *is_alives;  // packed contiguously
    uint8_t  *teams;
};

به این چیدمان می‌گن «ساختاری از آرایه‌ها» (Struct of Arrays). حالا با یه فچ، ۶۴ تا مقدار is_alive پشت سر هم میاد تو کش. به گفتهٔ نویسنده، وقتی ساختار Monster به ۱ کیلوبایت برسه می‌شه تا ۳۰ برابر بهبود دید؛ ولی وقتی ساختار کوچیکه فرقش کمتر دیده می‌شه چون چند تا Monster هم‌زمان تو یه کش‌لاین جا می‌شن. تو دسترسی ترتیبی، prefetcher سی‌پی‌یو می‌فهمه داری پشت سر هم می‌خونی و کش‌لاین بعدی رو قبل از این‌که لازمش داشته باشی میاره.

ولی همهٔ الگوهای دسترسی ترتیبی نیستن. تو دسترسی تصادفی مثل هش‌مپ، درخت و پیمایش گراف، سی‌پی‌یو نمی‌تونه چیزی که قابل پیش‌بینی نیست رو prefetch کنه. این‌جا اندازهٔ کل مجموعه‌ت تعیین‌کنندهٔ سطح پرفورمنسه: مثلاً با ۵۱۲ تا Monster، ساختار ۶۴ بایتی تو L1d با حدود ۳ نانوثانیه جا می‌شه، ولی ساختار ۱۲۸ بایتی همون موقع به L2 سرریز کرده و رفته رو حدود ۱۱ نانوثانیه. نویسنده با یه بنچمارک pointer-chasing نشون می‌ده که همهٔ اندازه‌ها همون الگوی پلکانی عبور از سطوح کش رو دارن، ولی ساختارهای بزرگ‌تر زودتر به افزایش زمان می‌خورن.

جمع‌بندی نویسنده اینه که دونستن اندازهٔ ساختار و اندازهٔ کل working set می‌تونه تفاوت قابل‌توجهی بسازه؛ برای دسترسی تصادفی اگه بتونی working set رو کوچیک نگه داری، زمان اجرا رو شدیداً بهتر می‌کنی.

نکات کلیدی:

• کش‌لاین ۶۴ بایته؛ خوندن یه بایت کل ۶۴ بایت اطرافش رو میاره تو کش
• چیدمان «ساختاری از آرایه‌ها» (SoA) کش‌لاین رو فشرده‌تر پر می‌کنه و تا ۳۰ برابر سریع‌تره
• تو دسترسی ترتیبی، prefetcher سی‌پی‌یو کش‌لاین بعدی رو از قبل میاره
• تو دسترسی تصادفی، اندازهٔ کل working set سطح پرفورمنس رو تعیین می‌کنه
• ساختار بزرگ‌تر زودتر به سطوح کندتر کش سرریز می‌کنه