מדידה ושיפור ביצועים

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

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

בוחרים יחידת עבודה

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

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

ניסוי שאפשר להריץ

הקובץ layout_bench.cpp מיועד לMSVC על x64. הוא מבצע warmup, מחליף את סדר הרצת הגרסאות ושומר כמה דגימות. הכמות מוגבלת כדי שהניסוי לא יהפוך בטעות להקצאה בלתי מוגבלת.

#include <windows.h>
#include <algorithm>
#include <charconv>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <stdexcept>
#include <vector>

struct Particle {
    double x, y, z, vx, vy, vz;
    std::uint64_t id, flags;
};

__declspec(noinline) double sum_aos(const std::vector<Particle>& data) {
    double result = 0;
    for (const auto& item : data) result += item.x + item.y;
    return result;
}

__declspec(noinline) double sum_soa(const std::vector<double>& x,
                                   const std::vector<double>& y) {
    double result = 0;
    for (std::size_t i = 0; i < x.size(); ++i) result += x[i] + y[i];
    return result;
}

volatile double observed_result = 0;

template<class Function>
double measure(Function operation, double expected, double frequency) {
    LARGE_INTEGER start{}, finish{};
    QueryPerformanceCounter(&start);
    const double result = operation();
    QueryPerformanceCounter(&finish);
    observed_result = result;
    if (result != expected) throw std::runtime_error("different computation");
    return 1000.0 * static_cast<double>(finish.QuadPart - start.QuadPart) / frequency;
}

double percentile(std::vector<double> values, double fraction) {
    if (values.empty() || fraction <= 0 || fraction > 1)
        throw std::invalid_argument("invalid percentile");
    std::sort(values.begin(), values.end());
    const auto rank = static_cast<std::size_t>(std::ceil(fraction * values.size()));
    return values[rank - 1];
}

int main(int argc, char** argv) {
    try {
        std::size_t count = 250000;
        if (argc > 2) throw std::invalid_argument("usage: layout_bench [count]");
        if (argc == 2) {
            const char* end = argv[1] + std::strlen(argv[1]);
            auto parsed = std::from_chars(argv[1], end, count);
            if (parsed.ec != std::errc{} || parsed.ptr != end)
                throw std::invalid_argument("invalid count");
        }
        if (count == 0 || count > 4000000) throw std::invalid_argument("count out of range");
        std::vector<Particle> aos(count);
        std::vector<double> x(count), y(count);
        std::uint64_t seed = 1234567;
        auto next = [&] {
            seed = seed * 6364136223846793005ULL + 1;
            return static_cast<double>(seed & 65535) / 1024.0;
        };
        for (std::size_t i = 0; i < count; ++i) {
            x[i] = next(); y[i] = next();
            aos[i] = {x[i], y[i], 0, 0, 0, 0, i, 0};
        }
        LARGE_INTEGER frequency{};
        if (!QueryPerformanceFrequency(&frequency)) return 2;
        const double expected = sum_aos(aos);
        const double hz = static_cast<double>(frequency.QuadPart);
        auto first = [&] { return sum_aos(aos); };
        auto second = [&] { return sum_soa(x, y); };
        for (int i = 0; i < 3; ++i) {
            measure(first, expected, hz);
            measure(second, expected, hz);
        }
        std::vector<double> aos_times, soa_times;
        aos_times.reserve(31); soa_times.reserve(31);
        for (int run = 0; run < 31; ++run) {
            if (run % 2 == 0) {
                aos_times.push_back(measure(first, expected, hz));
                soa_times.push_back(measure(second, expected, hz));
            } else {
                soa_times.push_back(measure(second, expected, hz));
                aos_times.push_back(measure(first, expected, hz));
            }
        }
        std::printf("items=%zu particle_bytes=%zu checksum=%.3f\n",
                    count, sizeof(Particle), expected);
        std::printf("AoS median_ms=%.6f p95_ms=%.6f\n",
                    percentile(aos_times, .5), percentile(aos_times, .95));
        std::printf("SoA median_ms=%.6f p95_ms=%.6f\n",
                    percentile(soa_times, .5), percentile(soa_times, .95));
    } catch (const std::exception& error) {
        std::fprintf(stderr, "%s\n", error.what());
        return 1;
    }
}

cl /std:c++20 /EHsc /O2 /Zi /fp:precise /W4 layout_bench.cpp /link /DEBUG:FULL
layout_bench.exe 250000
layout_bench.exe 1000000

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

הקריאה לQueryPerformanceCounter מחזירה ticks, והfrequency מאפשרת להמיר אותם למשך. לא נשתמש בשעון קיר לצורך המדידה. החוזה מופיע בתיעוד מונה הביצועים.

המספרים לא מספרים הכול

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

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

הwarmup משנה את מצב הcache. במוצר עם סריקה חד פעמית אחרי טעינה, גם cold behavior חשוב. במוצר עם reuse תכוף, warm behavior יכול להיות רלוונטי יותר. לא נערבב בין השניים ונבחר רק את הגרף שמחמיא לגרסה שלנו.

מה cache רואה

במערך האובייקטים השדות שאינם נקראים עדיין תופסים מקום בין זוגות x וy. המעבד מביא cache lines, לא "שדות של C++". במערכים הנפרדים הקריאה רציפה וצפופה יותר עבור העבודה הזאת.

אם השלב הבא מעדכן את כל שדות האובייקט יחד, המבנה הראשון יכול להיות נוח ואף יעיל יותר. אם כמה threadים כותבים לשדות סמוכים, נחקור גם false sharing. לכן בוחרים layout לפי דפוסי גישה וגבולות בעלות, ולא לפי כלל שלפיו SoA תמיד מנצח.

וקטוריזציה אחרי בדיקת החוזה

נבקש מהקומפיילר דוח באמצעות /Qvec-report:2, ונבדוק גם disassembly. דוח על לולאה שלא עברה vectorization יכול להצביע על aliasing, תלות בין איטרציות או חוזה floating point שמונע שינוי סדר. לא נוסיף הבטחת no-alias אם היא אינה נכונה רק כדי שהדוח יהיה ירוק.

שימוש בSIMD מפורש דורש טיפול באיברים שנותרו בסוף, בalignment ובתמיכת ISA. בנייה של כל הבינארי עם /arch:AVX2 משנה את דרישת המכונה; היא אינה מספקת fallback למעבד אחר. עבור dispatch בזמן ריצה נפריד את המימושים ונבדוק גם תמיכת המעבד וגם את מצב הOS שנדרש לשמירת האוגרים. הפרטים של דוח הvectorizer הם כלי לאבחון, לא הבטחת שיפור.

מלמדים את הקומפיילר איזה מסלול נפוץ

בתהליך PGO בונים גרסה עם instrumentation, מריצים workload מייצג ומשתמשים בprofile כדי ליצור build מאופטם. בMSVC התהליך כולל /GL, קישור עם /LTCG /GENPROFILE, הרצת התרחישים ואז קישור עם /LTCG /USEPROFILE על התוצרים המתאימים.

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

חוזרים למשתמש

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

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