2018-10-13

מה *לא* לימדו אותנו באוניברסיטה על מבני-נתונים?

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

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

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

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


הכלל הראשון שארצה להדגיש הוא זה:

כלל חשוב לחיים המקצועיים!

כדי להסביר את הכלל, אפתח בדוגמה משעשעת של אלגוריתם חיפוש בשם Sleep Sort:

ע״פ האלגוריתם הזה, יש רשימת מקור (הקלט) ורשימת יעד (התוצאה). בעת ההרצה אנו סורקים את רשימת המקור ולכל איבר מפעילים פונקציה (למשל: co-routine) שתכניס את האיבר לרשימת היעד בעוד n שניות, כאשר n הוא גודל האיבר.

אם רשימת המקור היא 2, 4, ו 3 אזי האיבר 2 יכנס לרשימת היעד לאחר שתי שניות, האיבר ארבע לאחר 4 שניות, והאיבר 3 - לאחר 3 שניות. והנה ביצענו מיון!

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

למשל, עבור קלט קלט של המספרים 2 ו 1,000,000,000 האלגוריתם ירוץ במשך  כמעט 32 שנים - מה שבהחלט פחות יעיל אפילו מ Bubble Sort. 


מה היה לנו כאן? מחיר אמיתי מאוד, ומשמעותי מאוד, שלא לקחנו בחשבון בהערכת הזמן של האלגוריתם. יכולנו בהתאם לשכלל את התאוריה שלנו ולנסח זמן ריצה בנוסח:
(O(max(item_size) * sec) +n - כאשר בעיקרון אפשר להזניח את n.



באופן דומה (והרבה פחות קיצוני) ניתן לומר שיש מחירים נוספים ומשמעותיים שלא נלקחים בחשבון בחלק גדול ממבני-הנתונים שלמדנו עליהם:
  • HashTable
  • LinkedList
  • Binary Search Tree
  • Graphs
בהמשך הפוסט אסביר את המחיר הנוסף, ועוד כמה תובנות שכדאי להכיר בהקשר למבני-נתונים.



חוק המספרים הקטנים


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


אם אנחנו מסתכלים על זמני הריצה התאורטיים שאנו נוהגים להסתכל עליהם, תחת ההקשר ש CPU בימנו מבצע מיליארדי cycles בשנייה, אזי עבור מאות או אולי אלפי איברים - סיבוכיות האלגוריתם עד לרמת nlogn - לא ממש משנה:


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

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

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


חשוב לציין שלא כל "פקודת מחשב" מתבצעת ע"י cycle בודד של מעבד. ליהפך: תנאי if פשוט לכאורה, עלול בקלות להתתרגם לעשרות ומאות CPU cycles. כאמצעי ביטחון אפשר לחשוב על ה CPU כמבצע עשרות-מיליוני פעולות בשנייה בלבד.



"מספרים שכל מתכנת חייב להכיר" (2012). איפה הייתם בקורס מבני-נתונים?!

המחיר הנוסף


בניגוד למשתמע בקורס מבני-נתונים, אלגוריתמים בפועל לא רצים על הלוח או במוחם של מתמטיקאים, אלא על חומרת מחשב. החומרה הזו פועלת על כמה הנחות מאוד חשובות:
  • גישה לדיסק היא מאוד מאוד יקרה (לפני עידן ה SSD היא הייתה מאוד מאוד מאוד יקרה).
  • גישה לזיכרון היא יקרה, ובהחלט לא אקראית - על אף השם "Random Access Memory = RAM". 
  • נתונים, גם מהרשת, גם מהדיסק, וגם משכבות הזיכרון השונות מוגשות בבלוקים רציפים. העלות להביא את הבלוק היא החלק היקר, בעוד ההבדל בין סריקה של בית בודד או את כל הבלוק - הוא לרוב משני עד זניח.
    • אפשר לראות את ההתנהגות הזו בנתונים למעלה, כאשר קריאה של בית בודד מ SSD תיקח 0.15ms בעוד קריאה של מיליון בתים מ SSD (עשרות עד מאות בלוקים) - תיקח רק מעט יותר: כ 1.0ms.
    • שווה מאוד לקרוא ולטפל בנתונים ברציפות, ולא בסדר אקראי
  • למעבדים יש היררכיה של זיכרונות Cache. נתון שלא נמצא ב Cache יובא קודם ל L3 ואז ל L2 ואז ל L1, ולכל הבאה שכזו, יקדם חיפוש ברחבי ה Cache Level שהנתון אכן לא שם.
    • זה בזבוז להביא מילה בודדת בזיכרון, ולכן כל פעם מביאים בלוק זיכרון רציף. גודל הבלוק - תלוי בארכיטקטורת המעבד.





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


קרב ראשון: Vector/ArrayList מול LinkedList


אנחנו מעונינים להוסיף דינאמית איברית לרשימה. איזה מבנה-נתונים הכי מתאים? Vector (אשתמש בשם הקדום ב ++C) או רשימה משורשרת?

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

רשימה משורשרת פשוט מוסיפה עוד ועוד ערכים במחיר (O(1 לכל פעולה.

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

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

בואו נראה מה קורה בפועל:


הממ... לא בדיוק.

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

  • כל אלמנט ברשימה המשורשרת תופס יותר זיכרון: צריך להכניס לזיכרון גם את הערך וגם את המצביע לאלמנט הבא. כנ"ל אם הערך הוא מצביע לאובייקט ולא Int. זה אותו הדבר.
  • בתאוריה: העתקה של מרחבי זיכרון רציפים היא עלות (O(n או משהו יקר אחר.
    בפועל: במעבדים מודרניים יש פקודה יעילה למדי להעתקה של בלוקים של זיכרון. זו איננה פעולה יקרה כ"כ.
  • חיפוש המקום להכנסה ברשימה משורשרת הוא הנקודה החלשה הבולטת של הרשימה המשורשרת: ה nodes של הרשימה מפוזרים אקראית במרחב הזיכרון. כשאנו סורקים את הרשימה (בממוצע n/4 איברים בכל פעם) אנחנו "חוטפים" עוד ועוד cache misses הדורשים לעדכן את זיכרון המטמון.
    • כאשר אנחנו סורקים את הוקטור, ככמט כל בלוק של זיכרון שנביא ל cache - ינוצל במלואו.
    • במקרה של שימוש ב virtual memory (לא נכלל בגרף) - המקרה גרוע הרבה יותר: ייתכן ובגלל קפיצות בין דפים שונים של ה main memory "נחטוף" Page Fault ויהיה עלינו להביא את דף הזיכרון מהדיסק, רחמנא ליצלן! 



שיפור עמודות לטובת הרשימה-המשורשרת

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

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

עד כמה עומדת הרשימה המשורשרת למחוץ את הוקטור? בתיאוריה זה אמור להיות אכזרי כלפי הוקטור. בואו נראה בפועל:

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

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

אין כמעט תסריטים של scale בהם הרשימה המשורשרת יכולה לנצח את הוקטור בעולם האמיתי. רק כאשר גודל האלמנט בכל node הוא גדול מאוד (מאות בתים, למשל) ואז גם ה cache מתרפרש מהר בכל מקרה וגם התקורה של ה next-pointer של הרשימה המשורשרת הופכת לזניחה.



בעולם הג'אווה - המשחק משתנה

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


בג'אווה (או #C) ואולי גם בפייטון / רובי - הדברים מעט שונים. יש מפרשן או JVM/CLR שנמצאים בין מערכת ההפעלה לקוד. יש שימוש מאסיבי ב Heap - שאינו רציף.

איך הדברים נראים בג'אווה? אולי שם ההבדל בין וקטור לרשימה משורשרת נמחק?
בואו נבדוק שוב את המקרה של הכנסת איבר למקום הממוין ברשימה.


אין לי גרף מתאים (הנה המקור לנתונים), אבל מאיסוף ידני של הנתונים ממבחן ב ++C, ב 20,000 איברים היו התוצאות 617 מילישניות לרשימה משורשרת, ו 234 מילישניות לוקטור - שזה יחס דומה.

ה DynamicIntArray, אם תהיתם, הוא מימוש של ArrayList המאחסן איברים מסוג int (פרמיטיב) ולא ב Integer (אובייקט) - ולכן הוא ידידותי באמת ל cache. הנתונים באמת שמורים במערך רציף (כמו ב ++C) והם לא reference לאובייקט שתלוי ב Heap (שאותו ג'אווה אכן משתדלת למלא בצורה רציפה).


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


עם השנים ה caches של המעבדים גדלים ומתייעלים היתרון של הוקטור, המבוסס על זיכרון רציף - הולך וגדל.


את זה לא סיפרו לי בקורס מבני-נתונים!




סיכום ביניים


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

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


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

מה עושים?

במקום עצי חיפוש בינריים, משתמשים ב B-Tree. עץ חיפוש שבו כל node מותאם לגודל בלוק בדיסק (ומכאן: כמה בלוקים של זיכרון, בהתאמה). כל בלוק מכיל רשימה של מצביעים רלוונטיים. האופטימיזציה היא לצמצום הגישה לבלוקים, כך שכל פעם טוענים בלוק מהדיסק / זיכרון - מנצלים אותו ביעילות ע"י שימוש בסריקה רציפה.

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

מפתחים של בסיסי נתונים משתמשים ב B-Tree (או B+Tree - וריאציה מעט שונה) כדרך קבע כעצי חיפוש למשל: בשימוש באינקסים.


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

מה עושים בגרפים? אני לא מכיר באופן אישי, אבל אני מניח שגם Neo4J או AWS Neptune מצאו את הדרך שלהם לבנות את מבנה הנתונים החשוב והנהדר הזה Graph - בצורה שאיננה עוינת לזיכרון. או לפחות: עוינת פחות ככל האפשר.


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

שיהיה בצלחה!





קישורים רלוונטיים:

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


20 comments:

  1. פוסט מעניין ומעורר מחשבה, במיוחד לבוגרים טריים :)

    השבמחק
  2. אנונימי14/10/18 09:19

    אהבתי

    השבמחק
  3. אנונימי14/10/18 09:37

    תרשה לי לנטפק ולהגיד שהדוגמה של ה-sleep sort שנתת לא נכונה גם בתיאוריה. אם יש לך n איברים אבל על האיבר ה-k אתה עושה פעולה שלוקחת k זמן (גם אם הפעולה שלך היא לישון בפועל), חישוב זמן הריצה התיאורטי שלך יהיה n^2.

    בלי קשר, תודה על הפוסט.

    השבמחק
    תשובות
    1. אנונימי14/10/18 09:42

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

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

      מחק
  4. אחלה פוסט!
    הערה קטנה- חוק המספרים הקטנים חי וקיים.
    https://he.m.wikipedia.org/wiki/%D7%97%D7%95%D7%A7_%D7%94%D7%9E%D7%A1%D7%A4%D7%A8%D7%99%D7%9D_%D7%94%D7%A7%D7%98%D7%A0%D7%99%D7%9D

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

      מחק
  5. כרגיל on point. תודה!

    השבמחק
  6. כתוב מדהים.
    החכמתי.

    השבמחק
  7. אנונימי14/10/18 15:22

    מעולה!!

    השבמחק
  8. אנונימי14/10/18 22:47

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

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

    השבמחק
    תשובות
    1. א. אלו לא חומרות זהות, אז לא יהיה נכון להשוות אבסולוטית.
      ב. כשעושים אופטימיזציות (למשל: ב cache) לרוב יש tradeoffs ומקרים שלא נכללים באופטימיזציה עלולים להגיב טוב פחות מבעבר (למשל: המקרה של cache misses מתרחש פחות - אבל כשהוא מתרחש המחיר גבוה יותר).

      מחק
  10. אנונימי31/10/18 11:11

    ממש אהבתי
    חושב שיש לך טעות רק במשפט
    "אנחנו להוסיף דינאמית איברית לרשימה"

    השבמחק
    תשובות
    1. תודה רבה!

      עובד עכשיו על חלק ב'...

      מחק
  11. אנונימי8/11/18 09:20

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

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

    חשוב לתקן את זה.

    השבמחק
    תשובות
    1. היי,

      תודה על ההערה!

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

      בשימוש ב(vector.push_back(n:

      elements, list, vector_best, vector_worst(naive)
      10, 1, 5, 6
      100, 5, 4, 8
      500, 34, 6, 41
      1000, 63, 11, 128
      2000, 127, 20, 449
      10000, 699, 124, 8768
      20000, 889, 158, 34597
      40000, 2143, 275, 140525
      100000, 3971, 605, 906315


      שימוש ב (vector.insert(vector.begin(), n:

      elements, list, vector_best, vector_worst(naive)
      10, 1, 5, 0
      100, 4, 5, 3
      500, 21, 24, 24
      1000, 36, 75, 142
      2000, 84, 262, 260
      10000, 415, 6951, 6882
      20000, 836, 35056, 35194
      40000, 1678, 144794, 144710
      100000, 4176, 925421, 922736

      מחק
  12. אנונימי12/11/18 14:50

    תודה על המאמר ועל עוד רבים אחרים.

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

    עם השנים למדתי לתהות ולבדוק תיאוריות "בשטח" בעצמי - בייחוד כשהמציאות (כמו שלנו) וההנחות משתנות די מהר.

    - משה ג.

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

    השבמחק