אי(ה) המטמון

תמונת אוצר.png

כאשר אנו כותבים קוד שעובר על מטריצה, כלומר מערך דו ממדי, היינו יכולים לחשוב שאין כל הבדל אם נעבור עמודה עמודה:

image-15.png

או שמא שורה שורה:

image-14.png

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


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


ראשית אוכיח, ואז בע"ה אסביר למה, לשם דוגמה נשתמש בפונקציה שמאפסת מערך, ראשית ננסה שורה שורה, ואז טור טור, ונשוה את הזמנים (אגב, לא אשתמש בפייתון אלא בJS כי זה לא טבעי לפייתון לעבור שלא בשורות שורות):

שורה שורה או עמודה עמודה, יש הבדל? נבדוק:

ניצור שתי פונקציות זהות, למעט סדר הפעולות כאמור:

image-12.png

(שימו לב להבדל בסדר האינדקסים, i וj)


ניצור פונקציה למדידת זמן ריצה ממוצע, לאחר 1000 ריצות:

image-8.png

נבנה מערך בן מיליון אברים:

image-10.png

ונריץ:

image-13.png

(הקוד נגיש כאן, אשמח לשמוע בתגובות כמה מהר רץ אצלכם...)


בממוצע, מעבר על מערך בן מליון אברים שורה אחר שורה, לקח אצלי במחשב כ5 אלפיות השניה. ואילו אותו מערך לעבור עמודה אחר עמודה לקח בערך פי שבע! כ36 אלפיות השניה.

מדוע יש הבדל כה גדול?

הסיבה היא שבעת הריצה, כאשר אנו מבקשים מידע כל שהוא - נניח ניגשים לתחילת שורה של מערך - אז ניתן להניח שאם אנו מתחילים לקרוא מידע מתוך קטע זכרון, אז ייתכן שנרצה גם את המשך אותו הקטע, ולכן יטען לזכרון מראש גם המשך השורה!, כ"הכנה לעתיד", ומידע זה נשמר ב"מטמון" שזה זכרון מהיר מאד וקרוב למעבד.


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


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


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


הערות:


  • פוסט זה מתבסס על מה שלמדנו אצל ד"ר אליהו חלסצ'י.
  • לא זכיתי להבין מיהו האחראי על טעינת הזכרון למטמון, האם המעבד, מערכת ההפעלה, או שמא ישנו כלי מיוחד לכך? אודה למי שיאיר את עיני.
על המחבר
eliezer
בלוג תכנות כאן: code-review.blog

תגובות

בתוצאה אצלכם זמן הריצה של החישוב לפי עמודות גדול כמעט פי 7 מהשורות,
הרצתי את הקוד הנ"ל ואצלי הפרש היה של פחות מפי 2 זמן.
rows : 1.466
columns : 2.098
 
תודה, תקנתי. :)
לגבי זמן הריצה, זה מאד קשור לגודל המטמון ואורך השורה.
אם יש לך מטמון גדול ושורות קצרות כל המערך כולו יכנס למטמון ואז לא יהיה שום הבדל...
לא חידדתי זאת מספיק, מוטען למטמון פשוט המשך רציף מהזכרון, זה לא "דווקא" שורה. ייתכן שיכיל 2 שורות או חצי שורה וכו'
כנראה המטמון של המחשב שלך גדול מזה שלי, נסה להגדיל את אורך השורות של המערך ויש להניח שיהיה הבדל ניכר יותר.
 
נערך לאחרונה ב:
תודה רבה :)
בנתיים פרסמתיו עם תיקונים ושינויים קלים בבלוג שלי, ותודה לכל מי שהעיר ותיקן
 
הבעיה היא לא הלולאה, הבעיה היא הכתיבה.
הורדתי את הכתיבות למערך, ויצרתי מערך של 10000 על 10000
והתוצאה היא:
fillZeros_byRows : 878.436
fillZeros_byColumns : 927.054

נראה לי שהעניין הוא הרבה יותר פשוט
כשאתה כותב ל arr2d[99][99]
כל מערך arr2d[99] נטען לזכרון, ורק אחר כך המחשב יכול לדעת בכלל איפה arr2d[99][99] נמצא.
אחרת איך המחשב ידע איפה הכתובת של התת מערך?
עריכה: אופסס, ראיתי שהתגובות כאן לא עובדות, אז הגבתי בבלוג.
אגב הגבתי גם לפוסט "בל י_תואר" אבל נראה שזה לא נקלט
אולי זה טוב כי זה היה קצת חריף...
 
נערך לאחרונה ב:
תודה רבה, הגבתי שם, אבל אכתוב גם פה שלא להטריח ללכת רחוק....:
(אשמח אם תגיב שוב לפוסט הקודם.. לא יודע למה לא נקלט)


תודה על התגובה. ואני מעריך מאד את זה שטרחת לחכות זמן רב כזה עד שקיבלת את
התוצאה שהעלת…

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

(ניתן לראות את הקוד הסופי כאן )
והתוצאות שקיבלתי בהתחלה הן כך:
קוד:
line's length: 10 rows: 0.02 columns: 0.01
line's length: 100 rows: 0.01 columns: 0.01
line's length: 1000 rows: 0.57 columns: 1.53
line's length: 10000 rows: 54.35 columns: 307.08
(יותר ארוך מזה המחשב שלי לא מצליח לסחוב)

אני רואה שגם בקריאה לבד, יש הבדל ניכר, בין קריאה בטורים או בשורות, לטובת השורות, החל מסף מסוים.
אבל פה חשדתי, שהמפרש בעצם מבצע אופטימזציה, ובכלל לא קורא מהמערך, אלא רק עושה את הלולאה. ולכן הוספתי בלולאה משתנה שאליו נקרא תוכן המערך, כדי להכריח אותו ממש לקרוא מהמערך. התוצאה זינקה דרמטית, מה שהראה לי שאכן בוצעו קודם אופטימזציות שכעת מנעתי אותן, וזו התוצאה אצלי:
קוד:
line's length: 10        rows: 0.01     columns: 0.01
line's length: 100       rows: 0.04     columns: 0.02
line's length: 1000      rows: 1.62     columns: 20.19
line's length: 10000     rows: 200.51   columns: 5955.92
הפרש ניכר מאד לטובת שורות, גם בקריאה לבד.

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

אז מה מסביר את ההפרש הקטן בהרבה אצלך?
או שאני טועה במשהו, שלא שמתי לב, גם כעת… אבל אם לא, אני יכול לנחש כמה אופציות, (חלק זה ניחוש מפני שאינני מכיר את המחשב וגם לא בקיא בחומרה, וחלק זה ניחוש כי אינני יודע מה הקוד שהשתמשת בו):
א. יש לך מטמון גדול יותר שהכיל את המערך כולו…
ב. יש לך מטמון קטן יותר, שלא הכיל כמעט אברים בייחס לשורה באורך 100000 ולכן לא היה הבדל ניכר.
ג. המחשב שלך יודע לבצע חישוב מקבילי בצורה יעילה יותר מהמחשב שלי.
ד. הקוד שלך לא באמת קרא את המערך אלא רק נכנס ללולאה ותו לא, בשל ביצוע אופטימיזציות. ואז כל הזמן שרץ הוא בעצם פשוט הזמן שלקח לרוץ בלולאות, בלי קשר אמיתי למערך בעצם.

ואחרי הכל זה ניחוש.
אבל כמדומני שתסכים איתי שניתן לסכם על דעת הכל: מומלץ לעבור על מטריצה ולכתוב אליה בשורות דווקא.
 
נערך לאחרונה ב:
לגבי תגובתך לפוסט הקודם, כעת מצאתיה ואישרתיה אותה.
 
ניסיתי לממש את זה בvlang (שפה חדשה ללא GC)
והביצועים הרבה יותר טובים

קוד:
import time

fn main() {

        mut arr1 := [][]int{len: 10000, init: []int{len: 10000, init: 1}}
        mut arr2 := [][]int{len: 10000, init: []int{len: 10000, init: 1}}
        sw1 := time.new_stopwatch({})

        for i in 0 .. arr1.len {
                for j in 0 .. arr1.len {
                        arr1[j][i] = 0
                }

        }

        println('loop arr1 took: ${sw1.elapsed().nanoseconds()}ns')

        sw2 := time.new_stopwatch({})

        for i in 0 .. arr2.len {
                for j in 0 .. arr2.len {
                        arr2[i][j] = 0
                }

        }
        println('loop arr2 took: ${sw2.elapsed().nanoseconds()}ns')


}
והתוצאה היא:

loop arr1 took: 2074337667ns
loop arr2 took: 1669131524ns

נראה לי שכתבתי את הכל נכון, אמנם יש הבדלים אבל הרבה פחות מבJS
אז יתכן שההבדל נובע גם בגלל הGC?
 
מימשתי את זה גם בGO
וגם כשאני מבטל את הGC יש הבדל גדול
אז למה בV אין הבדל?
הנה הקוד בGO:
קוד:
import (
    "log"
    "time"
)

func main() {
    matrix1 := make([][]int, 1000)
    for i := 0; i < 1000; i++ {
        for j := 0; j < 1000; j++ {
            matrix1[i] = append(matrix1[i], 1)
        }
    }

    start := time.Now()
    for i := 0; i < 1000; i++ {
        for j := 0; j < 1000; j++ {

            matrix1[i][j] = 2
        }
    }
    elapsed := time.Since(start)
    log.Printf("loop 1 took %s", elapsed)

    matrix2 := make([][]int, 1000)
    for i := 0; i < 1000; i++ {
        for j := 0; j < 1000; j++ {
            matrix2[i] = append(matrix2[i], 1)
        }
    }

    start = time.Now()
    for i := 0; i < 1000; i++ {
        for j := 0; j < 1000; j++ {

            matrix2[j][i] = 2
        }
    }
    elapsed = time.Since(start)
    log.Printf("loop 2 took %s", elapsed)
}
והתוצאה היא :
קוד:
loop 1 took 1.00647ms
loop 2 took 9.007759ms
 
מימשתי את זה גם בGO
וגם כשאני מבטל את הGC יש הבדל גדול
אז למה בV אין הבדל?
הנה הקוד בGO:
קוד:
import (
    "log"
    "time"
)

func main() {
    matrix1 := make([][]int, 1000)
    for i := 0; i < 1000; i++ {
        for j := 0; j < 1000; j++ {
            matrix1[i] = append(matrix1[i], 1)
        }
    }

    start := time.Now()
    for i := 0; i < 1000; i++ {
        for j := 0; j < 1000; j++ {

            matrix1[i][j] = 2
        }
    }
    elapsed := time.Since(start)
    log.Printf("loop 1 took %s", elapsed)

    matrix2 := make([][]int, 1000)
    for i := 0; i < 1000; i++ {
        for j := 0; j < 1000; j++ {
            matrix2[i] = append(matrix2[i], 1)
        }
    }

    start = time.Now()
    for i := 0; i < 1000; i++ {
        for j := 0; j < 1000; j++ {

            matrix2[j][i] = 2
        }
    }
    elapsed = time.Since(start)
    log.Printf("loop 2 took %s", elapsed)
}
והתוצאה היא :
קוד:
loop 1 took 1.00647ms
loop 2 took 9.007759ms
תודה רבה על הבירור... :)
לצערי את vlang לא זכיתי להכיר כלל עד כה, ולכן עלי לנחש, אך הייתי חושש שאתחול המערך לוקה בחסר ובעצם כל השורות מפנות לאותה שורה בעצם במערך. כך לפחות זה מתנהג בJS וpython באתחול דומה.
יותר מזה אני לא מכיר אותה ולא יודע איך היא מתנהלת.
תאורתית כדי שיהיה הבדל (מצד המטמון) בין קריאה בשורות לקריאה בטורים הכרחי שהמערך ישמר בזכרון ברצף. אם יש שפה שתשמור את המערך על ידי רשימה מקושרת נניח, לא יהיה שום תועלת במטמון במקרה כזה.
כמו כן אם כל איבר במערך יכול להיות מטיפוס שונה, משמע שהיכן שהוא מאחורי הקלעים כל איבר הוא בעצם פוינטר למקום אחר בזכרון, והשורות הרציפות בזיכרון מכילות רק מצביעים. אז עדיין יש תועלת למטמון, בקריאת הפוינטרים, אבל לא יודע כמה זה ניכר, כי יש עוד עלות רבה מעבר לעצם קריאת המערך עצמו הרציף. (ייתכן אגב שזה מה שקורה בJS גם כאשר אני מאתחל מערך מטיפוס אחיד, ואם כן, מה שבחרתי בשפה זו זה לא היה רעיון מוצלח. כי קשה לבודד את השפעת המטמון עצמו בוודאות. אך אני לא יודע איך היא ממומשת מאחורי הקלעים, במנוע V8, ייתכן שפרימטיבים נשמרים ישירות במערך עצמו.)

בgo אני לא מכיר מקרוב אבל אני מבין שהיא סטטית ומתקמפלת, ואם כך, במידה ולא הקצת את הזכרון דינמית, אין צורך כלל בGC בפועל מצד אחד ומצד שני כנראה יש ניצול טוב של המטמון, כי הזכרון רציף. (אם הטיפוסים במערך אחידים, כמו למשל בC)
 
נערך לאחרונה ב:
לגבי GC, קשה לי להאמין שזה קשור, כי למה שיכנס לפעולה דווקא בעת ריצה על טורים ויפריע במידה כזו ולא בעת ריצה על שורות?
הרי בשני המקרים לא חל שום שינוי מהותי בקוד ואין צורך בשחרור של שום זכרון משמעותי.
 
@eliezer
גם GO וגם V הם סטטיים ומתקמפלים
ההבדל המרכזי הוא שלGO יש GC ולV אין.
לכן חשבתי אולי זה בגלל הGC ,שאגב בGO מספיק להתערב קצת תוך כדי ריצה של הקוד הקצר הזה
אבל מתברר שגם כשאני מבטל את הGC בGO, זה משפר (בקצת) את הביצועים בשני הלולאה במידה שווה.

מה שנראה לי הכי סביר, זה שפיספסתי משהו במימוש של V.
 
לגבי V האם בדקת שאכן כל שורה היא מערך נפרד?
כי זה למשל:
Python:
option1 = [["0",]*1000]*1000
#שונה לגמרי מ:
option2 = [["0" for i in range(1000)] for j in range(1000)]

וכן:
JavaScript:
const option1 = new Array(1000).fill(new Array(1000).fill(0));
//שונה לגמרי מ
const option1 = new Array(1000);
for (let i=0;i<1000;++i){
    option1[i] = new Array(1000).fill(0);
}

השאלה מה קורה בV.
מ"מ אני לא בטוח שאני מבין מה בעצם אתה מנסה להוכיח, האם אינך מסכים שיש מטמון?
אני מניח שלא, ואם כן לעצם העניין זה פחות מהותי אם טעיתי באיזה שורה ולכן קוד ההדגמה שלי לא נכון דיו, המטרה בו הייתה רק להמחשה של הרעיון. וגם אתה רואה הבדל ניכר בביצועים במקרים רבים. אז יוצא שלהלכה ולמעשה עדיף ברוב המקרים לעבור על מערך בשורות (זה גם יותר אינטואיטיבי, אבל נעזוב זאת).
 
@eliezer
לא באתי לחלוק עליך.
אני רק בודק האם ההבדל ההענק הזה הוא בגלל המטמון או שיש כאן עוד סיבה
ואז זה לא כל כך נורא לקרוא ממקומות שונים בזיכרון.
במקרה של קריאה ממטריצה ברור שהרבה יותר נכון לקרוא שורה אחרי שורה, גם אם אין הבדל בביצועים,
השאלה היא מה קורה אם למשל מחזיקים מערך של מצביעים?
 
נערך לאחרונה ב:
לגבי V האם בדקת שאכן כל שורה היא מערך נפרד?
לא יודע איך אני אמור לבדוק את זה
יצרתי מערך של 10X10, והדפסתי:
קוד:
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]
 
תשנה את הערך שנמצא במקום [0][0], אם כל השורות זהות בפועל, כל אבר ראשון בכל השורות יכיל כעת את השינוי, ואם כל שורה עצמאית , רק השורה הראשונה תכיל כן.
בפייתון אפשר גם לבדוק את הID של כל שורה ולראות אם זהה.
 
@eliezer
לא באתי לחלוק עליך.
אני רק בודק האם ההבדל ההענק הזה הוא בגלל המטמון או שיש כאן עוד סיבה
ואז זה לא כל כך נורא לקרוא ממקומות שונים בזיכרון.
במקרה של קריאה ממטריצה ברור שהרבה יותר נכון לקרוא שורה אחרי שורה, גם אם אין הבדל בביצועים,
השאלה היא מה קורה אם למשל מחזיקים מערך של מצביעים?
זה שאלה טובה, אני לא יודע מצד התאוריה, אבל בפועל לא קשה לנסות אם נכניס למערך אובייקטים במקום פרימטיביים.
קשה לי כרגע לבדוק, אולי בהמשך אנסה.
 
תשנה את הערך שנמצא במקום [0][0], אם כל השורות זהות בפועל, כל אבר ראשון בכל השורות יכיל כעת את השינוי, ואם כל שורה עצמאית , רק השורה הראשונה תכיל כן.
בפייתון אפשר גם לבדוק את הID של כל שורה ולראות אם זהה.
זה משנה רק את השורה הראשונה.
 
נראה לי שזה באג בV (אחרי הכל שפה בגרסה 0.2.2 )
כי כשאני עושה קוד דומה בC

קוד:
#include<stdio.h>
int main(){
   int disp[10000][10000];
   int i, j;
   for(i=0; i<10000; i++) {
      for(j=0;j<10000;j++) {
         disp[i][j] = 0;
      }
   }
   return 0;
}
הוא רץ מהר:
קוד:
real    0m0.191s
user    0m0.001s
sys    0m0.000s
לעומת זאת קוד דומה בV

קוד:
fn main() {

     mut arr1 := [][]int{len: 10000, init: []int{len: 10000}}
     for i in 0 .. 10000 {
        for j in 0 .. 10000 {
         arr1[i][j] = 0
        }
     }
}
לוקח הרבה יותר זמן לרוץ:
קוד:
real    0m1.537s
user    0m1.409s
sys    0m0.128s

המסקנה: לא לנסות להשתמש בשפות לפני 1.0v
וודאי שלא לבנות על זה תזות והוכחות.....
 
זה מסקנה הגיונית :)
אגב בC מערך דו ממדי רגיל הוא בלי ספק רציף בזיכרון (כי מצהירים מראש כל כל ממדיו והוא מכיל ערכים מאותו סוג וגודל) ולכן ניתן לקפוץ ביעילות (1)O לכל איבר, ואם יש הבדל בין שורות לטורים לכאורה זה רק בגלל מטמון. רק השאלה איך בכלל למדוד את המהירות שייקח כאשר כנראה הוא מהיר כברק ויש להניח שהשינוי יהיה יהיה באיזה כמה ספרות אחרי הנקודה..
 

הפרק היומי

הפרק היומי! כל ערב פרק תהילים חדש. הצטרפו אלינו לקריאת תהילים משותפת!


תהילים פרק קיט א'

א אַשְׁרֵי תְמִימֵי דָרֶךְ הַהֹלְכִים בְּתוֹרַת יְהוָה:ב אַשְׁרֵי נֹצְרֵי עֵדֹתָיו בְּכָל לֵב יִדְרְשׁוּהוּ:ג אַף לֹא פָעֲלוּ עַוְלָה בִּדְרָכָיו הָלָכוּ:ד אַתָּה צִוִּיתָה פִקֻּדֶיךָ לִשְׁמֹר מְאֹד:ה אַחֲלַי יִכֹּנוּ דְרָכָי לִשְׁמֹר חֻקֶּיךָ:ו אָז לֹא אֵבוֹשׁ בְּהַבִּיטִי אֶל כָּל מִצְוֹתֶיךָ:ז אוֹדְךָ בְּיֹשֶׁר לֵבָב בְּלָמְדִי מִשְׁפְּטֵי צִדְקֶךָ:ח אֶת חֻקֶּיךָ אֶשְׁמֹר אַל תַּעַזְבֵנִי עַד מְאֹד:
נקרא  29  פעמים

לוח מודעות

More from eliezer

שתף את המאמר

למעלה