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

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

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

איפה הבעיה?

נניח שאנו עובדים ברזולוציית VGA, כלומר 640x480 או 307,200 פיקסלים. עבור כל אחד מאלה אנחנו מבצעים את לולאת החישוב, שנועדה לגלות אם הנקודה שהפיקסל מייצג שייכת לקבוצת מנדלברוט או לא. המספר המרבי של "סיבובים" בלולאה נתון לשיקולנו, אך כדי לא לפגוע בדיוק של התוצאות מוטב לבחור ערך גבוה יחסית, כגון 256. עם זאת, לא כל לולאה מגיעה עד הסוף: לצורך העניין, אפשר להניח שהפיקסל הממוצע דורש רק חצי ממספר החזרות המרבי. נכפיל את זה במספר הפיקסלים והגענו ל-39,321,600 חישובים. כל חישוב כזה כולל לא מעט הכפלות וחיבורים של מספרים בעלי נקודה עשרונית (floating point) – פעולות איטיות יחסית, מכיוון שהייצוג של מספרים כאלה במחשב מורכב הרבה יותר מזה של מספרים שלמים. אם ניקח הערכה גסה ביותר של 10 פעולות חשבוניות בכל חישוב ו-10 פעולות מעבד עבור כל פעולה חשבונית, נגיע לכמעט ארבעה מיליארדי פעולות עבור פריים יחיד – שניה או שתיים של חישוב נטו במחשבים מודרניים, וזה עוד לפני שדיברנו על כל הבלגן שמתווסף מסביב על ידי הקומפיילר - ומערכת ההפעלה.


 
המון חישובים (כל צילומי המסך: עידו גנדל)
 המון חישובים (כל צילומי המסך: עידו גנדל) 
 
 

שלב ראשון: ציור ישיר

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

שלב שני: פחות חישובים לפיקסל

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

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

while (Result < MaxIterations) AND (SqrR + SqrI < 4) do

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

שלב שלישי: פחות פיקסלים לחישוב

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

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

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


 
תהליך ציור הפרקטל בעזרת חלוקה לרבעים
 תהליך ציור הפרקטל בעזרת חלוקה לרבעים 
 

תנו לי מ', תנו לי נ', תנו לי ד'...

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

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


 
ארטיפקטים של דיוק מוגבל בחישוב
 ארטיפקטים של דיוק מוגבל בחישוב 
 
 
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
 
תגובות
הוסף תגובה0 תגובות
הוספת תגובה
מאת
 
נושא
 
תוכן
 
 
 
 
תודה! תגובתך התקבלה.
התגובה תתפרסם בכפוף לתנאי האתר.
 
 
 
 
 

כל הזכויות שמורות 2011 © נענע 10 בע"מ
 
 
 
 
כל הזכויות שמורות © Nana10 בע"מ
Video powered by