ניסוי ביצועים ומדדי מערכת

מספר מהיר בלי שאלה הוא תוצאה חלשה

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

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

השוואת שתי מפות לאותו חוזה חיפוש

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

use std::collections::{BTreeMap, HashMap};
use std::hint::black_box;
use std::time::{Duration, Instant};

fn hash_lookup(map: &HashMap<u64, u64>, queries: &[u64]) -> u64 {
    queries.iter().fold(0_u64, |sum, key|
        sum.wrapping_add(*map.get(black_box(key)).unwrap()))
}
fn tree_lookup(map: &BTreeMap<u64, u64>, queries: &[u64]) -> u64 {
    queries.iter().fold(0_u64, |sum, key|
        sum.wrapping_add(*map.get(black_box(key)).unwrap()))
}
fn measure(mut work: impl FnMut() -> u64) -> (Duration, u64) {
    let begin = Instant::now();
    let value = black_box(work());
    (begin.elapsed(), value)
}
fn report(name: &str, mut samples: Vec<Duration>, queries: usize) {
    samples.sort_unstable();
    let median = samples[samples.len() / 2];
    println!("{name}: min={:?} median={median:?} max={:?} lookups_per_sec={:.0}",
        samples[0], samples[samples.len() - 1], queries as f64 / median.as_secs_f64());
}
fn main() {
    let size: u64 = std::env::args().nth(1).unwrap_or_else(|| "16384".into())
        .parse().expect("positive map size");
    assert!((1..=1_000_000).contains(&size));
    let hash: HashMap<_, _> = (0..size).map(|key| (key, key ^ 0x55)).collect();
    let tree: BTreeMap<_, _> = (0..size).map(|key| (key, key ^ 0x55)).collect();
    let mut state = 1234567_u64;
    let queries: Vec<_> = (0..1_000_000).map(|_| {
        state = state.wrapping_mul(6364136223846793005).wrapping_add(1);
        state % size
    }).collect();
    assert_eq!(hash_lookup(&hash, &queries), tree_lookup(&tree, &queries));
    let mut hash_samples = Vec::new();
    let mut tree_samples = Vec::new();
    for round in 0..9 {
        let (hash_result, tree_result) = if round % 2 == 0 {
            (measure(|| hash_lookup(&hash, &queries)),
             measure(|| tree_lookup(&tree, &queries)))
        } else {
            let tree_result = measure(|| tree_lookup(&tree, &queries));
            let hash_result = measure(|| hash_lookup(&hash, &queries));
            (hash_result, tree_result)
        };
        assert_eq!(hash_result.1, tree_result.1);
        println!("round={round} hash_ns={} tree_ns={}",
            hash_result.0.as_nanos(), tree_result.0.as_nanos());
        hash_samples.push(hash_result.0);
        tree_samples.push(tree_result.0);
    }
    report("hash", hash_samples, queries.len());
    report("tree", tree_samples, queries.len());
}

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

חימום והטיית סדר

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

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

טווחי קלט ונכונות

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

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

אי־ודאות אינה טעות שצריך להסתיר

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

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

קצב מול זנב זמן תגובה

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

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

הוגנות ועלות משאב

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

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

מסקנה שמוגבלת לראיות

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

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