ארכיון

רשומות עם התג ‘Benchmark’

To(Decimal)String

28 דצמבר, 2010 9 תגובות

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

בקיצור: "קליין! מַמֵּש ToString של int חיובי! יש לך 2 דקות, זוז!!"

פתרתי, אלא מה. אומרים לי, אני עושה.

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

אז בואו נראה איך אפשר להפוך קוד "כללי" לקוד תלוי משימה ספציפית.

ToDecimalString – גירסה ראשונה

בואו ניזכר רגע בדרישות: נתון int שהוא חיובי, ועלינו להמיר אותו ל string מבלי להיעזר במתודת ToString שמגיעה באופן מובנה עם הפריימוורק.

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

public class V1
{
  public static string ToDecimalString(int value)
  {
    if (value == 0)
      return "0";
    var list = new List<char>(1);
    while (value != 0)
    {
      var digitAsInt = value%10;
      var digitAsChar = (char) ('0' + digitAsInt);
      list.Add(digitAsChar);
      value /= 10;
    }
    list.Reverse();
     
    return new string(list.ToArray());
  }
}

אוקיי, עכשיו בואו נבדוק מה הולך כאן: מכיוון שאנחנו לא יודעים מראש מה אורכו של המספר, אנחנו משתמשים ב List של תוים, שמאפשר לנו בכל פעם מחדש להוסיף char למערך פנימי משלו. בכל איטרציה אנחנו בודקים מהי השארית של חלוקה ב 10 (זו פעולת המודולו), ואח"כ מחלקים את המספר ב 10 (חלוקת int ב int היא ללא שארית). ממשיכים כך עד שמה שנשאר מכל החלוקות האלו הוא אפס (0).

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

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

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

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

קצת מספרים: ה ToString הסטנדרטי לוקח בממוצע 7 טיקים (Ticks) והמימוש שיש כאן עכשיו לוקח 12 (!) טיקים. זה הפרש של עשרות אחוזים, כך שיש לנו עוד עבודה לעשות.

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

ToDecimalString – גירסה שניה

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

כאן באה לעזרתנו האלגברה. זוכרים את פונקציית ה Log? זאת של המתמטיקה, לא של log4net! אה, כן, Log, ויש גם ln ויש איזה e שקיים שם. טוב, בלי שאני אסחף כאן, בדוט נט יש את הפונקציה Log10 מובנית בפריימוורק. התוצאה שלה היא מספר לא שלם (double), ואם נעגל את המספר שיצא כלפי מעלה, נקבל את מספר הספרות שהמספר הנתון יצטרך בייצוג העשרוני שלו.

כלומר, הביטוי הבא:

var digitCount = (int)Math.Ceiling(Math.Log10(value));

יתן לנו את מספר הספרות הנדרשות.

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

public static string ToDecimalString(int value)
{
  if (value == 0)
    return "0";
  var log10 = Math.Log10(value);
  var digitCount = (int) Math.Ceiling(log10);
  //fix if needed for the values of 10^n (10, 100, etc.)
  if (digitCount == (int)log10)
    ++digitCount;
  var chars = new char[digitCount];
  for (var k = chars.Length 1; k >= 0 ; k)
  {
    var mod = value%10;
    chars[k] = (char) ('0' + mod);
    value /= 10;
  }
  return new string(chars);
}

[לצערי הביטוי "מינוס מינוס" מומר אוטומטית ב WordPress ל "–"]
שימו לב שכבר תוך כדי הלולאה, סדר הכתיבה למערך התוים הוא הפוך, כדי שלא נצטרך להפוך אותו אח"כ.

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

ToDecimalString – גירסה שלישית

אני מסתכל על הקוד, והקוד מסתכל עלי.

אני שוב מסתכל על הקוד, ונראה לי שאני עולה על משהו.

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

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

0-9

10-99

100-999

וכו'.

למעשה, נוכל לבנות מערך עם הערכים הבאים: 1, 10, 100 וכו' (המערך יהיה ממויין). כדי לדעת כמה ספרות יש במספר הנתון, נחפש אותו במערך בחיפוש בינארי. יש בדוט נט פונקציה מובנית לחיפוש בינארי, שלא סתם אומרת "מצאתי" או "לא מצאתי". בגדול, אפשר לדעת מהו האינדקס של הערך הקרוב ביותר למה שאנחנו מחפשים, גם אם לא נמצא. אני לא נכנס כאן לפרטים של המתודה Array.BinarySearch, מי שרוצה שיבדוק ב MSDN. אבל הנה הקוד:

private static int[] powersOf10 = new int[]
                                        {
                                            1, 10, 100, 1000, 10000, 100000, 1000000,
                                            10000000, 100000000, 1000000000
                                        };
public static string ToDecimalString(int value)
{
    if (value == 0)
        return "0";
    var index = Array.BinarySearch(powersOf10, value);
    if (index < 0)
        index = ~index; // not found, get closest index
    else
        ++index;

    var digitCount = index;
    var chars = new char[digitCount];
    for (var k = chars.Length 1; k >= 0; k)
    {
        var mod = value % 10;
        chars[k] = (char) ('0' + mod);
        value /= 10;
    }
    return new string(chars);
}

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

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

אבל! אולי, במקום לחלק את הטווח לחזקות של 10, נתחכם עוד יותר.

ToDecimalString – גירסה רביעית

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

איך?

נוכל לדעת מהי הסיבית שהיא ה MSB, שזה קיצור של Most Significant Bit. זוהי הסיבית שמבטאת פחות או יותר את המשפט הבא:

אם נתון לנו מספר x, כמה ספרות נדרשות לייצוג בינארי של x?

למשל, אם x=123, אז הייצוג הבינארי שלו הוא 1111011, ונדרשנו ל 7 ספרות בינאריות. כלומר MSB של 123 זה 7.

באותו אופן, אם x = 9 אז ה MSB שלו הוא 4, כי 9 בייצוג בינארי הוא 1001.

ולמה אני כותב את כל זה? כי למצוא MSB של מספר זה תהליך יחסית מהיר.

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

כלומר ה"סוד" של הגירסה הזו הוא מיפוי (מראש) של כל הסיביות לטווח העשרוני שלהם.

אני לא נכנס כאן לתיאור מלא של הקוד, תצטרכו לסמוך עלי שזה עובד:

public class V4
{
  private static readonly int[] powersOf10 = new int[]
                      {
                        1, 10, 100, 1000, 10000, 100000, 1000000,
                        10000000, 100000000, 1000000000
                      };

  private static readonly int[] powersOf2 = new int[]
                      {
                        1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,
                        2048, 4096, 8192, 16384, 32768, 65536, 131072,
                        262144, 524288, 1048576, 2097152, 4194304,
                        8388608, 16777216, 33554432, 67108864,
                        134217728, 268435456, 536870912, 1073741824
                      };

  private static int[] decimalDigitsByMsb;

  static V4()
  {
    decimalDigitsByMsb = new int[powersOf2.Length];
    for (int k = 1; k < powersOf2.Length; k++)
    {
      decimalDigitsByMsb[k] = powersOf2[k 1].ToString().Length;
    }
  }

  public static string ToDecimalString(int value)
  {
    var mostSignificantBit = 0;
    for (int k = powersOf2.Length 1; k >= 0; k)
    {
      var bit = (value & powersOf2[k]) != 0;
      if (bit)
      {
        mostSignificantBit = k + 1;
        break;
      }
    }
    if (mostSignificantBit == 0)
      return "0";

    int index;
    if (mostSignificantBit >= decimalDigitsByMsb.Length)
      index = decimalDigitsByMsb[decimalDigitsByMsb.Length 1];
    else
      index = decimalDigitsByMsb[mostSignificantBit];
    if (value >= powersOf10[index])
      index++;
    var digitCount = index;
    var chars = new char[digitCount];
    for (var k = chars.Length 1; k >= 0; k)
    {
      var mod = value%10;
      chars[k] = (char) ('0' + mod);
      value /= 10;
    }
    return new string(chars);
  }
}

והביצועים?

סוף-סוף, המדידות מראות באופן מובהק יתרון קל לגירסה הרביעית: הגענו לממוצע של 6 טיקים! שיפור של 14% בממוצע!

זה לא נגמר

יש עוד כמה שיפורים שאפשר להכניס לכל גירסה:

  • תנאי הלולאה בלולאות for לא חייב להיות "גדול מ-", מספיק לראות אם "שונה מ-".
    מכאן והלאה הקוד יקבל את השידרוג הזה.
  • במקום לחשב בכל פעם מחדש את הביטוי '0' + mod, נוכל להשתמש (שוב) בטבלת מיפוי.

כלומר נוכל לכתוב פונקציה סטאטית באופן הבא:

private static char[] digits = new[]
  {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };

public static char ToChar(int digit)
{
    return digits[digit];
}

אלא שזה יכול קצת לקלקל לנו אם נשאיר את הפונקציה הזו כמו שהיא. למה?

כי עצם הקריאה והביצוע של פונקציה נוספת על ה stack יוצר overhead די רציני. בשפות קרובות יותר למעבד, כמו C, אפשר להנחות את הקומפיילר שיכניס את הפונקציה כמו שהיא לתוך הקוד שקורא לה. זה נקרא inline. זה נותן יתרון בביצועים, לצד תחזוקתיות גבוהה. מצד שני, זה יכול להגדיל קצת את גודל ה executable כולו. בכל מקרה, ב C# אין לנו את הלוקסוס הזה (וטוב שכך. רק למה השאירו לנו את ה volatile?). אז נצטרך לעקוף את זה ע"י הטמעת הקוד של הפונקציה ב class באופן ישיר.
גם את השידרוג הזה נוסיף לגירסאות השונות של המימוש שלנו.

נו, ומה עוד?

ToDecimalString – גירסה חמישית

כן, תמיד יש עוד. והפעם – פעולת החילוק.

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

ואנחנו צריכים למשימה שלנו רק חילוק ב 10.

אז אולי יש איזה אלגוריתם של חילוק שלמים ב 10 בלבד?

חיפוש קצר העלה את הקוד הבא (מתוך stackoverflow, והנה לינק למקור):

public static int div10(int n)
{
    int q, r;
    q = (n >> 1) + (n >> 2);
    q = q + (q >> 4);
    q = q + (q >> 8);
    q = q + (q >> 16);
    q = q >> 3;
    r = n q * 10;
    return q + ((r + 6) >> 4);
}

בדקתי את הקוד הזה על כל מרחב ה int32 החיובי. עובד.

ועכשיו נכניס אותו פנימה, כ inline כמובן:

public static string ToDecimalString(int value)
{
  // …
  // old code remains the same
  // …
  var chars = new char[digitCount];
  for (var k = chars.Length 1; k != (1); k)
  {
    // inline the div10 operation
    int q, r;
    q = (value >> 1) + (value >> 2);
    q = q + (q >> 4);
    q = q + (q >> 8);
    q = q + (q >> 16);
    q = q >> 3;
    r = value q * 10;
    var valueDiv10 = q + ((r + 6) >> 4);
    var mod = value (valueDiv10 * 10);
    chars[k] = digits[mod];
    value = valueDiv10;
  }
  return new string(chars);
}

והצלחנו להרוויח עוד קצת: קבלנו ממוצע של 5 טיקים! שיפור של 28% בממוצע!

התוצאות עד כה

הגענו בינתיים לחמש גירסאות שונות, והנה הגרף המתבקש:

העמודה משמאל – מייצגת את ה ToString הסטנדרטי. העמודות שמימינה מייצגות את המימושים שמוצגים כאן.

יש עוד! כנסו כנסו!

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

  • הקוד כאן בונה את הטקסט המתקבל ספרה אחרי ספרה, מה שגורם גם להעתקות זכרון של תו אחד בכל פעם. כלומר הזכרון משוכפל בכל איטרציה בגודל של תו אחד. אפשר, למשל, לבצע העתקת זכרון של יותר מתו אחד בכל פעם. נניח בזוגות של תוים. או ברביעיות של תוים. סביר להניח שזה ישפר במשהו את הביצועים, כי אז תתבצע העתקה של מספר תוים בבת אחת. סביר להניח שזה גם יסבך קצת את הקוד. וגם יגדיל את צריכת הזכרון הסטאטי.
  • ברמת המתמטיקה, אפשר לעשות קצת אנליזה נומרית, ולמצוא פולינום "קל" יותר מהמימוש של Log10, שיהיה קירוב מספיק טוב לדרישות שלנו מ Log10, אבל יהיה יותר קל לביצוע.
  • אפשר להקצות מראש מערך באורך 10 תוים, שזה המקסימום שיכול להיות כאן (כי int.MaxValue זה 2147483647, וזה לוקח 10 ספרות. לא יכול להיות יותר מזה). וכך "ניצלנו" מכל העניין של לדעת מראש כמה ספרות יש למספר הנתון. מצד שני, נצטרך להפוך את הסדר של התוים במערך, כך שנוצרה לנו עוד קצת עבודה.

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

רגע, מה לגבי שלמים שליליים?

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

סיכום

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

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

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

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

קידוד נעים! כמובן, כל הקוד זמין להורדה מכאן.

קטגוריות:תכנות תגיות:, , , ,

Parallels and Internals Shminternals

25 אוקטובר, 2010 6 תגובות

הלכתי לאחרונה למפגש במיקרוסופט רעננה בנושא 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;
    }
  }
}

פשוט וקל.

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

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

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

1

מגדירים משתנה מספרי משותף, נניח 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;
    }
  }
}

2

במקום להגדיר משתנה משותף ולהגן עליו באמצעי סנכרון שונים, נוכל להגדיר מערך שבו לכל משימה מוקצה תא משלה. הגישה לאיברי המערך היא 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ים כדי לכתוב קוד יעיל, ובסוף הם נאלצים להיכנס לפינות שהם לא חלמו עליהם, ושמרחיקות אותם מכתיבת קוד "נטו".
במילים פשוטות ובוטות יותר: פייר, התאכזבתי 🙂

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

מיקבול נעים!

קטגוריות:תכנות תגיות:, ,
Quantcast