[El Tocho]

Hey ,

ich bin seit einiger Zeit dabei ein Programm zu schreiben, in welchem ich Listen mit teilweise mehreren millionen Objekten nutze. Diese Objekte sind alles selbst erschaffene Klassen, wobei es nur 22 unterschiedliche Klassen gibt, welche dann beliebig oft in einer Liste auftauchen. Das nutzen dieser Listen an sich ist kein Problem, allerdings benötigt das Programm unglaublich viel Zeit um Eintragungen einer Liste zu löschen oder neue hinzuzufügen.

Quellcode ist folgendermaßen aufgebaut (Sinngemäß in Textform):

Das ganze ist ein Kampfsimulator für ein Spiel.

- Es werden 2 Listen angelegt und mit unterschiedlichen Objekten aus 22 einzelnen Klassen gefüllt (Raumschiffen), teilweise bis zu 5.000.000 Eintragungen pro Liste
- Diese Eintragungen werden jede einzeln abgefragt und "interagieren" mit jeweils einem anderen Objekt der jeweils anderen Liste (Die Raumschiffe aus der ersten Liste greifen die Raumschiffe aus der zweiten Liste an)
- Der Schaden der einzelnen Schiffe wird ausgewertet, und zerstörte Raumschiffe werden aus der Liste gelöscht.

Während der mittlere Teil, der "Kampf" innerhalb von sekunden abläuft, warte ich bei dem Befüllen der Listen, und dem Löschen der Raumschiffe nach dem Kampf zum Teil über 1ne Minute.
Und das obwohl während dem Kampf komplexe Kampfabläufe berechnet werden wie z.B. Bonusangriffe (ein Raumschiff darf mehrmals angreifen), Schutzschilde, Schutzschildregeneration, Hüllenschaden, angriffsbonus usw.

Hat jemand eine Idee wie ich das Löschen/Beschreiben der beiden Listen beschleunigen könnte?

mfg
El

[Marthog]

Ich vermute, du verwendest List<>.
Setze mal vor dem Einfuegen capacity auf die Anzahl eingefuegter Raumschiffe, dann muss das Array nicht zwischendurch vergroessert werden.

Beim loeschen loeschst du wahrscheinlich auch jedes einzeln. Das fuehrt aber dazu, dass alle Nachfolgenden um eine Stelle aufgerueckt werden. Da das bei jedem Einfuegevorgang passiert, hast du quadratische Laufzeit (O(n^2)), was bei n=5M eine ganze Menge ausmacht. Verwende stattdessen RemoveAll, denn das geht nur einmal durch die Liste (O(n)). Du kannst auch das letzte Element der Liste an die gerade freigewordene Stelle kopieren und dann das letzte entfernen.

[El Tocho]

Hat beides sehr geholfen, das Programm läuft jetzt um ein vielfaches so schnell, danke dir

Edit:
Jetzt muss ich doch nochmal nachfragen^^ :
grade das mit dem Löschen, das bislang mit Abstand am längsten gedauert hat geht jetzt deutlich schneller. Auch das erstellen der Liste hat sich beschleunigt, wenn auch nicht so stark wie das Löschen.
Nachdem ich jetzt den gesammten Kampfablauf (einlesen, kämpfen, löschen) den gesammten Tag über optimiert habe läuft das Programm in einem bereits mehr als akzeptablem Tempo.
Allerdings bin ich häufig ein wenig perfektionistisch und versuche auch den letzten Rest an Effizienz irgendwo herauszu ziehen, weshalb ich gerade versuche auch noch das letzte Bisschen an Geschwindigkeit herauszuhohlen.
Nachdem ich mir nach jedem Schritt die jeweilige Berechnungszeit habe ausgeben lassen merkte ich, dass über 90% der Zeit für das erstellen der Listen am Anfang des Programmes drauf gingen.
Grade dem komplexen Kampfsystem gegenüber war das recht überraschend und schührte in mir die Hoffnung, dass hier womöglich noch eine Zeitersparnis herauszuhohlen sei.
Folgendermaßen sieht für das Befüllen der Listen mein Code aus:

List<Raumschiff> angreifer = new List<Raumschiff>(eingabe_angreifer_leichter_jäger + eingabe_angreifer_schwerer_jäger + [...]);
for (int count = 0; count < eingabe_angreifer_leichter_jäger; count++)
angreifer.Add(new leichter_jäger(schildbonus, hüllenbonus, angriffsbonus));
[...]

Diese For-Schleife wird für alle der verfügbaren 22 Schiffsklassen genauso abgearbeitet, und das ganze dann auch nochmal für den Verteidiger.

Und wie es scheint sind genau diese For-Schleifen mit dem .Add Befehl das, was den mit Abstand größten Zeitbedarf bei einem Programmablauf aufweißt.
Gibt es hier vielleicht auch eine elegantere Lösung? Eine die womöglich auch noch schneller abläuft?^^

ps: wie erwähnt, das Programm läuft nach der von Marthog empfohlenen Änderung bereits schnell genug, das jetzt wäre halt bloß noch das i-Tüpfelchen^^

mfg
El

[Multithread]

Probiers mal damit:
Anstelle einer Liste ein Array mit 5 Milionen Einträgen.

Raumschiff[] angreifer= new Raumschiff[5000000];
int erstepos=0;
int count=0;
for (count = erstepos; count < eingabe_angreifer_leichter_jäger+erstepos; count++)
  angreifer[count] = new leichter_jäger(schildbonus, hüllenbonus, angriffsbonus);
erstepos=erstepos+eingabe_angreifer_leichter_jäger;
for (count = erstepos; count < eingabe_angreifer_schwere_jäger+erstepos; count++)
  angreifer[count] = new schwerer_jäger(schildbonus, hüllenbonus, angriffsbonus);

Anstelle das du Elemente Löschst, fügst du einen null wert in die Liste ein. Ausserdem kannsrt du dir in 2 Variablen merken bei welchem Shiff du gerade in der Liste bist, dadurch musst du weniger schauen wie viele schiffe du am Anfang der Liste schon gelöscht hast.

Oder, sofern du mehrere Simulationen im gleichen Programmlauf machst, würde ich den Raumschiffen einen Boolschne wert 'besigt' geben und dann beim erneuten Befüllen keine neuen Objekte machen, sondern versuchen so viele bestehende Schiffe wie möglich weiter zu verwenden. Dadurch bist du schnell 2-3 mal schneller beim 2ten befüllen solange die Anzahl Schiffe nicht zu sehr variiert, und nur im absoluten Worst case langsamer als wenn du jedes Schiff neu machst.
zb. als sehr unoptimierte Variante:

int erstepos=0;
int count=0;
for (count = erstepos; count < eingabe_angreifer_leichter_jäger+erstepos; count++)
{
  if(angreifer[count] is leichter_jäger)
  {
    angreifer[count].Renew(schildbonus, hüllenbonus, angriffsbonus);
   }else{
   angreifer[count](new leichter_jäger(schildbonus, hüllenbonus, angriffsbonus));
  }
}
...

Das ist im Idealfall (gleiche Anzahl schiffe von jedem Typ) um ein vielfaches schneller als wenn du jedes mal ein neues Objekt erstellst, aber selbst im worst case nur unmerklich langsamer.
Allerdings lässt sich die Effizienz noch deutlich verbessern, zb. indem du schaust ob es später noch schiffe vom entsprechenden Typ gibt und dir merkst wo du das letzte Schiff her hast, die hilft wenn am anfang eine der zahlen, zb. eingabe_angreifer_leichter_jäger, kleiner wurde als beim ersten durchlauf, da die nachfolgenden dann dennoch auf die maximale anzahl Ihrer Schiffe zurückgreifen können.
Für weitere Obtimierungen müsstest du dir dann abseits davon Metainformationen merken, also bei welchem Eintrag fängt eine bestimmte Schiffsklasse an, dadurch könntest du die maximale Anzahl Objekte weiter verwenden (bei richtiger implementation), was sich im durchschnitt in maximaler Performance widerspiegeln würde.

Ausserdem kannst du dir überlegen die beiden Listen (angreifer und verteidiger) per Multithreading Paralell zu füllen. Dies kann je nachdem nochmals einen guten Geschwindigkeitsschub bedeuten
Was so unendlich lange dauert, ist das erstellen der Objekte, also deine bis zu 10 mio. new Einträge, das zuweisen der variablen ist dagegen vernachlässigbar.

Und äöü sowie scharfe S solltest du in C# nicht verwenden, auch wenn es geht


Poste doch sonst mal den kompletten Code als zip, da kann ich dann sehen wo man sonst so noch optimieren könnte

EDIT: Mehrthreadiges befüllen bringt nur wenig mehr Leistung auf eine normalen Rechner (VM, 6GB RAM Dual Channel 1333, i7 der ersten gen)
Das wiederverwenden der Objekte bedeutet eine Beschleunigung von bis zu 1000% gegenüber dem neu erstellen jedes Objektes, bei einem Thread. Wobei das neu zuweisen von Multithreading im geringen umfang (so 4 Threads) durchaus noch etwas mehr Performance rausholen lässt.

[Pyrokar]

Eventuell gewinnst du auch etwas, wenn du nicht drei Schleifen benutzt, um die Schiffe zu erstellen, sondern eine. Allerdings befürchte ich, dass diese Maßnahme bei der Menge erzeugter Objekte eher Rauschen ist. Interessant wär es aber allemal.
Du bestimmst erst die größte der drei Eingaben und benutzt die als Abbruchbedingung für die Schleife. Im Rumpf erzeugst du dann pro Durchgang ein Schiff von jedem Typ der noch nicht sein Limit erreicht hat.

[Multithread]

Eventuell gewinnst du auch etwas, wenn du nicht drei Schleifen benutzt, um die Schiffe zu erstellen, sondern eine. Allerdings befürchte ich, dass diese Maßnahme bei der Menge erzeugter Objekte eher Rauschen ist. Interessant wär es aber allemal.
Du bestimmst erst die größte der drei Eingaben und benutzt die als Abbruchbedingung für die Schleife. Im Rumpf erzeugst du dann pro Durchgang ein Schiff von jedem Typ der noch nicht sein Limit erreicht hat.

Das sollte Performancemässig keinen einfluss haben, eher im gegenteil, dadurch das ich nicht schauen muss wlechen Typ von schiff ich erzeuge dürften mehrere Schleifen sogar schneller sein. Ausserdem kann ich bei mehreren schleifen die Aufgaben problemlos auf mehrere Threads verteilen, was zwar auch mit einer ginge, aber dann nicht so schön aussieht


Was man auch noch machen kann: den Equatec profiler (Gratis version) drüber laufen lassen, damit siehst du welche Funktionen am längsten haben, bzw. wo wie viel Zeit verloren geht.

[El Tocho]

Tut mir leid, dass ich mich einige Tage nicht gemeldet habe, hatte ein wenig Stress^^

Danke erstmal für all die hilfreichen Tipps

Auch danke für das Angebot mal über meinen Code zu schauen, aber dann hätte ich glaube ich dieses "das hab ich selbst gemacht" Gefühl nicht mehr. Ein paar Zeilen Code oder einige Tipps von anderen übernehmen ist eine Sache, aber, dass jemand den gesammten Quellcode durchgeht und mir jede Stelle nennt die optimiert werden könnte wäre mir zu viel fremde Hilfe.
Dennoch danke für das Angebot

Einige der Tipps wie z.B. das Multithreading habe ich umgesetzt (immerhin eine gewisse Zeitersparnis hat es gebracht). Andere waren aufgrund der Aufgaben des Programms so nicht umsetzbar - dennoch danke für diese

Das Programm läuft mittlerweile alles in allem relativ zügig durch. Werde das Programm erstmal als erledigt abhacken und mich auch mal wieder meinen anderen beiden Projekten widmen, nicht, dass ich die hier noch zu sehr vernachlässige^^

Danke nochmal an alle die hier geholfen haben

mfg
El