תכנון תחת מגבלת זיכרון

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

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

משאב שמסרב לפני חריגה

הקוד הבא הוא תוכנית מלאה ב־C++20. המשאב מיועד לשימוש מתהליכון אחד, והוא חייב לחיות יותר מכל המכולות שמשתמשות בו:

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <memory_resource>
#include <new>
#include <vector>

class BudgetResource final : public std::pmr::memory_resource {
    std::size_t limit_;
    std::size_t live_ = 0;
    std::size_t peak_ = 0;
    std::pmr::memory_resource* upstream_ =
        std::pmr::new_delete_resource();

    void* do_allocate(std::size_t bytes,
                      std::size_t alignment) override {
        if (bytes > limit_ - live_) throw std::bad_alloc{};
        void* result = upstream_->allocate(bytes, alignment);
        live_ += bytes;
        peak_ = std::max(peak_, live_);
        return result;
    }

    void do_deallocate(void* p, std::size_t bytes,
                       std::size_t alignment) override {
        upstream_->deallocate(p, bytes, alignment);
        live_ -= bytes;
    }

    bool do_is_equal(
        const std::pmr::memory_resource& other) const noexcept override {
        return this == &other;
    }

public:
    explicit BudgetResource(std::size_t limit) : limit_(limit) {}
    std::size_t live() const noexcept { return live_; }
    std::size_t peak() const noexcept { return peak_; }
};

int main() {
    BudgetResource budget(4096);
    try {
        std::pmr::vector<std::byte> bytes(&budget);
        bytes.resize(1024, std::byte{7});
        std::cout << "before: " << bytes.size()
                  << " live=" << budget.live() << '\n';
        try {
            bytes.reserve(4096);
        } catch (const std::bad_alloc&) {
            std::cout << "growth rejected\n";
        }
        std::cout << "after: " << bytes.size()
                  << " first=" << std::to_integer<int>(bytes.front())
                  << " live=" << budget.live() << '\n';
    } catch (const std::bad_alloc&) {
        std::cerr << "initial allocation failed\n";
        return 1;
    }
    std::cout << "released=" << budget.live()
              << " peak=" << budget.peak() << '\n';
}

הבדיקה משתמשת בחיסור אחרי שמירת invariant שלפיו live_ <= limit_. כתיבה של live_ + bytes > limit_ בלי בדיקת גלישה הייתה יכולה לקבל בקשה גדולה מאוד בטעות. העדכון של המונה נעשה רק אחרי שהמקצה העליון הצליח, ולכן כשל ממנו אינו מייצר חיוב פיקטיבי.

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

משמעות המספר שאנחנו מגבילים

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

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

תגובה לכישלון היא חלק מהממשק

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

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

תקציב לפי שלבים

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

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

קריאה להעמקה

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