ביצועים ומיקום בזיכרון

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

היררכיית המטמון של המעבד

מעבד מודרני לנייד מהיר הרבה יותר מזיכרון ה-RAM הראשי של המערכת (DRAM). כדי לגשר על הפער הזה בביצועים, המעבדים משתמשים בכמה רמות של זיכרון קטן ומהיר במיוחד שנקרא מטמון.

  • מטמון L1 (רמה 1): המטמון הכי קטן והכי מהיר (‎~1ns). במעבד של ‎3 GHz, מדובר ב-3 מחזורי שעון.
  • מטמון L2 (רמה 2): גדול יותר וקצת יותר איטי (כ-3 עד 5 ננו-שניות, או כ-10 עד 15 מחזורים).
  • מטמון L3 (רמה 3): המטמון הגדול ביותר (‎~10-20ns, או ‎~30-60 מחזורים).
  • זיכרון ראשי (DRAM): הזיכרון הכי גדול והכי איטי (‎~100ns+‎ או ‎~300+‎ מחזורים).

פירמידת השהייה של הזיכרון

הקשר של זמן האחזור: העלות של השהיה

כדי להבין את ההשפעה של המספרים האלה, כדאי להתייחס למעבד סופר-סקלארי מודרני שיכול להשלים 4 עד 8 הוראות בכל מחזור שעון.

אם המעבד מפספס את כל המטמונים וצריך לחכות 100 ננו-שניות (300 מחזורים) לקריאת DRAM:

  • מחזורים שאבדו: כ-300 מחזורים.
  • הוראות 'מבוזבזות': בין 1,200 ל-2,400 הוראות שיכולות היו להתבצע אם הנתונים כבר היו ברגיסטר מקומי או במטמון L1.

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

הוראות לכל מחזור (IPC)

מדד מרכזי למדידת היעילות הזו הוא הוראות לכל מחזור (IPC). הערך IPC מייצג כמה הוראות המעבד משלים בממוצע במהלך כל מחזור שעון.

  • ערך גבוה של IPC (לדוגמה, 3.0 עד 5.0): המעבד פועל ביעילות גבוהה, וסביר להניח שרוב הנתונים שלו נמצאים במטמון L1/L2 או ברגיסטרים.
  • ערך נמוך של IPC (למשל, < 0.5): צוואר הבקבוק של המעבד חמור. גם אם השימוש במעבד הוא 100% במוניטורים של המערכת, בפועל רוב הזמן המעבד ממתין לזיכרון – מצב שנקרא השהיית זיכרון.

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

שורות במטמון

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

מנגנונים של שורות מטמון

TLB (מאגר נתונים זמני לחיפוש תרגום)

מערכת Android משתמשת בזיכרון וירטואלי. כל גישה לזיכרון מחייבת תרגום של כתובת וירטואלית לכתובת פיזית. TLB הוא מטמון מיוחד שמאחסן תרגומים מהזמן האחרון. פספוס ב-TLB מחייב את ליבת מערכת ההפעלה לעבור על טבלאות דפים בזיכרון הראשי, וזו פעולה יקרה יחסית בהשוואה לפגיעה ב-TLB.

פרופיל חומרה: Pixel 10 Pro Fold

בתרגילים הבאים השתמשנו במכשיר Pixel 10 Pro Fold. המכשיר הזה כולל מערכת על שבב (SoC) מסוג Google Tensor G5.

בדיקת החומרה

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

# Check CPU architecture and core parts
adb shell cat /proc/cpuinfo | grep 'CPU part' | sort -u
# Output:
# CPU part  : 0xd8b
# CPU part  : 0xd8c
# CPU part  : 0xd90

# Check cache line size
adb shell getconf -a | grep CACHE_LINESIZE
# Output:
# LEVEL1_ICACHE_LINESIZE             64
# LEVEL1_DCACHE_LINESIZE             64

פענוח של חלקי המעבד (CPU)

הערכים CPU part ב-/proc/cpuinfo הם מזהים הקסדצימליים של ליבות מעבד ARM. ב-SoC של Laguna שנמצא ב-Pixel 10 Pro Fold, המיפוי הוא:

  • ‫0xd8b: ARM Cortex-A520 (ליבות יעילות)
  • ‫0xd90: ARM Cortex-A720 (ליבות ביצועים)
  • ‫0xd8c: ARM Cortex-X4 (ליבת Prime)

ההגדרה הזו של 4+3+1 נפוצה במערכות מודרניות על שבב (SoC) לניידים, שבהן יכול להיות שלאשכולות שונים יש גדלים שונים של מטמון וזמני השהיה שונים.

סוגי יישובים

תכנון יעיל של תוכנה מתבסס על שני סוגים עיקריים של לוקאליות:

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

תרגיל מעשי: מדידת לוקאליות באמצעות simpleperf

בתרגיל הזה נשתמש ב-simpleperf כדי לעקוב אחרי מוני ביצועי החומרה בזמן הפעלה של שני מעברים שונים במטריצה בגודל 256MB.

  1. מעבר לפי שורות: גישה לאלמנטים של המטריצה בסדר שבו הם מאוחסנים בזיכרון. השיטה הזו מתאימה לשימוש במטמון ומנצלת את המיקום המרחבי.
  2. Column-major Traversal: דילוג על פני הזיכרון כדי לגשת לאלמנטים לפי עמודה. במקרים כאלה, הגישה למטמון ול-TLB נכשלת, וה-CPU נאלץ להשהות את הפעולה.

1. הרצה עם Simpleperf

מעבירים את הקובץ הבינארי, מוודאים שהוא ניתן להרצה ומשתמשים ב-simpleperf stat כדי למדוד אירועים של מטמון ו-TLB. אנחנו משתמשים בסיומת :u כדי למדוד אירועים במרחב המשתמש. כדי להשתמש בפקודות האלה, צריך adb root כדי לגשת למונים של PMU בחומרה ברוב המכשירים.

adb root
adb shell "chmod +x /data/local/tmp/LocalityLab"

פרופיל Row-major:

adb shell "simpleperf stat -e cpu-cycles:u,instructions:u,cache-misses:u,L1-dcache-load-misses:u,dTLB-load-misses:u /data/local/tmp/LocalityLab row"

פרופיל לפי סדר עמודות:

adb shell "simpleperf stat -e cpu-cycles:u,instructions:u,cache-misses:u,L1-dcache-load-misses:u,dTLB-load-misses:u /data/local/tmp/LocalityLab col"

2. דוגמה למדידות (Pixel 10 Pro Fold)

התוצאות הבאות נמדדו במכשיר חומרה מדגם Pixel 10 Pro Fold:

מדד Row-major (Friendly) סדר עמודות (לא ידידותי) הפרש
מועד הביצוע ‫0.83 שניות ‫68.3 שניות איטי פי 82
הוראות ‫5.27 מיליארד ‫10.20 מיליארד בערך פי 1.9 יותר
מחזורי CPU ‫1.20 מיליארד ‫62.18 מיליארד פי 52 יותר
הוראות לכל מחזור (IPC) 4.40 0.16 יעילות נמוכה פי 27
L1 Data Cache Misses ‫210 מיליון ‫3,369 מיליון פי 16 יותר החמצות
dTLB Load Misses ‫0.13 מיליון ‫2,888 מיליון 22,000x more misses

3. ניתוח התוצאות

  • הקריסה של IPC: בבדיקה של שורות ראשיות, המעבד משיג IPC של 4.40, מה שמצביע על כך שהוא מבצע ביעילות כמה הוראות בכל מחזור. בבדיקה של עמודות, ה-IPC יורד ל-0.16. המשמעות היא שהמעבד מושהה 96% מהזמן וממתין לנתונים שיגיעו מ-DRAM.
  • צוואר הבקבוק של TLB: ההבדל הכי משמעותי הוא ב-dTLB-load-misses. גישה עוקבת (row-major) נשארת באותם דפי זיכרון, ולכן יש מעט מאוד החמצות ב-TLB. דילוג בין עמודות (column-major) גורם למעבד להפנות כל הזמן לדפים חדשים, מה שמעמיס על ה-TLB ומאלץ אותו לבצע סריקות יקרות של טבלאות דפים.
  • יעילות המטמון: מעבר בין עמודות יוצר פי 16 יותר החמצות במטמון L1, ולכן המעבד נאלץ לאחזר נתונים ממטמון L3 או מ-DRAM, שהם הרבה יותר איטיים.

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

מעקב אחר מצביעים במבני נתונים ב-Java וב-Kotlin

המדד של מטריצת 2D מראה את המיקום המרחבי במערכים נייטיביים רציפים, אבל רוב הקוד של אפליקציות ל-Android ומסגרות נכתב ב-Java וב-Kotlin. בשפות מנוהלות, משתני אובייקט ורכיבי אוסף לא מאחסנים אובייקטים בתוך השורה, אלא מאחסנים הפניות (מצביעים) לאובייקטים שהוקצו לערימה ומפוזרים בערימת ה-ART.

העלות של תרשימי הפניה מוטמעים

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

למרות שב-ArrayList, ב-ArrayMap וב-ArraySet המערכים הפנימיים Object[] מאוחסנים ברצף, כל רכיב במערך Object[] הוא עדיין הפניה לערימה. ביטול ההפניה לשרשרת כמו process.services.valueAt(i).connections.valueAt(j).client דורש חמש טעינות זיכרון רציפות ותלויות:

  1. טוענים את Object[] הגיבוי services.
  2. טוענים את הכותרת והשדות של אובייקט ServiceRecord.
  3. טוענים את Object[] הגיבוי connections.
  4. טוענים את אובייקט ConnectionRecord.
  5. טוענים את שדה היעד ProcessRecord.

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

פרימיטיבים מוקופסאים (ArrayList<Integer>, HashMap<Long, Boolean>) וביטויי למדא גנריים מגדילים את התקורה הזו: כל חיפוש של רכיב דורש ביטול הפניה נוסף של מצביע כדי לבטל את ההקפסה של הערך, וקריאות חוזרות גנריות (Consumer<T>) מוסיפות פלחי קוד (stub) של בדיקת סוג בזמן ריצה (CheckCast) שמוסיפים עומס על מטמון ההוראות (L1-icache).

אבחון של מעקב אחר מצביעים באמצעות simpleperf

בעומסי עבודה של Java ו-Kotlin בעולם האמיתי (כמו תהליך המעבר של system_serverOomAdjuster, שירות וגרפים של הפניות לספק), מעקב אחר מצביעים בדרך כלל לא מוריד את ה-IPC עד ל-0.16 כמו סריקה סינתטית של 256MB בעמודות, כי חלק ממערך העבודה מתאים למטמון L2 או L3. במקום זאת, כדאי לחפש את החתימה האופיינית הזו ב-simpleperf:

  • ערך נמוך של IPC (בערך 0.6 עד 0.9): הרבה מתחת לרוחב הפרישה הסופר-סקלארי של המעבד.
  • השהיות גבוהות בזיכרון העורפי (raw-stall-backend-mem): לעיתים קרובות, 35% עד 45% מכל מחזורי המעבד מושקעים בהמתנה למילוי מטמון הנתונים.
  • אי מציאה במטמון L1-dcache-load-misses ושל L1-icache-load-misses: שיעורים גבוהים של אי מציאה במטמון הנתונים בשילוב עם אי מציאה במטמון ההוראות, כשחוליות חמות של מעבר חוצה קופצות בין שיטות וירטואליות ובין קטע קוד חלופי (stub) של lambda כללי.

אפשר למדוד את המונים האלה בתהליך שפועל באמצעות simpleperf stat:

adb shell simpleperf stat \
  -e cpu-cycles:u,instructions:u,raw-stall-backend-mem:u,L1-dcache-load-misses:u,L1-icache-load-misses:u \
  -p $(pidof system_server) --duration 10

שיפור הלוקאליות בקוד מנוהל

  • החלפת אוספים מוקופצים במערכים פרימיטיביים או באוספי AndroidX: משתמשים בפרימיטיבים IntArray,‏ LongArray,‏ SparseIntArray או androidx.collection (IntList,‏ LongLongMap,‏ ScatterMap) כדי לבטל אובייקטים של wrapper ולשמור על ערכים רציפים בתוך הקצאה של מערך יחיד.
  • השטחת נתיבי מעבר פופולריים: אם לולאה פופולרית עוברת שוב ושוב שלוש או ארבע קפיצות בגרף אובייקטים כדי לקרוא דגל בוליאני או דגל של מספר שלם יחיד, כדאי להעלות או לשמור במטמון את המצב הזה במערך שטוח או במסכת ביטים עם אינדקס לפי מזהה צפוף.
  • לא כדאי ללכוד או להשתמש בפונקציות למדא גנריות בלולאות פנימיות צפופות: עדיף להשתמש בלולאות for עם אינדקס רגיל על רשימות RandomAccess במקום בשרשראות של forEach או איטרטורים, כדי להימנע מהקצאות של איטרטורים, משליחה מגה-מורפית ומעומס יתר של בדיקות סוגים בזמן ריצה.

← Threads | ↑ Up | Service bindings →