Liran Chen's Blog

הצבעים השונים מסמלים את תדירות הגישות לכל תא זכרון באובייקט. אדום לתדירות גבוהה, וירוק לנמוכה.
ניתן לראות שכאשר אנחנו לוקחים את האובייקט הזה, בו השדות ממוקמים ללא קשר למידת "החום" שלהם, ומכניסים אותו לתוך ה-Cache הדמיוני שלנו, אנחנו מכניסים לאותו Cache Line גם תאים שניגשים אליהם בתדירות גבוהה, וגם תאים שניגשים אליהם בתדירות נמוכה. כלומר, נניח שאנחנו מריצים כרגע קטע בקוד שעובד בצורה אינטנסיבית עם מבנה הנתונים הזה. בפועל, הוא ניגש אך ורק לתאים המסומנים באדום/כתום. מה שיקרה, זה שכדי לשמור את כל השדות האלו ב-Cache, אנחנו למעשה נצטרך להשתמש במספר רב יחסית של Cache Lines, רק מהסיבה שתאים רבים ב-Cache "מתבזבזים" על אזורי זכרון שאנחנו בכלל לא עושים בהם שימוש. ניצול המקום הבזבזני הזה משפיע בצורה ישירה לביצועים. זה אומר שאנחנו יכולים לסבול מיותר Cache Misses וגישות ל-Main Memory.
בדיוק כאן מגיע הרעיון של פיצול ל-Hot/Cold Data. הכוונה היא להגיע למצב בו אנו מנצלים את ה-Cache שלנו בצורה כמה שיותר אופטימלית. כדי לעשות זאת, כל מה שעלינו לעשות הוא לדאוג שהשדות האדומים יוקצו בקבוצה אחת, בעוד שהתאים הכתומים/ירוקים יוקצו בקבוצות נפרדות.
כך שלאחר אופטמיזציה מסוימת של אותו המבנה ממקודם, אנחנו יכולים לקבל את התוצאה הבאה:


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

הבעיה עם האופטמיזציה הזאת, היא שהיא לא טובה. או ליתר דיוק, לא מתאימה עבור אפליקציות המריצות קוד מקבילי.
אם אנחנו חוזרים לבעיית ה-False Sharing, אפשר להבין שהחלוקה הזאת בין Hot/Cold Data היא למעשה ההפך ממה שהיינו רוצים לעשות. מאחר ולא נעשית כאן הבחנה בין שדות שקוראים מהם נתונים בתדירות גבוהה, לעומת שדות שכותבים אליהם ערכים בתדירות גבוהה. מאחר וכשהמעבד משנה את ערכיו של משתנה, קיים צורך לבצע Invalidation עבור ה-Cache Lines (זה נכון במיוחד עבור פעולות אטומיות הדורשות אחזקה בלעדית על Cache Lines בזמן הפעולה), ומאחר ב-Hot/Cold Split לא קיימת הפרדה בין שדות המשנים את ערכם לבין אלו שלא, אנחנו למעשה יכולים לגרום לאינוולידציה מיותרת של שדות אלו הנמצאים במקרה על אותו Cache Line שנמצא עליו איזשהו שדה שכותבים אליו בתדירות גבוהה. כך שלמעשה, אפשר ללכת צעד אחד קדימה ולבצע הפרדה נוספת בין שדות בעלי תדירות גבוהה של Written To ו-Read From.
אבל, כדי להגיע ל-Locality מירבי, אנחנו צריכים להיפטר לגמרי מאיזשהו קיום של False Sharing אצלנו בקוד. לכן גם חלוקה של אותו Cache Line עבור מספר שדות שמשנים את ערכם בתדירות גבוהה היא למעשה טעות (זאת למעשה הסיטואציה הלא נעימה איתה הפוסט התחיל). כך שכדי להגיע ל-scalability אופטימלי, אנחנו נדרשים למעשה לנצל את ה-Cache באופן הכי בזבזני שאפשר, והוא לשמור בכל Cache Line אך ורק שדה זכרון אחד. בצורה הזאת, אנחנו סוף סוף מקבלים את אותו אפקט לוקאליות, שיאפשר לנו לגשת לאותו תא זכרון בלי שאף ת'רד אחר באפליקציה יפריע לנו.
כדי להשיג layout שכזה נצטרך להשתמש ב-StructLayout עם הדגל Explicit, כאשר עבור כל שדה משתמשים ב-FieldOffset שגודל בכל פעם בגודל ה-Cache Line בחיסור גודלו של השדה. באותה מידה, אפשר גם להקצות מערך של האובייקט המדובר, אבל שבין כל איבר ואיבר "אמיתי" קיימים מספר איברי "דמה" שלמעשה צריכים לתפוס את המקום שיכנס לתוך ה-Cache Line. כלומר, אנחנו מקצים הרבה יותר זכרון ממה שאנחנו צריכים באמת, רק בשביל "לרפד" את המרווחים בין האיברים האמיתיים, כך שבזמן הריצה בתוך כל Cache Line יכנס אך ורק תא אמיתי אחד. אפשר לראות דוגמה לשימוש בטכניקות האלו בפוסט False sharing is no fun מהבלוג של Joe Duffy.

לסיכום, כל ההתחשבות הזאת ב-Data Cache שהפוסט מדבר עליה רק מדגישה את העובדה שעם הזמן החומרה עליה האפליקציה רצה כבר לא כל כך שקופה למתכנתים. מצד אחד אנו חיים בעולם של Managed Code שחוסך לא מעט עבודה "טרחנית" אפשר לומר, אבל בו בזמן עולות שאלות כגון "על כמה מעבדים הקוד הזה אמור לרוץ? 1? 4? 128? 256?", או "מהו גודלו של כל Cache Line במעבד?". אופן כתיבת הקוד יכול להיות מושפע באופן ישיר מהתשובות שאלות האלה, וגם אחרות ("מה ה-memory model של המעבד?"), כך שאם יש דבר אחד בטוח, זה לא הופך את החיים שלנו לפשוטים יותר. אלא רק .. ליותר מעניינים.

string str2 = 1.ToString() + 2.ToString() + 3.ToString() + 4.ToString() + 5.ToString();

string[] CS$0$0000 = new string[] { 1, 2, 3, 4, 5 }; // edit: removed ToString

string text1 = string.Concat(CS$0$0000);

while(true)

{

    Stopwatch sw = Stopwatch.StartNew();

 

    for (int i = 0; i < 500000; i++)

    {

        // 960ms

        string str1 = string.Format("{0}, {1}, {2}, {3}, {4}", 1, 2, 3, 4, 5);

        // 665ms

        string str2 = string.Concat(1, ", ", 2, ", ",3, ", ", 4, ", ", 5);

        // 566ms

        string str3 = string.Join(", ", new string[] { 1, 2, 3, 4, 5 });

    }

 

    Console.WriteLine(sw.ElapsedMilliseconds);

}