string konstanten zur compilezeit durch int-konstanten ersetzen.

volkard

Nur mal so ne Idee:

Ich geh mal vom Hash weg und denke an eine Atomtabelle.
Also

char const* findOrInsert(char const* str);

gibt eine eindeutige ID aus, die zu diesem String gehört, und über die gesamte Programmlaufzeit unverändert bleibt. Dürfte über einen geeigneten Baum gelöst werden.
Entsprechend

char const* find(char const* str);

gibt nullptr zurück, wenn es den String nicht gibt.

Jetzt könnte man den str als Template-Argument benutzen und ein paar bekannte Strings anlegen und denen Template-Instanzen geben, die den str selber zurückgeben.
Und nur alle anderen werden tatsächlich gesucht.

camper

volkard schrieb:

Jetzt könnte man den str als Template-Argument benutzen und ein paar bekannte Strings anlegen und denen Template-Instanzen geben, die den str selber zurückgeben.
Und nur alle anderen werden tatsächlich gesucht.

Verstehe ich nicht so ganz. Geht es um die Suche eines Literals in einem Container, der garantiert bereits einige beim Compilieren bekannte Strings enthält?

volkard

camper schrieb:

volkard schrieb:

Jetzt könnte man den str als Template-Argument benutzen und ein paar bekannte Strings anlegen und denen Template-Instanzen geben, die den str selber zurückgeben.
Und nur alle anderen werden tatsächlich gesucht.

Verstehe ich nicht so ganz. Geht es um die Suche eines Literals in einem Container, der garantiert bereits einige beim Compilieren bekannte Strings enthält?

Könnte sein. Ich habe die Aufgabe nicht ganz verstanden und mal eine alte Überlegung in den Raum gestellt, die vielleicht zur ursprünglichen Problembeschreibung passen könnte.
Nur so als Idee. Kann sein, daß er das gar nicht braucht. Kann sein, daß ich einen Volltreffer gelandet habe. Ich weiß nicht, was er machen mag.

knivil

In Entity-Component Systemen haben Entities häufig irgendwelche Namen, die natürlich oft verglichen werden müssen. Sehr, sehr oft sind diese Namen komplett zur compile-time als Konstanten bekannt.

Und weiter ...

von Editoren angelegt werden sollen

D.h. wenn der Kompiler einige Strings zur Kompilezeit kennt, hilft dir das nicht, da nicht beide Strings fuer einen Vergleich zwingend zur Kompilezeit bekannt sind. Loesungen gibt es dafuer viele, beispielsweise einen neuen "String" zu benutzen, der zusaetzlich einen Hash-Wert verwaltet. Nur wenn dieser beim Vergleich uebereinstimmt, muss der eigentliche String verglichen werden. Aber das ist wahrscheinlich "premature optimization".

Es ist ja eigentlich egal, ob es eine Compile-Zeit-Optimierung ist oder eine Ladezeit-Optimmiereung (d.h. wenn das Spiel lädt). Letzteres würde auch vollkommen genügen, allerdings kam mir kein möglicher Ansatz in den Sinn der aus Compile-Zeit-Code wie

if(objekt.GetName() == GUID("irgendeinstring"))
{
    //foo
}

bei der Ausführung des Programms irgendwas mit diesem Codeteil macht als im Endeffekt mit den einzelnen Stellen des Strings zur Laufzeit zur rechnen (was natürlich keinen Sinn machen würde - das wäre ja wahrscheinlich langsamer als ein direkter Stringvergleich).

Ohne die Lösung mit constexpr muss hier zur Laufzeit irgendwie aus dem String ein int gemacht werden, und das kostet auf alle Fälle mehr Zeit als das ganze einfach zur Compile-Zeit direkt zu nem int zu optimieren.

objekt.GetName() kann ja direkt ein int zurückliefern. Wenn "objekt" dabei eine Entity wäre, die ich irgendwo aus ner Datei geladen hab, dann kann ich ihr ja bei der Ladezeit den passenden Hash-Wert geben und die Sache hat sich.

Ich kann die Lösung mit constexpr noch nicht ausprobieren, da ich jetzt zu faul bin die ganzen 15k Zeilen für GCC aufzusetzen (benutze Visual Studio und damit natürlich den msvc compiler, der constexpr nicht kennt), aber ich denke das sollte schon nen spürbaren Performanceunterschied machen. Diese Namensvergleiche werden ziemlich oft vorkommen, wenn diese Entitäten miteinander interagieren sollen. Bei 60FPS sind grob geschätzt zehntausende Vergleiche dieser Art denke ich normal für das Spiel, das ich im Moment anstrebe.

Die Namen der Entities können lang werden. Wenn ihr schonmal mit irgendwelchen Modding-Tools von Spielen gearbeitet habt, dann kommen euch Namen wie "level1_upperfloor_entrydoor" oder so öfters mal über die Wege. Das finde ich auch sehr sinnvoll, einfach der Lesbarkeit halber. Könnt ihr anhand des Namens ungefähr erahnen worum es sich bei der Entity handelt? Dann erfüllt es wohl seinen Zweck.

Da merkt man denke ich auch bei sehr schnellen modernen CPUs auch einen Unterschied zwischen den dutzenden char-überprüfungen (obwohl es cool wäre, wenn der Compiler bei solchen String literalen gleich 4 chars zu einem int zusammenfügt und diese dann vergleicht. Da die Teile zusammehängend im Speicher liegen sollte das doch gehen, oder?) und einem einzigen int-Vergleich.

knivil

Laufzeit irgendwie aus dem String ein int gemacht werden

Das wird einmal beim Laden des Strings gemacht, im Idealfall also beim Start des Programms. Was kuemmerts, wenn es 1sec laenger dauert?

gleich 4 chars zu einem int zusammenfügt

memcmp

Übrigens ist mir schon klar, dass es keinen Unterschied macht, dass der Test-Code mit den Entities auf meinem i5-2500k auf einem einzigen Kern jetzt mit 50,5k FPS anstatt mit 50k FPS läuft, aber bei solchen Optimierungen geht es mir ja drum die Schranke, die angibt, wie schlecht ein Gerät sein muss um mein Spiel zu spielen, noch etwas nach unten zu drücken.

Anhand der Tatsache, dass dies wirklich eine relativ triviale Optimierung ist, sobald man über constexpr Bescheid weiss (nochmals danke!), ist das denke ich eine sehr sinnvolle frühzeitige Optimierung.

knivil schrieb:

Laufzeit irgendwie aus dem String ein int gemacht werden

Das wird einmal beim Laden des Strings gemacht, im Idealfall also beim Start des Programms. Was kuemmerts, wenn es 1sec laenger dauert?

Wie stellst du dir das konkret vor? Also in Code. Ich kann mir nicht vorstellen, welche Lösung aus meinem Code von oben das ganze so hin biegt, dass nach dem einmaligen Laden des Strings auf einmal nur noch ein int ohne wenn und aber ausgespuckt wird.

Kann es sein, dass du das Pferd von hinten aufzuzäumen versuchst? Womöglich wäre dir eher damit geholfen, aus Zahlen Strings zu machen und immer die Zahlen zu vergleichen - quasi eine GetID() statt einer GetName()-Methode. Wenn du dann wirklich mal den String brauchst, kannst du damit beispielsweise in ein String-Array greifen oder so.

Das ließe sich mit X-Makros sogar ohne doppelte Datenhaltung machen, sofern alle Bezeichner auch gültige Variablennamen wären. Beispiel:

list_of_guids.inl:

DECLARE_GUID(das_ist_ein_string)
DECLARE_GUID(das_auch)
DECLARE_GUID(das_nicht)
DECLARE_GUID(aber_das_wieder)

#undef DECLARE_GUID

id_enum.hpp:

#define DECLARE_GUID(id) guid_##id,
enum guid_t {
#include "list_of_guids.inl"
  GUID_COUNT
};

extern char const *const guid_str[];

id_enum.cpp:

#define STRINGIFY_I(x) #x
#define STRINGIFY(x) STRINGIFY_I(x)

#define DECLARE_GUID(id) STRINGIFY(id),

char const *const guid_str[] = {
#include "list_of_guids.inl"
};

Benutzung dann:

#include "id_enum.hpp"

...

if(obj.GetID() == guid_das_ist_ein_string) {
  std::cout << guid_str[obj.GetID()];
}

string_to_int schrieb:

objekt.GetName() kann ja direkt ein int zurückliefern.

Juhu.

Bei 60FPS sind grob geschätzt zehntausende Vergleiche dieser Art denke ich normal für das Spiel, das ich im Moment anstrebe.

Hört sich verdammt danach an, als ob dein Spiel perfekt designt ist.

Wieso optimieren Anfänger eigentlich immer solchen Kram, anstatt mal richtig zu programmieren?