סיפורי אופטימיזציה: shiftOut לממהרים

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

תעלומה!!

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

void shiftOut(uint8_t dataPin, 
              uint8_t clockPin, 
              uint8_t bitOrder, 
              uint8_t val) {
  
  uint8_t i;

  for (i = 0; i < 8; i++)  {
    if (bitOrder == LSBFIRST)
      digitalWrite(dataPin, 
                   !!(val & (1 << i)));
     else    
      digitalWrite(dataPin, 
                   !!(val & (1 << (7 - i))));
            
    digitalWrite(clockPin, HIGH);
    digitalWrite(clockPin, LOW);        
  }
}

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

התשובה!!

למעשה, יש היגיון בפעולה המוזרה הזו. הערך שעובר את ההיפוך הכפול יכול להיות, במקור, שתיים-בחזקת-משהו, והוא נשלח בסופו של דבר לפונקציה digitalWrite שמכירה את הקבועים LOW או HIGH, שערכיהם 0 ו-1 בהתאמה. מה יקרה אם נשלח לה ערך אחר, כמו למשל 64?

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

השאלה הנשאלת עכשיו היא, מה באמת יקרה אם נשלח ל-digitalWrite ערך שהוא לא 0 ולא 1? בואו נסתכל בחלק הרלוונטי של קוד הפונקציה, שנמצאת בקובץ wiring_digital.c:

    if (val == LOW) {
        *out &= ~bit;
    } else {
        *out |= bit;
    }

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

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

קדימה, לקצץ

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

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

void MY_shiftOut(uint8_t dataPin, 
uint8_t clockPin, 
                 uint8_t bitOrder, 
                 uint8_t val) {
  uint8_t i;

  if (bitOrder == LSBFIRST)
   for (i = 1; i; i <<= 1)  {
     digitalWrite(dataPin, val & i);     
     digitalWrite(clockPin, HIGH);
     digitalWrite(clockPin, LOW);        
   } else 
      for (i = 128; i; i >>= 1)  {
        digitalWrite(dataPin, val & i);     
        digitalWrite(clockPin, HIGH);
        digitalWrite(clockPin, LOW);        
      }
}

כתבתי קוד עם שתי הפונקציות הללו, כשלכל אחת הוספתי בהתחלה כתיבת HIGH שתשמש כסמן למדידה, ואז מדדתי בעזרת Logic Analyzer את הזמן שנדרש לשליחת בייט אחד (כלומר, עד העליה האחרונה של פין השעון). הגרסה המקורית לקחה 132 מיליוניות השניה, ואילו הגרסה שלי 120 – שיפור של כ-9%.

לקצץ עוד

כידוע, הפונקציה digitalWrite בעצמה היא בזבזנית זמן לא קטנה, וברור שרוב זמן הריצה שנמדד מוקדש לה. מצד שני, כדי לוותר עליה אנחנו חייבים לוותר גם על הנוחות שלה ולקודד בצורה קשיחה את הפינים שאנחנו רוצים לתפעל. במקרה זה בחרתי בפינים 7 ו-8, שנמצאים בביט הגבוה של PORTD ובנמוך של PORTB, בהתאמה. הנה הקוד של shiftOut ממוטבת ספציפית לפינים אלה (את הפרמטרים הנשלחים אליה השארתי כפי שהם מתוך עצלות):

void MY_FAST_shiftOut(uint8_t dataPin, 
                      uint8_t clockPin, 
                      uint8_t bitOrder, 
                      uint8_t val) {
  uint8_t i;

  if (bitOrder == LSBFIRST)
   for (i = 1; i; i <<= 1)  {
     val & i ? PORTD |= 128 : 
               PORTD &= 127;     
     PORTB |= 1;
     PORTB &= 254;
   } else 
      for (i = 128; i; i >>= 1)  {
        val & i ? PORTD |= 128 : 
                  PORTD &= 127;     
        PORTB |= 1;
        PORTB &= 254;
      }
}

לפונקציה הזו נדרשו 9 מיליוניות השניה בלבד לרוץ – פחות מ-7% מהזמן שנדרש לפונקציה המקורית!

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

מעניין מאוד, אך מה משמעות ה- ? בקוד?
val & i ? PORTD |= 128 :

האם הרכיב שמחובר בקצה השני יעבוד עם כל מהירות שליחה?