Entwickler-Ecke

Algorithmen, Optimierung und Assembler - 180'000 Timer laufen lassen....


Martin W - Mo 25.10.04 17:51
Titel: 180'000 Timer laufen lassen....
Also ich hab gerade folgendes Problem...

Kurze Erklärung: Ich habe unterschiedliche Ereignisse die zu unterschiedlichen Zeiten aufgerufen werden müssen. Der Sinn der da hinter steckt ist folgender: In einem Spiel kann der User z.B. ein Gebäude bauen. Da das Gebäude Zeit braucht bis es fertig ist, brauche ich einen Timer, der mir sagt "das Gebäude x ist jetzt fertig". Und von solchen Ereignissen die zu einer Zeit x initiert werden und zu einer Zeit x gestartet werden müssen habe ich bis zu 180'000 Stück.

Geplant habe ich das ganze folgendermaßen:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
type timer_execute_functions = record
                      ID_der_zu_startenden Funktion: integer;
                      Parameter_a: string;
                      Parameter_b: string;
                      Parameter_c: string;
                      Parameter_d: string;
                      Parameter_e: string;
                      Endtime: integer;
                    end;

var
  currenttimerpostion: integer = 0;
  aktionen: array of timer_execute_functions;


Ein Timer erhöht den Wert currenttimerpostion jede Sekunde um 1.


Anwendungsbeispiel:

Der User klickt auf einen Button, ab jetzt soll ein Gebäude in 500 Sekunden fertig sein. Das Array "aktionen" wird um 1 verlängert, die Werte werden ins Array geschrieben. Der Wert Endtime wird wie folgt berechnet: currenttimerpostion + 500.

Der Timer überprüft nun jede Sekunde nachdem es den Wert currenttimerpostion um 1 erhöht hat ob der Wert currenttimerpostion irgendeinem Wert Endtime entspricht. Wenn ja, wird das dazugehörige Ereigniss ausgeführt.

Allerdings funktioniert das bei 180'000 verschiedenen Records im Array nicht mehr richtig, da der PC es nicht schafft innerhalt einer Sekunde 180'000 Variablen zu überprüfen.

Wie kann ich das ganze optimieren??? Wenn ihr fragen habt, dann postet bitte!!!


jasocul - Mo 25.10.04 18:59

Vielleicht gehtst du den falschen Weg. Wenn du versuchst das ganze mit Threads zu lösen, kannst du im Thread die Variablen setzen.
Ich kann dir aber auch nicht sagen, wie ein Programm auf 180.000 Threads reagiert.


.Chef - Mo 25.10.04 19:24

jasocul hat folgendes geschrieben:
Ich kann dir aber auch nicht sagen, wie ein Programm auf 180.000 Threads reagiert.

Ähm ... gar nicht? :gruebel:


jasocul - Mo 25.10.04 19:54

Hast du es ausprobiert? :twisted:


.Chef - Mo 25.10.04 19:57

War ein Gedankenexperiment.


jasocul - Mo 25.10.04 20:04

War meine Ironie also nicht deutlich genug. Mist.
Nochmal:
Ob nun 180.000 Timer (im Sekundentakt) oder Threads ist mehr oder weniger egal. Es ist in beiden Fällen definitiv zuviel. Du solltest das Konzept deines Programms überdenken.
Ein Freund hat ein Programm geschrieben, dass einige Hundert Threads benutzt. Das ist dann aber auch schon eine heiße Maschine, damit das überhaupt einigermaßen läuft.


BenBE - Mo 25.10.04 20:05

Wieso gar nicht??? Ich glaub mal eher, der Thread Manager wird, wenn er nicht grad vorher mit ner Fehlermeldung "Ungenügende Ressourcen" mit 80% Kernel-Zeiten arbeiten ;-) Für'n Spiel also genau das Richtige, um Verzögerung zu produzieren. Dann bräuchte er in jedem Thread nur ein Sleep positionieren von einer ms und kriegt gleich seine 500 Sekunden Bauzeit :evil:

Naja, würd das eher über einen Hintergrund-Thread machen, der das Array nach Ereignissen absucht und jeweils fällige Objekte an einen Event-Handler übergibt.


AndyB - Mo 25.10.04 20:13

BenBE hat folgendes geschrieben:
Naja, würd das eher über einen Hintergrund-Thread machen, der das Array nach Ereignissen absucht und jeweils fällige Objekte an einen Event-Handler übergibt.

Das wäre wohl die idealste Lösung.


jasocul - Mo 25.10.04 20:27

Der Ansatz ist vermutlich der beste bisher. Aber ob damit auch 180.000 Objekte gut verwaltet werden können?
Schaun wir mal, was Martin dazu meint.


blackbirdXXX - Mo 25.10.04 21:05

Ähh.
Anderer Weg.
Ein Timer, der auf 2000ms (oder 1000ms) eingestellt ist, und 180.000 Variablen überprüft?
Dürfte etwas besser sein, als 180.000 Timer laufen zu lassen.


Martin W - Di 26.10.04 14:04

blackbirdXXX hat folgendes geschrieben:
Ähh.
Anderer Weg.
Ein Timer, der auf 2000ms (oder 1000ms) eingestellt ist, und 180.000 Variablen überprüft?
Dürfte etwas besser sein, als 180.000 Timer laufen zu lassen.


Sehr gut, die Idee hatte ich auch schon ;-) Die Überschrift war nur Sinngemäß gemeint!!!

Ein Timer, der auf 2000ms (oder 1000ms) eingestellt ist, und 180.000 Variablen überprüft. Genau so habe ich mir das auch gedacht.

Ich habe im Anfangsthread das ganze genau so versucht zu erklären!!! Die Überschrift war nur Sinngemäß gemeint.

Meine Idee war so:
EINE Variable

Delphi-Quelltext
1:
i: integer;                    


EIN Record

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
type timer_execute_functions = record  
                      ID_der_zu_startenden Funktion: integer;  
                      Parameter_a: string;  
                      Parameter_b: string;  
                      Parameter_c: string;  
                      Parameter_d: string;  
                      Parameter_e: string;  
                      Endtime: integer;  
                    end;


EIN Array

Delphi-Quelltext
1:
aktionen: array of timer_execute_functions;                    


EIN Timer der jede Sekunde folgendes macht

Delphi-Quelltext
1:
2:
inc(i);
checkfunc;


EINE Funtion, die sich in einem Thread befindet

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
function checkfunc: boolean;
var
  k: integer;
begin
  for k := 0 to 179999 do
    begin
     if aktionen[k].Endtime > i then
       begin
         exe_befehl(aktion[k].ID_der_zu_startenden Funktion (..und parameter));
       end;
    end;
end;



Hat jemande einen Bessern Vorschlag???

Gruß
Martin ;-)

Ach und danke für alle eure Vorschläge bis jetzt!!!


NeWsOfTzzz - Di 26.10.04 14:32

Doch einen Vorschlag hätte ich... Du machst ein objekt
type
TTrigger=class
public
count;
start[1..100];
end;

das du sagen wir mal mit 600 erstellst
var
Triggers[1..600]:TTrigger;

oncreate()
for x:=1 to 600
Triggers[x]:=TTrigger.create;

trigger[1] entspricht jetzt was du in der nächsten sekunde machen willst, trigger[600] was du in 10 minuten machen willst.

Jetzt wenn Timer ausgeführt wird:
for x:=1 to Triggers[1].count do
start(Triggers[1].start[x]);

Und wenn jetzt ein start in 500 sekunden erfolgen soll dann:
inc(Triggers[500].count);
triggers[500].start[triggers[500].count]:= ...was auch immer gestartet werden soll..

und dann evtl noch jede Minute das Triggers array um 60 aufrücken lassen..


Martin W - Di 26.10.04 20:33

Geht leider nicht, es kann sein, das um z.B. 16:14:18 Uhr mehrere Befehle gleichzeitig ausgeführt werden müssen...

Gibt es noch Vorschläge zur optimierung des Codes??? Auch ein "ist perfekt so" als Antwort wäre sehr nett...

Gruß
martin ;-)


NeWsOfTzzz - Di 26.10.04 20:49

Dann machst du halt das Trigger Objekt mit 86400 = die Anzahl Sekunden eines Tages.. Dann brauchste auch net mal "aufrücken" weil das dann sowieso den ganzen Tag abdeckt..
Und wenn du das noch für mehrere Tage brauchst dann machste das noch größer und wenn du das für noch mehr brauchst dann speicherst du halt Teile die weit in der Zukunft liegen in einer Text Datei ab


wulfskin - Di 26.10.04 20:57

Wie wärs mit einer Liste und einsortieren? Sprich, du ordnest die Liste nach Endzeiten und sortierst neue Elemente entsprechend ihrer Endzeit ein. So weisst du das immer das oberste Item an der Reihe ist und kannst zum Beispiel in einem Thread überprüfen ob es fällig ist oder nicht.

Außerdem kann ich mir kaum vorstellen das 180.000 Elemente gleichzeitig passieren. Was macht den das Spiel alles?

Mfg, Hape!


delphiDeveloper - Di 26.10.04 21:00
Titel: alternative strategie
bau dir sowas wie eine warteschlange auf, jedoch sortierst du neue Elemente sofort
in der richtigen Reihenfolge ein.
On top das Ereignis was als naechstes ausgeführt werden soll.
Dann braucht ein Timer immer nur schauen ob die Zeit für dein Element on top reif ist.


NeWsOfTzzz - Di 26.10.04 21:05

Ja die Warteschlange hab ich mir auch schon überlegt, aber erstens müsste die Warteschlange 180.000 groß sein und bei jedem Objekt das ausgeführt wird die 179.999 nachfolgenden um einen nach vorne geschoben werden.. ergo dasselbe wie direkt alle 180.000 variablen zu prüfen..


Martin W - Di 26.10.04 21:12
Titel: Re: alternative strategie
NeWsOfTzzz hat mir gerade das vorweggennommen was ich schreiben wollte ;-)

Zitat:
Außerdem kann ich mir kaum vorstellen das 180.000 Elemente gleichzeitig passieren. Was macht den das Spiel alles?


gleichzeitig ist falsch, da sind allerdings auch erst Objekte, die erst innerhalb von z.B. 10 Tagen passieren! Zum anderen - "180'000" wäre die höchstzahl der möglichen Objekte - Normalerweise arbeite ich mit einem sehr kleinen Bruchteil davon - Die Zahl 180'000 zu erreichen ist praktisch nicht möglich!!! Aber bis zu 9000 Elemente die in den Kommenden Tagen ausgeführt werden sollen ist relatistisch. Die Chache auch nur gleichzeitig auf 15'000 zu kommen ist schon sehr gering - aber mir geht es weniger um diese eine Zahl, wichtig ist nur das sie groß ist. Mir geht es darum meine Routine zu optimieren!!!

So, ich hab noch ne Frage... Wieviel Clients könnten an der INDY UDP Komponente connecten so das das Programm noch stabil läuft??? Was sagt ihr aus eigener Erfahrung dazu?


NeWsOfTzzz - Di 26.10.04 21:16

Soviele wie dein PC schafft? Nur geraten aber..


Martin W - Di 26.10.04 21:23

NeWsOfTzzz hat folgendes geschrieben:
Soviele wie dein PC schafft? Nur geraten aber..


3 Ghz Rechenleistung, 2 TB Festplatte, 1 GB RAM, Standleitung der Telekom, Windows XP SP2!

Vorschläge?


NeWsOfTzzz - Di 26.10.04 21:26

2 TB Festplatte
Mein Vorschlag: die Wahrheit sagen? ^^


Martin W - Di 26.10.04 21:33

NeWsOfTzzz hat folgendes geschrieben:
2 TB Festplatte
Mein Vorschlag: die Wahrheit sagen? ^^


sry, 1 TB... :oops:

4 Festplatten á 250 GB in Raid geschalten.


NeWsOfTzzz - Di 26.10.04 21:36

Selbst dann isses immer noch net 1 TB festplatte hehe ^^ Aber mit meinem PC hab ich mal mit nem FTP Scanner 2000 Threads/Connections gehabt und ca 200 FTP´s pro Sekunde gescannt.. Wenn ich über 2000 eingestellt habe wurde das nur langsamer ^^.. habe 2400+


Martin W - Di 26.10.04 21:39

NeWsOfTzzz hat folgendes geschrieben:
Selbst dann isses immer noch net 1 TB festplatte hehe ^^ Aber mit meinem PC hab ich mal mit nem FTP Scanner 2000 Threads/Connections gehabt und ca 200 FTP´s pro Sekunde gescannt.. Wenn ich über 2000 eingestellt habe wurde das nur langsamer ^^.. habe 2400+


Das heißt ich schaffe mit der INDY UDP Komponente ohne weiteres z.B. 3000 Clientverbindungen???


fritierte - Di 26.10.04 21:42

nur um mal ne idee einzuwerfen:

wie wärs mit ner tabelle(meinetwegen ein dynamisches array of record / objekt *schulterzuck*) in der das erstellungsdatum und die 'bauzeit' eingetragen werden. in jedem spielzug wird datum auf >= erstellungsdatum+bauzeit eines jeden elementes geprüft, bei zutreffend wird aktion ausgeführt


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
for i:=0 to count(bauliste) do
  if bauliste[i].erstellt+bauliste[i].bauzeit <= datum then
  begin
    bauliste[i].pointeraufobjekt^.baue;
    löscheelement(bauliste,i);
  end;

so würd ich so ne aufgabe zumindest machen


NeWsOfTzzz - Di 26.10.04 21:42

Du musst bedenken, das waren 2000 AKTIVE Verbindungen.. und dann hatte ich 100% cpu auslastung, wenn jetzt ein Großteil deiner Verbindungen IDLE ist, könntest du natürlich noch viel mehr schaffen.


Martin W - Di 26.10.04 21:50

NeWsOfTzzz hat folgendes geschrieben:
Du musst bedenken, das waren 2000 AKTIVE Verbindungen.. und dann hatte ich 100% cpu auslastung, wenn jetzt ein Großteil deiner Verbindungen IDLE ist, könntest du natürlich noch viel mehr schaffen.


IDLE = Verbunden, aber Cliet senden keine Befehle?

Zitat:
wie wärs mit ner tabelle(meinetwegen ein dynamisches array of record / objekt *schulterzuck*) in der das erstellungsdatum und die 'bauzeit' eingetragen werden. in jedem spielzug wird datum auf >= erstellungsdatum+bauzeit eines jeden elementes geprüft, bei zutreffend wird aktion ausgeführt


"in jedem Spielzug"... wenn ich jetzt zum Beispiel KI- Gegner hab, die im Hintergrund selbstständig was machen müssen geht des schon mal nicht mehr ;-) Aber kannst du mir deine Idee noch mal etwas genauer erklären?

Gruß und noch mal dank euch beiden!!!


delphiDeveloper - Di 26.10.04 21:53
Titel: verschiebn?
Zitat:
Ja die Warteschlange hab ich mir auch schon überlegt, aber erstens müsste die Warteschlange 180.000 groß sein und bei jedem Objekt das ausgeführt wird die 179.999 nachfolgenden um einen nach vorne geschoben werden.. ergo dasselbe wie direkt alle 180.000 variablen zu prüfen..


da wird nichts verschoben! du baust dir doch eine pointerstruktur auf und nimmst nach abarbeitung einfach die abgearbeiteten elemente raus. 180000 elemente in einer verketteten Liste sehe ich auch nicht als grosses problem.

lediglich das Einfügen in die warteschlange kostet im mittel n/2 vergleiche.


Martin W - Di 26.10.04 21:56
Titel: Re: verschiebn?
delphiDeveloper hat folgendes geschrieben:
Zitat:
Ja die Warteschlange hab ich mir auch schon überlegt, aber erstens müsste die Warteschlange 180.000 groß sein und bei jedem Objekt das ausgeführt wird die 179.999 nachfolgenden um einen nach vorne geschoben werden.. ergo dasselbe wie direkt alle 180.000 variablen zu prüfen..


da wird nichts verschoben! du baust dir doch eine pointerstruktur auf und nimmst nach abarbeitung einfach die abgearbeiteten elemente raus. 180000 elemente in einer verketteten Liste sehe ich auch nicht als grosses problem.

lediglich das Einfügen in die warteschlange kostet im mittel n/2 vergleiche.


Zitat:
mittel n/2 vergleiche

Zitat:
pointerstruktur


Kannst du mir die beiden Begriffe mal etwas näherer erklären??? Ebendso wie deine Idee!


delphiDeveloper - Di 26.10.04 22:03
Titel: Listenstruktur und aufwand
deine mimimal Liste

ROOT --> even1 22:00 --> event2 --> 22:10 --> event3 22:20 --> event4 22:30 --> NIL

einfuegen
1. Best case ganz vorne ein vergleich und fertig
2. worst case ganz hinten also n vergleiche notwendig


im Mittel also n/2

1.) schau mal beim google nach linearer suche und aufwand
2.) Listenstrukur
schau dir mal die Datenstrukturen Tlist und TObjectList in Delphi an


fritierte - Di 26.10.04 22:14

Martin W hat folgendes geschrieben:

"in jedem Spielzug"... wenn ich jetzt zum Beispiel KI- Gegner hab, die im Hintergrund selbstständig was machen müssen geht des schon mal nicht mehr ;-) Aber kannst du mir deine Idee noch mal etwas genauer erklären?


spielzug ist gleichzusetzen mit zeitfortschritt oder rundenende(bei rundenbasierter form), ich hab aber leider den post weiter vorn nicht gesehn der im prinzip das selbe macht.

die schleife kann man ja noch um status erweitern, z.B. verbleibende baudauer, ka, wie gesagt, war nur ne idee eines dummen user :?


MathiasH - Fr 29.10.04 14:55

ich hätte ne idee, wie du die Zugriffe minimieren könntest.
Jedes Element enthält neben der Zeit auch einen "link"/Pointer auf seinen Nachfolger(oder einfach dessen id). Der entscheidende Vorteil dabei ist, dass du beim einfügen neuer Elemente nur die kleinste obere bzw untere Schranke finden musst und dein Element dann (von den links her) dazwischen einfügen muss. Wo es letzendlich gespeichert wird ist ja egal, einfach ne freie stelle im array

Allerdings steigt dadurch der Speicherplatzverbrauch, aber ich denke die erheblich kleinere Zahl von Vergleich spricht für sich...

MathiasH


mimi - Sa 30.10.04 09:51

im moment plane ich auch so ein aufbau spiel.
ich dachte mir das so:

ich zeichne alle gebäude in einem DXTimer(da ich es mit delphiX erstlelen möchte)
und vordem zeichen wird geschaut ob ein gebäude fertig ist bzw. gerade gebaut wird, wenn es geade gebaut wird wird z.b. eine andre garfik angezeigt du wirst ja niemals 1000 gebäude gleichzeitig bauen sonden immer sagen wir mal 20 stück vieleicht sogar noch wenige und wenn das dann immer noch zu viele sind kann man ja auch ein maximum einbauen so und so viele gebnäude kann man dann halt bauen gleichzeitig.

Hier mal etwas code:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
zeichung der gebäude:
for i:= to Hig(gebäude) do begin
  if gebäude[i].gebaut = True then 
    GFL.DrawImage(geäude[i].x,gebäude[i].y,gebäude[i].name,gebäude[i].tex) // glf ist einie enige klasse mit der ist noch leichte ist dx anwendungen zu schreiben *G*
  else begin
    with Gebäude[i] do begin
      if bg+1 >= bgCount then begin
         bg:=0;

        inc(pa) 
       end
       else
        inc(bg)
    end;
  end;
  GFL.DrawImage(geäude[i].x,gebäude[i].y,gebäude[i].name,gebäude[i].tex)  
   
end;


erläerung:
im beispiel wird eine zeit variable hochgezählt wenn dieser count ereicht wurde, wird ein andres Baubild angezeigt aber nur wenn noch gebaut wird jetzt müsste nur noch eine if abfrage rein, wie viele baubilde ist gibt und so aber das kann man ja anpassen.


blackbirdXXX - Sa 30.10.04 10:14

[OT]@mimi: Seit wann kann man Umlaute in Variablen Namen verstecken?[/OT]


mimi - Sa 30.10.04 10:54

das war nur ein beispiel, du kannst sie ja auch austauschen gegen oe bzw. ae *G*