Tricks und Fallstricke bei der Speicherplatzoptimierung auf dem Arduino

Für die Gamuino getaufte Kombination von Arduino, Funduino Joystick Shield und Nokia 5110 Display habe ich ja bereits vorgestellt: Nun war mir das eine Spiel aber nicht genug. Ich fand noch einen FlappyBird-Klon von Huy Tr. und einen Tetris-Klon von Yo! im Internet, die beide sehr schön waren und die ich auch ganz gerne im Gerät haben wollte.

Doch schon beim Kompilieren des sehr schön gemachten TetrisDuino von Yo! war mir klar: Hier wird es Speicherplatzprobleme geben: Der Sketch verwendet 19442 Bytes (60%) des Programmspeicherplatzes. Das Maximum sind 32256 Bytes. Globale Variablen verwenden 1733 Bytes (34%) des dynamischen Speichers, 315 Bytes für lokale Variablen verbleiben. Das Maximum sind 2048 Bytes. Wenig Arbeitsspeicher verfügbar, es können Stabilitätsprobleme auftreten. Das Tetris allein reizte den Variablenspeicher schon über Gebühr aus. Wie sollte da noch Snake laufen? Das brauchte ja fürs Halten des Zustands des Speilfeld schon 20 mal 11, also 220 Zeichen Speichern, dazu kam noch mal die Speicherung des zurückgelegten Wegs der Schlange, um jeweils das Schlangenende löschen zu können. Da die Schlange maximal das ganze Spielfeld einnehmen kann bei einem perfekten Spiel, wären das nochmal 220 Zeichen. Macht zusammen 440 Bytes. Plus, was noch so alles dazu kommt.

Alleine auf dem Arduino lief Tetris wunderbar. Snake auch. Aber beide zusammen unter einen Hut kriegen? Wie anstellen?

Ich ließ es auf den Versuch ankommen, das Unmögliche zu versuchen und beide Spiele unterzukriegen und machte mich daran, den Speicherverbrauch zu optimieren, wo es ging.

Dabei habe ich ein paar Techniken und Tricks kennengelernt, die ich euch hier nicht vorenthalten will.

Am besten fangen wie bei den Techniken an, die schnell und einfach einen Erfolg bringen und wagen uns dann schrittweise an die komplizierteren und aufwändigeren Sachen.

Um es vorwegzunehmen: Ich habe es geschafft, Snake, Tetris, FlappyBird und ein Testprogramm so unterzubringen, dass alle stabil laufen, auch wenn es nicht einfach war.

Nicht unbedingt nötige Libraries rausschmeissen

Kleine unscheinbare #include <...> Statement können immens Speicher kosten. Denn häufig werden hier Module nachgeladen, die viel Speicher reservieren. Ist ein Modul nicht nötig, sollte das entsprechende #include entfernt werden.

Das gilt übrigens auch für das beliebte Serial.begin(115200); Nur durch den Aufruf wird Speicher verbraucht, denn hier wird die serielle Schnittstelle initialisiert. Wenn man nicht unbedingt etwa darüber ausgeben will, sollte das Statement rausfliegen. Oft wird Serial auch nur zum Debugging benutzt. Wird nicht mehr gebuggt: raus damit.

Lokale statt globale Variablen benutzen

Wird, wie beim Gamuino immer nur eines von mehreren Programmteilen ausgeführt, nämlich jeweils nur ein Spiel, macht es einen Unterschied, ob die Variablen lokal (also in der Funktion) oder global (außerhalb) der Funktion definiert sind. Globale Variablen nehmen immer Platz weg, lokale nur, wenn die Funktion aufgerufen wird.

So braucht ein Spiel erst Speicher, wenn es aufgerufen wird. So können sich die Spiele gemeinsamen Speicher teilen, wenn sie nicht gleichzeitg zusammen laufen (was sie ja nicht tun).

Es gibt zwei Nachtteile von lokalen Variablen. Erstens müssen diese immer an Funktionen übergeben werden, um darin manipuliert zu werden. Das ist mit globalen Variablen natürlich viel bequemer. Und zweitens - eigentlich ein Vorteil, aber ein gefährlicher - fordern lokale Variablen erst an, wenn sie gebraucht werden. Wenn dann allerdings nicht genügend Speicherplatz mehr übrig ist, weil woanders schon belegt, dann reagiert das Programm instabil: es führt einfach einen Reset aus oder reagiert komisch.

So hatte ich es bei Snake z. B. dass der String, in dem ich den Weg speicherte, ab einer bestimmten Länge nicht mehr erweitert werden konnte, weil kein Speicher mehr da war. Was dazu führte, dass nicht der Block das Schwanzende sondern irgendwo gelöscht wurde. Das sah schon sehr seltsam aus. Und beim Testen denkt man auch nicht daran, dass die Schlange 100 Glieder oder länger werden kann, geschweige man schafft solch eine lange Schlange erst gar nicht. Wenn dann doch einmal wird der Weg zum Super-Highscore jäh unterbrochen. Das ist natürlich sehr ärgerlich.

Darum: bei dynamischer Speicheranforderungen (das sind z. B. auch Strings) mit dem maximalen Speicherhunger rechnen und sich vorher Gedanken machen.

#define statt Variablen für Konstanten verwenden

Statt int btnA = 2; int btnB = 3; int btnC = 4; int btnD = 5; int btnE = 6; int btnF = 7; int btnK = 8; lieber #define btnA 2 #define btnB 3 #define btnC 4 #define btnD 5 #define btnE 6 #define btnF 7 #define btnK 8 schreiben. #define ist eine Präprozessor-Anweisung, die im Grunde nichts macht, als überall im Source-Code den ersten Teil (btnE) durch den zweiten Teil (2) zu ersetzen.

So wird aus einem Serial.println(btnA) ein Serial.println(2). Das heißt dass nur Speicher reserviert wird, wenn die Variable auch gebraucht wird, bei der Variablendefinition immer.

Besonders bei langen Werte-Listen, bei denen nicht alle Werte auch immer benutzt werden, macht das Sinn. Für Melodien habe ich z. B. in pitches.h die Frequenzen zu 89 Noten mit #define gespeichert. Benutze ich im Programm dann später nur 8 dieser 89 Noten, dann wird auch nur für 8 Noten Speicher verbraucht. Die nicht aufgeführten Noten werden ja auch nicht "ersetzt" und kommen so gar nicht zum Einsatz.

#define funktioniert natürlich nur für Konstanten. Der Wert kann zur Laufzeit nicht verändert werden. Will man das, muss man gezwungenermaßen auf Variablen zurückgreifen.

Programmspeicher statt Variablenspeicher benutzen

Mit 32 Kilobyte gegenüber 2 Kilobyte haben wir 16 mal soviel Programmspeicher wie Variablenspeicher. 2 Kilobyte Variablenspeicher sind schon sehr knapp und deshalb auch sehr kostbar.

Programmspeicher ist im Flash gespeichert. Hier liegt unser Programm, die Firmware. Auch nach dem Ausschalten ist der Speicherinhalt im Flash noch erhalten. Flashspeicher kann man beliebig auf lesen, aber Achtung, nur ca. 10'000 (bis max. 100'000) mal schreiben. Dann sind die Zellen kaputt und man kann den Arduino wegwerfen (oder die zuletzt benutze Firmware auf ewig benutzen). Beim Hochladen nach dem Kompilieren wird in den Programmspeicher geschrieben.

Variablenspeicher ist schneller SRAM. Hier kann nach belieben verschoben, addiert und manipuliert werden. Dieser Speicher nutzt sich nicht durch Schreiben ab.

Für unveränderliche Konstanten, die nur gelesen werden müssen, wäre es doch schon, diese im Flash statt im SRAM speichern zu können, wo wir doch so viel mehr davon haben.

Stringkonstanten mit F(..) in Programmspeicher auslagern

Eine super-einfach Möglichkeit, dies zu tun, ist die #define .. F("..")-Notation. Ein Präprozessor-Makro sorgt durch die Notation dafür, dass solche Konstanten im Programmspeicher abgelegt und aus diesem abgerufen werden.

Man sollte darum seinen Source-Code durchforsten und alle dort gebrauchten Konstanten auslagern. Aus Serial.print ("Beispieltext"); machen wir #define sc_Beispieltext F("Beispieltext") ... Serial.print (sc_Beispieltext); Es empfiehlt sich, die Stringkonstanten in eine eigene Datei / Tab auszulagern: rechts in der IDE in der Zeile, in der der Programmname steht, das kleine Dreieck nach unten anklicken und dann neuer Tab auswählen. Dann kann man zwischen Programm und Stringkonstanten-Tab hin und her wechseln. Braucht man eine Konstante mehrfach, wie z. B. den Programmtitel, dann kann man ihn natürlich mehrmals benutzen.

Für ganz Faule gibt es auch die Möglichkeit Serial.print (F("Beispieltext")); zu schreiben. Dazu muss man nur jeweils ein F und zwei Klammern einfügen. Man verbraucht aber so mehrmals Speicher im Programmspeicher, wenn man denselben String zweimal benutzt. Bei der #define - Lösung hingegen nur einmal.

Mein Gamuino-Code enthielt sehr viel Stringkonstanten, z. B. für die Start-Bildschirme, die ich so ruck zuck in den Programmspeicher auslagern konnte. Das allein schon hat eine Menge gebracht.

Andere Konstanten mit PROGMEM in Programmspeicher auslagern

Man kann aber auch andere Konstanten auslagern, wie uns die Arduino-Doku zu PROGMEM erklärt. Dies kann man z. B. für Array mit Bytes oder Integers anwenden. Hier gibt es allerdings kein Makro, und man muss die Definition ausschreiben, etwa: const int fx_einschalt_melody[] PROGMEM = { NOTE_C4, NOTE_C4, NOTE_D4, NOTE_B3 }; const byte fx_einschalt_duras[] PROGMEM = { 4, 4, 4, 2 }; NOTE_C4 etc. sind übrigens an anderer Stelle (pitches.h) ebenfalls bei #define definiert.

Für das Laden der Konstanten aus dem Programmspeicher in den Variablenspeicher braucht man dann eine zusätzliche Variable, in die man mit den Befehlen byte dur = pgm_read_byte_near(durations + i); int note = pgm_read_word_near(melody + i); aus dem Flash ins SRAM lädt und dann verwenden kann. pgm_read_byte_near liest ein Byte (für char, byte, uint8_t etc.), pgm_read_word_near jeweils zwei Bytes (für int, unsigned int, uint16_t etc.). Bei pgm_read_word_near ist zu beachten: hier ist der Platz des Words anzugeben, nicht die Anfangsadresse; für das 4. Word also 4 und nicht 8 (für das etwaig 8. Byte).

Die kleinste passende Variablenart wählen

Eine kleine Übersicht über die Variablenarten und wieviel Speicher sie benötigen (auf dem Arduino Uno 328P): Variablenart Speicherverbrauch Wertebereich boolean 1 Byte (!) true | false byte 1 0 ... 255 uint8_t 1 0 ... 255 char 1 -128 ... 127 int8_t 1 -128 ... 127 int 2 -32768 ... 32767 int16_t 2 -32768 ... 32767 unsigned int 2 0 ... 65535 uint16_T 2 0 ... 65535 long 4 -2,147 Mrd. ... 2,147 Mrd. int32_t 4 -2,147 Mrd. ... 2,147 Mrd. unsigned long 4 0 ... 4'294'967'295 uint32_t 4 0 ... 4'294'967'295 float 4 -3.4028235E+38 ... 3.4028235E+38 double 4 -3.4028235E+38 ... 3.4028235E+38 String 1 pro char +1 ges. Kette von chars Man sollte - ganz besonders, wenn es um ein Array mit mehreren Elementen geht - immer darauf achten, den Variablentyp so klein wie möglich und so groß wie nötig zu wählen.

Beispiel: Das Alter einer Person speichern? Unsigned int reicht bis 255 Jahre. Nur int reicht nur bis 127 und könnte ggf. in Zukunft mal knapp werden, und ein negatives Alter gibt es ja nun nicht.

Häufig reicht ein byte (0-255) und es muss kein int (-32768 ... 32767) benutzt werden. Das spart gleich mal die Hälfte des Speichers. Besonders bei Arrays summiert sich das.

Bei Tetris konnte ich z. B. 10 Bytes nur für eine Melodie einsparen, indem in die Durations als byte statt vorher als int speichere. Und da gibt es einige Melodien. const byte FX_OVER_DURATIONS[] PROGMEM = { 100, 100, 100, 100, 100, 100, 100, 100, 100, 100 }; const int FX_OVER_TONES[] PROGMEM = { NOTE_A2, NOTE_C2, NOTE_E2, NOTE_A3, NOTE_C3, NOTE_E3, NOTE_A4, NOTE_C4, NOTE_E4, NOTE_A5 };

Fallstrick: ein boolean verbraucht nicht 1 bit, sondern ein ganzes Byte

Wer jetzt allerdings meint, mit einem bit, also boolean-Array statt eines Byte-Arrays jede Menge Speicherplatz zu sparen, der irrt. Denn intern belegt jedes boolean genau 1 Byte. Da haben sich es sich die Compiler-Bauer vielleicht ein wenig einfach gemacht, denn natürlich ist der Umgang mit Bits ein wenig komplexer als mit ganzen Bytes.

Der Eintrag in der Tabelle oben ist also richtig.

Wer's nicht glaubt, kann sich den Beweis in folgendem Video anschauen, zusammen mit gesprochenen Erläuterungen und Beispielcode zu dem Obigen:



Wie man es hinkriegt, das ein Bit wirklich nur ein Bit verbraucht

Aber es hindert uns ja keiner daran, ein Byte-Array zu benutzen, um die einzelnen Bits zu speichern und zu manipulieren. Das lohnt sich natürlich nur für Arrays und nicht einzelne Bits, denn für ein einzelnen Bit müssen wir auch ein Byte anbrechen.

Aber für unser Snake-Spielfeld mit 20 mal 11 Feldern lohnt es sich schon. boolean sf[21][12]; // Spielfeld -> X=1-20; Y=1-11 // false=frei; true=Schlangenkörper verbraucht genausoviel Speicherplatz wie byte sf[21][12]; // Spielfeld -> X=1-20; Y=1-11 // false=frei; true=Schlangenkörper wie wir ja schon leidlich erfahren musste. Was wir machen müssen, ist, alle Bits zusammenzufassen in einem Byte-Array: byte sf[28]; // 20*11 = 220 bit / 8 = 28 Byte aufgerundet und dann das jeweilige Bit in dem betreffenden Byte zu manipulieren, um es dort zu speichern. Ich habe dazu zwei Funktionen geschrieben: boolean getBit (byte byteArray[], unsigned int absBitPos) { unsigned int bytePos = absBitPos / 8; unsigned int bitPos = absBitPos % 8; return (boolean) ( byteArray[bytePos] & (1 << bitPos) ); } void setBit (byte byteArray[], unsigned int absBitPos, boolean bitVal) { unsigned int bytePos = absBitPos / 8; unsigned int bitPos = absBitPos % 8; if (bitVal) { // Bit setzen byteArray[bytePos] |= (1 << bitPos); } else { // Bit löschen byteArray[bytePos] &= ~(1 << bitPos); } } setBit setzt ein Bit an einer bestimmten Position, getBit holt es wieder aus dem Speicher. Statt sf[x][y] = true; muss ich jetzt zwar setBit (sf, (y-1) * spielfeldBreite + (x-1), true); schreiben und damit die absolute Bitpostion selbst ausrechnen und übergeben, aber hey: dafür nur noch ein Achtel des Speichers zu verbrauchen ist es doch allemal wert. Das (y-1) und (x-1) rührt übrigens aus meiner menschlichen Gewohnheit, ab eins für das Spielfeld zu zählen, also nicht wundern.

Als weiteren Trick habe ich mir gedacht: statt die Laufrichtung (deren es ja vier gibt: 'r', 'l', 'd' und 'u') als char zu speichern und damit jeweils 1 Byte zu verschwenden, könnte man die vier Richtungen doch auch mit 2 Bit (=4 Zustände) sparen. Dann bräuchte man nur ein Viertel des sonstigen Speicherbedarfs von max. 220 Byte - falls es wirklich mal jemand schaffen sollte, das perfekte Spiel hinzulegen und alle Spielfelder mit seiner Schlange zu belegen.

Wie ich die Richtung in zwei Bits kodiere und wieder dekodiere, erläutere ich im nachfolgenden Video. Hier nochmal der Code dazu: boolean wegBit(char dir, boolean firstBit) { // Bitkodierung für den Weg, 2 Bit pro Direction left, right, down, up if (dir == 'r') { if (firstBit) return false; else return false; } if (dir == 'l') { if (firstBit) return true; else return false; } if (dir == 'd') { if (firstBit) return false; else return true; } if (dir == 'u') { if (firstBit) return true; else return true; } } char wegDir(boolean firstBit, boolean secondBit) { if (!firstBit && !secondBit) return 'r'; if ( firstBit && !secondBit) return 'l'; if (!firstBit && secondBit) return 'd'; if ( firstBit && secondBit) return 'u'; } ... setBit (weg, wegPos, wegBit (d, true)); wegPos++; setBit (weg, wegPos, wegBit (d, false)); wegPos++; ... dend = wegDir( getBit (weg, wegEnd), getBit (weg, wegEnd+1) );


Zum Schluss noch ein Video mit alle drei Games zusammen im Speicher und einer kleinen Vorführung der Games:



Diesmal sehe ich davon ab, den Source-Code zu veröffentlichen, weil ich nicht weiß, ob die anderen Autoren (von Tetris und FlappyBird) evtl. etwas dagegen hätten, wenn ihr Code in einem fremden Projekt bzw. auf einer fremden Website auftaucht. Darum hier nur Links zu den Originalquellen: