310. Jagged arrays vs Multi-dimensional arrays

אז פעם שעברה הכרנו קצת את הקונספט של Jagged Arrays וראינו מה ההבדל ביניהם לMulti-dimensional Arrays.

כזכור, מערך רב מימדי ממומש ע”י מערך חד-מימדי רצוף באורך של מספר התאים שלו.

לעומת זאת, Jagged Array ממומש ע”י מספר מערכים בזכרון שלאו דווקא רצופים זה אחר זה.

עושה רושם שגישה אל מערך רב מימדי אמורה להיות מהירה יותר, שהרי המערך כולו יושב רצוף בזכרון.

עם זאת, באופן מפתיע, מסתבר שגישה אל מערך שהוא Jagged היא יותר מהירה.

הרצתי את הקוד השקול הזה:

private static void JaggedArrayTest(int width, int height, int length)
{
    int[][][] matrix;

    // Initialize array
    // ...

    Stopwatch sw = new Stopwatch();
    sw.Start();

    for (int i = 0; i < width; i++)
    {
        for (int j = 0; j < height; j++)
        {
            for (int k = 0; k < length; k++)
            {
                matrix[i][j][k] = i*j*k;
            }
        }
    }

    sw.Stop();
    Console.WriteLine("Jagged Array: {0}", sw.ElapsedMilliseconds);
}

private static void MultidimensionalArrayTest(int width, int height, int length)
{
    int[,,] matrix = new int[width,height,length];

    Stopwatch sw = new Stopwatch();
    sw.Start();

    for (int i = 0; i < width; i++)
    {
        for (int j = 0; j < height; j++)
        {
            for (int k = 0; k < length; k++)
            {
                matrix[i, j, k] = i*j*k;
            }
        }
    }

    sw.Stop();
    Console.WriteLine("Multidimensional: {0}", sw.ElapsedMilliseconds);
}

על מערכים גדולים יצא לי שלפעמים לוקח למערך הרב מימדי כמעט פי 2 יותר זמן לבצע פעולה זו מהמערך הJagged.

באופן דומה, אפשר להריץ קוד של קריאות ולראות שגם שם המערך הרב מימדי מפסיד בביצועים.

---

למה זה קורה?

הסיבה היא כזאת: אמנם מערכים רב מימדיים יושבים ברצף בזכרון, אבל הגישה אליהם מתבצעת באמצעות Indexer. הIndexer הזה הוא למעשה פונקציה לכל דבר, ולכן מתבצעת קריאה לפונקציה כדי להגיע למקום המתאים בזכרון.

הקריאה לפונקציה היא מה שעולה את רוב הזמן.

אז למה לא מרגישים את זה בJagged Array? הרי גם שם אנחנו ניגשים בIndexer, ואפילו פעמיים!

ובכן, הקומפיילר מקמפל גישה למערך חד מימדי בצורה יותר מהירה מגישה לפונקציה: זה מתבצע ע"י פקודות IL ייעודיות לכך:

• stelem.ref – להשמה במערך
• ldelem.ref – לקריאה ממערך

לכן במערכים שהם Jagged, שהם מערכים חד מימדיים לכל דבר, גישה לאיבר מסוים מתבצעת ע"י גישה מהירה.

במערכים רב-מימדיים רגילים, הגישה מתבצעת ע"י קריאה לאחת מהפונקציות:

call instance void int32[0...,0...,0...]::Set(int32, int32, int32, int32)
call instance int32 int32[0...,0...,0...]::Get(int32, int32, int32)

לקריאה לפונקציה יש Overhead נוסף, מאחר וצריך לדחוף את הפרמטרים המתאימים במחסנית וכו’.

---

אז מה המסקנה?

אם אתם משתמשים בקונספט של מערכים רב-מימדיים, והביצועים ממש קריטיים לכם, כדאי לשקול להשתמש בJagged Arrays.

אחרת, אין סיבה לא להשתמש במערכים רב-מימדיים רגילים.

למען האמת, קשה לי להאמין שמישהו משתמש בקונספט של מערכים רב מימדיים.

למעשה, לא יצא להשתמש בהם המון זמן, ובפעם הקודמת שהשתמשתי בהם, זה היה לצורך כתיבת תרגיל חפיפות.

סוף שבוע רב מימדי טוב!