Zugriffsgeschwindigkeit auf mehrdimensionale Arrays

[xcs]

Hallo!

Ich führe numerische Berechnungen durch und bin auf folgendes Phänomen gestoßen, das ich mir auf Anhieb nicht gleich erklären kann:

ich definiere ein statisches Array:

var mein_Array : array[0..x,0..y,0..z,0..x,0..y,0..z] of double; Ich kann in mein_Array also (x+1)(x+1)(y+1)(y+1)(z+1)(z+1) Gleitkomma-Werte abspeichern.
So weit, so gut.
Es wird im Programm folgende Schleife durchlaufen:

Delphi-Quellcode:

for i:=0 to 50 do for j:=0 to 2 do for k:=0 to 2 do
begin
for l:=0 to 50 do for m:=0 to 2 do for n:=0 to 2 do
begin
//mache irgendwas, bei dem auf mein_Array[i,j,k,l,m,n] zugegriffen wird
end;
end;

Was mich jetzt wundert, ist folgendes:
Wenn x=50, y=14, z=14, dann wird die Schleife um ein mehrfaches (ca. Faktor 5-10) langsamer durchlaufen, als wenn x=1274, y=2, z=2.
Die Anzahl der Zugriffe ist exakt die selbe und auch die Arraygröße ist exakt die gleiche.

Woran liegt das?

[jfheins]

Es könnte sein, dass diese 1 Gigabyte-Array ausgelagert wird (= auf Festplatte) und dadurch das lesen von weit auseinanderliegenden Daten langsamer ist.

Ist aber nur ne Vermutung - btw.: Wieviel Arbeitsspeicher gibts denn?

[hadschi92]

Ein 6 dimensionales Array? Ist das nicht etwas übertrieben? Das macht mich jetzt echt neugierig was du programmierst. Vielleicht könnten wir dann auch noch eine andere Lösung finden.

[xcs]

Hmmm, das mit dem Arbeitsspeicher wäre ne Möglichkeit.
Zwar wird nix auf die Platte ausgelagert..., aber was da nun genau bei der Adressierung gemacht wird und wie sich das Programm durch das Array "hangelt", weiß man halt nicht so genau (ich jedenfalls nicht )

Also, glaubt mir, ich habe mir schon überlegt, ob ich das nicht umgehen könnte.
Ich benötige es zur Berechnung des elektrischen Potentials im 3dimensionalen Raum, ausgehend von einer Ladungsverteilung.
An jeder Stelle i,j,k ist eine Ladungsdichte innerhalb eines diskreten Volumens dx*dy*dz gegeben.

Wenn das elektrische Potential am Ort i,j,k berechnet werden soll, müssen alle anderen Ladungen an den Stellen l,m,n mit jeweils einem Faktor multipliziert und aufsummiert werden (der Faktor ist eine Funktion des Abstandes zwischen i,j,k und l,m,n sowie der dielektrischen Permittivität des Mediums). Weil der Abstand ja zeitlich konstant ist (und die Permittivität auch), berechne ich die Faktoren f(i,j,k,l,m,n) einmal zu Beginn und speichere sie in dem Array ab.

Eine etwas elegantere Lösung wäre vielleicht, die Poisson-Gleichung zu lösen, aber das ist aufwändig zu programmieren und ich habe ein paar Probleme beim Übergang zwischen verschiedenen Werten (wenn sich die Permittivität ändert).

Aber wenn hier zufällig jemand Erfahrung mit der Numerik elektrostatischer Problemstellungen hat, würde ich mich über Rat freuen


Schönen Abend!

[xcs]

Aber falls jemand von euch Lust und Zeit hat, probiert es doch selbst mal aus.
Deklariert das Array wie ich und lasst die Schleife durchlaufen wie ich, mit irgend einem Zugriff auf das Array,
z.B.

Array[i,j,k,l,m,n] := i*j*k*l*m*n

o.ä.

die Zeit des Durchlaufens lässt sich mit QueryPerformanceCounter fast auf die ms genau bestimmen:

Start, Ende, f : int64;
Zeit : double;

QueryPerformanceFrequency(f)

QueryPerformanceCounter(Start);

//Schleife ausführen

QueryPerformanceCounter(Ende)

Zeit := (Ende-Start)/f;


Denn vielleicht liegt ja nur an meinem alten Delphi 7 Compiler ...

[jfheins]

Ich weis jetzt nicht ob ich das rtichtig verstanden habe ...

Du hast einen dreidimensionalen Raum und benötigst das array[x1, y1, z1, x2, y2, z2] um "Abstandsdaten" zwischen jedem Punktepaar zu speichern?

Wie kompliziert ist eigentlich die Berechnung der Werte? Wenn sie einfach ist, könnte man vll. auf das Array verzcihten

Du könntest ja mal versuchen, einen 1 Gigabyte großen Speicherblock zu reservieren - wenn das fehlschlägt ist das Array wahrscheinlich in mehrere Teile aufgeteilt und der Zugriff entsprechend langsamer (normalerweise geschieht der Zugriff in O(1) also in konstanter Zeit)

[Medium]

Uff... Ich sehe das richtig, dass du ein Vektorfeld in einem Raum mit gewisser Auflösung komplett, also über das gesamte Volumen am Stück speichern möchtest? Warum brauchst du zu jedem Zeitpunkt alle diese Daten, und schnell verfügbar? Du hast zwar geschrieben was du da berechnest, aber dem "Normalohr" wie meinem erschließt sich noch immer nicht zu was das ganze letztlich führen soll.
Je nach dem was das werden soll, ließe sich evtl. über Näherungsverfahren, oder HD-gestützte Datenhaltung (evtl. mit prefetching wahrscheinlich demnächst gebrauchter Segmente), oder gar auf den Verzicht des ganzen nachdenken.

Volumendaten komplett am Stück lassen oft (nicht immer) auf konzeptionelle Schwächen schließen, da seltenst wirklich alles immer in voller Genauigkeit und super schnell gebraucht wird - so gut wie nie eigentlich. Ganz davon abgesehen ist es halt auch meist ziemlich unpraktikabel wie du merkst

Fazit: Erklär doch bitte nochmal in möglichst einfachen Worten was du berechnest, und vor allem wie du diese Werte anschließend benötigst (Simulation von einem/mehreren Teilchen in dem Feld, Echtzeit, Punktproben wählen, partiel summieren - das wären z.B. so Dinge wo ich mir vorstellen kann dass man sie in einem Vektorfeld tun wollen könnte, mal so als Beispiel).

[himitsu]

Zitat von jfheins:

Du könntest ja mal versuchen, einen 1 Gigabyte großen Speicherblock zu reservieren - wenn das fehlschlägt ist das Array wahrscheinlich in mehrere Teile aufgeteilt und der Zugriff entsprechend langsamer (normalerweise geschieht der Zugriff in O(1) also in konstanter Zeit)

also Delphi selber sollte das Array nicht aufsplitten (im virtuellen Speicher)

aber was Windows macht, ist damit natürlich nicht sicher (dieses kann den Block ja aufteilen und auch auslagern ... z.B. in 8 bzw. 64 KB-Schritten)

[Blup]

Die Faktoren in (l,m,n) sind ausgehend von jedem Punkt im Raum (i,j,k) immer gleich.
Verschoben werden eigentlich nur die Punkte, auf die diese Faktoren anzuwenden sind.

Man kann also mit zwei getrennten Arrays arbeiten.

[xcs]

Danke für die bisherigen Ideen.

Was ist mit "Reservierung eines Speicherblocks" gemeint? Mit der Deklaration des Arrays wird doch der Speicher schon reserviert...

Zur Problemstellung:

- es geht um Elektrodiffusion von Ionen zwischen zwei Elektrolyten, welche durch eine teildurchlässige Membran getrennt sind
- die Membran hat eine andere relative dielektrische Permittivität ("Dielektrizitätszahl epsilon_r") als Wasser
- um Regionen, in denen "wenig" passiert (also weit weg von der Membran), gröber aufzulösen, und somit Rechenzeit zu sparen, will ich die Möglichkeit eines nicht-äquidistanten Gitters offen lassen

Daraus folgt:
- die diskreten Volumina sind nicht immer gleich groß --> f(i,j,k,l,m,n) ungleich f(l,m,n,i,j,k)
- wenn zwischen zwei Punkten gleichen Abstandes die Membran liegt, ändert sich der "Abstandsfaktor" auch: f(i,j,k,i+a,j+b,k+c) ist nicht gleich für alle i,j,k

Somit lässt sich das Problem nur sehr schlecht auf ein Array geringerer Dimension reduzieren.
(im homogenen, äquidistanten Fall würde ein 3D-Array reichen, weil ja jeder Punkt mittels eines Vektors vom Ursprung aus beschrieben werden könnte)

Eine Berechnung des "Abstandsfaktors" (ohne Array) würde viel länger dauern als es abzurufen. Das würde dann so aussehen:
faktor := sqrt(sqr(pos_x[i,j,k]-pos_x[l,m,n]) + sqr(pos_y[i,j,k]-pos_y[l,m,n]) + sqr(pos_z[i,j,k]-pos_z[l,m,n]))/(4*PI*epsilon_0*epsilon_r) wobei epsilon_r streng genommen wieder eine Funktion von (i,j,k) ist.

Achso, die Schleife muss für jeden Zeitschritt delta_t erneut durchlaufen werden, weil sich dann ja die Ionenkonzentrationen (ergo die Ladungsdichten) durch die Diffusion verändert haben. Deswegen ist ja die Geschwindigkeit so entscheidend.