2.4 - מכולות כבחירה הנדסית - הרצאה

הרשימה גדלה והמצביע נשבר

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

התוכנית הבאה מדגימה שינוי מיקום בלי לגשת דרך pointer שפג תוקפו:

#include <cstdint>
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> values;
    values.reserve(1);
    values.push_back(7);

    const auto before = reinterpret_cast<std::uintptr_t>(values.data());
    const auto capacity = values.capacity();

    while (values.size() < capacity) values.push_back(0);
    values.push_back(9);

    const auto after = reinterpret_cast<std::uintptr_t>(values.data());
    std::printf("old=%llx new=%llx capacity=%zu\n",
                static_cast<unsigned long long>(before),
                static_cast<unsigned long long>(after),
                values.capacity());
}

הקוד ממלא את הcapacity שהמימוש נתן בפועל, במקום להניח ש־reserve(1) נותן בדיוק מקום אחד. ההוספה האחרונה דורשת גדילה מעבר לcapacity הנוכחי. נשמרת כתובת כמספר לצורך הצגה בלבד; אין dereference של האחסון הישן.

הגדלת capacity יכולה להעביר או להעתיק את האיברים לאחסון חדש. לכן pointerים, references ו־iteratorים לאיברים עלולים להיפסל. ניהול החיים של vector עצמו תקין, אבל aliases שהקוד החיצוני שמר אינם עוברים איתו אוטומטית.

גודל לעומת קיבולת

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

הפעולה reserve אינה בונה את האיברים החסרים. אחרי reserve(100) על vector ריק, עדיין אסור לגשת ל־values[50]. יש אחסון זמין, אבל אין חמישים ואחד איברים חיים במכולה.

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

רציפות ומקומיות

ה־vector וה־array מחזיקים איברים רציפים. המשמעות היא שאפשר לעבור בין איברים דרך טווח רציף, ולמסור span בהתאם לחוזי החיים.

ה־deque מאפשר גישה באינדקס, אבל אינו מחויב לאחסון רציף של כל האיברים. הוא מתאים לדפוסי עבודה אחרים, כמו הוספה והסרה משני הקצוות. אין לקבל pointer לאיבר הראשון ולחשב ממנו באופן חופשי את כתובת כל האיברים כאילו מדובר ב־vector.

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

יציבות כתובות היא דרישה נפרדת

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

הקוד הבא מראה vector של unique_ptrים:

#include <cassert>
#include <memory>
#include <vector>

struct Job {
    int id;
};

int main() {
    std::vector<std::unique_ptr<Job>> jobs;
    jobs.push_back(std::make_unique<Job>(Job{7}));
    Job* observed = jobs[0].get();

    for (int i = 0; i < 100; ++i) {
        jobs.push_back(std::make_unique<Job>(Job{i}));
    }

    assert(observed->id == 7);
}

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

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

עץ או טבלת גיבוב

ה־map מחזיק מפתחות בסדר לפי comparator, ואילו unordered_map מארגן אותם לפי hash ו־equality. הבחירה משפיעה על סדר מעבר, על עלויות ועל תנאי התקינות.

ב־map ההשוואה צריכה לספק strict weak ordering. ב־unordered_map מפתחות שנחשבים שווים חייבים להתאים לחוזה הhash, כך שחיפוש לא יישלח למקום שאינו יכול להכיל את המפתח המבוקש.

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

גיבוב מחדש ופסילת איטרטורים

כאשר unordered_map מבצעת rehash, ה־iteratorים שלה נפסלים. ה־references וה־pointerים לאיברים קיימים נשמרים לפי החוזה הרלוונטי, כל עוד האיבר עצמו לא נמחק.

זהו הבדל משמעותי מ־vector שעוברת reallocation. אי אפשר לזכור כלל אחד שלפיו כל שינוי מכולה פוסל הכל או לא פוסל כלום. צריך לקרוא את הכלל של הפעולה המסוימת ושל סוג הalias שנשמר.

גם iterator של end יכול להיפסל אף שpointer לאיבר קיים נשאר תקף. לולאה ששומרת end לפני הוספות עשויה להיות שגויה בלי שהאיברים עצמם זזו.

השוואה הוגנת

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

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

הניסוי צריך לשמור על אותה משמעות של בעלות. השוואת vector של אובייקטים ל־map של pointerים ללא ספירת ההקצאות החיצוניות יכולה להציג תמונה מטעה של העלות האמיתית.

בדיקת כשל לפני מדידה

לפני שמודדים ביצועים, מפעילים תרחישים שמגדילים capacity, מוחקים איבר נצפה ומפעילים rehash. לכל alias מציינים איזו פעולה פוסלת אותו.

מכולה שנבחרה לפי benchmark אך מאפשרת use-after-free אינה פתרון מהיר יותר. קודם שומרים על חוזי החיים והגישה; אחר כך בודקים אם הייצוג מתאים לעומס ולתקציב המשאבים.