איך איסוף זבל עובד באמת, מעבר לפייתון¶
בפוסט קודם הסברנו איך פייתון מנהלת זיכרון בעזרת ספירת רפרנסים, עם אספן מחזורי בתור גיבוי למעגלים. אבל זו רק אחת האסטרטגיות האפשריות לניהול זיכרון אוטומטי, ולא הנפוצה ביותר בעולם השפות בכלל. Java, JavaScript, Go, ורוב השפות המודרניות האחרות, משתמשות באסטרטגיה שונה לגמרי, שנקראת tracing garbage collection, ובליבה שלה עומד אלגוריתם קלאסי בשם Mark and Sweep.
הבעיה הכללית שכל אספן זבל פותר¶
בכל שפה עם ניהול זיכרון אוטומטי, יש אובייקטים בזיכרון שהתוכנית כבר לא צריכה - אין אליהם שום דרך להגיע מהקוד הרץ. השאלה שכל אספן זבל צריך לענות עליה היא פשוטה לניסוח וקשה למימוש - איך יודעים בוודאות שאובייקט מסוים כבר "מת", כלומר בלתי נגיש, בלי לסרוק כל בית זיכרון בכל רגע.
ספירת רפרנסים - הפתרון המקומי¶
ספירת רפרנסים, שפייתון משתמשת בה, פותרת את זה מקומית - כל אובייקט זוכר כמה מצביעים אליו יש כרגע. ברגע שהמונה מגיע לאפס, האובייקט מת ואפשר לפנות אותו מיד. זה פשוט ומיידי, אבל יש לו שתי בעיות - הוא לא פותר לבד מעגלי רפרנסים, ויש לו עלות ריצה קבועה בכל פעולת השמה, כי צריך לעדכן מונה בכל פעם שמצביע נוצר או נעלם.
Mark and Sweep - הגישה הגלובלית¶
Mark and Sweep, שנחשב האלגוריתם היסודי מאחורי רוב אספני הזבל המודרניים, לוקח גישה שונה לגמרי - במקום לעקוב אחרי כל אובייקט בנפרד כל הזמן, הוא עוצר מדי פעם, וסורק את כל הזיכרון בבת אחת, בשני שלבים ברורים:
- סימון - Mark. האספן מתחיל מקבוצת נקודות שנקראות שורשים (roots) - משתנים גלובליים, ומשתנים מקומיים על מחסנית הריצה כרגע - ועוקב אחרי כל מצביע שיוצא מהם, שלב אחר שלב, כמו הליכה ברשת דרכים. כל אובייקט שמצליחים להגיע אליו מהשורשים, מסמנים כ"חי".
- טאטוא - Sweep. אחרי שהאספן סימן את כל האובייקטים החיים, הוא עובר על כל הזיכרון פעם נוספת, ומשחרר כל אובייקט שלא סומן. אובייקט שלא הגיעה אליו שום הליכה מהשורשים הוא, בהגדרה, בלתי נגיש מהתוכנית - גם אם הוא חלק ממעגל רפרנסים ענק, כי בגישה הזאת מעגלים בכלל לא רלוונטיים, נבדקת רק שאלת ההגעה משורש, לא ספירת מצביעים.
זו בדיוק הסיבה ש-Mark and Sweep, בניגוד לספירת רפרנסים, פותר מעגלים באופן טבעי לגמרי, בלי צורך במנגנון נפרד.
המחיר - עצירות עולם¶
היתרון של Mark and Sweep מגיע עם מחיר. כדי לסרוק את הזיכרון בביטחון, בגרסה הבסיסית של האלגוריתם צריך לעצור את כל הקוד הרץ בזמן הסריקה - אחרת מצביעים עלולים להשתנות באמצע הסריקה ולבלבל אותה. זה נקרא Stop the World, ובתוכניות עם הרבה זיכרון פעיל, זה יכול ליצור השהיה מורגשת, בדיוק ברגע הכי לא נוח.
אספנים מודרניים - הדור שחוסך עבודה¶
כדי לצמצם את ההשהיה הזאת, אספני זבל מודרניים משתמשים בהנחה סטטיסטית שנקראת ההשערה הדורית (generational hypothesis) - רוב האובייקטים מתים צעירים, זמן קצר אחרי שנוצרו, ומעט מאוד אובייקטים שורדים הרבה זמן. בהתאם לזה, הזיכרון מחולק לדורות - דור צעיר, שנסרק לעיתים קרובות כי רוב הפינוי קורה בו, ודור מבוגר, שנסרק לעיתים רחוקות בהרבה, כי רוב האובייקטים בו כבר הוכיחו שהם חיים לאורך זמן. אובייקט ששרד כמה סבבי סריקה בדור הצעיר "מקודם" לדור המבוגר. זה מצמצם דרמטית את כמות הזיכרון שצריך לסרוק בכל סבב, בלי לוותר על נכונות התוצאה.
למה שווה להבין את שני המודלים ביחד¶
מפתח שמכיר גם ספירת רפרנסים וגם Mark and Sweep מבין למה בפייתון קשה יותר ליצור memory leak אמיתי, ולמה בשפות כמו Java יש מושג של "עצירת GC" שגורמת לפעמים להשהיה קצרה ומורגשת בשירות בזמן ריצה - שתי תופעות שנובעות ישירות מהבחירה האסטרטגית השונה שכל שפה עשתה.
הבנה כזאת של ניהול זיכרון ברמת העיקרון היא בדיוק מה שמפריד בין מתכנת שרק כותב קוד ברמה גבוהה, למישהו שמבין למה התוכנית שלו מתנהגת כמו שהיא מתנהגת, וזה בדיוק הכיוון שאנחנו בונים בקורס ליבת המחשב שלנו.
קורס ליבת המחשב נמצא כאן, חינם ובעברית, עם ירידה אמיתית לרזולוציה של מה שקורה מתחת לשפות התכנות שאתם משתמשים בהן.
יש לכם שאלה על התנהגות זיכרון מוזרה בשפה שאתם עובדים בה? שאלו בדיסקורד.
לסיכום¶
איסוף זבל הוא לא רעיון אחד אלא משפחה שלמה של אסטרטגיות - ספירת רפרנסים מקומית ומיידית אבל עיוורת למעגלים, ו-Mark and Sweep גלובלי שפותר מעגלים בטבעיות אבל דורש עצירות מדי פעם, שאספנים מודרניים מצמצמים בעזרת חלוקה לדורות. הבחירה בין הגישות האלה משפיעה ישירות על איך התוכניות שלכם מתנהגות בפועל.