كود متوافق مع الكاش (Cache-Friendly) بلغة C++: ما هو ولماذا هو مهم للسرعة

هل يعمل كودك ببطء على الرغم من أن الخوارزمية مثالية؟ ربما هو ليس "صديقًا" للكاش

هل سبق لك أن كتبت كودًا بلغة C++ يجب أن يعمل بسرعة البرق من الناحية النظرية، ولكنه يتباطأ عمليًا؟ أو لاحظت أن اجتياز مصفوفة ثنائية الأبعاد صفًا بصف وعمودًا بعمود يعطي سرعات مختلفة، على الرغم من أن تعقيد الخوارزمية هو نفسه؟ إذا كان الأمر كذلك، فقد واجهت الكود المتوافق مع الكاش (cache-friendly) ونقيضه — الكود غير المتوافق مع الكاش (cache-unfriendly).

اليوم سنشرح ما يعنيه هذا على مستوى العتاد، ولماذا الكاش ليس مجرد "ذاكرة أخرى"، بل هو مفتاح الأداء، وكيفية كتابة كود "يحبه" المعالج. بدون تجريدات معقدة — فقط C++ وأمثلة واضحة.

لماذا لا يمكن للمعالج القراءة ببساطة من الذاكرة العشوائية (RAM)؟

زادت سرعة المعالج آلاف المرات على مدى العقود الأخيرة، بينما زادت سرعة الذاكرة العشوائية (DRAM) بعشرات المرات فقط. تخيل سائق سيارة فورمولا 1 (المعالج) الذي يضطر للتوقف كل ثانية للحصول على الوقود (البيانات) من شاحنة تسير بسرعة 30 كم/ساعة (الذاكرة العشوائية). أمر محزن وبطيء.

الحل هو كاش المعالج: ذاكرة صغيرة جدًا ولكنها سريعة جدًا، مدمجة مباشرة في الشريحة. إنها تخزن نسخًا من البيانات المستخدمة بشكل متكرر. عندما يحتاج المعالج إلى بيانات، يتحقق أولاً من الكاش (L1 — الأسرع، ثم L2، L3). فقط إذا لم تكن البيانات موجودة (خطأ في الكاش (cache miss))، يذهب إلى الذاكرة العشوائية البطيئة.

إليك فترات الانتظار التقريبية (بدورات المعالج):

\n
• كاش L1: ~3-5 دورات
\n
• كاش L2: ~10-20 دورة
\n
• كاش L3: ~30-50 دورة
\n
• الذاكرة العشوائية: ~100-300 دورة
\n

الفرق بين L1 و RAM — من 50 إلى 100 مرة. لهذا السبب يمكن أن يكون الكود المتوافق مع الكاش بلغة C++ أسرع بعدة مرات من نظيره "غير الصديق".

مبدأ التوطين: كيف يقرر الكاش ما يحتفظ به

لا ينسخ الكاش بايتًا واحدًا — إنه يعمل بكتل (أسطر الكاش (cache lines))، عادةً بحجم 64 بايت. عندما تقرأ متغيرًا واحدًا، يقوم المعالج بتحميل الكتلة بأكملها التي تحتوي على هذا المتغير. ويراهن على مبدأين:

\n
• التوطين المكاني (Spatial locality): إذا قرأت عنصر مصفوفة arr[i]، فمن المحتمل أنك ستحتاج قريبًا إلى arr[i+1].
\n
• التوطين الزمني (Temporal locality): إذا قرأت بيانات الآن، فمن المحتمل أنك ستصل إليها مرة أخرى في المستقبل القريب.
\n

الكود المتوافق مع الكاش هو الكود الذي يستخدم هذه المبادئ إلى أقصى حد. دعنا نرى كيف يبدو هذا عمليًا.

مثال 1: اجتياز مصفوفة ثنائية الأبعاد — كلاسيكيات المجال

غير متوافق مع الكاش (كود سيء)

const int SIZE = 1024;\nint matrix[SIZE][SIZE];\n\n// الاجتياز حسب الأعمدة (column-major)\nfor (int j = 0; j < SIZE; ++j) {\n    for (int i = 0; i < SIZE; ++i) {\n        matrix[i][j] = i + j;\n    }\n}\n

في C++، يتم تخزين المصفوفات بترتيب الصفوف (row-major order). أي أن عناصر الصف matrix[0][0], matrix[0][1], matrix[0][2]... تقع في الذاكرة بشكل متسلسل. الحلقة الخارجية على j (الأعمدة) تجبر المعالج على القفز عبر الصف بأكمله في كل خطوة — كل وصول إلى matrix[i][j] هو على الأرجح خطأ في الكاش (cache miss). يضيع المعالج وقتًا في تحميل كتل جديدة، بينما يتم طرد البيانات السابقة من الكاش.

متوافق مع الكاش (كود جيد)

// الاجتياز حسب الصفوف (row-major)\nfor (int i = 0; i < SIZE; ++i) {\n    for (int j = 0; j < SIZE; ++j) {\n        matrix[i][j] = i + j;\n    }\n}\n

الآن نسير في الذاكرة بشكل متسلسل. بمجرد تحميل الكتلة التي تحتوي على matrix[0][0]، تكون العناصر الـ 15 التالية (مع int بحجم 4 بايت) موجودة بالفعل في الكاش! هذا يعطي زيادة في السرعة من 5 إلى 10 مرات