מקצים ומחזור חיי מאגר זיכרון

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

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

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

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Key { index: usize, generation: u64 }
struct Slot<T> { generation: u64, value: Option<T> }
struct Pool<T> { slots: Vec<Slot<T>>, free: Vec<usize> }
impl<T> Pool<T> {
    fn new() -> Self { Self { slots: Vec::new(), free: Vec::new() } }
    fn insert(&mut self, value: T) -> Key {
        if let Some(index) = self.free.pop() {
            let slot = &mut self.slots[index];
            slot.value = Some(value);
            Key { index, generation: slot.generation }
        } else {
            let index = self.slots.len();
            self.slots.push(Slot { generation: 0, value: Some(value) });
            Key { index, generation: 0 }
        }
    }
    fn get(&self, key: Key) -> Option<&T> {
        let slot = self.slots.get(key.index)?;
        if slot.generation != key.generation { return None; }
        slot.value.as_ref()
    }
    fn remove(&mut self, key: Key) -> Option<T> {
        let slot = self.slots.get_mut(key.index)?;
        if slot.generation != key.generation { return None; }
        let value = slot.value.take()?;
        if let Some(next) = slot.generation.checked_add(1) {
            slot.generation = next;
            self.free.push(key.index);
        }
        Some(value)
    }
}
fn main() {
    let mut pool = Pool::new();
    let old = pool.insert(String::from("first"));
    assert_eq!(pool.remove(old).as_deref(), Some("first"));
    let current = pool.insert(String::from("second"));
    assert_eq!(old.index, current.index);
    assert!(pool.get(old).is_none());
    assert_eq!(pool.get(current).map(String::as_str), Some("second"));
}

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

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

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

המימוש מחזיר מקום לשימוש פנימי אבל אינו מקטין בהכרח את ההקצאה של ה־Vec. לכן ירידה במספר האובייקטים החיים אינה מחייבת ירידה מיידית ב־RSS. גם מקצה כללי יכול לשמור arenas ומטמונים מקומיים לתהליכון כדי להאיץ הקצאות עתידיות. מחיר השמירה יכול להיות fragmentation פנימי או זיכרון שאינו זמין מיד למשתמש אחר.

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

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

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