Autor Beitrag
JayEff
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2971

Windows Vista Ultimate
D7 Enterprise
BeitragVerfasst: Mo 22.12.08 18:25 
In meinem Programm (Ein Spiel :mrgreen: ) werden sehr häufig Objekte vom Typ TSimpleObject aus Fear's Fear2D Engine erzeugt und wieder freigegeben. Dabei nutze ich ein dynamisches Array welches je nach Bedarf angepasst wird. Der Code sieht etwa so aus:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
{create:}  SetLength(Flyings, length(Flyings) + 1);
  Flyings[High(Flyings)].o := TSimpleObject.Create(Engine);
  with Flyings[High(Flyings)].o do

{Freigeben:}
procedure Free_Flying(Index: Integer);
var
  i: Integer;
begin
  FreeAndNil(Flyings[Index].o);
  if Index < High(Flyings) then
    for i := Index to High(Flyings) - 1 do
      Flyings[i] := Flyings[i + 1];

  SetLength(Flyings, High(Flyings));
end;


Die Objekte werden jedes Frame gezeichnet, das geschieht hier:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
  while i <= High(Flyings) do
  begin
    //Hier wird die Bewegung der objekte realisiert:
    if Flyings[i].ms - Get_ms > 0 then
      Flyings[i].o.Position.Y := 475 - (Flyings[i].ms - Get_ms) / 1583 * 465
    else
      Flyings[i].o.Position.y := Flyings[i].o.Position.Y + flyspeed * Engine.Timestep;

    Flyings[i].o.Draw(true);

    //Hier wird getestet, ob eines der Objekte gelöscht werden muss.
    if Flyings[i].o.Position.Y > 500 then
    begin
      if Flyings[i].o.Alpha > 50 then
      begin
        Timing('FAIL'); //:mrgreen: Der Spieler hatte ein ... Timing-Fail.
        ScoreTextPos := 400;
        ScoreRender := 60;
      end;
      Free_Flying(i);
    end
    else
      inc(i);
  end;


Jetzt wär das in einem Spiel natürlich sehr schön, wenn das vieel Performanter liefe und keine Ruckler erzeugen würde. Mein Kumpel hat gemeint, dass beim Zugriff auf ein Array-Element, das Array erst einmal durchlaufen wird bis der geforderte Index erreicht ist. Das wäre natürlich fatal und alles andere als performant. Ebenso frage ich mich, wieviel Zeit für's Erzeugen der Objekte drauf geht und wie das im Verhältnis zum Array steht: Meine Idee wäre nämlich gewesen, Geschwindigkeit zu Lasten von Speicher zu erkaufen, indem ich ein großes Array bereits mit fertigen Objekten fülle und nur noch Speichere, welches davon gerade gezeichnet werden muss.

Lohnt sich der Aufwand, gibt es eine bessere Möglichkeit zur Optimierung, oder ist das etwa schon halbwegs ... "gut" ?

PS: Das Spiel läuft auf 60 Frames und je nach dem, wie es gerade aussieht, kann das "Flyings" array... naja, sagen wir mal, 100 Einträge haben. Theoretisch kann man die Elemente des Arrays in 4 logische Kategorien einteilen, falls das Aufspalten auf 4 kleinere Arrays eine Option wäre.

_________________
>+++[>+++[>++++++++<-]<-]<++++[>++++[>>>+++++++<<<-]<-]<<++
[>++[>++[>>++++<<-]<-]<-]>>>>>++++++++++++++++++.+++++++.>++.-.<<.>>--.<+++++..<+.
F34r0fTh3D4rk
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5285
Erhaltene Danke: 29

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Mo 22.12.08 18:54 
Je nach dem wie häufig Free_Flying(i); aufgerufen wird, kann es sein, dass sich deine Array Größe ziemlich oft ändert. Und jeder Aufruf von setlength(); kostet jede Menge Zeit.
Vielleicht solltest du die Objekte nur als "entfernt" markieren und später löschen.
Jann1k
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 866
Erhaltene Danke: 43

Win 7
TurboDelphi, Visual Studio 2010
BeitragVerfasst: Mo 22.12.08 18:56 
Was mir an Optimierungsmöglichkeit einfallen würde:

Zitat:

if Index < High(Flyings) then
for i := Index to High(Flyings) - 1 do
Flyings[i] := Flyings[i + 1];


Anstatt jeden nachfolgenden Eintrag zu verschieben, kannst du einfach das letzte Element an die STelle des gelöschten setzen. Natürlich nur, wenn die Reihenfolge der Objekte keine Rolle spielt.


Zitat:

if Flyings[i].ms - Get_ms > 0 then
Flyings[i].o.Position.Y := 475 - (Flyings[i].ms - Get_ms) / 1583 * 465
else
Flyings[i].o.Position.y := Flyings[i].o.Position.Y + flyspeed * Engine.Timestep;


Anstatt die CPU ständig 465/1583 rechnen zu lassen, könntest du gleich 0.294 oder eine andere Näherung nehmen.
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Mo 22.12.08 19:06 
Also mit dem neuen Memorymanager ist das eigentlich kein großes Problem mehr (mehrmals SetLength aufrufen). Der MM sorgt schon dafür, das nicht ständig hin-und-her kopiert wird.

Das 'Free_Flying' ist allerdings sehr unperformant. Und dein Kumpel hat viel Phantasie. Array-Zugriffe sind sehr performant, manchmal sind sie sogar schneller als direkte Pointer-Arithmetik.

Anstelle des Arrays könntest Du eine verkettete Liste verwenden. Damit werden Löschoperationen in O(1) erledigt.

In einem meiner Projekte habe ich beim Programmstart 100.000 Objekte erzeugt und die in einer verketteten Liste vorrätig gehalten: Neue Objekte habe ich aus der Liste ausgeschnippelt und nicht mehr benötigte dadurch 'freigegeben', das ich sie in die Liste gehängt habe. Das ist schneller, als eine herkömmliche Speicherverwaltung per Create/Destroy.

_________________
Na denn, dann. Bis dann, denn.
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 3661
Erhaltene Danke: 604

Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
BeitragVerfasst: Mo 22.12.08 19:11 
user profile iconJann1k hat folgendes geschrieben Zum zitierten Posting springen:
Anstatt die CPU ständig 465/1583 rechnen zu lassen, könntest du gleich 0.294 oder eine andere Näherung nehmen.

Also wenn die CPU das jedes mal ausrechnet, hat der Compiler irgendwas falsch gemacht^^

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
Kha
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Mo 22.12.08 19:44 
user profile iconalzaimar hat folgendes geschrieben Zum zitierten Posting springen:
Anstelle des Arrays könntest Du eine verkettete Liste verwenden. Damit werden Löschoperationen in O(1) erledigt.
Würde ich auch vorschlagen, da er zumindest in den bisherigen Schnipseln ja gar keinen Random Access benötigt.

_________________
>λ=
JayEff Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2971

Windows Vista Ultimate
D7 Enterprise
BeitragVerfasst: Mo 22.12.08 20:19 
user profile iconalzaimar hat folgendes geschrieben Zum zitierten Posting springen:
In einem meiner Projekte habe ich beim Programmstart 100.000 Objekte erzeugt und die in einer verketteten Liste vorrätig gehalten: Neue Objekte habe ich aus der Liste ausgeschnippelt und nicht mehr benötigte dadurch 'freigegeben', das ich sie in die Liste gehängt habe. Das ist schneller, als eine herkömmliche Speicherverwaltung per Create/Destroy.
Klingt interesant, das wird dann vermtl. die nächste Änderung. Wird das denn einen großen Performancesprung bringen?
Eine Liste hab ich auch z.B. für die einzelnen "Zeilen" in einer Datei eingesetzt, die beim Start eingelesen werden. Zuerst hatte ich das als Array gelöst. Das schöne ist, um das ganze als Liste handlen zu können, konnte ich das einlesen als Array einfach lassen und dabei immer einen pointer auf das darauf folgende Objekt setzen, wodurch ich eine einfach verkettete Liste bekam - sind denn Listen schneller oder langsamer als Arrays, vllt. am Beispiel Array von vorn nach hinten durchlaufen im Verhältnis zu Liste von vorn nach hinten durchlaufen?

_________________
>+++[>+++[>++++++++<-]<-]<++++[>++++[>>>+++++++<<<-]<-]<<++
[>++[>++[>>++++<<-]<-]<-]>>>>>++++++++++++++++++.+++++++.>++.-.<<.>>--.<+++++..<+.
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Mo 22.12.08 21:01 
Eine Iteration ist in einem Array eigentlich immer schneller als mit einer verketteten Liste. Dafür ist sie aber auch nicht gedacht, sondern für sehr schnelle Lösch- und Einfügeoperationen. Ich hatte meine verkettete Liste auch als MRU-Cache verwendet, ansonsten kann man sowas natürlich auch mit einem Array lösen. Mir ging es um die quasi statische Alloziierung von Blöcken und eine verkürzte Freispeicherverwaltung. Und DAS hat wirklich etwas gebracht, vor allen Dingen, in Verbindung mit dem MRU-Cache.

_________________
Na denn, dann. Bis dann, denn.