Liran Chen's Blog

.Net Internals, Development, Multithreading - and More!

Hot/Cold Data in Multithreaded Environments

בתקופה האחרונה שמתי לב שהנושא של False Sharing עולה לעתים די קרובות בבלוגים שמפרסמים פוסטים המסבירים במה בעצם מדובר ובאיך אפשר להמנע מהתופעה. כך שכמובן שהגיע הזמן שאתייחס בעצמי לנושא החשוב אך חמקמק הזה.
אבל קודם כל, נסביר בקצרה במה בעצם מדובר ובאיפה טמונה הבעיה.
אחד הנושאים הרגישים בפיתוח קוד מקבילי הוא הגישה לזיכרון המשותף למספר Thread'ים שונים. (כדי שנשאר ממוקדים בנושא הפוסט, אני אתעלם לרגע מבעיות העלולות להגרם כתוצאה מ-Instruction Reordering או אופטימיזציות אחרות שמבוצעות ברמת הקומפיילר או החומרה), אחת מבעיות הליבה היא לסנכרן את הגישה לאותם אזורי זכרון משותף. נניח שאנחנו מריצים את האפליקציה שלנו על מחשב עם 8 ליבות, והיא משתמשת ב-8 ת'רדים שמעבדים נתונים כלשהם ובסופו של דבר מעדכנים מבנה נתונים המשותף לכל הת'רדים בגודל 500KB. כדי למנוע corruption (העלול להיגרם מכמה ת'רדים שקוראים/כותבים לאותו בלוק זכרון בו-זמנית), סביר שנשתמש במנגנון נעילה כלשהו שיסנכרן את הגישות לאותו בלוק זכרון משותף. הבעיה בפתרון הזה הוא שיכול להיווצר לנו contention מאוד גדול על אותה נעילה, מה שלמעשה יהרוג את ה-scalability של הקוד שלנו (סביר שנראה שככל שנוסיף עוד מעבדים ועוד ת'רדים שירוצו עליהם, למעשה נראה ירידה בביצועים במקום עליה, מאחר והסיכוי שנקבל contentions על אותה נעילה בודדת רק הולך וגודל).
מאחר ושיתוף הזכרון הזה פוגע ב-scalability שלנו, והפגיעה הזאת למעשה מתורגמת לפגיעה בביצועים, ושיפור בביצועים הוא למעשה המוטיבציה היחידה לכתוב קוד מקבילי מלכתחילה, אפשר להבין שמדובר למעשה בבעיה קשה שצריך לטפל בה באיזשהיא צורה.
אחת האפשרויות העומדות בפנינו, היא להקטין במידת האפשר את השימוש בזכרון משותף. כך שאם נחזור לדוגמה הקודמת, זה אומר שנוכל לשפר את ביצועי הקוד אם נחליט שבמקום שכל ת'רד יעדכן את אותו בלוק זכרון מרכזי בתדר גבוה מאוד, נוכל להקצות עבור כל ת'רד תא זכרון נפרד שיהיה נגיש אך ורק לו. כך שלמעשה, בזמן העיבוד האינטנסיבי כל ת'רד יעדכן בתדירות גבוהה רק את תא הזכרון השייך לו (גישות אליו לא מצריכות שום סוג של נעילה מאחר והוא נגיש רק לת'רד בודד), ורק בסוף כל התהליך (אחרי שכל ת'רד סיים את החלק היחסי שלו בעבודה), נאסוף את כל המידע הזה ונעדכן בעזרתו את בלוק הזכרון המרכזי. בצורה הזאת הורדנו את הסנכרון הנדרש בין הת'רדים למינימום, וניתן להניח שנראה הבדל ניכר בביצועי התוכנית כשהיא תרוץ על מספר רב של מעבדים.
עם זאת, קיימת בעיה מהותית בפתרון הזה. לתופעה קוראים False Sharing, והיא מקבלת את שמה מכך שבזמן כתיבת קוד הדוגמה שלנו, אנחנו מפרידים בין תאי הזיכרון הייחודים לכל ת'רד בצורה לוגית. אנחנו אומרים "ת'רד 1 יגיש לתא X ות'רד 2 יגש לתא Y. מאחר ומדובר בשני תאי זכרון שונים לגמרי, אין לנו שום צורך לסנכרן גישות אליהם". אבל בפועל, המצב אינו כל כך פשוט. תלוי באופן בו הקצנו את תאי הזכרון עבור הת'רדים, יתכן שבזמן ריצת האפליקציה, תאי זכרון שהוקצו "בסמוך לאחרים" יגיעו בסופו של דבר לאותו Cache Line במעבד.
מעבדים מודרנים משתמשים ב-Cache פרטי בשביל לשמור (בין היתר) ערכים של משתנים שהשתמשו בהם לאחרונה. בעוד שהגישה ל-Main Memory נחשבה ליקרה יחסית, הגישה ל-Cache נחשבת למהירה בצורה ניכרת (בייחוד אם מדובר בגישות ל-L1). בדוגמה שלנו עלולה להיגרם בעיה חמורה בהנחה שאותם תאי זכרון פרטיים יותר קטנים מגודל ה-Cache Line של המעבד בו אנו משתמשים. כך שאם הם קטנים מספיק, והוקצו "מספיק קרוב" אחד לשני, יתכן מאוד שמספר תאי זכרון סמוכים כאלה יכנסו לאותו ה-Cache Line. כאשר ת'רד מסויים ירצה לשנות את אחד מהערכים שנמצאים ב-Cache Line המדובר, הוא יצטרך לקבל בלעדיות על אותו Line. כך שאם למשל 4 ת'רדים שונים מנסים לשנות 4 ערכים שונים שנכנסו לאותו Cache Line, זה אומר שתמיד 3 ת'רדים יחכו עד שהת'רד הרביעי יסיים את העבודה שלו, ורק אז יוכלו לעדכן את המשתנה הפרטי שלהם בעצמם.
כלומר, אם אנחנו רוצים לסכם את כל זה במשפט אחד, אפשר להגיד שאותם "תאי זכרון פרטיים" שהזכרנו מקודם כדרך להמנע משיתוף זכרון בין ת'רדים, הם לא יותר מאשליה גסה. מאחר ובסופו של דבר אנחנו כן נאלצים (למעשה, המעבד נאלץ), לסנכרן את הגישות ל-Cache Line בו הם נמצאים. כך שאם נריץ את הקוד, נוכל לגלת שהמעבדים שלנו אומנם עובדים קשה מאוד, אבל בפועל, אנחנו לא מקבלים את ה-speedup שהיינו מצפים לקבל.
כדי ללמוד עוד על הנושא ולקבל גם מעט יותר דוגמאות קונקרטיות על איך התופעה משפיעה על הביצועים של אפליקציה, מקום טוב הוא המאמר Eliminate False Sharing של Herb Sutter.

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



הצבעים השונים מסמלים את תדירות הגישות לכל תא זכרון באובייקט. אדום לתדירות גבוהה, וירוק לנמוכה.
ניתן לראות שכאשר אנחנו לוקחים את האובייקט הזה, בו השדות ממוקמים ללא קשר למידת "החום" שלהם, ומכניסים אותו לתוך ה-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 של המעבד?"), כך שאם יש דבר אחד בטוח, זה לא הופך את החיים שלנו לפשוטים יותר. אלא רק .. ליותר מעניינים.
פורסם: Nov 21 2009, 11:32 AM by Liran Chen | with 4 comment(s)
תגים:, ,

תוכן התגובה

יוני אורנשטין כתב/ה:

כמו תמיד מעניין ומרחיב את הידע

# November 26, 2009 10:22 PM

מני אריאל כתב/ה:

מאמר מצויין!

# November 28, 2009 10:38 AM

Noam כתב/ה:

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

פתרון אחר הוא להשתמש בספריות של יצרן המעבד אשר לטעמי יודעות ליצר את התלויות הנכונות ב90% מהמצבים אך גם הן לא נותנו מענה לסביבות VM

# February 1, 2010 12:12 AM

Liran Chen כתב/ה:

@Noam

השימוש בחומרה שעליה רץ הקוד שלנו כבר מזמן הפך לפחות ופחות "שקוף" עבור המתכנת, וזה בייחוד נכון עבור פיתוח מקבילי. לכן כשכותבים קוד High Performance ורוצים להבטיח לוקאליות אמיתית, חייבים להיות קשובים לתכונות סביבת היעד עליה האפליקציה מתוכננת לרוץ (למשל, האם אנו עובדים על-SMP או ccNuma?). נתונים לגבי גודל ה-Cache ,גודלו של כל Cache Line והאם אנחנו רצים על מכונת SMP או NUMA אפשר לקבל דרך קריאה לפונקציה GetLogicalProcessorInformation (למרות שכמובן שההבדלים בין שימוש ב-SMP או NUMA מתבטא למעבר לעדכון איזשהו פרמטר בקוד).

# February 1, 2010 7:19 AM
שלח תגובה

(שדה חובה)  

(שדה חובה)  

(אופציונלי)

(שדה חובה) 

Please add 1 and 3 and type the answer here:


Enter the numbers above: