Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Bitwise Operatoren - Game of Life

Werbeanzeige

viti

Frischling

  • »viti« ist der Autor dieses Themas

Beiträge: 9

  • Private Nachricht senden

1

15.08.2015, 14:24

Bitwise Operatoren - Game of Life

Hallo

Ich beschäftige mich gerade zum zweiten Mal mit Conways Game of Life. Dazu habe ich zwei Kapitel aus dem Buch "Graphics Programming Black Book" von Michael Abrash gefunden (http://www.drdobbs.com/parallel/graphics…-book/184404919). Ich weiss, dass das Buch an sich veraltet ist, aber ich finde die Optimierungsmethoden da drin teilweise extrem clever.

Ohne hier zu fest in die Details zu gehen: In einem ersten Versuch speichert Abrash die Zellen aus dem Game of Life in einer Bitmap aus chars. Ich habe das leicht angepasst:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9

cMap::cMap(unsigned int width, unsigned int heigth, bool wrap_edges /* = false */)
    : w{width}, h{heigth}, 
      wBytes{(w + 7 )/ 8},              /* 1 char has 8 bits -> we store 8 cells in it */
      toroid{wrap_edges}
{
    totalBytes = wBytes * heigth;
    cells = new unsigned char[totalBytes];
    memset(cells, 0, totalBytes);       /* clear all cells on construction */
}


So weit versteh ich das. Was ich nicht versteh, ist die Methode, eine Zelle als lebend und tot zu setzen:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9

void cMap::on(unsigned int x, unsigned int y) {
    unsigned char* cell_ptr = cells + (y * wBytes) + (x / 8);
    *cell_ptr |= 0x80 >> (x & 0x07);
}

void cMap::off(unsigned int x, unsigned int y) {
    unsigned char* cell_ptr = cells + (y * wBytes) + (x / 8);
    *cell_ptr &= ~(0x80 >> (x & 0x07));
}


Die beiden letzten Zeilen in beiden Methoden sind mir ein Rätsel. Ich verstehe, was die Bitwise-Operatoren machen, aber warum genau er mit diesen Operationen die richtigen Daten für die richtigen Zellen findet, geht an meinem Hirn vorbei ?(

Steef

Alter Hase

Beiträge: 492

  • Private Nachricht senden

2

15.08.2015, 15:23

Die Methoden sind nicht "extrem clever", sondern einfach nur schwer zu verstehen, zumindest in diesem Fall.

Schritt für Schritt:
  1. Setzen eines bestimmten Bits macht man mit einem OR auf eine Maske, die genau dieses eine Bit gesetzt hat.
  2. Löschen eines Bits ist ein AND mit einer Maske, die genau an der zu löschenden Stelle eine 0 hat . Das ist genau die Invertierung der Maske eins höher => ~-Operator
  3. x & 0x07 ist das selbe wie x % 8.
  4. 0x80 ist binär genau 1000 0000. Der Shift bestimmt dann das Bit innerhalb. Der Code ordnet die Zellen innerhalb eines chars also vom MSB zum LSB und das ist genau andersherum als die Chars im Array angeordnet sind.
Ganz allgemein: Benutzer einen std::vector anstelle eines dynamischen Speicherbereiches.
"Theory is when you know something, but it doesn’t work. Practice is when something works, but you don’t know why. Programmers combine theory and practice: Nothing works and they don’t know why." - Anon

Roflo

Alter Hase

Beiträge: 955

  • Private Nachricht senden

3

15.08.2015, 15:33

Zitat von »viti«

IIch weiss, dass das Buch an sich veraltet ist, aber ich finde die Optimierungsmethoden da drin teilweise extrem clever.

Lieber den Code ausdrücklich gestalten als zu "optimieren", sodass es niemand versteht.
Wie alt ist das Buch? Jeder gängige Compiler heutzutage optimiert das besser als mit solcher Bitrotze ;)

Spiele Programmierer

Alter Hase

Beiträge: 1 223

Wohnort: Deutschland Bayern

Beruf: Schüler

  • Private Nachricht senden

4

15.08.2015, 15:51

Bitweise Operatoren sind dafür tatsächlich eine gute Idee, es geht hier aber viel besser!
Du sitzt mit hoher Wahrscheinlichkeit vor einem 64 Bit Prozessor auf dem mit etwas Glück auch noch ein 64 Bit Betriebssystem installiert ist. Ohne gleich die etwas komplexeren Geschütze mit SIMD aufzufahren(128/256 Bit auf einmal), kannst du die Geschwindigkeit schon sehr deutlich verbessern in dem du nicht einzelne Bits in chars verarbeitest sondern ganze Wörter auf einmal. Das Game of Life sollte sich als Bitoperationen abbilden lassen.

Übrigens, auch wenn viele Optimierungen dort vielleicht clever sind, sind viele Informationen darauf inzwischen schlicht und ergreifend veraltet und teilweise sogar kontraproduktiv. Das Buch mag interessant sein und auch noch ein paar interessante Ideen für modenere Anwendungen enthalten, aber man sollte das definitiv neu bewerten. Es sind seit dem Erscheinen des Buchs(Der Autor hat den Text auch noch vorher geschrieben und sein Wissen noch früher erlangt) 14 Jahre vergangen und die arbeitsweise von Prozessoren und auch Compiler hat sich enorm gewandelt. In der Zeit hat sich viel getan. Wenn du also beabsichtigst deine Software schneller zu bekommen, solltest du dir eine moderne Quelle suchen. Ein paar Stichworte die damals noch fast keine Rolle gespielt haben: Cache(Cache Density, Datenorientierung), Parallelisierung, Vektorisierung(SIMD), Branch Prediction, Out-of-order execution

Anhand der Überschrift zu einem meiner Lieblingsthemen "Linked Lists"
"Primary among the strengths are: simplicity; speedy sequential processing; ease and speed of insertion and deletion;"
Das so allgemein zu sagen ist in der Praxis inzwischen schlicht und ergreifend falsch. Durch das schlechte Cacheverhalten wird das ganz schnell ganz langsam. Kontinuierliche Speicherregionen sind insgesamt fast ausnahmelos in der Geschwindigkeit überlegen.

EDIT:
Habe den Code nicht richtig gelesen. :P

Zitat

Jeder gängige Compiler heutzutage optimiert das besser als mit solcher Bitrotze ;)

Naja, in dem Fall nicht übertreiben. Also eine naive Implementierung wäre ja mit einem bool-Array ist der Compiler machtlos. Den Compiler der da irgendetwas optimiert, möchte ich mal sehen. Bei einem vector<bool> wären zwar die Bits gepackt, aber das umwandeln in Operationen auf ganzen Wörtern halte ich trotzdem für sehr unwahrscheinlich.

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »Spiele Programmierer« (15.08.2015, 16:03)

Tobiking

1x Rätselkönig

Beiträge: 1 231

  • Private Nachricht senden

5

15.08.2015, 16:54

Man darf nicht vergessen, dass Prozessoren intern parallelisieren (superskalare Architektur). Quetscht man die 8 bit zusammen verschwendet man zwar keinen platz, aber sorgt dafür das die einzelnen Bits voneinander abhängig sind. Trennt man die bits, kann der Prozessor diese gleichzeitig berechnen.

Bei Daten die komplett in Register oder Cache passen würde ich mir eher weniger Gedanken über verschwendeten Platz machen.

Hello_Kitty!

unregistriert

6

15.08.2015, 17:43

Zitat von »Steef«

Ganz allgemein: Benutzer einen std::vector anstelle eines dynamischen Speicherbereiches.

Zitat von »Roflo«

Lieber den Code ausdrücklich gestalten als zu "optimieren", sodass es niemand versteht.
Nur um dem noch die Krone aufzusetzen: Nimm Java. ;)

Zitat von »Spiele Programmierer«

Ein paar Stichworte die damals noch fast keine Rolle gespielt haben: Cache(Cache Density, Datenorientierung), Parallelisierung, Vektorisierung(SIMD), Branch Prediction, Out-of-order execution
Ich hab neulich etwas in The Zen of Assembly reingelesen, das Buch ist mit 25 Jahren sogar noch älter. In Kapitel 4 wird der Intel 8088 beschrieben - der war damals bereits 10 Jahre alt und sein Flaschenhals der Speicherbus. Das erste was dieses 1990 erschienene Buch zur Codeoptimierung auf einem Chip von 1979 zu sagen hatte war also: Instruktionen so anordnen (out of order), dass deren Ausführung mit dem Prefetch des Speichercontrollers überlappt (Parallelität, Cache).

In gewisser Weise war das alles damals sogar noch relevanter, denn man musste sich darum selbst kümmern. Heute gilt man ja schon als gut, wenn man die im Compiler und der CPU eingebauten Optimierungen wenigstens nicht aktiv verhindert. :)

viti

Frischling

  • »viti« ist der Autor dieses Themas

Beiträge: 9

  • Private Nachricht senden

7

15.08.2015, 17:51

Danke für die Erklärung, Steef.

Um das Buch etwas zu verteidigen: Das "clevere" im Bezug auf das Game of Life sind nicht die Bitwisen Operatoren hier. Das war einfach der Teil, den ich nicht verstanden habe.

Die eigentliche Optimierung liegt dann in etwa darin, nicht das ganze Feld aus Zellen zu speichern, sondern nur die lebenden Zellen in einem byte, das auch den Zustand aller Nachbarszellen enthält. Und das Game of Life ist ohne Optimierung auch auf modernen PCs nicht flüssig, wenn man gegen 800 auf 800 Zellen geht.

Aber das ein Buch, das den Pentium als das Neuste vom Neuen schildert, an sich überholt ist, ist mir schon klar 8)

Gibt's denn ein vergleichbares Buch auf neustem Stand?

Hello_Kitty!

unregistriert

8

15.08.2015, 18:02

Zitat von »viti«

Gibt's denn ein vergleichbares Buch auf neustem Stand?
Für Code(mikro)optimierung wären da die Agner Manuals und natürlich die Intel Manuals selbst. Aber die helfen natürlich nur, wenn du schon die optimale Datenstruktur gefunden hast.

Werbeanzeige

Ähnliche Themen