קוד C++ יעיל: הכל מתחיל בפריסת הנתונים בזיכרון

בחירה ב-C++ אינה הופכת תוכנית למהירה מעצמה. במאמר “Writing Efficient C++ Code” מסביר המתכנת Adam Sawicki מה קובע אם הקוד באמת מנצל את החומרה: כיצד הנתונים מונחים בזיכרון ובאיזו תדירות המעבד ממתין למטמון. המאמר פורסם לראשונה בפולנית במגזין Programista בשנת 2013.

C++ לבדה אינה מבטיחה מהירות

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

תכנון מונחה נתונים

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

היררכיית הזיכרון קובעת את המחיר

במעבד בתדר 3 גיגה־הרץ פעולה חשבונית אחת נמשכת כ-0.33 ננושנייה, מחזור אחד. ערך במטמון L1 עולה כננושנייה אחת, ב-L2 כ-4.7, וב-RAM כ-83 ננושניות, כלומר 250 מחזורים. הנתונים עוברים בשורות מטמון של 64 בייט, ולכן ערכים שמשתמשים בהם יחד צריכים לשכב זה לצד זה.

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

AOS, SOA ומגבלות המהדר

מערכת חלקיקים ממחישה את הפשרה. ב-Array of Structures המיקום, המהירות והצבע של כל חלקיק נשמרים יחד; ב-Structure of Arrays לכל תכונה יש מערך נפרד, כך שהערכים הדרושים בלולאה נשארים סמוכים ושדות שאינם בשימוש אינם נכנסים למטמון.

המהדר אינו יכול לתקן הכול. כאשר מצביע עשוי להצביע על איברי המערך, הערך נטען מחדש בכל איטרציה; העתקה למשתנה מקומי או __restrict פותרים זאת. הוצאת std::string מחוץ ללולאה וניקויו בכל סיבוב קיצרו בדיקה מ-0.36 ל-0.27 שניות, 25%, משום שהמחרוזת שומרת על המאגר שהוקצה לה.