Spieleprogrammierung: C vs C++ - SDL vs SFML

[Nai]

Was soll die Diskussion um den Platzbedarf des Binaries überhaupt, wenn man ein Spiel programmieren möchte? Die Binary an sich belegt bei modernen Spielen nur wenige MB im RAM, im Vergleich zu den restlichen 1-8 Gigabyte an Daten ist das komplett vernachlässigbar. Davon wird auch ein Großteil von großen Objekten (Videos, Sound, Texturen, 3D-Daten, Leveldaten, KI-Daten, Logikdaten) belegt sein, so dass ein paar byte an Overhead bei diversen kleineren Objekten egal sein sollten. Deshalb sollte man lieber die 80-20 Regel (http://de.wikipedia.org/wiki/Paretoprinzip) befolgen und an dem restlichen Zeug optimeren, anstatt seine Zeit auf das Binary zu verschwenden. Außerdem bis man ein Spiel programmiert hat, was so viel Speicherplatz sinnvoll belegt, so sind schon ein paar Mannjahre an Entwicklungszeit vergangen. Deshalb braucht man bei kleineren Projekten erst gar nicht damit anfangen sich darüber auch nur irgendwelche Gedanken zu machen. Ähnlich verhält es sich mit der Rechenleistung: Man braucht sich keine Gedanken um kleinere Optimierungen oder um die Performance seiner Programmiersprache machen. Man darf nur nicht etwas extrem dummes wie eine naive Kollisionsberechnung mit n^2 Komplexität machen.

Des Weiteren: Der größte Nachteil von VTable ist m.E. nicht der höhere Speicherplatzbedarf oder die direkte höhere Laufzeit, sondern dass der Compiler die virtuellen Funktionsaufrufe nicht inlinen und dadurch auch nicht über mehrere Funktionsaufrufe vektorisieren kann, wie zum Beispiel bei:
for each Object in Vector
Oject -> VirtualFunction();
Da SIMD immer wichtiger wird bei CPUs wird kann das Vektorisieren aber für die Performance entscheidend sein.

 

[LastChosenOne]

@antred: ja, ein paar kB fallen nicht ins Gewicht, die wird man wahrscheinlich auch nicht einmal merken, aber ich möcht dann mal probieren, so klein wie möglich ein 'sinnvolles' Spiel zu programmieren. ^^

@kuddlmuddl: nochmal danke für den Link ^^
Was genau macht -OS? Ich benutz selber soweit nur -O2/-O3 und/oder -s (für Binary-Größe) und konnt auf die Schnelle nichts brauchbares finden, das mir Google hinterher geworfen hat.

Es ist ja verständlich, dass Exceptions die Binary größer machen, aber für jeden throw fast 1 kB? Das wunderte mich iwie,..

Und wer sagt denn, dass man mit Debian vielleicht nicht sogar mehr Anfangen kann als mit Windows 7?

@Nai: Das Paretoprinzip kannte ich bereits, ist (leider?) wirklich so.
Und ja, später optimieren wird wohl mehr bringen als sich über so eine Kleinigkeit Gedanken drüber zu machen.

Wie meinst du das in dem Fall, dass der Compiler die virtuellen Funktionsaufrufe nicht vektorisieren kann,..?

 

[Nai]

Die modernen Compiler erzielen in den meisten Fällen eine gute Vektorisierung nicht dadurch, dass sie innerhalb eines Schleifendurchlaufs vektorisieren, da die Vektorisierung dort oft beschränkt ist, sondern über mehrere Schleifendurchläufe hinweg. Zum Beispiel folgende Schleife:

float2 PointArrayA[Size];
float2 PointArrayB[Size];
float   Dots[Size];
for(int i=0; i< Size; i++) //  Size ist groß
      Dots[i] = dot(PointArrayA[i],PointArrayB[i]);

Hier könnte man bei Vektorisierung innerhalb eines Schleifendurchlaufs die Multiplikation des Skalarprodukts noch gut per 2er Vektoroperation durchführen, das Aufsummieren nur noch als Skalaroperation. Die modernen Prozessoren haben jedoch 8er Vektoroperationen. Dadurch wäre die Auslastung gering. Deshalb muss man Tricksen, und über mehrere Schleifendurchläufe hinweg vektorisieren. Deshalb wird der Compiler in etwa folgenden Code erzeugen wenn möglich:

float2 PointArrayA[Size];
float2 PointArrayB[Size];
float   Dots[Size];
for(int i=0; i< Size /SIMDWIDTH; i++)
{
//Load sollte so mit AVX2 Gather Instruktionen funktionieren
VectorRegisterAX = PointArrayA[i*SIMDWIDTH+SIMDLANE].x; 
VectorRegisterAY = PointArrayA[i*SIMDWIDTH+SIMDLANE].y;
VectorRegisterBX = PointArrayB[i*SIMDWIDTH+SIMDLANE].x;
VectorRegisterBY = PointArrayB[i*SIMDWIDTH+SIMDLANE].y;

VectorRegisterAXBX =  VectorRegisterAX *VectorRegisterBX;
VectorRegisterAYBY =  VectorRegisterAY *VectorRegisterBY;

VectorRegisterResult = VectorRegisterAXBX + VectorRegisterAYBY;
Dots[i*SIMDWIDTH+SIMDLANE] = VectorRegisterResult;
 // Das haut denke ich nicht so hin das Store, da es für die Gather-Lade-Instruktion keine analoge Store-Instruktion gibt
}

Durch diese Vektorisierung würde der Compiler nur noch die optimalen 8er Vektoroperationen verwenden, was ein deutlicher Performancegewinn über die 2er Multiplikation und 1er Skalaroperation wäre. Da moderne Prozessoren immer breiter werden, wird diese Art von Optimierung auch immer wichtiger. Für die Optimierung muss der Compiler allerdings die entsprechenden Funktionen inlinen, was er bei virtuellen Funktionen nicht kann. Denauso gehen übrigens moderne GPUs bei ihrer Vektorisierung vor.

 

[LastChosenOne]

@Nai: gut, dass ich nur die hälfte versteh
kann mich nächste woche mal genauer damit beschäftigen, in der Hoffnung, dass ich dann mehr davon check
aber danke

Edit:
Ähm, hab jetzt gerade etwas versucht deine Erläuterung der Vektorisierung zu verstehen - und ähm, wie soll ichs sagen,.. ich häng irgendwie überall.
Ich glaub im Groben und Ganzen versteh ichs. ^^
Also besteht der Nachteil der VTables darin, dass der Compiler die Funktionen nicht inlinen kann und dadurch auch nicht vektorisieren kann, was dazu führt, dass die Funktionen, die mit VTables aufgerufen werden langsam sind (da die 8er Vektoroperationen der neueren CPUs nicht benutzt wird) - oder hab ich irgendwas falsch verstanden,..?

Und wenn ichs richtig verstanden habe, wäre das dann nicht eigentlich ein 'Designfehler'? Dass das nicht "unterstützt" wird, bzw. über die VTables nicht möglich ist,..?

 

[asdfman]

Das ist in etwa so ein Designfehler, wie der bei den meisten Autos. Weißt schon, dass die nicht fliegen konnten und so.

 

[Nai]

Also besteht der Nachteil der VTables darin, dass der Compiler die Funktionen nicht inlinen kann und dadurch auch nicht vektorisieren kann, was dazu führt, dass die Funktionen, die mit VTables aufgerufen werden langsam sind (da die 8er Vektoroperationen der neueren CPUs nicht benutzt wird) - oder hab ich irgendwas falsch verstanden,..?

Er kann selbst bei virtuellen Funktionen mehrere aufeinanderfolgende Befehle innerhalb eines Funktionsaufrufes vektorisieren.
Er kann jedoch nicht Befehle aus zwei aufeinanderfolgenden virtuellen Funktionsaufrufen vektorisieren.

Wenn das Innere der virtuelle Funktion an sich aber bereits gut vektorisierbar ist, dann reicht die Vektorisierung innerhalb der Funktion bereits komplett aus.

Und wenn ichs richtig verstanden habe, wäre das dann nicht eigentlich ein 'Designfehler'? Dass das nicht "unterstützt" wird, bzw. über die VTables nicht möglich ist,..?

Es ist kein "Design-Fehler" in dem Sinne, da es sich Design-technisch bei dem Konzept der virtuellen Funktionen nicht vermeiden lässt. Denn auf Kosten der Performance bringen virtuelle Funktionen dem Programmierer relativ viele Vorteile. Es wird lediglich zu einem Design-Fehler, wenn ein Programmierer es an einer entscheidenden Stelle missachtet.

Kleine Anmerkung am Rande: Rekursion ist im Vergleich zur Iteration ebenfalls aus diesem Grund schlecht.

 

[asdfman]

Kleine Anmerkung am Rande: Rekursion ist im Vergleich zur Iteration ebenfalls aus diesem Grund schlecht.

Das ist zu undifferenziert, als dass ich es einfach so unkommentiert stehen lassen könnte. Bitte mal über Tail Call Optimization informieren.

 

[Nai]

Ich bezweifelte auch nicht, dass der Compiler es schafft in manchen Fällen rekursive Funktionsaufrufe hinauszuoptimieren (wie auch virtuelle Funktionsaufrufe unter diversen Bedingungen), sondern dass er eben in denjenigen Fällen, wo er es nicht schafft, nicht vektorisieren kann.

 

[Sculletto]

Und zwar stelle ich mir derzeit die Frage, was besser wäre, wenn man einfache/normale 2D und später vielleicht einmal so ein 2,5D/3D-Spiel programmieren will.
(Duke Nukem 3D ist beispielsweise ein 2,5D-Spiel, kein vollwertiges 3D)

Mal ne Frage abseits der C vs. C++ Diskussion: wozu will man eigentlich heute noch 2,5D programmieren? Das hat man doch damals nur deswegen gemacht, weil die technischen Möglichkeiten für echtes 3D nicht ausreichten. Das ist aber heute, und seit mindestens 10+ Jahren, nicht mehr der Fall.

Es sei denn, du willst von der Pike an deine eigene Grafikbibliothek, unabhängig von DirectX oder OpenGL, programmieren, dann wäre 2,5D für den Anfang vielleicht der erste Schritt. Da du aber nach SDL & co. fragst, kann man davon ausgehen, dass du derartiges nicht im Sinn hast.

Daher: entweder du programmierst in 2D, wenn es halt ein reines 2D-Spiel werden soll, oder gleich in richtigem 3D.

Zum Thema Speicherverbrauch von C vs. C++, da hätte ich auch noch was beizusteuern. Ich habe mal auf einer Plattform entwickelt, wo nur 256 KB RAM zur Verfügung stand. Einen Compiler gab es nur für C (war so um 2010 rum). An einer Stelle habe ich dann mal ein sscanf() verwendet, da wurde das Executable gleich um satte 5 KB größer. Da habe ich mir dann lieber ne eigene String-Parsefunktion geschrieben.

 

[asdfman]

Ich bezweifelte auch nicht, dass der Compiler es schafft in manchen Fällen rekursive Funktionsaufrufe hinauszuoptimieren (wie auch virtuelle Funktionsaufrufe unter diversen Bedingungen), sondern dass er eben in denjenigen Fällen, wo er es nicht schafft, nicht vektorisieren kann.

Deshalb sagte ich, dass das Statement zu undifferenziert ist. Der Compiler "schafft" das auch nicht in "manchen Fällen", sondern es ist eine der ältesten bekannten Optimierungstechniken und die Umstände der Anwendbarkeit sind ganz klar.
Dass du im Allgemeinen recht hast, bestreite ich nicht. Aber das heißt nicht, dass der Spezialfall, bei dem TCO möglich ist eine nebensächliche Randerscheinung ist. Im Gegenteil ist er vielmehr der Regelfall.
Mich stört allein, dass du eine rekursive Definition und einen rekursiven Prozess über einen Kamm scherst und damit den falschen Eindruck erweckst, Rekursion sei grundsätzlich schlecht.

Zur Erklärung für Leute, die nicht wissen, worum es geht, erkläre ich TCO mal so simpel wie mir gerade möglich ist.

Um erst einmal den trivialen Fall aus dem Weg zu räumen. Gucken wir mal folgende rekursive Definition an:
F_n = F_n-1
F₀ = 1337
Statt F_n über einen rekursiven Prozess zu "errechnen", kann man einfach die Konstante 1337 einsetzen.

Und als weiteres, weniger triviales Beispiel, kann eine rekursive Definition auch zu einer Iteration optimiert werden:

int Fact(int n) {
    if(n == 1) return 1;
    return n * Fact(n - 1);
}

Das ist eine rekursive Definition der Fakultätsfunktion, die naiv als Rekursiver Prozess ausgeführt werden Würde. Man kann sie aber umformulieren:

#define Fact(n) G((n), 1)

int G(int a, int b) {
    if(a == 0) return b;
    return (a - 1, a * b);
}

Weil man sich in der letzten Zeile keine zusätzlichen Werte auf dem Stack merken muss, kann man das zu folgendem Pseudocode optimieren (ich kann keinen echten Assembler. Das Prinzip sollte klar sein):

Fact:
    pop a
    set b = 1
G:
    if (a == 0) return b
    set b = a * b
    dec a
    jmp G

Die Definition der Funktion G ist hier immer noch rekursiv, aber der Prozess, der bei der Ausführung abläuft ist ein iterativer Prozess.

Also: Du hast Recht, wenn du sagst, Iteration ist besser als Rekursion. Aber das übersimplifiziert und man kann dazu verleitet werden, eine völlig legitime Lösung zu verwerfen, weil man die Iteration auf den ersten Blick übersieht.

 

[LastChosenOne]

Mal ne Frage abseits der C vs. C++ Diskussion: wozu will man eigentlich heute noch 2,5D programmieren?

Es gibt immernoch 2,5D-Spiele, wie z.B. Sims
abgesehen davon, dass ich mich erst noch herantasten möchte und da 2,5D evtl. leichter zu erlernen wäre als 3D.

 

[Sculletto]

Es gibt immernoch 2,5D-Spiele, wie z.B. Sims
abgesehen davon, dass ich mich erst noch herantasten möchte und da 2,5D evtl. leichter zu erlernen wäre als 3D.

Da du dir nicht selbst eine Grafikbibliothek programmieren möchtest, sondern auf eine fertige Bibliothek wie SDL zurückgreifen willst, ist es das mit ziemlicher Sicherheit nicht. Du musst ja nichts weiter machen als die Objekte in der 3D-Szene zu modellieren, die Umrechnung in Bildschirmkoordinaten erledigt SDL bzw. das davon verwendete OpenGL.

EDIT: mir ist gerade aufgefallen, dass das so gar nicht stimmt, dass SDL OpenGL verwenden würde. SDL bietet lediglich eine Unterstützung für OpenGL an, indem es Funktionen bereitstellt, um OpenGL zu initialisieren oder beim Double-Buffering zwischen den Puffern umzuschalten, und ist ansonsten von OpenGL völlig unabhängig. Du könntest also tatsächlich SDL dazu benutzen, eine eigene Grafik-API z.B. für 2,5D zu implementieren. Die Frage ist halt nur, wie sinnvoll das wäre. Da dein Fokus auf der Spieleentwicklung liegt und nicht auf der Entwicklung von Grafikschnittstellen, wäre es sicherlich sehr viel sinnvoller, eine bereits existente und praxiserprobte Schnittstelle wie OpenGL oder DirectX zu nutzen.

 

[LastChosenOne]

@Sculletto: Es wäre soweit ja die Möglichkeit gewesen, SDL oder SFML zu benutzen, wobei SFML über OpenGL läuft (man soll irgendwie umstellen können zwischen Software- und Hardware-Rendering mit OpenGL).

es wäre soweit eine Überlegung gewesen, wenn 2,5D leichter zu Implementieren wäre als 3D.

 

[Sculletto]

es wäre soweit eine Überlegung gewesen, wenn 2,5D leichter zu Implementieren wäre als 3D.

Wenn du deine eigene Grafikschnittstelle programmieren müsstest/wolltest, dann wäre 2,5D vermutlich einfacher als 3D. Aber da es für 3D bereits fertige Schnittstellen gibt, in Form von OpenGL und DirectX, ist der einfachste Weg sicherlich der, einfach auf diese zurückzugreifen.

 

[Zweipunktnull]

@Nai

Wie gut funktioniert die automatische Vektorisierung denn überhaupt in der Praxis? Ist der Compiler da halbwegs gut drin oder klappt das nur in den trivialsten Fällen? Ich frage, weil ich immer recht große Performance-Steigerungen bekomme, wenn sich SSE-Instruktionen von Hand in meine Algorithmen einbaue. Da sind dann typischerweise Steigerungen um den Faktor 3 drin, also ziemlich nahe am optimalen Faktor 4 (bei der Arbeit mit vier 32 Bit Werten in 128 Bit Registern). So schön das einerseits für mich ist, bedeutet es andererseits, dass der Compiler von selbst da praktisch gar nichts macht. Da stellt sich mir schon die Frage, ob diese automatische Vektorisierung in der Praxis überhaupt zu gebrauchen ist, da sie sich anscheinend (?) auf triviale Fälle beschränkt.

 

[asdfman]

So schön das einerseits für mich ist, bedeutet es andererseits, dass der Compiler von selbst da praktisch gar nichts macht. Da stellt sich mir schon die Frage, ob diese automatische Vektorisierung in der Praxis überhaupt zu gebrauchen ist, da sie sich anscheinend (?) auf triviale Fälle beschränkt.

Da stellt sich mir die Frage, ob du deinen Compiler bedienen kannst.

https://gcc.gnu.org/onlinedocs/gcc-4.9.1/gcc/i386-and-x86-64-Options.html#i386-and-x86-64-Options

 

[Nai]

Also: Du hast Recht, wenn du sagst, Iteration ist besser als Rekursion. Aber das übersimplifiziert und man kann dazu verleitet werden, eine völlig legitime Lösung zu verwerfen, weil man die Iteration auf den ersten Blick übersieht.

M.E. immer noch nicht, denn es gibt noch weitere Probleme:
-In diesem Fall bist du auf deinem Compiler angewiesen, dass er dir die Rekursion in eine Interation umformt. Generell kann man jedoch nie 100 prozentig sicher sein, ob der Compiler das jetzt gerade erkennt und für sinnvoll hält diese Optimierung zu verwenden. Hier darf man sich dann im Assembly nachschauen, was dann wiederum ein gefriggel ist.
-Du bist bei Veränderungen des Codes immer daran angewiesen, dass die Tail-Rekursion erhalten bleibt. Bei einfacheren Sachen mag das ja noch gut Funktionieren, aber bei komplexeren Problemen verliert man m.E. leicht die Übersicht.Da ist es besser, dass man es gleich iterativ programmiert, denn da wird es auf jedenfall iterativ in Maschinencode umgesetzt.
-Viele Optimierungen bei der Vektorisierung von nicht komplett datenparallelen Problemen beschäftigen sich damit, wie man die Schleifenstrukturen umformt um die SIMD-Effizienz zu erhöhen (siehe zum Beispiel das GPU Paper hier: https://mediatech.aalto.fi/~timo/publications/aila2009hpg_paper.pdf CPU-Optimierung sollte allerdings analog funktionieren). Diese Kontrolle über die Schleifenstrukturen hat man bei einem rekursiven Programmcode nicht mehr.

@ Zweipunktnull
Tut mir leid, ich kann dazu keine großen Erfahrungswerte liefern, da ich mich selbst nur mit GPU-Optimierung befasst habe. Allerdings habe ich aus eigenem Interesse ein paar Artikel bezüglich Vektorisierung gelesen und ein paar Praktikavortärge an der Uni diesbezüglich gehört. Bei letzteren schien sie ebenfalls nicht so gut zu funktionieren und vor allem schien es relativ chaotisch zu sein, ob der Compiler ein Problem jetzt vektorisiert hat oder nicht. Allerdings will ich dabei ein Versagen der entsprechenden Studenten nicht ausschließen.

Auf Grund von dem was ich gelesen habe, kann ich die allerdings folgende Tipps geben. Es tut mir leid, falls die komplett trivial sind, aber evtl kannst du damit etwas anfangen:
Ein Problem bei der Vektorisierung ist, dass der Compiler einen hohen Instruction Level Parallelism (ILP) für die Vektorisierung benötigt. Da ist es ersteinmal interessant anzumerken, dass er Load und Rechen-Instruktionen abgesehen von direkten Abhängigkeiten belieibig untereinander vertauschen und damit auch vektorisieren kann. Allerdings darf er eine Load-Instruktion mit einer Store-Instruktion oder zwei Store-Instruktionen untereinander nur dann vertauschen, wenn er absolut definitiv sicher ist, dass sich die Instruktionen auf unterschiedliche Addressen beziehen. Dies Aufzulösen ist gerade bei Stack-Variablen schwierig, vor allem, da hier potentiell Zeiger-Aliasing auftreten kann. (z.B. *PointerA[1] = &Array[0], *PointerA[0] = &Array[1]). Dafür gibt es im CPP extra das restrict-Schlüsselwort, womit man dem Compiler sagen kann, dass es eben kein Aliasing gibt. In diesem Fall sollte er das ganze - zumindest soweit die Theorie - wegen dem höheren ILP viel besser vektorisieren können. Aus einem ähnlichen Grund, kann es auch vorteilhaft sein OpenCL zu verwenden. Denn hier ist der ILP durch das Programmiermodell und das Speicherzugriffsmodell relativ gut definiert, so dass die Compiler gut vektorisieren können.

Des Weiteren sollen diverse Compiler besser und diverse Compiler besser für die Vektorisierung sein. So sind die Intel C/CPP-Compiler meines Wissenstands nach am besten, während der Microsoft C/CPP-Compiler nur mittelmäßig sind. Wie es mit den Open-Source Compilern ausschaut, weiß ich nicht. Ebenso ist der Intel-OpenCL-Compiler extrem gut.