المستوى: متوسط — يفترض إنك بتكتب حلقات على مصفوفات وتعرف تشغّل 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 في كل عنصر. ده مصدر الفرق.

اقيس الفرق بنفسك (NumPy)

الكود ده بيبني مصفوفة 8000×8000 من float64 (حوالي 488 ميجابايت، أكبر من الكاش بكتير عشان نشوف الأثر الحقيقي)، وبيجمع مرة بمحاذاة الصفوف ومرة بمحاذاة الأعمدة:

import numpy as np, time

N = 8000
a = np.ones((N, N), dtype=np.float64)  # ~488MB، مخزّنة row-major

t = time.perf_counter()
s_rows = a.sum(axis=1)   # جمع كل صف: مرور متجاور
row_time = time.perf_counter() - t

t = time.perf_counter()
s_cols = a.sum(axis=0)   # جمع كل عمود: قفز بخطوة = عرض الصف
col_time = time.perf_counter() - t

print(f"rows : {row_time*1000:6.0f} ms")
print(f"cols : {col_time*1000:6.0f} ms")
print(f"ratio: {col_time/row_time:5.1f}x")

مخرجات تقريبية على جهاز مكتبي عادي (هتختلف عندك حسب حجم الكاش وتردد الذاكرة):

rows :     46 ms
cols :    287 ms
ratio:    6.2x

الافتراض هنا إن المصفوفة أكبر من كاش L3 بكتير. لو المصفوفة صغيرة وبتتحط كلها في الكاش، الفرق بيختفي تقريبًا، لأن مفيش miss أصلًا.

نفس المبدأ في C — وهو الأوضح

في C الفرق بيظهر صريح من غير أي طبقة مكتبة. الحلقة الأولى بتمشي صفًا صفًا (متجاور)، والتانية عمودًا عمودًا (قفز):

// مرور بالصفوف: i ثابت، j بيتحرك جوه الصف المتجاور
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += a[i][j];

// مرور بالأعمدة: j ثابت، i بيقفز صف كامل كل خطوة
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        sum += a[i][j];

النسخة التانية بتعمل نفس الجمع بالظبط، بس بتقفز N عنصر كل تكرار، فبتكسر استغلال سطر الكاش. على مصفوفات كبيرة الفرق بيوصل لـ 6× أو أكتر، زي ما قاس Ulrich Drepper في ورقته الشهيرة عن الذاكرة.

ليه الفرق بيكبر كل ما البيانات تكبر

القاعدة البسيطة: طول ما المصفوفة جوه الكاش، اتجاه المرور مش مهم. أول ما تكبر عن الكاش، اتجاه المرور بيقرر نسبة الـ miss. عشان كده الكود اللي بيشتغل تمام على بيانات صغيرة في التطوير، بيبوظ فجأة على بيانات الإنتاج الكبيرة.

سيناريو واقعي: لو بتعالج صورة أو مصفوفة استشعار 10000×10000 وبتلف عليها بالأعمدة في كل frame، الفرق بين 46ms و287ms معناه 21 frame/ثانية بدل 130. ده الفرق بين تجربة سلسة وتهنيج.

الـ trade-offs وما يجب الانتباه له

• المكسب: ترتيب الحلقة صح ممكن يديك 5×–10× مجانًا، من غير ما تغيّر الخوارزمية ولا تشتري عتاد.
• الثمن: أحيانًا المنطق الطبيعي للمسألة بالأعمدة. وقتها بتحتاج تعمل transpose للمصفوفة الأول (بيكلّف مرور كامل + ذاكرة إضافية بحجم المصفوفة) عشان تكسب بعدين. يستاهل بس لو هتمر عليها كذا مرة.
• الانتباه: في NumPy، نتيجة np.ones((N,N)).T بتبقى view بترتيب أعمدة (Fortran-order)، فالمرور عليها "بالصفوف" بيرجع بطيء. الترتيب الفعلي في الذاكرة هو اللي بيحكم، مش شكل الكود (مرجع: توثيق NumPy عن memory layout وC vs Fortran order).

متى لا تشغل بالك بهذا

متضيّعش وقتك في إعادة ترتيب الحلقات لو: بياناتك صغيرة وبتدخل الكاش كلها؛ أو الكود ده مش في مسار ساخن (بيتنفّذ مرة في الساعة مش مليون مرة في الثانية)؛ أو لسه ما قِستش وأكّدت إن ده فعلًا عنق الزجاجة. التحسين الأعمى قبل القياس بيعقّد الكود بلا فايدة. اقيس الأول بـ profiler، وبعدين رتّب.

الخطوة التالية

افتح أبطأ حلقة متداخلة عندك على مصفوفة كبيرة، وتأكد إن المتغيّر اللي بيتحرك في الحلقة الداخلية هو آخر index (الأكثر تجاورًا في الذاكرة: العمود في C/NumPy). لو لقيته بالعكس، اقلب ترتيب الحلقتين وأعد القياس. لو الزمن نزل، الـ cache locality كانت بتاكلك.

المصادر

• Ulrich Drepper، "What Every Programmer Should Know About Memory" (Red Hat, 2007) — المرجع التفصيلي عن سطر الكاش وأنماط الوصول.
• Jeff Dean، "Latency Numbers Every Programmer Should Know"، وتوسيع Peter Norvig — أرقام زمن L1 والذاكرة الرئيسية.
• Intel 64 and IA-32 Architectures Optimization Reference Manual — حجم سطر الكاش 64 بايت وسلوك الجلب المسبق.
• توثيق NumPy الرسمي: Internal memory layout of an ndarray (C-order مقابل Fortran-order).
• Agner Fog، Optimization manuals — تأثير أنماط الوصول للذاكرة على الأداء.