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

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

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

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

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

מלכודת ראשונה: מה היקף הבעיה?

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

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

כעת הוספתי לתוכנית מערך של פוינטרים ל-struct, ובתחילת התוכנית נתתי לכל אחד מהם את הכתובת של ה-struct המקביל במערך המקורי. כשניגשים דרכם לנתונים, זמן הקריאה של משתנה 8-ביט ירד מ-360us ל-40μs, ושל משתנה 32-ביט מ-370μs ל-70μs. כלומר, עבור משתני 8-ביט, שזו גם הארכיטקטורה של המיקרו-בקר עצמו, מערכים נפרדים רגילים (35μs, בטבלה למעלה) הם עדיין יותר יעילים, מכל בחינה, ממערך של פוינטרים ל-struct. אבל אם אנחנו רוצים את הנוחות של struct, או לחלופין צריכים לעבור את סף ה-8-ביט במשתנה כלשהו, הפוינטרים מנצחים בגדול.

מלכודת שנייה: זמן האתחול

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

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

מלכודת שלישית: מקום ב-SRAM

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

סיכום ודוגמה

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

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

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