streamalism.org

1. הקדמה

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

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

2. מהם צינורות הוראה?

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

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

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

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

לדוגמה, נוכל לקבל תוכנית פשוטה:

int a = 0; a + = 1; a + = 2; a + = 3;

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

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

3. מהם הסכנות?

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

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

בואו לשנות את התוכנית הפשוטה שלנו כדי להציג סניף:

int a = 0; a + = 1; אם (a <10) {a + = 2; } a + = 3;

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

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

4. מהו חיזוי ענף?

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

בדוגמה שלעיל, המעבד עשוי לחזות זאת אם (א <10) צפוי להיות נָכוֹןוכך הוא יתנהג כאילו ההוראה a + = 2 היה הבא להוציא לפועל. זה יביא את הזרימה להיראות בערך כמו:

אנו יכולים לראות מייד כי הדבר שיפר את ביצועי התוכנית שלנו - זה לוקח עכשיו תשעה קרציות ולא 11, אז זה מהיר יותר ב -19%.

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

בואו נהפוך את המותנה שלנו כך שזה יהיה עכשיו שֶׁקֶר:

int a = 0; a + = 1; אם (a> 10) {a + = 2; } a + = 3;

זה עשוי לבצע משהו כמו:

זה עכשיו איטי יותר מהזרימה הקודמת, למרות שאנחנו עושים פחות! המעבד ניבא באופן שגוי שהסניף יעריך זאת נָכוֹן, התחיל בתור a + = 2 הוראה, ואז היה צריך להשליך אותה ולהתחיל מחדש כשהסניף העריך אותו שֶׁקֶר.

5. השפעה אמיתית על הקוד

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

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

5.1. ספירת רשומות

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

מספרי רשימה = LongStream.range (0, למעלה) .boxed () .collect (Collectors.toList ()); if (shuffle) {Collections.shuffle (numbers); } חתך ארוך = עליון / 2; ספירה ארוכה = 0; התחלה ארוכה = System.currentTimeMillis (); עבור (מספר ארוך: מספרים) {if (number <cutoff) {++ count; }} סוף ארוך = System.currentTimeMillis (); LOG.info ("ספרות {} / {} {} מספרים ב- {} אלפיות שניים", ספירה, למעלה, דשדוש? "דשדוש": "מסודר", סוף - התחלה);

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

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

• ממוין - 44ms
• דשדוש - 221ms

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

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

5.2. סדר הסניפים

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

אם (mostLikely) {// עשה משהו} אחר אם (lessLikely) {// עשה משהו} אחר אם (leastLikely) {// עשה משהו}

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

מספרי רשימה = LongStream.range (0, למעלה) .boxed () .collect (Collectors.toList ()); אם (דשדוש) {Collections.shuffle (מספרים); } cutoff ארוך = (long) (top * cutoffPercentage); ארוך נמוך = 0; ארוך גבוה = 0; התחלה ארוכה = System.currentTimeMillis (); עבור (מספר ארוך: מספרים) {if (number <cutoff) {++ low; } אחר {++ גבוה; }} סוף ארוך = System.currentTimeMillis (); LOG.info ("מספרים {} / {} מספרים ב- {} אלפיות שניים", נמוך, גבוה, סוף התחלה);

קוד זה מבוצע בערך באותו זמן - ~ 35ms למספרים ממוינים, ~ 200ms למספרים מעורבבים - כאשר סופרים 10,000,000 מספרים, ללא קשר לערך של cutoff אחוז.

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

5.3. שילוב תנאים

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

לדוגמא, אם אנו משווים שני מספרים ל- 0, גישה חלופית היא להכפיל אותם יחד ולהשוות את התוצאה ל- 0. לאחר מכן החלפת תנאי בכפל. אך האם זה כדאי?

הבה נבחן דוגמה:

long [] first = LongStream.range (0, TOP) .map (n -> Math.random () Math.random () <FRACTION? 0: n) .toArray (); ספירה ארוכה = 0; התחלה ארוכה = System.currentTimeMillis (); עבור (int i = 0; i <TOP; i ++) {if (first [i]! = 0 && second [i]! = 0) {++ count; }} סוף ארוך = System.currentTimeMillis (); LOG.info ("ספרות {} / {} מספרות המשתמשות במצב נפרד ב- {} ms", ספירה, TOP, סוף התחלה);

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

• תנאים נפרדים - 40ms
• מצב מרובה ויחיד - 22ms

כך שהאפשרות שמשתמשת בשני תנאים שונים נמשכת למעשה לביצוע כפול.

6. מסקנה

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

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

דוגמאות למקרים ממאמר זה זמינים ב- GitHub.