OutOfMemory und StringBuffer

Anfaenger

Hi,

ich habe in meinem Programm einen leeren StringBuffer, zu dem ich 20 Millionen Zeichen hinzufügen möchte.

Ich mache das so:

StringBuffer stBu = new StringBuffer();//20000000);
Random random = new Random();
for (int i = 0; i <20000000; ++i) {
    if (i % 1000000 == 0) System.out.println(i);
    stBu.append((char) (random.nextDouble()*('z'-'a')+'a'));
}

Wenn ich StringBuffer nun eine initial capacity von 20 Millionen verpasse, funktioniert dieser Code, ansonsten bricht er bei etwa 18 Millionen ab. Warum ist dieses so.

Ich habe die maximale heap size schon auf 256mb erhöht, in der Hoffnung, dass es was bringt.

Danach möchte ich dann gerne ein HashSet mit 1 Million Einträge noch hinzufügen ....

eigentlich denke ich, sollte das doch mit 256 mb (bzw. 512 als max heap size, die allerding nie ganz erreicht werden kann, da mein Windows sich ein gute Stück davon abschneidet) eigentlich gehen, oder nicht?

Vielen Dank schonmal

Hast du überhaupt genug Speicher? Das ist sicherlich mehr als 256 mb

Anfaenger

naja, zumindest die Strings sollten doch wohl funktionieren .... 2 * 20 Millionen Byte = 40 Millionen Byte =(ungefähr) 40 Mb plus ein wenig overhead für Stringbuffer, der sollte aber wohl doch konstant sein und damit kaum ins gewicht fallen.

Gregor

EDIT : Hier stand Müll!

[ Dieser Beitrag wurde am 01.02.2003 um 20:36 Uhr von Gregor editiert. ]

O'Dog

Original erstellt von Anfaenger:
naja, zumindest die Strings sollten doch wohl funktionieren .... 2 * 20 Millionen Byte = 40 Millionen Byte =(ungefähr) 40 Mb plus ein wenig overhead für Stringbuffer, der sollte aber wohl doch konstant sein und damit kaum ins gewicht fallen.

Dazu müsste man wissen wie der StringBuffer arbeitet.
Wenn man den Konstruktor von StringBuffer ohne Parameter aufruft wird er mit der Größe 16 initialisiert.
Die ersten 16 chars die man hinzufügt gehen problemlos rein, beim Versuch den 17 char hinzuzufügen geht der StringBuffer wie folgt vor:

Addiere eine 1 zur bisherigen Größe
multipliziere das Ergebnis mit 2
lege ein Array mit der neuen Größe an
kopiere das alte Array herein

d.h.
- Am Anfang hat der StringBuffer 'ne Länge von 16
- ab den 16 char hat der Buffer 'ne Länge von (16+1)*2=34
- dann (34+1)*2=70
- dann (70+1)*2=142 usw.

Daraus können wir 'ne Funktion bauen die wäre:

(2^n)*x + ([summe von 1 bis n] (2^n))

wobei x die initialgröße ist (hier also 16)
und n>=1

- für n=1 gilt 216+2 = 34
- für n=2 gilt 416+2+4 = 70
- für n=3 kommen wir auf 142 usw.

wenn wir für n 20 einsetzen erhalten wir
18.874.366

Wenn du mal versuchst deine Schleife nicht bis 20 Millionen laufen zu lassen sondern nur bis 18.874.366 wirst du keine Speicherprobleme feststellen.
Wenn du allerdings nur ein char mehr hinzufügst d.h. die Schleife bis 18.874.367 laufen läßt bekommst du wieder eine OutOfMemoryException.

Wenn du dir nochmal oben das Vorgehen des StringBuffer anguckst siehst du auch warum. Beim 18.874.367sten char wird wieder neuer Speicher benötigt und der StringBuffer holt sich ein (18874366+1)*2 großes Array (was auch rauskommt wenn wir in unsere Funktion (2^n)*x + ([summe von 1 bis n] (2^n)) für n=21 einsetzen).

Das sind 37.748.734 chars, jedes char hat zwei Byte macht also ca. 72MB.
Da die VM defaultmäßig mit 64MB Heap gestartet wird passt es nun net mehr.

Jetzt wirst du dich Fragen:
Alles schön und gut wenn ich die VM aber mit der Option -Xmx80MB startet funktioniert es immer noch net.

Das stimmt hier fallen die oben genannten Punkte 3 und 4 ins Gewicht
**
3) lege ein Array mit der neuen Größe an
4) kopiere das alte Array herein
**

Das heißt:
Wenn du das 18.874.366ste Zeichen zu deinem Buffer hinzufügst hat dein Buffer noch das alte Array mit ca.36MB im Speicher und legt dann das neue Array mit 72MB an um anschließen die Daten des alten Array ins neue zu kopieren, es sind also temporär über 100MB im Heapspeicher.

Bei mir läuft deine Schleife mit der Option -Xmx117MB durch.

Wenn du deinen Buffer schon mit 20000000 Initialisierst dann wird intern direkt ein Array mit 40MB angelegt und das ganze interne reallokieren des StringBuffers fällt weg. Ist wesentlich Speicherschonender und auch schneller.

bis dänn, O'Dog

[ Dieser Beitrag wurde am 02.02.2003 um 19:48 Uhr von O'Dog editiert. ]

wow, das war doch mal ne spitzen erklärung!!

Gamba

Super Posting O'Dog !

Wenn es sowas wie das Posting des Monats gäbe
würde ich deines vorschlagen.

Cengiz hat doch irgendso einen Pokal den er vergibt

CengizS

Ihr meint den Goldenen Duke? Na ja der ist zwar nicht von mir aber für die Erklärung hätte O'Dog wirklich einen verdient

Das Ding kommt in die FAQ ... irgendwelche Zusätze?

Anfaenger

Eine sehr schöne Erklärung, vielen Dank.

Das erklärt auf jeden Fall die Unterschiede ... wieder was gelernt.