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

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

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

1. תזכורת: משימת ההשוואה

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

int main(int argc, char *argv[])
{    
    QCoreApplication a(argc, argv);

    QCryptographicHash hasher(QCryptographicHash::Md5);
    StringHash results;

    for ( size_t i=0; i < qPow(sz, len); i++ ) {
        QString next;

        for ( size_t d=0; d < len; d++ ) {
            next += ab[int(i / qPow(sz, d)) % sz];
        }
        if ( i % trace == 0 ) {
            qDebug() << int(i / trace) << " / " << int(total / trace);
        }

        hasher.addData(next.toLocal8Bit());
        QString md5 = QString(hasher.result().toHex());
        QString word = next;

        results[md5] = word;
        hasher.reset();
    }
    qDebug() << results["657f8b8da628ef83cf69101b6817150a"];

    return 0;
}

זמן ריצה על הנייד שלי:

real    0m8.019s
user    0m7.223s
sys    0m0.497s

 

2. מעבר לריצה מקבילית

הדרך הקלה ביותר למקבל משימות חישוביות היא להשתמש במבנים ואלגוריתמים ידועים, עדיף כאלה שמישהו אחר כבר מימש. במקרה של C++ הספריה Qt מגיעה עם מימוש מקבילי לפונקציה map. הגירסא המקבילית מחלקת את רשימה המקור למקטעים לפי מספר הליבות שיש במעבד ומריצה את פונקציית ההמרה על כל המקטעים במקביל (תהליכון נפרד לכל ליבה). כך אנו מקבלים ניצול אופטימלי של משאבי המערכת.

דרך אחת להפוך את הלולאה לפונקציית map היא לבנות רשימה של כל המספרים מ-0 עד total, ולהריץ map על רשימה זו. קוד הלולאה ייכתב בנפרד כפונקציה של האינדקס. 

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

כך ייראה הקוד לאחר המרה ל map והפעלה מקבילית:

#include <QCoreApplication>
#include <QDebug>
#include <QtCore>
#include <QtConcurrent>


typedef QPair<QString, QString> StringPair;
typedef QHash<QString,QString> StringHash;

static const char ab[] = "0123456789abcdefghijklmnopqrstuvwxyz";

size_t len = 4;
size_t sz = sizeof(ab) - 1;
size_t total = qPow(sz, len);
size_t trace = 100000;

char char_at(const char ab[], size_t i, size_t d, size_t sz)
{
    return ab[int(i / qPow(sz, d)) % sz];
}

void mergePairs(StringHash &acc, StringPair nextValue)
{
    acc[nextValue.first] = nextValue.second;
}

StringPair nextWord(size_t i)
{
    QString next;

    for ( size_t d=0; d < len; d++ ) {
        next += ab[int(i / qPow(sz, d)) % sz];
    }
    if ( i % trace == 0 ) {
        qDebug() << int(i / trace) << " / " << int(total / trace);
    }

    QCryptographicHash hasher(QCryptographicHash::Md5);
    hasher.addData(next.toLocal8Bit());
    QString md5 = QString(hasher.result().toHex());
    QString word = next;
    return StringPair(md5, word);

}

int main(int argc, char *argv[])
{    
    QCoreApplication a(argc, argv);
    QList<size_t> ind;

    for ( size_t i=0; i < qPow(sz, len); i++ )
    {
        ind << i;
    }

    StringHash results = QtConcurrent::blockingMappedReduced<StringHash>(ind, nextWord, mergePairs);


    qDebug() << results["657f8b8da628ef83cf69101b6817150a"];

    return 0;
}

למרבה ההפתעה, הרצה על הנייד שלי הביאה לשיפור זניח בלבד בזמן הריצה. זו התוצאה:

real    0m7.915s
user    0m12.940s
sys    0m1.016s

מה קרה כאן? מדוע לא קיבלנו את התוצאה במחצית הזמן?

3. איתור צוואר הבקבוק ושיפור הקוד

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

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

void mergePairs(StringHash &acc, StringPair nextValue)
{
    if ( nextValue.first == "657f8b8da628ef83cf69101b6817150a" )
    {
        qDebug() << "Found: " << nextValue.second;
    }
}

וזמן הריצה של התוכנית ירד באופן משמעותי וכעת עומד על:

real    0m3.076s
user    0m10.262s
sys    0m0.088s

 

4. פה חשדתי

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

real    0m4.886s
user    0m4.752s
sys    0m0.056s

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

קוראים חדי עין עשויים להבחין בגוזל זכרון נוסף בקוד שהוצג, הוא החישוב מראש של רשימת האינדקסים כולה. Qt מאפשרת שימוש באיטרטורים בפונקציה map במקום העברת מבנה הנתונים המלא ולכן אפשר לנסות לקבל שיפור ביצועים נוסף באמצעות כתיבה של Range Iterator — כלומר איטרטור שלא מחזיק את כל רשימת האינדקסים בזכרון אלא בכל פעם שמבקשים ערך מסוים מחשב אותו בזמן ריצה, בדומה ללולאת ה for שהיתה לנו בתוכנית הטורית. כתיבת איטרטור כזה בהחלט יכולה להיות רעיון טוב לפוסט אחר. בינתיים אספר רק ששיפור הביצועים שהתקבל אם בכלל משינוי כזה היה זניח. לסקרנים העליתי את קוד התוכנית לקישור:
https://gist.github.com/ynonp/9def66ea3d59ee063998

 

5. סיכום ומסקנות

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

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