פריסת נתונים וחישוב וקטורי

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

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

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

fn scalar(bytes: &[u8]) -> u64 {
    bytes.iter().fold(0u64, |sum, &x| sum.wrapping_add(u64::from(x)))
}

הקוד הבא מצטרף לאותו קובץ ומספק מסלול AVX2 עבור x86-64. כל קריאה של 32 בייטים מתבצעת רק כאשר הטווח קיים, והשארית מטופלת במימוש הייחוס.

#[cfg(target_arch = "x86_64")]
#[target_feature(enable = "avx2")]
unsafe fn vector(bytes: &[u8]) -> u64 {
    use std::arch::x86_64::*;
    let mut position = 0;
    let mut accumulator = _mm256_setzero_si256();
    let zero = _mm256_setzero_si256();
    while bytes.len() - position >= 32 {
        let block = unsafe {
            _mm256_loadu_si256(bytes.as_ptr().add(position).cast::<__m256i>())
        };
        let sums = _mm256_sad_epu8(block, zero);
        accumulator = _mm256_add_epi64(accumulator, sums);
        position += 32;
    }
    let mut lanes = [0u64; 4];
    unsafe { _mm256_storeu_si256(lanes.as_mut_ptr().cast::<__m256i>(), accumulator); }
    lanes.into_iter().fold(scalar(&bytes[position..]), u64::wrapping_add)
}
fn sum(bytes: &[u8]) -> u64 {
    #[cfg(target_arch = "x86_64")]
    if std::is_x86_feature_detected!("avx2") {
        return unsafe { vector(bytes) };
    }
    scalar(bytes)
}
fn main() {
    for length in [0, 1, 31, 32, 33, 300, 4097] {
        let data: Vec<u8> = (0..length).map(|i| (i * 17) as u8).collect();
        assert_eq!(sum(&data), scalar(&data));
        if !data.is_empty() { assert_eq!(sum(&data[1..]), scalar(&data[1..])); }
    }
}

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

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

הקריאה ל־vector מוגנת בבדיקת יכולת בזמן ריצה. התכונה target_feature מתירה למהדר להפיק הוראות מתאימות בגוף הפונקציה, אבל אינה בודקת שהמעבד שעליו נרוץ תומך בהן. בנייה עם target-cpu=native יכולה ליצור בינארי שמתאים למחשב הבנייה ואינו מתאים לשרת אחר, ולכן צריך לקשור את הדגל למדיניות הפצה מפורשת.

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

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

הרחבות SIMD ניידות וכלי אופטימיזציה משתנים עם גרסאות המהדר. הקורס משתמש כאן ב־intrinsics יציבים של הארכיטקטורה ובמסלול fallback, ואינו מניח שממשק ניסיוני מסוים קיים בכל stable. בדקו את תיעוד std::arch ואת דרישות כל intrinsic לפני שימוש.

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