שיעור 15: מטמון CPU ולוקליות זיכרון
המעבד מהיר בהרבה מהזיכרון הראשי. כדי לגשר על הפער, הוא משתמש בהיררכיה של מטמון — L1, L2, L3 — שמאחסנת עותקים של נתונים שנגשנו אליהם לאחרונה. כאשר קוד C++ ניגש לנתונים בסדר ידידותי-מטמון הביצועים קופצים פי עשרות. בשיעור הזה נראה מדוע לולאות row-major מהירות מ-column-major, מהי cache line, ומה גורם ל-
המעבד זוכר דברים שגישת אליהם לאחרונה — אם תקרא נתונים לפי הסדר שבו הם יושבים בזיכרון, המעבד כבר יחכה עם הנתון הבא לפני שתבקש אותו.
- cache line
- יחידת ההעברה בין הזיכרון הראשי למטמון — 64 בתים ברוב ה-CPU המודרניים. כל גישה לזיכרון טוענת את כל ה-cache line שמכיל את הכתובת.
- false sharing
- מצב שבו שני threads כותבים למשתנים שונים שיושבים באותה cache line, וגורמים לאינוולידציה מיותרת של המטמון בכל thread.
- לוקליות מרחבית
- הנטייה של תוכניות לגשת לכתובות זיכרון הקרובות זו לזו. ניגוש סדרתי למערך מנצל לוקליות מרחבית כי כל ה-cache line נטען יחד.
- לוקליות זמנית
- הנטייה של תוכניות לגשת לאותה כתובת זיכרון שוב ושוב בפרק זמן קצר. לולאות שמשתמשות באותו משתנה מספר פעמים מנצלות לוקליות זמנית.
- prefetch
- מנגנון שבו המעבד (או הקומפיילר) טוען cache lines מראש לפני שהקוד דורש אותם, על סמך זיהוי דפוסי גישה סדרתיים.
