Speicher-Effiziente Array Strukturen

    • Studio

      Speicher-Effiziente Array Strukturen

      Vorwort
      Dieses Tutorial befasst sich mit dem schlauen Nutzen von Binär. Ich werde euch zeigen wie man einen Array mit Daten füllt, der weniger (oder gleichviel, kommt drauf an) Speicher verbraucht als ein Buffer.

      Was passiert?
      Normalerweise kann man ja eine Zelle eines Arrays nur mit einer Zahl oder String füllen. z.B.
      my_array[4,7] = 129;
      Das Verbraucht, egal wie gross oder genau der Wert ist, 4 Bytes oder 32 Bits. In einem Buffer, wenn er einen Alignement von 1 hat, verbrauche das nur einen Byte oder 8 Bit.
      Das ist nur ¼ des Speichers. Je kleiner der Wert (solange es nur Ganzzahlen sind) desto mehr effektiver Speicher wird verschwendet.

      Quellcode

      1. array: <Daten + Verschwendung> // 4 Byte / 32 Bit
      2. buffer: <Daten> // 1 Byte / 8 Bit


      - Ein [12000] x [4000] Array braucht 183 Megabytes.
      - Für Spiele die Zell-basiert sind und eine Menge von Informationen per Zelle speichern müssen wäre das absolut untragbar.
      - 5 [12000] x [4000] Arrays brauchen fast 1 Gigabyte.
      - Andere Daten müssen auch ihren Platz finden.
      - Bei etwa 1.5 Gigabytes, kommt der out-of-memory Error!

      Natürlich können Buffer genutzt werden, diese sind aber nicht so schnell.
      Und auch die Handhabung 5 Buffers gleichzeitig kann schnell zu Verwirrungen führen.

      Was kann man da tun?
      Hier kommen die Binären Konstellationen ins Spiel. So muss man Dinge nicht mehr so sehen:
      my_array[3,23] = 493;
      sondern so:
      my_array[3,23] = 1 1110 1101;
      Wie man sieht ist die Obere Zahl als Binär geschrieben worden. Auf einen Blick ist erkennbar das die Zahl 7 Bits an Speicher verbraucht.

      Eine Game Maker Zahl hat 32 Bits (von 0 bis 4'294'967'295 solange keine negativen vorkommen).
      Also warum nicht einfach 5 verschiedene Zahlen auf 32 Bits aufteilen?
      Man könnte das so darstellen:
      Zahl1: 1011 0100 1100 1101 0101 0100 1111 0110 = 723
      Zahl2: 1011 0100 1100 1101 0101 0100 1111 0110 = 53
      Zahl3: 1011 0100 1100 1101 0101 0100 1111 0110 = 20
      Zahl4: 1011 0100 1100 1101 0101 0100 1111 0110 = 15
      Zahl5: 1011 0100 1100 1101 0101 0100 1111 0110 = 6
      Schlüssel: 1011 0100 1100 1101 0101 0100 1111 0110 = 3'033'355'510

      Was In diesen Infos steht kann man selbst interpretieren.
      Die Zahlen können zwar nur eine bestimmte Grösse haben, jedoch sind sie alle in einem „Schlüssel“ gespeichert.
      Dieser Schlüssel ist eine Riesenzahl und man kann unmöglich aus ihr herauslesen, welche Unter-informationen sich in ihr befinden.

      Ja und wie bekommt man die Zahlen aus dem Schlüssel?
      Um den Schlüssel zu entschlüsseln muss man eine Reihe von Bit-berechnungen anstellen:
      Zahl1 muss ganz nach rechts rutschen damit sie nicht zu gross ist. Alle grauen 0 müssen weg.

      Quellcode

      1. Zahl1 = Schlüssel >> 22; //bitshiften der Anzahl grauen 0 auf der rechten Seite

      Bei den Zahlen 2 bis 5 müssen zudem alle oberen Zahlen ebenfalls gelöscht werden:

      Quellcode

      1. Zahl2 = (Schlüssel >> 14) & ((1 << 8)-1);

      wieder die grauen 0 wegshiften, dann um alle Bits auf der linken Seite zu löschen, einfach die Anzahl der Bits die man braucht (hier 8) auf 1 bitunden.
      Das sähe so aus:
      1011 0100 11 0011 0101 & 1111 1111 = 0000 0000 00 0011 0101;
      was wiederum so aussieht:
      1011 0100 11 0011 0101 & 0000 0000 0000 0000 0000 0000 1111 1111 = 0000 0000 00 0011 0101;
      Alle Bits die einen &0 durchgehen sind automatisch 0.

      Bei Zahl 5 kann man das Shiften auslassen und nur den & verwenden.

      Quellcode

      1. Zahl5 = Schlüssel & ((1 << 4)-1); // die zweite Berechnung ((1 << 4)-1) kann man auch ersetzen durch 15, wäre dann noch schneller.

      Beispiel in einem Script:

      Quellcode

      1. ///scr_get_zahl3(array_x,array_y)
      2. var Schlüssel = my_array[@ argument0,argument1];
      3. return ((Schlüssel >> 8) & 63);


      Wie stellt man einen Schlüssel zusammen?

      Um den Schlüssel wieder zusammen zu stellen muss man die einzelnen Zahlen zurück-shiften und dann mit dem Bitoder | zusammenrechnen.

      Quellcode

      1. Schlüssel = (zahl1 << 22) | (zahl2 << 14) | (zahl3 << 8) | (zahl4 << 4) | (zahl5);

      Auch das könnte in einem Script stehen.

      Schlusswort
      Soeben wurden aus fünf Arrays einer gemacht. Der Speicher hat sich von 0.9 Gigabytes auf 183 Megabytes reduziert.
      Ein Array lässt sich auch gut in einen Buffer konvertieren damit man ihn speichern und laden kann.
      Wahrscheinlich gibt’s da noch mehr Tricks oder Optimierungen. Könnt es ja hier mitteilen.
      Cooles Tutorial :)
      Ich liebe es zu bitshiften und bitwise Operatoren zu verwenden :D

      Habe auch mal so etwas ähnliches gemacht. Finde ich persönlich aber zu aufwändig, wenn man jetzt nicht wirklich so übergroße Arrays benutzt

      Ich bin mir nicht ganz sicher, wie es der GameMaker handhabt, aber im eigentlichen sollte ein String pro Zeichen ein Byte gebrauchen. So kann man dann ein String als ByteArray missbrauchen. Funktionen wie chr und ord sind dabei hilfreich. Blöderweise kann man beim String auch eher schlecht sagen, wie groß er sein soll, sodass eine "char Addierung" jeweils immer sehr aufwändig ist.
      Ein Bug ist mehr als nur ein Bug, es ist ein... Käfer!
      Egal, wie gut du eine Mauer baust, sie fällt um.... der klügere gibt nach :D

      Willst du mit mir auf Discord Chatten/Quatschen?
      Meine Husi's Tutorial Reihe

      Husi012 schrieb:

      Cooles Tutorial :)
      Ich liebe es zu bitshiften und bitwise Operatoren zu verwenden :D

      Habe auch mal so etwas ähnliches gemacht. Finde ich persönlich aber zu aufwändig, wenn man jetzt nicht wirklich so übergroße Arrays benutzt

      Ich bin mir nicht ganz sicher, wie es der GameMaker handhabt, aber im eigentlichen sollte ein String pro Zeichen ein Byte gebrauchen. So kann man dann ein String als ByteArray missbrauchen. Funktionen wie chr und ord sind dabei hilfreich. Blöderweise kann man beim String auch eher schlecht sagen, wie groß er sein soll, sodass eine "char Addierung" jeweils immer sehr aufwändig ist.


      Dankeschön das freut mich. :)
      Hab auch schon mit den strings rumgetestet, musste aber feststellen das Funktionen wie string_char_at eher langsam sind. Ich bin mir auch nicht im Klaren wie gross so ein String ist :P
      Tipp:
      Eine Position des Arrays kann auch mit der Funktion int64() behandelt werden, dann besitzt sie sogar 8 Bytes!
      Kommazahlen fallen weg, d.h. alle Werte werden gerundet und bleiben Ganzzahlen.
      Mir ist eben etwas eingefallen was hier zugehören würde:
      Es gibt sogenannte Flags, die in dem Fall ein boolsches (true oder false) Array darstellen.
      Du möchtest beispielsweise einfach und performant einer Variable mehrere Optionen auf einmal geben.

      GML-Quellcode

      1. options = flag_fullscreen | flag_control_wasd | flag_show_fps;

      So sähe das in etwa aus. Ziemlich kryptisch oder? Es kommt noch komischer:

      GML-Quellcode

      1. //soll das Spiel die FPS anzeigen?
      2. if (options & flag_show_fps)
      3. //zeige FPS

      Bevor ich alles aufkläre, zeige ich noch, wie man die Variablen flag_* definiert:

      GML-Quellcode

      1. flag_fulscreen = 1 << 0;
      2. flag_control_wasd = 1 << 1;
      3. flag_show_fps = 1 << 2;

      rechts siehst du diese Zahlen. Diese sind von 0 aus durchnummeriert. Du hast die Möglichkeit dies von 0 bis 63 zu machen. Bedeutet, es wäre ein Bool-Array der Größe 64.

      Oh Mann, das ist kompliziert.
      Eigentlich nicht.

      Wie Simon Gust schon von den Bits erzählt hat, geht es hier auch darum.

      Ich schaue zunächst erst einmal auf die flag_* Variablen selbst.

      GML-Quellcode

      1. flag_fulscreen = 1 << 0;

      Wenn du dir das Tutorial oben von Simon anschaust, dann kannst du dir wahrscheinlich erklären, was aus 1 << 0 wird: 1
      bei 1 << 1 wird es 2 und bei 1 << 2 4 ergeben. Durch's Shiften sieht das alles aber schöner aus und ist verständlicher. Dabei musst du dann nicht selbst rechnen.
      Wer mit dem ganzen Binären nicht klar kommt kann sich dieses Video ansehen:

      Als nächstes können wir uns die Zeile

      GML-Quellcode

      1. options = flag_fullscreen | flag_control_wasd | flag_show_fps;

      näher anschauen.
      Was wird hier gemacht?
      Ich werde hier nochmal die flag_* Variablen in Binär zeigen:
      flag_fullscreen: 00000000000000000000000000000001
      flag_control_wasd: 00000000000000000000000000000010
      flag_show_fps: 00000000000000000000000000000100
      Damit es leserlich ist, nehme ich gleich nur die ersten 8 Bits
      Der Bitwise-Or Operator also | kombiniert die Bits folgendermaßen:
      00001000 | 10000010 = 10001010
      Wenn du genau hinsiehst, dann siehst du, dass alle Einsen zusammengefasst worden sind.
      Hier sieht es noch deutlicher aus:
      00001000
      | 10000010
      = 10001010

      Kombiniert man also alle Flags mit dem | dann sieht es so aus:
      00000001
      | 00000010
      | 00000100
      = 00000111

      Mit dem & Operator kann man so eine Art Maske nutzen. Nur die Bits, die bei der Maske und dem anderen Wert 1 sind, die bleiben stehen. Alle anderen werden 0.
      Ich übertrage das jetzt in das letzte Codeschnipsel

      GML-Quellcode

      1. //soll das Spiel die FPS anzeigen?
      2. if (options & flag_show_fps)
      3. //zeige FPS

      options: 00000111
      flag_show_fps: 00000100
      00000111
      & 00000100
      = 00000100 = 4

      bei

      GML-Quellcode

      1. if (4) {/*do something*/}

      würde der Code ausgeführt werden, weil die Zahl 4 größer gleich 0.5 ist. Das ist jetzt cool, denn hätte ich flag_show_fps raus gelassen, sähe es so aus:
      00000011
      & 00000100
      = 00000000 = 0

      bei 0 wird der Code nicht ausgeführt.

      Ich hoffe das ganze war verständlich und nicht all zu lange

      PS:

      Simon Gust schrieb:

      Das Verbraucht, egal wie gross oder genau der Wert ist, 4 Bytes oder 32 Bits. In einem Buffer, wenn er einen Alignement von 1 hat, verbrauche das nur einen Byte oder 8 Bit.

      GameMaker arbeitet mit Double. Dementsprechend wären es 8 Byte :P

      Gruß Husi :)
      Ein Bug ist mehr als nur ein Bug, es ist ein... Käfer!
      Egal, wie gut du eine Mauer baust, sie fällt um.... der klügere gibt nach :D

      Willst du mit mir auf Discord Chatten/Quatschen?
      Meine Husi's Tutorial Reihe
      Hallo Husi,
      Danke dir für den informativen Beitrag über bit flaggen. Wäre natürlich gut gewesen wenn ich es in meinem Tutorial erwähnt hätte.

      Ach ja, wegen dem Datentyp, ist double-precision aber man hat halt nur die 32 bits oder wie viele (52 oder so) es sind.
      Mit der Funktion int64, oder erst grad letztens rausgefunden, jeder binären Rechnung kann aus der float ein integer mit 64 bits gemacht werden.
      Ja, ich glaube 52bit für die Ganzzahl, aber insgesamt 64bit.
      Hier ein Wikipediaeintrag: de.m.wikipedia.org/wiki/Doppelte_Genauigkeit
      int64 hört sich ganz cool an.
      Ein Bug ist mehr als nur ein Bug, es ist ein... Käfer!
      Egal, wie gut du eine Mauer baust, sie fällt um.... der klügere gibt nach :D

      Willst du mit mir auf Discord Chatten/Quatschen?
      Meine Husi's Tutorial Reihe