באחד הסרטונים הישנים שלו, מהתקופה שבה הוא קישקש פחות והיה מעניין יותר, דייב ג'ונס אמר משפט חכם לגבי אופטימיזציה של זיכרון במיקרו-בקרים: אנחנו לא בשנות השמונים, אם הגעת למצב שאתה צריך לחשוב על כל בייט, כנראה בחרת במיקרו-בקר לא מתאים. זה נכון, ולכן הפוסט הזה, שעוסק תכל'ס בחיסכון של בייטים בודדים ממש, הוא לא עצה מעשית שמומלץ ליישם אלא פשוט תרגיל מחשבתי, איך לערער קצת על מוסמכות ולא לקחת שום דבר כמובן מאליו.
הנושא, בגדול, הוא באפר מעגלי (Circular buffer). כל מי ששיחק עם ארדואינו נתקל בבאפר כזה, גם אם הוא לא ידע שהוא שם: כששולחים מידע ב-UART מהמחשב אל הלוח, אובייקט Serial צובר בבאפר, שנמצא בזיכרון ה-SRAM, את התווים הנכנסים עד שהקוד שלנו מתפנה לקרוא אותם באמצעות פקודות Serial.read.
הייחוד של באפר מעגלי לעומת באפר "סתם" הוא שמרגע שקראנו משהו ממנו, המקום הזה מתפנה באופן מיידי לנתונים חדשים. לא צריך לקרוא את כל תוכן הבאפר כדי שאפשר יהיה למלא אותו שוב. הטריק הזה מתבצע על ידי שמירה של שני אינדקסים: האינדקס שאליו צריך לכתוב עכשיו (head) והאינדקס שממנו צריך לקרוא עכשיו (tail). כל אחד מהם זז צעד אחד קדימה בעת כתיבה או קריאה בהתאמה, וכאשר הוא עובר את התא האחרון בזיכרון הפיזי, מגלגלים אותו בחזרה לאינדקס של התא הראשון. אפשר לדמיין את הבאפר הזה כמערך בצורת עיגול או טבעת, ומכאן שמו.
המימוש בפועל מחייב קצת מחשבה. איך אני יודע, למשל, כמה נתונים שמורים כרגע בבאפר? אפשר לבדוק מה ההפרש בין head ל-tail, תוך התחשבות בטבעו המעגלי של הבאפר. אבל אם ההפרש יוצא 0, האם זה אומר שאין נתונים? או ש-head התקדם כל כך שהוא השיג את tail, ולמעשה הבאפר מלא לגמרי? בספר המצוין Making Embedded Systems, שסקרתי כאן, מוצגים שני הפתרונות הקלאסיים והמקובלים לבעיה. הראשון הוא לא להניח לבאפר להתמלא לגמרי: אם מגיע נתון חדש, שכתיבה שלו תגרום ל-head להיות שווה ל-tail, לא נכתוב אותו כלל אלא נרים דגל בתוכנה שאומר שיש לנו עודף נתונים (overflow). הפתרון השני הוא להחזיק בצד משתנה נוסף, בואו נקרא לו count, שמתעדכן עם כל פעולת כתיבה או קריאה בכמות הנתונים שיש בפועל בבאפר. במקרה הפשוט ביותר, שבו הבאפר מחזיק בייטים נפרדים שמספרם לא עולה על 255, שני הפתרונות הנ"ל מחייבים אותנו להקריב בדיוק שלושה בייטים לצורך ניהול הבאפר.
שלושה בייטים זה באמת בקטנה, אבל לא מזמן דמיינתי – לא משנה למה – את המיקרו-בקר הצנוע ATtiny104 בתפקיד שמצריך, בין השאר, באפר לתקשורת UART. לג'וק הזה יש 32 בייטים בלבד ב-SRAM, אז אולי הוא לא הבחירה הכי נבונה לתפקיד. אף על פי כן, כתרגיל מחשבתי, האם אפשר לגלח בייט מניהול הבאפר, ככה בשביל ההרגשה הטובה?
והתשובה היא: בהחלט כן. אם אני יודע איפה ה-tail (במילים אחרות, איפה הנתונים שעוד לא קראתי מתחילים), ואני יודע כמה נתונים יש שעוד לא קראתי (count), אני הרי יכול לחשב משניהם איפה צריך לכתוב כל נתון חדש (את ה-head)!
שתי התנגדויות צצות מיד. הראשונה היא שהרווחנו בייט אבל יש לזה עלויות נוספות בזמן חישוב. זה לא לגמרי נכון – הרי בשיטה של "head+tail בלבד" אנחנו צריכים לחשב בכל פעם מחדש את ה-count, שכאן הוא נתון לנו, ואילו בשיטה של "head+tail+count" אנחנו צריכים לעדכן גם את head וגם את count בזמן כתיבה, במקום רק את count. ההתנגדות השנייה היא שאם אני מחשב את ה-head בשביל לכתוב נתון חדש, ממילא אזדקק למקום בזיכרון כדי להחזיק בו את תוצאת החישוב. זה נכון, אבל אם הקומפיילר לא יעשה פאדיחות, רוב הסיכויים שהתוצאה הזמנית הזו תוחזק ברגיסטר של ה-CPU ולא תתפוס לנו שום SRAM.
כל זה היה רק מנה ראשונה. אם הגענו למיקרו-בקרים שיש להם 32 בייט SRAM, ברור שהבאפר שבהם לא יכול להיות גדול. אז אם נגביל אותו למספר בייטים עגול ויפה כמו 16 או 8, אפשר לנהל את כולו בעזרת בייט אחד ויחיד. הסוד הוא להתייחס בנפרד לשני החצאים (Nybbles) של הבייט הזה: ארבעת הביטים הגבוהים יחזיקו, נניח, את אינדקס ההתחלה הנוכחי של הנתונים, מה שקראנו קודם tail, והארבעה הנמוכים יחזיקו את מספר הבייטים המאוכלסים (count). זהו מקרה ספציפי ביותר, אך בכל זאת כתבתי את הקוד, והוא יצא עוד יותר קצר ואלגנטי ממה שהנחתי בהתחלה.
אגב, על בסיס הקוד הזה אפשר ליצור כמה באפרים שרוצים ולנהל את כולם בעזרת הפונקציות שכתבתי. אבל ב"קהל היעד" החומרתי של באפר מינימליסטי שכזה, קשה לדמיין מצב שבו יהיה מקום ליותר מבאפר אחד. לכן הגיוני דווקא להגדיר באפר אחד ויחיד, כ-instance גלובלי בודד של ה-struct, ושכל הפונקציות יעבדו ישירות מולו. כיוון שאנחנו עוסקים במיקרו-בקרים, אל תשכחו להוסיף גם את מילת המפתח volatile והשהייה של הפסיקות בכל מקום רלוונטי.
קשה לי להאמין שאפשר להיפטר גם מהבייט האחרון הזה, אבל אם יש לכם רעיונות, אשמח לשמוע… 🙂