STL ungeeignet für Spieleprogrammierung?

Gleiter

Hi, vor x Jahren hatte ich mal ein Snake Clon programmiert ( wer nicht ) Ich hatte heute etwas Zeit und Lust das Programm von C nach C++ zu portieren. Um die Schlange zu verwealten benutzte ich diesmal keine eingene List sondern die aus der STL. Beide Versionen benutzen DX7.
Kann es sein das die STL langsamer ist? Das Gefühl habe ich. Was habt ihr für Erfahrungen mit der STL gemacht?

Die sollte nicht langsamer sein. Für sowas wäre aber IMHO eine queue auch besser geeignet. Oder ist bei dir jedes Körperteil der Schlange ein eindeutig bestimmtes Element, dass du wirklich verschieben musst?

DanEE

Also ich würde gar nicht mehr auf die STL verzichten wollen!
Und das die STL-Liste spürbar langsamer sein soll kann ich mir gar nicht vorstellen. Also ich habe keinen Performanceeinbruch erlitten als ich von meinen eigenen Listen auf die STL-Listen gesrpungen bin. Ganz im Gegenteil: meine Produktivität ist eindeutig gestiegen und die Zeit für Debuggingsessions um dumme Fehler in meinen LinkedLists zu finden gesunken!

spl*t

Ich hatte für mein Snake (in der Konsole ) stl::deque genommen, um einfach einen neuen Kopf setzen zu können und den Schwanz abzuhacken.
Ja, ich weiß, ich bin ekilg.

Dazu reicht ja ne queue, wie ich vorgeschlagen habe.
Ich bin nämlich auch eklig.

Ahvolon*F-Bytes*

Kommt wohl auf die STL Implementation an. Die von M$ ist doch recht negativ zu bewerten. Da ist STLPort schon ne bessere Alternative.

Kane

*ironie: true*
Ja natürlich, jeder hier in diesem Forum wäre in der Lage eine std::list oder
std::map-Implementierung hinzulegen die selbstredend performanter als die der
Compilerentwickler selbst ist.
*ironie: aus*

Ganz im ernst, die STL ist eine ausgezeichnete Lib, sehr flexibel (Templates über Templates :)) und ausgesprochen schnell.

Leute die behaupten die STL sei langsam haben sie garantiert falsch bedient!
Beispiel:
Du rechnetst nacheinander 5000 floats aus und willst sie in einem std::vector speichern. Es gibt immernoch Leute die sowas schreiben:

std::vector<float> floats;
for(int i=0; i < 5000; ++i)
    floats.push_back(Ein_Float_Bitte());

Für sowas sollte man gesteinigt werden. Einfach mal die std::vector-Docu lesen und man wird feststellen dass "floats" sich durch das push_back jedes mal neuen Speicher allokieren muß.
Ein einfaches
floats.reserve(5000);
am Anfang der Schleife würde das Problem lösen. Aber Docu lesen ist ja für Looser, da beschwert man sich lieber über die STL, die kann ja gar nicht hellsehen.

Trienco

Kane schrieb:

Einfach mal die std::vector-Docu lesen und man wird feststellen dass "floats" sich durch das push_back jedes mal neuen Speicher allokieren muß.

aber auch nur, wenn der vector von einem blindgänger implementiert wurde, der nichtmal soweit denkt, daß man vielleicht schonmal MEHR als nur platz für den einen float zusätzlich anfordern sollte. da dürfte es üblicher sein, den speicher bei jeder anforderung zu verdoppeln.

rapso

genau das ist das problem der stl. niemand weiß bei welcher implementierung man sich auf was verlassen kann. wovon man ausgehen kann das es selbstverständlich ist und für welchen sonderfall man was anderes annehmen muss.

stl ist halt eine allgemeine lösung für immerwieder kehrende probleme die zwar natürlich an sich möglichst performant gecodet wird, aber genauso wie man sich arbeit abnehmen lässt, nimmt man sich jegliche möglichkeit ein kontrolle zu haben wie sie optimiert wird.

ich würde z.b. gerne mal ne schleife schreiben wie while(container.size()!=0)... ist aber sehr viel langsammer als while(!container.empty())... was ist nun aber wenn ich while(container.size()>10) schreiben möchte? schon hört es auf mit der performance oder der abnahme der arbeit beim implementieren... (btw. ich hab diese erkenntnis dass empty schneller ist schmerzhaft selbst gemacht, aber sowas steht natürlich auch in "effective c++")

die stl ist an sich hochgeeignet für spieleprogrammierung solange man weiß wie und wofür sie genau verwendet werden darf, und wofür das nicht der fall ist.

in deinem beispiel hätte ich einen vector genummen und über myVector[bla%myVectorsizeOfThisCoolSnake] darauf indiziert, wobei bla dann der aktuelle logicdurchgang ist. geht's einfach und effektiver?

rapso->greets();

Kane

@rapso:
Dass steht schon genau fest welcher Aufruf wie lange (zumindest theoretisch braucht). Also O(1), O(n) etc.
Und dass std::list::size() O(n), also linear, ist und damit natürlich langsamer als std::list::empty() habe ich auch mal in irgend einer Doku gelesen.

Btw guter Link zu dem Thema:
http://www.tantalon.com/pete/gdc2001roundtablereport.htm

Kane

Nachtrag wegen Performance:
http://www.codecreator.net/stl_table.gif

Kane schrieb:

@rapso:
Dass steht schon genau fest welcher Aufruf wie lange (zumindest theoretisch braucht). Also O(1), O(n) etc.
Und dass std::list::size() O(n), also linear, ist und damit natürlich langsamer als std::list::empty() habe ich auch mal in irgend einer Doku gelesen.

Btw guter Link zu dem Thema:
http://www.tantalon.com/pete/gdc2001roundtablereport.htm

So logisch, wie das auf den ersten Blick scheint, ist das nicht. Die O-Notation gilt für große n, weil man nur dann konstante Faktoren vernachlässigen. In unserem Fall ist aber n = 0, was nicht sehr groß ist.

Trienco

ahh.. meine beliebte o-notation, die zwar ganz nett ist, aber einem oft irgendwie so gar nichts weiterhilft. O(n) ist besser als O(n^2)? für theoretiker schon, wenn in der praxis aber einmal der faktor 1000 und einmal der faktor 1 vorhanden wären, dann wirds in vielen "realen" fällen schon unsinnig.

soweit ich das im hinterkopf habe, ist bei der stl nichtmal vorgeben, für welchen container welche interne repräsentation als standard benutzt werden soll (aber wenigstens läßt sich das zur sicherheit sowieso angeben).

daß size allerdings so langsam ist verblüfft mich ein wenig. eigentlich hätte ich gedacht, daß size sowieso als wert im container liegt und nur bei änderung aktualisiert wird, aber nicht, daß bei jedem aufruf wieder relativ sinnlos neu nachgezählt wird. vor allem wäre empty dann ganz faul als return !_size implementiert *fg*

Die Implementierung ist zwar nicht vorgeschrieben, aber sehr wohl die Zeitkomplexität, die von den Implementierungen nicht überschritten werden darf.
size wird in aller Regel schon vorrätig gehalten, bei verketteten Listen verzichtet man allerdings oft darauf, um schneller splicen zu können.

Dein Faktor 1 und 1000 nebeneinander ist wohl eher Unsinn. Die O-Notation ist in aller Regel schon ein guter Anhaltspunkt. Nur bei n = 0 halt vielleicht nicht gerade. ;/

Trienco

Optimizer schrieb:

Dein Faktor 1 und 1000 nebeneinander ist wohl eher Unsinn. Die O-Notation ist in aller Regel schon ein guter Anhaltspunkt. Nur bei n = 0 halt vielleicht nicht gerade. ;/

und auch bei vielen anderen n nicht und spätestens bei "kritischen" stellen kann mans sowieso knicken. da dürften einige mit der gleichen komplexität wie bresenham eine linie pinseln und können trotzdem 10x schneller sein. von besonders großem n ausgehen und faktoren wegwerfen mag ja z.b. bei datenbanken noch ok sein, aber sobald n recht überschaubar wird ist der faktor in meinen augen zu wichtig, um den einfach unter den tisch zu kehren.

Na, wenn du das meinst, bitteschön.

Eine Sortierung mit n*log(n) ist mir trotzdem lieber als mit n^2. Wenn man den 2er Logarithmus (ungünstigster Fall) zugrunde legt und noch mal ganz allgemein den n*log(n) mit Faktor 4 "bestraft" (keine Ahnung wofür), lohnt er sich trotzdem schon bei nur 16 Elementen.

Aber du wirst es schon wissen...
Glaubst du die O-Notation ist ein Hirngespinnst?

Trienco

Optimizer schrieb:

Aber du wirst es schon wissen...
Glaubst du die O-Notation ist ein Hirngespinnst?

nein, ich denke die o-notation ist das typische spielzeug theoretischer informatiker, die nur zu gerne vergessen, daß sie bestenfalls eine grobe einschätzung erlaubt, weil sie einfach mal auf annahmen aufbaut, die man in der praxis vielleicht oft, aber bestimmt nicht immer vorfindet.

lohnt er sich trotzdem schon bei nur 16 Elementen.

eben, und wenn ich einen fall habe, bei dem ich schon vorher weiß, daß es nie mehr als 10 elemente sein werden? dann kann mal eben ein für große n unbrauchbarer algo deutlich besser geeignet sein. so wie man mit seinem baum fürs culling tierisch auf die schnauze fliegt, wenn man merkt, daß bis zu x-tausend tests brute-force jeden patch zu testen schneller ist. warum? reichlich overhead für den baum und ein komplexerer test, der fälle berücksichtigen muß, die einem sonst egal wären. da kann der quadtree von mir aus auch gerne log(log(n)) haben, solangs mit n trotzdem schneller läuft.

eben, und wenn ich einen fall habe, bei dem ich schon vorher weiß, daß es nie mehr als 10 elemente sein werden?

Wenn ich 10 Elemente habe, dann kann ich die Elemente auch so lange zufällig durchmischen, bis sie sortiert sind.
Jetzt wird dir gerade durch den Kopf schießen "ja lol die 10 war doch nur ein Beispiel, es kann ja auch bei 1000 noch besser sein", aber das ist in aller Regel nicht der Fall.
Die Unterschiede sind bei verschiedenen Ordnungen gigantisch und wenn du nicht gerade sehr kleine n's unter 100 und unrealistische Faktoren mit weit über 1000 annimmst (wo soll bitte Overhead herkommen, der alles aus Prinzip schon 1000mal langsamer macht?), bist du mit einer besseren Ordnung immer besser dran.

nein, ich denke die o-notation ist das typische spielzeug theoretischer informatiker

Ja, du hast keine Theorie mehr nötig. Mit deiner großen Praxiserfahrung bist der absolute Experte jetzt.

TGGC

Um nochmal zur Frage zurück zu kommen: die STL ist schnell genug für die Schlange...

Bye, TGGC (Dem beste BdT)

Jester

Und theoretische Informatiker haben ganz andere Spielzeuge...
frag doch mal elise.