1.9 - תכנון מבני נתונים לפי יחסי בעלות - הרצאה

גרף הנתונים קובע את צורת ההפניות

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

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

struct Jobs {
    names: Vec<String>,
    selected: Option<usize>,
}

impl Jobs {
    fn selected(&self) -> Option<&str> {
        let index = self.selected?;
        self.names.get(index).map(String::as_str)
    }
}

fn main() {
    let jobs = Jobs {
        names: vec!["scan".into(), "backup".into()],
        selected: Some(1),
    };
    println!("{:?}", jobs.selected());
}

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

מזהה דור שומר גם זהות

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

#[derive(Clone, Copy)]
struct Id {
    slot: usize,
    generation: u64,
}

struct Slot {
    generation: u64,
    value: Option<String>,
}

fn lookup(slots: &[Slot], id: Id) -> Option<&str> {
    let slot = slots.get(id.slot)?;
    if slot.generation != id.generation {
        return None;
    }
    slot.value.as_deref()
}

fn main() {
    let slots = vec![Slot { generation: 4, value: Some("scan".into()) }];
    assert_eq!(lookup(&slots, Id { slot: 0, generation: 3 }), None);
    assert_eq!(lookup(&slots, Id { slot: 0, generation: 4 }), Some("scan"));
}

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

בעלות במקום הפניה

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

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

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

מה static באמת אומר

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

fn label() -> &'static str {
    "fixed-label"
}

fn main() {
    println!("{}", label());
}

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

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

חוזרים לשאלה המקורית

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

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