Dynamische Arrays - Overhead

[blablab]

Hallo!

Ich hab folgendes Problem: Ich hab eine mehrdimensionales dynamisches Array ungefähr in folgender größenordnung array[0..100000] of array[0..24]. das äußere array muss wirklich dynamisch sein, die inneren aber eigentlich nicht. deren größe bleibt immer gleich, allerdings weiß ich die größe zur entwicklungszeit noch nicht.
Mein Problem ist nun, dass ich nicht weiß wie die dynamischen arrays bei delphi funktionieren. Aber ich kann mir vorstellen, dass wenn ich Setlength(array, 25) mach, dass delphi dann etwas mehr als 25 speicherplätze reserviert falls ich das array noch nachträglich vergrößere (was ich aber nicht mache).
Wenn jetzt also delphi zb statt 25 speicherplätze immer 30 reserviert, dann wäre das doch ein ziemlich großer overhead...
Diesen overhead, falls es ihn gibt, würde ich gerne verhindern. Was kann ich dagegen tun???

Vielen Dank!
Grüße
blablab

[jfheins]

Diesen gibt es nicht. Wenn du die Größe auf 25 setzt, wird das auch so gemacht. Das führt natürlich dazu, dass es extrem unperformant ist, die Größe des Array um 1 zu vergrößern - was ja aber nicht dein Problem ist ;)

[blablab]

ist das wirklich so?
ich hatte teilweise schon das problem, dass ich ein dyn Array immer um 1 vergrößern musste. Da hab ich dann immer extra ne zusätzliche Variable verwendet und das array immer stufenweise zb um 10000 vergrößert. Als ich es dann mit dem verglichen hab dass das Array immer nur um 1 vergrößert hab ich keinen geschwindigkeits-unterschied festgestellt und seit dem vergrößer ich dynamische arrays immer um 1 und mach mir die zusätzliche mühe nicht mehr...
heißt das jetzt ich sollte mir die mühe doch wieder machen??? :stupid:

[alzaimar]

Die neueren Delphi-Versionen verwenden einen optimierten Speichermanager, sodaß das von jfheins erwähnte Performanceproblem nicht mehr auftritt.

Ohne dein Programm zu kennen würde ich aber annehmen, das im Code mehr Optimierungspotential liegt, als in der Wahl der Datenstruktur.

[blablab]

ich hab halt ne tabelle mit 100000 reihen und 25 spalten, die ich anzeigen will...
aber statt ca 4 mb braucht die tabelle halt 50mb ram

[Klaus01]

.. was packst Du denn in Dein Array hinein?

Grüße
Klaus

[alzaimar]

Zitat:

Zitat von blablab

ich hab halt ne tabelle mit 100000 reihen und 25 spalten, die ich anzeigen will...

:shock: Und wer will sich das anschauen? :gruebel:
Das sieht nach einem Designfehler aus.

[himitsu]

Gut, dieses Beispiel liefert auch schon in Delphi 7 "theoretisch" sehr gute Ergebnisse,
> im Durchschnitt weniger als 10 kopiervorgänge
also nicht nur in neueren Delphi-Versionen.

Delphi-Quellcode:

Var A:  Array of String;
  i, C: Integer;
  P:    Pointer;

Begin
  A := nil;
  C := 0;
  P := Pointer(A);
  For i := 1 to 50000 do Begin
    SetLength(A, i);
    If Pointer(A) <> P Then Inc(C);
    P := Pointer(A);
  End;
  MessageBox(0, PChar(Format('%d von %d wurden kopiert', [C, 50000])), '', 0);
End;

Aber das ist nur ein Optimum, da in der Regel noch andere Speicheroperationen zwischendurch stattfinden und somit vermutlich oftmals der Speicher hinter dem Array belegt sein wird, womit es also dann doch nicht so oft Inplace vergrößert werden kann.


Also, im Prinzip stimmt es, daß hier nicht so der rießige Flaschenhals drinsteckt, wie man glauben könnte,

aber dennoch kann man es im Notfall noch optimieren, durch ein größeres Änderungsintervall.
- seltenere Initialisierungen/Finalisierungen der Elemente (je nach Datentyp)
- auch seltenere Zugriffe auf den Speichermanager
- eventuell auch seltenere Realocierungen ... jenachdem wie optimal es der MM normalerweise machen könnte


Es kommt also auf den Einzel fall drauf an, ob man es noch etwas optimieren kann/muß.

Zitat:

aber statt ca 4 mb braucht die tabelle halt 50mb ram

Stichwort Speicherfragmentierung

[blablab]

Ich hab folgende Datenstruktur:

Delphi-Quellcode:

ARR2 = record
   cont: Pointer;
   strs: array of integer;
end;
ARR1 = array of ARR2;

Den befüll ich zur Zeit mit 32000 Zeilen und 24 Spalten. -> Ich brauch 88MB Arbeitsspeicher (Differenz zwischen Array befüllen und SetLength(ARR1, 0)). Wenn ich mich nicht verrechne sollte das ganze aber um die 32000*(1+24)*4 =~ 3MB brauchen


@alzaimar:
Sorry, dass ich das net weiter rechtfertige, aber es ist kein Designfehler...
Aber darum gehts ja auch net. ich will einfach net das 30-fache an Speicher benötigen.

[Medium]

Zitat:

Zitat von blablab

ich will einfach net das 30-fache an Speicher benötigen.

Beste Methode: Hol dir auch nur das in den Speicher, was auch angezeigt wird (evtl. +/- etwas am "Rand" prefetchen). Das löst auch gleich dein nicht existentes Designproblem ;)

[blablab]

Kann man nicht irgendwie statische arrays benutzen? sowas wie

Delphi-Quellcode:

procedure unmöglich(count: integer);
var Arr: array of array[0..count] of integer;
begin
   SetLength(Arr, 10000);
   ...
end;

weil sonst muss ich halt des verwenden:

Delphi-Quellcode:

procedure nichtunmöglich(count: integer);
var Arr: array of integer;
begin
   SetLength(Arr, 10000*count);
   ...
end;

mir wärs aber schon lieber wenn ich gescheite Datenstrukturen verwenden könnte...

@Medium: das geht in meinem Fall leider net.

[alzaimar]

Ich glaub aber, deine Rechnung ist nicht ganz korrekt:

Delphi-Quellcode:

ARR2 = record
   cont: Pointer;
   strs: array of integer;
end;
ARR1 = array of ARR2;

Ein ARR2-Record belegt 8 Bytes. Die 24 Spalten extra sind nochmal 24*4 Bytes plus einen kleinen Overhead für die Größeninformation des 'strs'-Arrays, schätze ich. Macht also pro Record 104 Bytes. Sind dann immer noch 3MB plus -sagen wir- 200k für diesen Oberhead. Oder 400k oder 1MB, völlig wurscht.

Zitat:

Zitat von blablab

Ich brauch 88MB Arbeitsspeicher

Woher weisst Du das? Vielleicht ist hier dein Denkfehler? Und selbst wenn es so wäre. Was solls? Ksnn wirklich an der Speicherfragmentierung liegen.

Zitat:

Zitat von blablab

@alzaimar:Sorry, dass ich das net weiter rechtfertige, aber es ist kein Designfehler...

Wenn Du meinst. :zwinker: Würde nur gern wissen, was derjenige, der sich das anschauen muss, verbrochen hat.

[himitsu]

korrekt isses eh nicht, denn ich komme auf 3,8 MB (inklusive der Verwaltungsdaten für die Arrays)

Delphi-Quellcode:

procedure möglich(count: integer);
var Arr: array of array[0..10000] of integer;
begin
   SetLength(Arr, count);
   ...
end;

Delphi-Quellcode:

procedure möglich(count: integer);
var Arr: array[0..10000] of array of integer;
  i: Integer;
begin
   for i := Low(Arr) to High(Arr) do
     SetLength(Arr[i], count);
   ...
end;

PS: klar gibt es fast immer einen gewissen Overhead
die Speichermanager reservieren nunmal in gerundeten Größen

bei Windows-Manager kann man Speicher in 4 KB-Schritten anfordern und bis auf den nächsten 64-KB-Schritt kann da nichts mehr reserviert werden.

der DelphiMM verwalten dagengen zwar kleinere Bereiche, aber auch diese sind "genormt"
und dann holt sich Delphi bei Windows den Speicher.

also selbst wenn man nur 1 Byte reserviert, dann ist immer mehr belegt.

[blablab]

stimmt, die rechnung ist wirklich nicht ganz korrekt. ich habs ja auch nur überschlagen. machen wir aus den 3MB 4MB, dann sinds aber immernoch mehr als das 20fache...

die 88MB hab ich so ermittelt:
1) ARR1 befüllen mit daten
2) Taskmanager öffnen, Speicherbedarf abschreiben
3) Knopf mit Funktion SetLength(ARR1, 0) klicken
4) neuer Speicherbedarf (laut Taskmanager) von vorherigem abziehen
-> 88MB

Zitat:

Zitat von alzaimar

Zitat:

Zitat von blablab

@alzaimar:Sorry, dass ich das net weiter rechtfertige, aber es ist kein Designfehler...

Wenn Du meinst. :zwinker: Würde nur gern wissen, was derjenige, der sich das anschauen muss, verbrochen hat.

Man kann die Tabelle filtern, so dass nurnoch wenige Einträge angezeigt werden

[blablab]

Bleibt mir jetzt nurnoch übrig
a) das 20-fache an Speicher zu brauchen
b) meine Datenstruktur aufzugeben und alles in einen Riesen array of Pointer umzuwandeln?
:cry:

[himitsu]

du weißt aber schon, daß ein dynamisches Array schon ein Pointer ist?

Abgesehn davon heißt es noch lange nicht, daß die 80 MB an mehr auch wirklich von dir belegt sind.

Denn es gibt da 2 Arten von Overherad:
- Speicher, welcher wegen Größengruppierung (aufrunden) mitreserviert wurde und nicht mehr nutzbar ist
- Speicher, welcher wegen Gruppenbildung zwar mitreserviert wurde, aber dennoch für andere Variablen nutzbar ist

[blablab]

Zitat:

Zitat von himitsu

du weißt aber schon, daß ein dynamisches Array schon ein Pointer ist?

Ich versteh nicht was du mir damit sagen möchtest :stupid:

Zitat:

Zitat von himitsu

Abgesehn davon heißt es noch lange nicht, daß die 80 MB an mehr auch wirklich von dir belegt sind.

Denn es gibt da 2 Arten von Overherad:
- Speicher, welche Größengruppierung mitreserviert wurde und nicht mehr nutzbar ist
- Speicher, welcher wegen Gruppenbildung zwar mitreserviert wurde, aber dennoch für andere Variablen nutzbar ist

Das problem ist halt, sobald ich mehr Reihen/Spalten hab stürzt mein Programm ab mit der Meldung "Nicht genügend Arbeitsspeicher".

[Tryer]

Das liegt vermutlich eher an einem Speicherleck beim Befüllen als am Array selber (bzw. wenn kein Speicherleck - was steckt denn hinter dem Pointer?)

[blablab]

Die 88MB entstehen auch schon ohne dass ich das Array befülle. Das liegt nur am SetLength.

[himitsu]

klar, denn die Datenplätze (Variablen) sind auch vorhanden, selbst wenn du nichts da reinschreibst :zwinker:

einfache Lösung gegen eine übermäßige Defragmentierung,
denn genau das ist einer der Gründe, warum man nicht unbedingt ein Array oft in seiner Größe verändern sollte:
einfach den gesamten Speicher gleich am Anfang auf Einmal reservieren
und dann die Daten nur noch da reinschreiben.

[blablab]

Nochmal verständlich:

Delphi-Quellcode:

procedure overhead;
var i, zeilen, spalten: integer;
      arr: array of array of Typ;
begin
   zeilen := 32000;
   spalten := 25;
   SetLength(arr, zeilen);
   for i := 0 to zeilen - 1 do begin
      SetLength(arr[i], spalten);
   end;
end;

Mein Problem ist dass dieser Code nicht ca. Zeilen*Spalten*SizeOf(Typ) Bytes Ram braucht, sondern eher das 20fache.

[Tryer]

1. Das ist ja nunmal nicht der Record den du vorgestellt hast
2. Warum bei diesem "einfachen" 2-dimensionalen Array nicht sofort

Delphi-Quellcode:

SetLength(arr, zeilen, spalten);

[blablab]

habs zu stark vereinfacht :oops:

Delphi-Quellcode:

procedure overhead; 
var i, zeilen, spalten: integer; 
   arr: array of record 
      cont: Pointer; 
      strs: array of integer; 
   end; 
begin 
   zeilen := 32000; 
   spalten := 25; 
   SetLength(arr, zeilen); 
   for i := 0 to zeilen - 1 do begin 
      SetLength(arr[i].strs, spalten); 
   end; 
end;

[himitsu]

Delphi-Quellcode:

procedure overhead;
var i, zeilen, spalten: integer;
   arr: array of record
      cont: Pointer;
      strs: array of integer;
   end;
begin
   zeilen := 32000;
   spalten := 25;
   SetLength(arr, zeilen);
   for i := 0 to zeilen - 1 do begin
      SetLength(arr[i].strs, spalten);
   end;
end;

genau dieser Code belegt bei mir, laut Taskmanager zusätzliche 3,748 MB (D7) bzw 3,764 MB (D2009)
also fast 3,8 MB, so wie ich ausgerechnet hatte
(XP32)

[blablab]

Vielen Dank an alle!

Hab jetzt ne neue Datenstruktur und es klappt :)

[Neutral General]

Hi,

Aber bist du dir sicher, dass es überhaupt zu irgendeinem Zeitpunkt sinnvoll ist so viele Datensätze auf einmal anzuzeigen oder überhaupt im Speicher rumliegen zu haben?

1000 ist ja schon ne ganze Menge.. Und niemand wird sich je 1000 Datensätze angucken bzw alle auf einmal brauchen. die kannst du auch alle gar nicht auf einmal anzeigen. Und im Speicher brauchst du auch nicht immer alle. Ich würde zusehen, dass du nur das speicherst was du (gerade) auch wirklich brauchst...

[himitsu]

Ansonsten kommt es nur auf die Verwaltung drauf an ... in nichmal 60 MB bekommt ich locker 'nen großes Verzeichnislistening mit 300.000 Datensätzen/Dateien rein und zu jeder Datei noch 'ne Menge Zusatzinfos (SSF).
Also viele Datensätze bedeuten nicht immer gleich massig Speicherverbrauch.

[Sir Rufo]

Zitat:

Zitat von Neutral General

Hi,

Aber bist du dir sicher, dass es überhaupt zu irgendeinem Zeitpunkt sinnvoll ist so viele Datensätze auf einmal anzuzeigen oder überhaupt im Speicher rumliegen zu haben?

1000 ist ja schon ne ganze Menge.. Und niemand wird sich je 1000 Datensätze angucken bzw alle auf einmal brauchen. die kannst du auch alle gar nicht auf einmal anzeigen. Und im Speicher brauchst du auch nicht immer alle. Ich würde zusehen, dass du nur das speicherst was du (gerade) auch wirklich brauchst...

Warum nicht, ich starre hier den ganzen Tag auf 5.060.720 Datensätze die sich zudem auch noch temporär ändern, manchmal sogar ganz erheblich
3 Monitore 1900x1200, 1400x1050, 1280x1024 :mrgreen:

[Medium]

Das heisst ja, dass jeder Datensatz bei dir (1200+1050+1024)/5060720 = 0,00064694 Pixel hoch ist - Reschpäckt! :stupid:

[alzaimar]

Nachdem die Datenstruktur komprimiert wurde (durch ein einziges Array ginge das), könnte man noch die Visualisierung in Angriff nehmen. Man muss nicht alle 100.000 Datensätze anzeigen sondern jeweils nur die paar, die auf einen Bildschirm passen. Beim Scrollen kann man ja aus dem RAM nachladen. Und über das Filtern wird die Datenmenge eh beschränkt.

Aber wer partout 100.000 Datensätze anzeigen will (vermutlich in der Ansicht 'noch kein Filter' gesetzt), der kann das ja machen.

Die Optimierung der Visualisierung kann jedoch nicht ungefragt geschehen, dann das ist ja nicht Thema dieses Threads. blablab wird dann, wenn er meint, Hilfe/Anregungen zu benötigen, einen anderen Thread aufmachen.

Ich würde mich freuen, wenn blablab die Lösung (also die Änderungen in seiner Struktur) kurz erläutern würde.

[Sir Rufo]

Zitat:

Zitat von Medium

Das heisst ja, dass jeder Datensatz bei dir (1200+1050+1024)/5060720 = 0,00064694 Pixel hoch ist - Reschpäckt! :stupid:

häh, wie kommst du denn da drauf?

Die Datensätze werden flächig angezeigt und die jeweiligen Werte sind farblich dargestellt.
Also ist jeder Datensatz 1 Pixel hoch :mrgreen:

[Medium]

Och muh, jetzt versteh ich erstmal den latenten Sarkasmus deines Postings... Grippaler Infekt macht Hirn weicher als angenehm ist :stupid:

Aber back to topic, sorry.

[blablab]

Falls es euch noch interessiert:

Bei der neuen "verbesserten" Datenstruktur hab ich alles hintereinander in einen Array of Pointer reingeschrieben.
Dann hab ich noch ein bisschen rumgetrickst, damit ich an meiner alten Datenstruktur kaum was ändern musste und nicht den kompletten code umändern musste.

Außerdem hatte ja diesen Code geschrieben

Delphi-Quellcode:

procedure overhead; 
var i, zeilen, spalten: integer; 
   arr: array of record 
      cont: Pointer; 
      strs: array of integer; 
   end; 
begin 
   zeilen := 32000; 
   spalten := 25; 
   SetLength(arr, zeilen); 
   for i := 0 to zeilen - 1 do begin 
      SetLength(arr[i].strs, spalten); 
   end; 
end;

Als himitsu schrieb dass es bei ihm einwandfrei funktioniert hab ich mich nochmal damit beschäftigt und da ist mir etwas aufgefallen, mein code war doch ein klitzekleines bisschen anders :oops: :oops: :oops:

Delphi-Quellcode:

procedure overhead; 
var i, zeilen, spalten: integer; 
   arr: array of record 
      cont: Pointer; 
      strs: array of integer; 
   end; 
begin 
   zeilen := 32000; 
   spalten := 25; 
   for i := 0 to zeilen - 1 do begin 
      SetLength(arr, i); 
      SetLength(arr[i].strs, spalten); 
   end; 
end;

Dadurch entsteht die schreckliche Fragmentirung des Speichers...

Also hab ich nochmal ALLES umgeschrieben, die "verbesserte" Datenstruktur wieder rückgängig gemacht und den Fehler behoben. Jetzt funktioniert es dank eurer Hilfe einwandfrei :-D


Zu den vielen Datensätzen:
Als erstes sind die 100.000 Datensätze ein Maximalwert. Der wird wahrscheinlich nie erreicht werden, aber ich verlange halt etwas von meinen Programmen... :-D Nur dadurch bin ich ja letztendlich auf den blöden Fehler gekommen...
Und ich brauche die ganzen Datensätze im Speicher gerade damit ich es Filtern kann. Und so wies jetzt aussieht ist das auch kein Problem, weil das gerade mal ein paar MB sind und es inzwischen auch recht flüssig läuft...

Und eins noch: Ich zeige die ganzen Datensätze nicht auf einmal an. Ich möchte die nur im SPeicher haben damit ich sie so schnell wie möglich anzeigen kann, aber nicht um alle gleichzeitig anzuzeigen. So groß ist mein bildschirm auch wieder nicht :P

Nochmal Danke für eure Hilfe und euer Interesse!
Grüße
blablab

[himitsu]

Das mit dem Abverlangen kenn ich :oops:

Mein SSF hab ich auch mehrmals zum Test auf 2 Terrabyteplatten losgelassen, was im Normalfall wohl auch keiner so oft macht :nerd:


Und jupp, daß ist genau soein Problem.
Das zweite Array wird vom Speichermanager meißt hinter das Erste gelegt, weswegen für das Erste dann kein/kaum Speicher zur Inplace-Vergrößerung ist und es wieder hinten drankopiert wird und so weiter ... dadurch bleiben vorne sehr viele und auch größere freie Speicherplätze, welche aber Windows ja als belegt ansieht (siehe Taskmanager), da sie ja vom DelphiMM reserviert sind.