Array in anderes Array integrieren

[xZise]

Hallo DP,

ich möchte mein Programm effektiver machen, da es so aussieht, als würde es durch die ganzen CriticalSections zu lange blockiert, so dass sich mehrere Threads kaum lohnen (statt 17 nur 14 sekunden, bei 100% gegenüber ~60%).

Nun wie kann ich am schnellsten ein Array in ein anderes integrieren.
Was ich damit meine, ist: Ich habe zwei Arrays. Eins buffert und liefert auf wunsch gepufferte Werte zurück und das andere puffert Threadintern und wird nicht geschützt, da andere Threads nicht drauf zugreifen können.
Nun möchte ich manchmal das nach außen sichtbare Array "updaten" und die Werte erhöhen.
Es handelt sich um ein Integerarray:

Delphi-Quellcode:

for j := 0 to High(throws) do
  FThrows[j] := FThrows[j] + throws[j];

Oder geht es nicht mehr schneller?

MfG
xZise

[Apollonius]

Muss das Array in einem Rutsch aktualisiert werden oder ist es erlaubt, dass zwischenzeitlich nur ein Teil des Arrays neue Werte anzeigt?

[xZise]

Hmmm es handelt sich hierbei um eine erwürfelte verteilung, d.h. es wäre gut in einem rutsch das zu machen.

MfG
xZise

[Apollonius]

Wie wird das Array denn gelesen?

[xZise]

Was meinst du damit?

Es handelt sich um ein "array of Integer".

MfG
xZise

[Apollonius]

Allgemeiner gefragt: Was "macht" das Array? Und werden daraus einzelne Werte gelesen oder immer alle?

[xZise]

Also eine Funktionbeschreibung:
Ich habe ein Programm, welches mehrere Würfe von Würfeln simuliert. Nun habe ich das multitasked desgined, so dass jeder Thread eine eigene interne Liste mit dem Ergebnissen hat (wie häufig eine Augensumme gewürfelt wurde).

Und ich habe gedacht um es schneller zu machen habe ich mehrere Listen im Ram:
Der Mainthread hat eine UNVOLLSTÄNDIGE Gesamtliste (außer wenn es fertig ist, dann ist sie vollständig).
Jeder Thread hat eine UNVOLLSTÄNDIGE Einzelliste nach außen mit CriticalSections geschützt (FThrows).
Außerdem hat jeder Thread eine VOLLSTÄNDIGE innere Liste die jede 100 Würfe einmal in die nach außen Sichtbare Liste schreibt (throws).
Und als letztes hat jeder Thread eine Kopie der nach außen Sichtbaren Liste, um ein Ersatz für die zweite Liste zu liefern, sollte sie gerade beschreiben werden.

Und ausgelesen werden alle in einem "Rutsch" aber naürlich einzeln.

MfG
xZise

[Apollonius]

Und wer greift wann wie auf die Listen zu? Wann wird z.B. FThrows von außen verwendet?

[xZise]

Ich polle alle 130 ms oder so auf FThrows zu.
Auf throws wird sehr häufig zugegriffen (Ich würde sagen < 1 ms).

So wie es aussieht, sieht es sehr schlecht aus :( Ich glaube ich werde noch ein neuen Thread aufmachen mit dem Gesamten Sourcecode, weil jetzt ist es auf einen Dualcore mit 2 Threads langsamer als mit einem.

MfG
xZise

[SirThornberry]

anstelle der Schleife würde ich move verwenden und das Array komplett kopieren.

[xZise]

Zitat:

Zitat von SirThornberry

anstelle der Schleife würde ich move verwenden und das Array komplett kopieren.

Also inzwischen hat sich das dahingehend verändert, dass es nur kopiert wird, statt ergänzt.
Und dort bringt move kaum etwas (wenn überhaupt).

MfG
xZise

[Apollonius]

Meine Frage bezog sich eigentlich darauf, wer, also welche Threads, auf die Arrays zugreifen. Wenn du es klug anstellst, kannst du die Geschwindigkeit verbessern, indem du statt der Critical Section einen TMultiReadExclusiveWriteSynchronizer verwendest.

[xZise]

*schwitz* ich sollte mir wohl mal "TMultiReadExclusiveWriteSynchronizer" angucken!

Also Eigentlich greift der MainThread auf FThrows zu.
Und natürlich der Thread zu dem FThrows gehört. Ich hänge das einfach mal an! (Ich denke da besteht eindeutig optimierungspotential)

MfG
xZise

[Apollonius]

Du musst bedenken, dass dynamische Arrays in Delphi referenzgezählt werden, sodass du nicht einfach zuweisen kannst.
In deinem Code sind deutlich zu viele Critical Sections. Bedenke: Wenn nur ein Thread eine "einfache" Variable (z.B. einen Integer) beschreibt und alle anderen nur lesen, brauchst du gar keine Locks.

Ich würde ein neues Design vorschlagen: Du hast zwei globale Arrays. Eines ist enthält die gesamte bisherige Wurfstatistik. Auf das andere greifen alle Threads zu. Dazu musst du nur das Inc durch ein InterlockedIncrement ersetzen.
Im Timer tust du Folgendes: Ein drittes, lokales Array füllst du mit Nullen. Dann tauschst du dieses Array mit dem, auf das die Threads zugreifen, aus. Somit fangen die Threads wieder bei Null an zu zählen. Dann nimmst du das alte Array und addierst dessen Werte auf die globale Statistik. Aus diesem Array kannst du nun alle Daten abgreifen, ohne die Methoden der einzelnen Threads bemühen zu müssen.
Eine Skizze:

Delphi-Quellcode:

//Formular
WurfStatistik: TThrows;
//global
AktiveWuerfe: TThrows;

//Im Thread
//...
InterlockedIncrement(AktiveWuerfe[thrown - FCubesCount]);

//Im Timer
LokalesArray1 := AktiveWuerfe;
//Delphi erledigt das Nullen
SetLength(LokalesArray2, ArrayLaenge);
AktiveWuerfe := LokalesArray2;
Add(WurfStatistik, LokalesArray1);
//In Wurfstatistik sind jetzt alle vergangenen Würfe
//...

Und plötzlich kommen wir ohne Locks aus...

[xZise]

Rein hypothetisch:

Zitat:

Zitat von Apollonius

[...]

Delphi-Quellcode:

[...]
LokalesArray1 := AktiveWuerfe;
//Delphi erledigt das Nullen
SetLength(LokalesArray2, ArrayLaenge);
AktiveWuerfe := LokalesArray2;[...]

[...]

Was passiert, wenn jetzt beim SetLength ein Thread AktiveWürfe verändert?

Und können alle Threads auf AktiveWuerfe zugreifen, oder ist AktiveWuerfe threadspezifisch?
Und Setlength() nullt alle Werte? Auch wenn die Länge sich nicht ändert? Und das ist schneller als FillChar?
Und könnte man statt über LA2 einfach SetLength(AW) machen?
Und das "dritte lokale Array" ist LA1?

MfG
xZise

[Apollonius]

LokalesArray2 ist, wie der Name andeutet, eine lokale Variable. Es wird also einfach ein neues Array mit Nullen initialisiert. Und AktiveWuerfe springt nahtlos von einem Array zum anderen um.

Mir fällt allerdings gerade ein, dass es doch nicht so ganz nahtlos ist. Wenn du eine Korrektur gestattest:

Delphi-Quellcode:

Wurfstatistik,
AktiveWuerfe,
InaktiveWuerfe: TThrows;  //alle gleichzeitig initialisiert

procedure AddAndNull(var AThrows : TThrows; var AAdd : TThrows); //Du darfst hier übrigens auch const statt var verwenden
var
  i : Integer;
begin
  if Length(AThrows) >= Length(AAdd) then
  begin
    for i := 0 to High(AAdd) do
    begin
      AThrows[i] := AThrows[i] + InterlockedExchange(AAdd[i], 0); //!
    end;
  end;
end;

//Im Timer
//Das sieht hässlich aus, bewirkt aber lediglich, dass AktiveWuerfe und InaktiveWuerfe ausgetauscht werden
Integer(InaktiveWuerfe) := InterlockedExchange(Integer(AktiveWuerfe), Integer(InaktiveWuerfe)); 
AddAndNull(Wurfstatistik, InaktiveWuerfe);

Mit diesem Code ist gewährleistet, dass kein Wurf verlorengeht. Das Problem war vorher, dass ein Thread auch kurz nach dem Aktualisieren von AktiveWuerfe auf das alte Array zugreifen kann. Dieses Problem wird nun umgangen, da das Inkrementieren dann entweder vor der entsprechenden Runde in AddAndNull geschieht oder vor dem Inkrementieren das entsprechende Feld von InaktiveWuerfe auf 0 gesetzt wird und das Inkrementieren so beim nächsten Mal gezählt wird.

[xZise]

Genau das Problem sah ich auch, wunderbar, jetzt müsste ich es nur umsetzten.

Aber eine Frage: Kann ich irgendwie das globale array umgehen? Weil es wird ja immer empfohlen keine Variablen global zu deklarieren (du meinst, wahrscheinlich den var Teil oder?).

Ich dachte daran, dass jeder Thread ein Zeiger auf das array bekommt. Würde doch genauso sein?

[edit]Irgendwie will das InterlockedExchange nicht. Und zwar meint der Debugger, das die Parameter nicht übereinstimmen. Müsste es nicht [i]PInteger(AAdd) heißen? Das tut es auch nicht, weil TThrows ein array of Int64 ist! Aber was mir aufgefallen ist, dass er b zurückgibt?! Aber da wäre ja immer 0![/edit]

MfG
xZise

[Apollonius]

Ja, da ist mir ein Fehler unterlaufen. Du könntest entweder AktiveWuerfe und InaktiveWuerfe als array of Integer deklarieren - wenn das Timer-Intervall kurz genug ist, sollte es nicht zu Überläufen kommen - oder eine andere Funktion verwenden:

Delphi-Quellcode:

//Ersetzt Target durch Value und gibt den alten Wert von Target zurück
function InterlockedExchange64(var Target: Int64; const Value: Int64): Int64;
asm
  push ebx
  push esi
  mov esi, eax
  mov ebx, [ebp + 8] //ich hasse es, wenn Delphi einen Stackframe generiert, ohne mich zu fragen
  mov ecx, [ebp + 12]
  mov eax, [esi]
  mov edx, [esi + 4]
  @@Loop:
  lock cmpxchg8b [esi]
  jnz @@Loop
  pop esi
  pop ebx
end;