מבוא לאופטימיזציה (עם דוגמאות)

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

תמונת רקע באפס זיכרון

הנה דוגמה בסיסית לאופטימיזציה של זיכרון. בסרטון הבא מוצג יישום קטן שכתבתי עבור ה-MSP430 Launchpad, שמציג על גבי מסך LCD זול של Nokia 5110 מלבנים מעופפים מעל רקע פיקסלים אקראי.

למיקרו-בקר MSP430G2553 שמסתתר מתחת למסך יש 512 בייטים של זכרון RAM. מסך ה-LCD בנוי כמטריצה של 48×84 פיקסלים, ומכיוון שהוא מונוכרומטי, כל שמונה פיקסלים מיוצגים על ידי בייט יחיד – כלומר, בכל רגע נתון הוא מציג 504 בייטים. מה שעוד יותר גרוע, אין למסך הזה מאגר זיכרון משל עצמו: הכל מנוהל מבחוץ. אם הייתי רוצה לאחסן את תמונת הרקע האקראית שבסרטון על המיקרו-בקר, היו נשארים לי שמונה בייטים בלבד לשאר משתני התוכנית, וזה לחלוטין לא מספיק.

הבעיה נפתרה באמצעות טריק: הרקע מחושב על ידי המיקרו-בקר בכל פריים מחדש! שום חלק ממנו אינו נשמר בזיכרון. הכל מיוצר בזמן אמת, בייט אחרי בייט. הפונקציה random נותנת את המספרים האקראיים, וקריאה לפונקציה randomSeed עם פרמטר קבוע לפני תחילת הציור של כל פריים מבטיחה שהרקע יהיה תמיד אותו הדבר (RandomSeed קובעת מעין נקודת התחלה עבור מחולל המספרים האקראיים, שהוא לא באמת אקראי ולכן חוזר על אותו רצף תוצאות).

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

יותר מהר!

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

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

חשוב לשים לב שגזלני הזמן העיקריים הם לאו דווקא התהליכים שלוקחים יותר זמן כשלעצמם, אלא אלה שמבוצעים שוב ושוב וגוזלים זמן במצטבר. לצורך ההמחשה בלבד, אם הכנה לציור פריים לוקחת מאית שניה, וציור פיקסל אחד לוקח מיליונית שניה, מישהו עלול להתפתות לטפל קודם כל בהכנה – הרי היא ממושכת פי עשרת-אלפים! – אך ההכנה הזו מבוצעת פעם אחת לפריים, שמכיל במקרה זה 240×320 פיקסלים – כלומר 76,800 מיליוניות השניה לצייר את כולם. זאת אומרת, הפיקסלים אחראים למשהו כמו 88% מהזמן שנדרש לציור פריים. שיפור של, נניח, 30% בזמן ציור הפיקסלים ישפר את המהירות הכוללת יותר מכל מה שאפשר יהיה להשיג אי-פעם בעבודה על קוד ההכנה. מוטב למצות את כל האפשרויות עם גזלני הזמן העיקריים, ורק אז לעבור לגורמים המשניים. לפני שאסביר מה עשיתי במקרה שלי, הנה סרטון שממחיש את השיפור שהושג:

1. פחות פיקסלים

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

ניקח לדוגמה את המקרה הפשוט ביותר, של מלבן לבן (צבע אחיד) בגודל קבוע שמשייט משמאל לימין על פני רקע שחור. במקרה הכי גרוע, נצייר בכל פריים מחדש את כל הרקע השחור, ואחר כך נצייר את המלבן. בהנחה שגודל המסך הוא 240×320 פיקסלים וגודל המלבן הוא 24×32, יש כאן 77,568 פעולות ציור של פיקסלים לכל פריים. אבל רגע, אם המלבן לא משנה את מיקומו בציר Y אלא רק ב-X, אפשר לצבוע בשחור רק את תחום ה-Y שבו המלבן משייט, ואז לצייר את המלבן עצמו. זאת אומרת, 24×320 ועוד 24×32, שזה 8,440 פעולות. יותר מזה, מכיוון שהרקע נשאר שחור בכל מקרה, אפשר למחוק בכל פעם רק את האזור המדויק שבו היה המלבן קודם, ולצייר את המלבן במיקומו החדש: 1,536 פעולות!

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

2. פחות התעסקות

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

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

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

הצ'יפ ILI9325 מציע שיטה מעניינת למלא אזורים מלבניים בפיקסלים. אפשר להגדיר לו "חלון" בתוך מרחב הפיקסלים, ואז לכתוב את המידע ברצף. החומרה כבר תדע לסדר את הפיקסלים האלה לפי שורות וטורים במסגרת החלון שהוגדר. מי שעבד עם גרפיקה low-level בעבר יודע כמה כאב-ראש פונקציונליות כזו יכולה לחסוך לפעמים. גם הספריות של המסך בחרו לחסוך כאבי ראש, ומעיון בקוד הסתבר שהן מגדירות חלון כזה לכל פעולה "מלבנית": מילוי מלבן (fillRect), ציור קו אנכי וציור קו אופקי. הופה! קו אנכי ואופקי לא צריכים חלון מגביל! מספיק להציב את הסמן הווירטואלי במיקום הנכון בחלון הרגיל (המלא), להגדיר את כיוון הציור (אנכי או אופקי) ולרוץ!

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

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

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

להרשמה
הודע לי על
3 תגובות
מהכי חדשה
מהכי ישנה לפי הצבעות
Inline Feedbacks
הראה את כל התגובות

מצטרף למחמאות. פוסט רהוט, פרקטי ומענין. תודה!

מעניין מאד

אחלה פוסט. תודה.