אי(ה) המטמון

פרוגיוזרית · 23/4/21

מאמר מצוין וברור מאד.

לגבי שאלתך, זה רכיב חומרה שנקרא TLB (translation lookaside buffer), המצוי בחומרה שמנהלת את הזכרון (MMU).

עיטורים פלוס · 24/4/21

בתוצאה אצלכם זמן הריצה של החישוב לפי עמודות גדול כמעט פי 7 מהשורות,
הרצתי את הקוד הנ"ל ואצלי הפרש היה של פחות מפי 2 זמן.
rows : 1.466
columns : 2.098

eliezer · 24/4/21

תודה, תקנתי.

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

עיטורים פלוס · 24/4/21

אכן, כשהארכתי את השורות ל2000 ניכר ההפרש ועמד על הפרש של כמעט פי 7
rows : 3.023
columns : 20.974

eliezer · 25/4/21

נכתב ע"י פרוגיוזרית:
מאמר מצוין וברור מאד.

לגבי שאלתך, זה רכיב חומרה שנקרא TLB (translation lookaside buffer), המצוי בחומרה שמנהלת את הזכרון (MMU).

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

UU · 25/4/21

וואו, זה ממש מעניין
תודה!

eliezer · 25/4/21

תודה רבה

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

ynigun · 25/4/21

הבעיה היא לא הלולאה, הבעיה היא הכתיבה.
הורדתי את הכתיבות למערך, ויצרתי מערך של 10000 על 10000
והתוצאה היא:
fillZeros_byRows : 878.436
fillZeros_byColumns : 927.054

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

eliezer · 26/4/21

תודה רבה, הגבתי שם, אבל אכתוב גם פה שלא להטריח ללכת רחוק....:
(אשמח אם תגיב שוב לפוסט הקודם.. לא יודע למה לא נקלט)

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

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

(ניתן לראות את הקוד הסופי כאן )
והתוצאות שקיבלתי בהתחלה הן כך:

קוד:

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 ולכן לא היה הבדל ניכר.
ג. המחשב שלך יודע לבצע חישוב מקבילי בצורה יעילה יותר מהמחשב שלי.
ד. הקוד שלך לא באמת קרא את המערך אלא רק נכנס ללולאה ותו לא, בשל ביצוע אופטימיזציות. ואז כל הזמן שרץ הוא בעצם פשוט הזמן שלקח לרוץ בלולאות, בלי קשר אמיתי למערך בעצם.

ואחרי הכל זה ניחוש.
אבל כמדומני שתסכים איתי שניתן לסכם על דעת הכל: מומלץ לעבור על מטריצה ולכתוב אליה בשורות דווקא.

eliezer · 26/4/21

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

ynigun · 26/4/21

נכתב ע"י eliezer:
אז מה מסביר את ההפרש הקטן בהרבה אצלך?

פשוט מחקתי את השורה של

קוד:

 arr2d[i][j]= "0"

ynigun · 27/4/21

ניסיתי לממש את זה ב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?

ynigun · 27/4/21

מימשתי את זה גם ב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

eliezer · 27/4/21

נכתב ע"י ynigun:
פשוט מחקתי את השורה של

קוד:

arr2d[i][j]= "0"

התכוונתי מה מסביר את ההפרש הקטן בהרבה בין מה שייצא לי גם כן בלי כתיבה לבין מה שייצא לך

eliezer · 27/4/21

נכתב ע"י ynigun:

מימשתי את זה גם ב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)

eliezer · 27/4/21

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

ynigun · 27/4/21

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

מה שנראה לי הכי סביר, זה שפיספסתי משהו במימוש של V.

eliezer · 27/4/21

לגבי 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.
מ"מ אני לא בטוח שאני מבין מה בעצם אתה מנסה להוכיח, האם אינך מסכים שיש מטמון?
אני מניח שלא, ואם כן לעצם העניין זה פחות מהותי אם טעיתי באיזה שורה ולכן קוד ההדגמה שלי לא נכון דיו, המטרה בו הייתה רק להמחשה של הרעיון. וגם אתה רואה הבדל ניכר בביצועים במקרים רבים. אז יוצא שלהלכה ולמעשה עדיף ברוב המקרים לעבור על מערך בשורות (זה גם יותר אינטואיטיבי, אבל נעזוב זאת).

ynigun · 27/4/21

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

ynigun · 27/4/21

נכתב ע"י 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]]

eliezer · 27/4/21

תשנה את הערך שנמצא במקום [0][0], אם כל השורות זהות בפועל, כל אבר ראשון בכל השורות יכיל כעת את השינוי, ואם כל שורה עצמאית , רק השורה הראשונה תכיל כן.
בפייתון אפשר גם לבדוק את הID של כל שורה ולראות אם זהה.

eliezer · 27/4/21

נכתב ע"י ynigun:
@eliezer
לא באתי לחלוק עליך.
אני רק בודק האם ההבדל ההענק הזה הוא בגלל המטמון או שיש כאן עוד סיבה
ואז זה לא כל כך נורא לקרוא ממקומות שונים בזיכרון.
במקרה של קריאה ממטריצה ברור שהרבה יותר נכון לקרוא שורה אחרי שורה, גם אם אין הבדל בביצועים,
השאלה היא מה קורה אם למשל מחזיקים מערך של מצביעים?

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

ynigun · 27/4/21

נכתב ע"י eliezer:
תשנה את הערך שנמצא במקום [0][0], אם כל השורות זהות בפועל, כל אבר ראשון בכל השורות יכיל כעת את השינוי, ואם כל שורה עצמאית , רק השורה הראשונה תכיל כן.
בפייתון אפשר גם לבדוק את הID של כל שורה ולראות אם זהה.

זה משנה רק את השורה הראשונה.

ynigun · 27/4/21

נראה לי שזה באג ב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
וודאי שלא לבנות על זה תזות והוכחות.....

eliezer · 27/4/21

זה מסקנה הגיונית

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

י. צ. · 27/4/21

נכתב ע"י פרוגיוזרית:
לגבי שאלתך, זה רכיב חומרה שנקרא TLB (translation lookaside buffer), המצוי בחומרה שמנהלת את הזכרון (MMU).

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

יהודיה נחמדה · 10/4/22

יישר כח!

אי(ה) המטמון

תגובות

תאומים • אתגר 145

שתף את המאמר

תגיות נפוצות