הלכתי לאחרונה למפגש במיקרוסופט רעננה בנושא Parallel Programming in Visual Studio 2010. המרצה היה סשה גולדשטיין. אז קודם כל קצת מחמאות: למיקרוסופט על האירועים האלה שמאורגנים היטב, מהחניה ועד המשובים; לסשה גולדשטיין על הרצאה ברמה גבוהה, בשפה ברורה ועם הרבה סבלנות.

ועכשיו לעניינים הטכניים עצמם.

נעים להכיר – System.Threading.Tasks

נתחיל מהקדמונת: החל מגירסה 4.0 של הדוט נט פריימוורק, מיקרוסופט הכניסו פנימה פיצ'רים חדשים בתחום ה Multi-Threading. הפיצ'רים האלה מאפשרים פיתוח נוח יותר ל Multi-Threading, ולמעשה כדאי יותר לקרוא לזה מיקבול משימות, מתוך הנחת יסוד שמשימה ו Thread זה לא אותו הדבר, למרות שיש קשר הדוק. את הפיצ'רים והמחלקות למיניהם אפשר למצוא ב namespace שנקרא System.Threading.Tasks. הרעיון הכללי של הפיצ'רים האלה הוא שהמפתחים לא יטריחו את עצמם יותר מדי סביב הפרטים הקטנים של המיקבול עצמו, ויוכלו למקבל משימות בקלות יחסית.

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

namespace Bronze.Lib
{
  public class SimpleAggregator 
  {
    public int Sum(int[,] matrix)
    {
      var result = 0;
      for (var i = 0; i < matrix.GetLength(0); i++)
        for (var j = 0; j < matrix.GetLength(1); j++)
          result += matrix[i, j];
      return result;
    }
  }
}

פשוט וקל.

מקבילית המוחות

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

עכשיו, יש שתי גישות עיקריות לביצוע של הפתרון הזה:

מגדירים משתנה מספרי משותף, נניח sum, ומאתחלים אותו ל 0 (אפס). כל משימה תסכום את השורה שלה במטריצה, ותעדכן את ה sum הנ"ל לפי הסכום של השורה. התוצאה הסופית, אחרי שכל המשימות הסתיימו, תהיה ב sum.

הנה קצת פסודו-קוד לעניין זה:

1. common_sum = 0
2. Parallel: for each row in matrix:
  2.1 temp = sum(row)
  2.2 append temp to common_sum

הנקודה הכואבת יחסית בקוד הזה היא סעיף 2.2, שבו כל משימה מעדכנת את המשאב המשותף. מכיוון שזו סביבה של ריבוי משימות וככל הנראה גם ריבוי threads, הרי שיש לנו משאב משותף שיכול להתעדכן ע"י מספר threads במקביל. מקור לא אכזב ל data corruption. כדי להתגבר על זה, צריך לכתוב קוד של פעולת העדכון בצורה שתהיה thread-safe. ניתן להשיג את זה ע"י lock, ובמקרה הספציפי הזה, נוכל להשתמש גם ב Interlocked שיכול בפעולה אטומית להוסיף ערך למשתנה int.

בואו נראה את הקוד שמבצע את הגישה הראשונה, עם Interlocked:

using System.Threading;
using System.Threading.Tasks;

namespace Bronze.Lib
{
  public class ParallelWithInterlock
  {
    public int Sum(int[,] matrix)
    {
      var outerUpperBound = matrix.GetLength(0);
      var commonSum = 0;

      var innerUpperBound = matrix.GetLength(1);
      Parallel.For(0, outerUpperBound, i =>
      {
        var localSum = 0;
        for (var j = 0; j < innerUpperBound; j++)
          localSum += matrix[i, j];
        Interlocked.Add(ref commonSum, localSum);
      });

      return commonSum;
    }
  }
}

במקום להגדיר משתנה משותף ולהגן עליו באמצעי סנכרון שונים, נוכל להגדיר מערך שבו לכל משימה מוקצה תא משלה. הגישה לאיברי המערך היא thread-safe לפי הגדרה (אגב, יצא לי לחפור על זה פעם ב stackoverflow), ולכן כל משימה יכולה לעדכן את התא "שלה" במערך הנ"ל, מבלי לחשוש מ data corruption. בסוף התהליך סוכמים את כל איברי המערך, ובא לציון גואל. שימו לב, עיקר התחכום כאן הוא שהפקודה Parallel.For יוצרת משתנה אינדקס, ושולחת אותו כפרמטר ל delegate של המשימה המבצעת, וזה בדיוק האינדקס של התא ה"פרטי" של המשימה במערך המשותף. הנה הקוד שממחיש את זה:

using System.Linq;
using System.Threading.Tasks;

namespace Bronze.Lib
{
  public class ParallelAggregator
  {
    public int Sum(int[,] matrix)
    {
      var outerUpperBound = matrix.GetLength(0);
      var partialSums = new int[outerUpperBound];

      var innerUpperBound = matrix.GetLength(1);
      Parallel.For(0, outerUpperBound, i =>
      {
        partialSums[i] = 0;
        for (var j = 0; j < innerUpperBound; j++)
          partialSums[i] += matrix[i, j];
      });

      var result = partialSums.Sum();
      return result;
    }
  }
}

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

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

using System.Linq;
using System.Threading.Tasks;

namespace Bronze.Lib
{
  public class ParallelAggregatorWithLocalSum
  {
    public int Sum(int[,] matrix)
    {
      var outerUpperBound = matrix.GetLength(0);
      var partialSums = new int[outerUpperBound];

      var innerUpperBound = matrix.GetLength(1);
      Parallel.For(0, outerUpperBound, i =>
      {
        var localSum = 0;
        for (var j = 0; j < innerUpperBound; j++)
          localSum += matrix[i, j];
        partialSums[i] = localSum;
      });

      var result = partialSums.Sum();
      return result;
    }
  }
}

כפי שניתן לראות, ההצהרה על המשתנה הלוקאלי יכולה להיראות מיותרת למי שלא מכיר את האישו הזה.

של מי ארוך יותר?

כתבתי תוכנית קטנה שמשווה את הביצועים, ויש יתרון מובהק בביצועים של ParallelAggregatorWithLocalSum (בוצע ב Release על הלפטופ שלי). היתרון אצלי במחשב הוא של 40%, כלומר המחלקה ParallelAggregatorWithLocalSum רצה ב 40% בממוצע מהר יותר מהמחלקה ParallelAggregator. לא יאמן. באותה תוכנית ניתן גם לראות שהביצועים של ParallelAggregatorWithLocalSum ושל ParallelWithInterlock ממש קרובים אחד לשני (לפעמים האחד מהיר יותר באחוז או שניים ולפעמים השני). את הקוד המלא אפשר להוריד מכאן. הנה גרף שממחיש את התוצאות של סכימת מטריצה עם 99 שורות ו 31841 עמודות:

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

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

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

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

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

ומסקנה נוספת: כל מי שחשב שדוט נט זו סביבה שבה אין צורך לדעת את ה internals – צודק רק ברוב המקרים. בחלק קטן (אבל משמעותי) מהמקרים כדאי מאוד לדעת מה קורה under-the-hood, רק כדי להפיק יותר מהסביבה הזו. יש עוד הרבה דוגמאות שממחישות כמה טוב לדעת את ה internals, והפוסט הזה מציג רק דוגמה אחת, כמובן. עם זאת, התחושה האישית שלי היא שבמיקרוסופט ניסו לכוון לשפה שהיא יותר high-level ממה שהתקבל בסופו של דבר. במילים אחרות, הציפיה של המפתחים שרק מגיעים לדוט נט היא שהם לא יצטרכו להתעסק עם tweakים כדי לכתוב קוד יעיל, ובסוף הם נאלצים להיכנס לפינות שהם לא חלמו עליהם, ושמרחיקות אותם מכתיבת קוד "נטו".
במילים פשוטות ובוטות יותר: פייר, התאכזבתי 🙂

כל הקוד בפוסט הזה ניתן להורדה מכאן.

מיקבול נעים!