במרץ 2016 מתכנת בשם Azer Koçulu (לא בטוח שאני יודע לתרגם את השם הזה לעברית) שבר את האינטרנט. הוא מחק מ npm כמה מודולים שפירסם בפרשה שהביאה בפעם הראשונה את מנהלי npm להחזיר מודול שמשתמש מחק. המודול במרכז הפרשה נקרא left-pad ומה שמיוחד בו הוא שאינספור חבילות npm השתמשו בו בתור דרישת קדם. ברגע שמודול זה ירד, אי אפשר היה יותר להתקין אף חבילה שתלויה בו וכך מאות אלפי מתכנתים ברחבי העולם לא הצליחו להפעיל npm install.

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

1. הגירסה שהוסרה

אנחנו עובדים עם הריפו https://github.com/left-pad/left-pad וכמו שתשימו לב אם תיכנסו למאגר המודול הוא Deprecated מה שאומר שלא מומלץ להשתמש בו יותר. הוא הוחלף על ידי הפונקציה המובנית String​.prototype​.pad​Start כחלק מ ES 2017, כלומר קצת יותר משנה אחרי הפרשה. טיוטות ההצעה הסתובבו בשטח עוד מ 2015 כך שלא נראה שיש קשר בין הדברים.

דפדוף בהיסטוריית הגיט מביא אותנו לקומיט 76979f0a50877c50afd817923acf6f224bba3d36 בו Azer החליט להוריד את המודול מ npm, ולכן זה יהיה הקומיט בו ארצה להתחיל את הקריאה שלי. באותו קומיט קובץ ה readme מתאר את דרך ההתקנה המומלצת למי שרוצה להשתמש במודול:

$ npm install azer/left-pad

הכתיב npm install ואחריו שתי מילים מופרדות בלוכסן מאפשר התקנה של מודולים ישירות מגיטהאב בלי לעבור דרך הריפו המרכזי npm וזה מתועד כאן: https://docs.npmjs.com/cli/v8/commands/npm-install.

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

module.exports = leftpad;

function leftpad (str, len, ch) {
  str = String(str);

  var i = -1;

  if (!ch && ch !== 0) ch = ' ';

  len = len - str.length;

  while (++i < len) {
    str = ch + str;
  }

  return str;
}

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

var pad = new Array(len).join(ch);

אבל האמת שהמימוש עם לולאת ה while יותר מהיר אז אני לגמרי מבין את ההגיון. בכל מקרה אם יש דבר אחד שלמדתי מכל הסיפור של left-pad זה שהרבה יותר נוח להדביק חתיכת קוד שלא אנחנו כתבנו מאשר לממש לבד ולהרגיש רע עם זה שהקוד לא מספיק יפה.

2. לפט פד היום

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

'use strict';
module.exports = leftPad;

var cache = [
  '',
  ' ',
  '  ',
  '   ',
  '    ',
  '     ',
  '      ',
  '       ',
  '        ',
  '         '
];

function leftPad (str, len, ch) {
  // convert `str` to a `string`
  str = str + '';
  // `len` is the `pad`'s length now
  len = len - str.length;
  // doesn't need to pad
  if (len <= 0) return str;
  // `ch` defaults to `' '`
  if (!ch && ch !== 0) ch = ' ';
  // convert `ch` to a `string` cuz it could be a number
  ch = ch + '';
  // cache common use cases
  if (ch === ' ' && len < 10) return cache[len] + str;
  // `pad` starts with an empty string
  var pad = '';
  // loop
  while (true) {
    // add `ch` to `pad` if `len` is odd
    if (len & 1) pad += ch;
    // divide `len` by 2, ditch the remainder
    len >>= 1;
    // "double" the `ch` so this operation count grows logarithmically on `len`
    // each time `ch` is "doubled", the `len` would need to be "doubled" too
    // similar to finding a value in binary search tree, hence O(log(n))
    if (len) ch += ch;
    // `len` is 0, exit the loop
    else break;
  }
  // pad `str`!
  return pad + str;
}

ובנוסף קיבלנו בתיקיה גם קובץ index.d.ts עם הגדרת הטיפוסים ל TypeScript:

// Definitions by: Zlatko Andonovski, Andrew Yang, Chandler Fang and Zac Xu

declare function leftPad(str: string|number, len: number, ch?: string|number): string;

declare namespace leftPad { }

export = leftPad;

קריאה מהירה בקוד מראה לנו שני שינויים משמעותיים מבחינת ביצועים:

1. שינוי באלגוריתם שמקצר משמעותית את הלולאה.

2. תוספת Cache שמקצרת משמעותית את זמן החישוב עבור קלטים קצרים.

נתחיל עם ה cache. בנג'מן גרינבאום הוסיף אותו עם הערת הקומיט הבאה:

Cache for very common cases I estimate that the majority of people who left pad use it for formatting in which case performing any calculations at all is silly.

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

השינוי היותר משמעותי הוא זה שמופיע ב PR הזה: https://github.com/camwest/left-pad/pull/5 והוא השינוי באלגוריתם. הנה החלק המרכזי ממנו בלי הערות כדי שיהיה לנו קל לקרוא:

while (true) {
  if (len & 1) pad += ch;

  len >>= 1;

  if (len) {
    ch += ch;
  } else {
    break;
  }
}
// pad `str`!
return pad + str;

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

בגירסה של בנג'מן יש לנו אופטימיזציה מעניינית: נשים לב שכל מספר אפשר לייצג באמצעות סכום של חזקות של 2. זה בעצם הייצוג של המספר בבסיס 2. לדוגמה המספר 8 הוא פשוט 2 בחזקת 3, המספר 20 הוא 2 בחזקת 4 ועוד 2 בחזקת 2, והמספר 73 הוא בסך הכל 64 (כלומר 2 בחזקת 6) ועוד 8 (כלומר 2 בחזקת 3) ועוד 1 (שזה 2 בחזקת 0).

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

" "
"  "
"    "
"        "
"                "

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

ch += ch;

מקוד התוכנית.

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

if (len & 1) pad += ch;

בואו ננסה את זה עם אורך 20 כדי לראות שהמנגנון עובד:

1. בסיבוב הראשון len הוא 20, ch מכיל רווח בודד ו pad הוא ריק. מחלקים את len ב 2 כדי לקבל 10, הוא גדול מאפס ולכן מכפילים את האורך של ch וממשיכים לאיטרציה הבאה.

2. בסיבוב השני len הוא באורך 10, ch מכיל שני רווחים ו pad עדיין ריק. זיכרו שאנחנו צריכים את 16 ו 4 כדי להגיע ל 20. גם הפעם len הוא זוגי אז מחלקים אותו ב 2 וממשיכים לאיטרציה הבאה.

3. בסיבוב השלישי len הוא באורך 5. זו הפעם הראשונה שהוא אי זוגי ולכן אנחנו לוקחים את ch, שכרגע יש בו 4 רווחים, ומעתיקים אותו ל pad. אנחנו משתמשים במספר 4 שמצאנו כדי לבנות את מחרוזת הרווחים. עכשיו ממשיכים לפי התוכנית - מחלקים את len ל 2 בחלוקת מספרים שלמים ונשארים עם 2, ושוב מכפילים את ch כך שעכשיו יש בו 8 רווחים.

4. בסיבוב הרביעי len הוא באורך 2, כלומר זוגי. אפשר להכפיל את ch ולקבל שם מחרוזת עם 16 רווחים ולהמשיך לאיטרציה הבאה.

5. בסיבוב החמישי len יורד לאורך 1 (כי 2 חלקי 2 נותן 1). זה אי זוגי אז מוסיפים ל pad את הערך הנוכחי של ch כלומר את ה 16 רווחים. קודם היו בו 4 רווחים ולכן עכשיו ב pad יש 20 רווחים. ממשיכים לסיבוב הבא.

6. באיטרציה האחרונה len מתאפס ואנחנו יוצאים מהלולאה בקריאה ל break.

סך הכל בשביל לייצר מחרוזת של 20 תווים היינו צריכים רק 5 איטרציות במקום 20 - או במקרה הכללי log2(n) איטרציות. זה חיסכון משמעותי בזמן ריצה אם משתמשים בפונקציה הרבה פעמים.

3. וקטנה על ch

לפני שניפרד בואו נתעכב רגע על שורת הגדרת ברירת המחדל למשתנה ch:

if (!ch && ch !== 0) ch = ' ';

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

שימוש ב git blame מגלה לי ששורה זו נכנסה לקוד בקומיט 0e04eb4d עם הודעת הקומיט המופלאה:

make the third argument work

מסתבר שבגירסה קודמת של הפונקציה זה הופיע כך:

ch || (ch = ' ');

רואים את הבעיה? אם עדיין לא תשמחו לדעת ש Steve Mao הוסיף גם בדיקה כדי להראות איפה בדיוק הקוד הקודם נכשל:

assert.strictEqual(leftpad(1, 2, 0), '01');

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

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