Performance-Optimierung

[Traude]

Hallo, Ihr Hübschen und Klugen,
Ich beschäftige mich grade damit, große Gleichungssysteme mit linearen Solvern zu lösen. Dabei fallen jede Menge Hilfsroutinen an: Vektoren kopieren, Skalarprodukt berechnen, Vektor mit Matrix multiplizieren und so weiter.
Die Vektoren sind eindimensionale dynamische Arrays.

Die typische Konstruktion sieht so aus:
[pascal]

Type
   TVectorValue = Double; 
   TVectorArray = Array Of TVectorValue;
 
Function CopyVector(AVector,AResultVector: TVectorArray): Boolean;

[/pascal]

Die Vektoren müssen bereits eine gültige Länge > 0 haben, wenn sie übergeben werden.
Der Result-Vektor wird in der Funktion verändert. Es ist essentiell, dass diese Hilfsroutinen schnell sind.

Jemand hat mich mal drauf hingewiesen, dass Parameter, die nicht mit "Const" übergeben werden, kopiert werden und daher unnötig Speicher und Verarbeitungszeit brauchen. Hat es jetzt hier einen Sinn, die Vektoren als Const zu übergeben? Dynamische Arrays werden als Pointer übergeben (glaub ich). Maximal kopiert er hier nur den Zeiger, aber ich bin mir nicht sicher.

Wenn der Compiler hier den ganzen Vektor für die Hilfsroutine kopiert, wäre das ziemlich schlecht. Ich glaub das aber nicht, denn dann würde ja nie etwas zurückgegeben werden. Aber der Vektor wird ganz brav kopiert. Daher könnte ich mit "Const" hier maximal das Kopieren der beiden Zeiger sparen. Habe ich recht?
Vielen Dank im Voraus
Traude

[Hitman]

Die werden kopiert - aber du vergisst, dass dynamische arrays lediglich Pointer (mit bisschen drum herum) sind. Die eigentlich Daten kommen natürlich nicht mit auf den Stack.

[mse]

Daher könnte ich mit "Const" hier maximal das Kopieren der beiden Zeiger sparen. Habe ich recht?
Traude

Var und auch Const AFAIK sparen zudem den incref/decref Vorgang und sind deshalb vorzuziehen.

[Traude]

Dankeschön - habe es auf Const umgestellt.

[Euklid]

Hallo Traude,

dynamische Arrays werden in der Tat nur als Pointer übergeben. Es gibt bereits eine FPC-Routine zum Kopieren von dynamischen Arrays, die nennt sich copy. Beispiele:

Code: Alles auswählen

var a, b: array of ...;
 
// ...
 
a:=b; // kopiert nur den Pointer.
a:=copy(b); // legt eine vollständige Kopie von b im Speicher an. a zeigt insbesondere auf einen anderen Speicherbereich.
 
//...

Du kannst Dir also eine separate CopyVector-Routine ersparen.

Viele Grüße, Euklid

[mschnell]

Ich habe vor einiger Zeit eine paar Unterprogramme zur Matrizenrechnung gemacht, u.a. a auch Lösen eines lineare Gleichungssystems (auch mehrerer parallelr z.B. zur Matrix-invertierung).

Ist nicht extrem Performance-optimiert, funktioniert aber gut und ist Dank permanenter Pivot-Optimierung sehr stabil. Kannst Du Dir gern anschauen. (Bei der Pivot-Optimierung brauchen bei dynamischen Arrays keine Zeilen kopiert zu werden !)

Zur Performance Optimierung würde ich vorschlagen, je nach Anzahl der Prozessoren des Rechners mehrere Threads für Aktionen anzuwerfen, die Parallel ablaufen können. Das kann bei großen Systemen auf einer 8 Prozessor-Maschine mit zwei Threads pro CPU einen Faktor 8 bringen.

-Michael

[lrlr]

>Zur Performance Optimierung würde ich vorschlagen, je nach Anzahl der Prozessoren des Rechners mehrere Threads für Aktionen anzuwerfen,

oder CUDA usw. (GPU rechnen lassen)...
ber da gibts wohl nix in pascal..

die ganzen FPU erweiterungen (sse usw) müsste auch für so sachen gut geeignet sein ??

[Traude]

Wow, danke für die vielen Hinweise.

Du kannst Dir also eine separate CopyVector-Routine ersparen

Ja, klar, grundsätzlich Du hast natürlich recht. Aber wenn ich mich recht erinnere stellt Copy auch den Speicherbereich zur Verfügung, und das kann ich nicht brauchen, denn ich kopiere häufig von einem gültigen Vektor in einen anderen gültigen Vektor. Ich müßte mir die Copy-Routine erst ansehen, ob sie das auch berücksichtigt.

Ich habe vor einiger Zeit eine paar Unterprogramme zur Matrizenrechnung gemacht, u.a. a auch Lösen eines lineare Gleichungssystems (auch mehrerer parallelr z.B. zur Matrix-invertierung)

Ist nicht extrem Performance-optimiert, funktioniert aber gut und ist Dank permanenter Pivot-Optimierung sehr stabil. Kannst Du Dir gern anschauen. (Bei der Pivot-Optimierung brauchen bei dynamischen Arrays keine Zeilen kopiert zu werden !)

Super! Ich mache grade etwas Ähnliches, folgende Lineare Solver habe ich in den letzten Monaten implementiert:

[pascal]

TGaussJordanSolver = Class(TSparseSolver);
TGaussSeidelSolver = Class(TIterativeSolver); // der ODE-Solver
TConjGradSolver = Class(TIterativeSolver);  // Methode der konjugierten Gradienten
TBiCGStabSolver = Class(TIterativeSolver)

[/pascal]

Das war nicht einfach, und den BiCGStabSolver habe ich gerade vor einer Stunde zum Laufen gebracht. Das feiere ich gerade. *Luftsprung mach*

Die Dinger sind alle (bis auf den ersten) für das Lösen von großen, dünnbesetzten Matrizen gedacht. Lt. Googlecode-Suche gibt es so etwas im Internet für C/C++, Fortran, Matlab, aber nicht für Pascal. Ich hätte auch gar nichts dagegen, die Dinger herzuzeigen bzw. Open Source zu machen, wenn sie dann fertig sind.

Ich hatte nie angenommen, dass ich das überhaupt schaffe. Wenn ich ganz ehrlich bin, muss ich zugeben, dass mir irgendwo ab der Methode der konjugierten Gradienten die Theorie ziemlich schleierhaft wird. Aber nachdem ich das wieder Erwarten geschafft hatte, hat mich der Größenwahn gepackt.

>Zur Performance Optimierung würde ich vorschlagen, je nach Anzahl der Prozessoren des Rechners mehrere Threads für Aktionen anzuwerfen,

oder CUDA usw. (GPU rechnen lassen)...
ber da gibts wohl nix in pascal..

Tja, das mit den Threads sollte man machen, ja. Die C-Open-Source-Implementierungen machen das angeblich. Ich muss mir aber erstmal ansehen, ob das bei diesen Methoden überhaupt geht. Wenn sich eine Iteration aus der vorherigen berechnet geht es halt eben nicht. Und bei Threads bin ich ein Neuling.

Wenn man die GPU ansprechen will, muss man soweit ich weiß Shader verwenden (auch da bin ich ein Neuling, aber Shader sind ein Fixpunkt in meinem Programm für dieses Jahr). Aber in meinem Fall geht das Rechnen per GPU nicht, denn die Solver sind u.a. für eine Physik-Engine gedacht, und während die CPU Physikberechnungen anstellt soll die Grafikkarte zeichnen was das Zeug hergibt.
Viele Grüße
Traude