المستوى: متوسط — يفترض إنك بتكتب حلقات على مصفوفات وتعرف تشغّل Python أو C، لكن مش لازم تكون فاهم معمارية المعالج.
ليه المرور على مصفوفة بالأعمدة أبطأ من المرور بالصفوف؟
نفس البيانات، نفس عدد العمليات، ونفس الحلقة. تغيّر اتجاه المرور بس من الصفوف للأعمدة، فيتضاعف الزمن 6 مرات أو أكثر. ده مش بطء في المعالج، ده Cache Locality: ترتيب وصولك للذاكرة بيقرر هتستنى قد إيه. هنا هتقيس الفرق بنفسك وتعرف تستغله.
المشكلة باختصار
المصفوفة في الذاكرة مش مربع. هي شريط طويل واحد من الأرقام، متخزّن صفًا ورا صف (ده اسمه row-major، وهو الافتراضي في C وNumPy). لما تمر على عناصر صف واحد بالترتيب، انت بتمشي على الشريط جنب بعضه. لما تمر على عمود، انت بتقفز كل خطوة مسافة = عرض الصف كله.
القفز ده هو المشكلة. المعالج بيحب البيانات المتجاورة، وبيعاقبك بقسوة لما تتنطط في الذاكرة. والفرق مش نظري، انت هتقيسه بعد شوية.
مثال أمين الأرشيف (للمبتدئ تمامًا)
تخيّل موظف أرشيف بيجيب لك ملفات. عنده قاعدة غريبة: كل مرة تطلب ورقة واحدة، بيجيب الدرج اللي فيها كله (افرض 64 ورقة متجاورة) ويحطه على المكتب قدامك.
لو طلبت الأوراق بالترتيب — 1، 2، 3 — أول طلب بيجيب الدرج كله، وباقي الـ 63 طلب بتلاقيهم جاهزين على المكتب فورًا. سريع جدًا. ده المرور بالصفوف.
لكن لو طلبت ورقة من كل درج بالتناوب، كل طلب بيخلّي الموظف يرجّع الدرج اللي على المكتب ويروح يجيب درج جديد عشان ورقة واحدة بس. وبعدين يرجّعه ويجيب غيره. ده المرور بالأعمدة. نفس عدد الأوراق، بس الموظف بيتعب أضعاف ومنتظره وقت أطول.
التفسير العلمي: سطر الكاش (Cache Line)
المعالج عمره ما بيقرأ بايت واحد من الـ RAM. بيقرأ كتلة ثابتة اسمها cache line، حجمها 64 بايت على معظم معالجات x86 الحديثة (المرجع: دليل Intel للتحسين). الدرج في مثالنا هو سطر الكاش.
لما تطلب عنصر مش موجود في الكاش، بيحصل cache miss: المعالج يستنى لحد ما يجيب الـ 64 بايت من الذاكرة الرئيسية. لو طلبك التالي وقع جوه نفس الـ 64 بايت، بيحصل cache hit وبتاخد البيانات شبه فورًا.
الأرقام التقريبية اللي بتفرق كل حاجة (مرجع: "Latency Numbers Every Programmer Should Know" لـ Jeff Dean، وتوسيع Peter Norvig):
- إصابة كاش L1: حوالي 1 نانوثانية.
- فقدان الكاش والرجوع للذاكرة الرئيسية: حوالي 80 إلى 100 نانوثانية.
الفرق قرابة 100 ضعف. مرور الصفوف بيستغل كل بايت في السطر، فبيعمل cache miss كل 8 عناصر تقريبًا (8 أرقام float64 = 64 بايت). مرور الأعمدة بيقفز بعيد كل خطوة، فممكن يعمل miss في كل عنصر. ده مصدر الفرق.