Java: Speicherverbrauch StringBuilder [Archiv]

Watson007

2011-12-07, 16:59:06

ich habe hier ein kleines Verständnisproblem: wenn ich mit dieser Routine eine 64MB grosse Textdatei einlese, steigt der RAM-Verbrauch des java.exe-Prozesses auf ca. 600 MB. Warum?!

ich habe schon überlegt ob es woanders dran liegt, aber das kann ich ausschließen.

Das Problem scheint der StringBuilder zu sein - wenn ich es alternativ mit +-Verkettung auf die Variable completeString versuche kommt er zwar zu keinem Ende, aber der Speicherverbrauch wächst nicht so stark an.

Warum braucht das 8x soviel Speicher wie die Datei groß ist?!

// systemeigenes Zeilenumbruchszeichen ermitteln
String sep = System.getProperty("line.separator");

File file = new File(patternFile);
int fileLength = (int) file.length();
file = null;

StringBuilder sb = new StringBuilder(fileLength);
try
{
String thisLine=null;
BufferedReader br = new BufferedReader(new FileReader(loadPath));
while ((thisLine = br.readLine()) != null)
{
/* eingelesene Zeile anhängen */
sb.append(thisLine);
/* Zeilenumbruch hinzufügen */
sb.append(sep);
}
} catch (IOException e)
{
println("Error: " + e);
}

completeString = sb.toString();
sb.setLength(0);
sb = null;

übrigens, mit completeString = sb.toString(); sollen nur die Pointer umkopiert werden und nicht die Inhalte soweit ich weiss.

Shink

2011-12-07, 17:13:08

Das Problem scheint der StringBuilder zu sein - wenn ich es alternativ mit +-Verkettung auf die Variable completeString versuche kommt er zwar zu keinem Ende, aber der Speicherverbrauch wächst nicht so stark an.
Eine Verkettung mit + erzeugt einen StringBuffer. Dieser ist prinzipiell sogar fetter als ein StringBuilder da er Thread-Safe ist.

Was heißt "er kommt zu keinem Ende" bei der Verwendung vom + - Operator?

Gibt es bei dir mehr als einen Thread?

Ach ja: Wenn es performant sein soll und wenig Speicher benötigen dann verwendet man java.nio

Watson007

2011-12-07, 17:17:27

nein ich benutze nur einen Thread. Mit Verkettung statt Stringbuilder meinte ich das:

completeString+=thisLine+sep;

dass Stringbuilder schneller ist verstehe ich, aber warum braucht Stringbuilder soviel RAM?

#44

2011-12-07, 17:29:05

Was heißt "er kommt zu keinem Ende" bei der Verwendung vom + - Operator?
Ich schätze, dass dann durch ständiges instanziieren und GC 100% CPU-Last erzeugt wird und es deutlich länger dauert - so lange, bis der TE keine Lust mehr hat und das Ganze stoppt. Den niedrigeren Speicherverbrauch könnte man dadurch erklären, dass es durch einen vorzeitigen Abbruch erst gar nicht soweit kommt.

Aber das ist nur Spekulation...

---

Welche Zeichencodierung nutzt die Textdatei?

Watson007

2011-12-07, 17:31:53

normale windows-zeichensatzcodierung, ansi... irgendwas

wie würde das Datei-Laden in einen einzelnen String denn mit NIO aussehen?

PatkIllA

2011-12-07, 17:42:14

Java verwendet ja auch 2 Bytes pro Zeichen.
Das dann mit den ganzen temporären Objekten und dann kann das schon deutlich mehr sein.
Warum willst du das überhaupt als einen großen String haben?

Watson007

2011-12-07, 17:43:36

angenommen ich mache statt das mit dem stringbuilder dass hier:

while ((thisLine = br.readLine()) != null)
{
completeString=thisLine;
}

dadurch wird nur die letzte eingelesene Zeile im RAM gehalten und der RAM-Verbrauch ist entsprechend minimal. Das beweist aber auch dass es nicht am alten I/O-System liegt, sondern am Stringbuilder - der Hinweis mit NIO bringt mir dann doch gar nichts.

Watson007

2011-12-07, 17:46:10

Java verwendet ja auch 2 Bytes pro Zeichen.
Das dann mit den ganzen temporären Objekten und dann kann das schon deutlich mehr sein.
Warum willst du das überhaupt als einen großen String haben?

gut dass mit den 2 Bytes pro Zeichen habe ich nicht bedacht, wegen Unicode nehme ich an. Ist aber noch keine ausreichende Erklärung.

Ich experimentiere für die Fachhochschule und muss für Textsuchalgorithmen alles in einen einzelnen String laden.

PatkIllA

2011-12-07, 17:46:28

Wird es denn weniger,wenn du mal zwischendurch die Garbage Collection aufrufst?
Wobei du dann trotzdem nicht direkt die Anzeige des Taskmanager nutzen kannst.

Watson007

2011-12-07, 17:48:25

Wird es denn weniger,wenn du mal zwischendurch die Garbage Collection aufrufst?

ich bin noch Java-Anfänger. Ich dachte man kann die nicht selbst aufrufen, sondern das passiert automatisch?!

Objekt auf null zu setzen reicht jedenfalls nicht aus.

PatkIllA

2011-12-07, 17:52:12

ich bin noch Java-Anfänger. Ich dachte man kann die nicht selbst aufrufen, sondern das passiert automatisch?!Die läuft ja auch automatisch und man sollte da auf jeden Fall sehr vorsichtig mit umgehen und nicht dauernd Garbage Collection aufrufen.
http://docs.oracle.com/javase/6/docs/api/java/lang/System.html#gc%28%29

Was denn für Textsuchalgorithmen? Kannst du die nicht direkt beim Einlesen machen?

#44

2011-12-07, 17:52:16

Objekt auf null zu setzen reicht jedenfalls nicht aus.
Exakt.

System.gc()

Aber auch das ist kein Garant. Nur das nächst "beste" was du als Programmierer tun kannst. Sollte es wirklich an der GC liegen, kannst (und solltest) du den Speicherverbrauch ignorieren. Java kümmert sich schon irgendwann drum - spätestens wenn der Speicher gebraucht wird...

Watson007

2011-12-07, 18:11:13

Was denn für Textsuchalgorithmen? Kannst du die nicht direkt beim Einlesen machen?

verschiedene im Vergleich - und bei einigen muss man ja vor- und rückwärtsspringen ;)

bspw. werden beim naiven Algorithmus in der inneren Schleife Zeichen im voraus gelesen, die in der äußeren Schleife erst später eingelesen werden.

Trap

2011-12-07, 19:05:38

Es gibt da folgende Faktoren:
2x wegen Unicode-chars
2x wegen http://docs.oracle.com/javase/6/docs/api/java/lang/StringBuilder.html#toString%28%29 - toString() kopiert

Wenn du es genauer wissen willst: heap profiler benutzen

PatkIllA

2011-12-07, 19:08:19

2x wegen http://docs.oracle.com/javase/6/docs/api/java/lang/StringBuilder.html#toString%28%29 - toString() kopiertSicher? Bei .NET führt das ToString() auf StringBuilder nicht zu einem extra Speicherverbrauch. Da wird direkt das interne Array verwendet. Teuer wird es dann, wenn man nachdem ToString noch was ändert, dann dann wieder das Array kopiert werden muss.

Watson007

2011-12-07, 19:31:59

also ich hatte irgendwo gelesen das die toString-Methode von Stringbuilder Pointer kopiert bei Java... aber ich habe das Tab gestern schon wieder geschlossen.

PatkIllA

2011-12-07, 19:44:49

also ich hatte irgendwo gelesen das die toString-Methode von Stringbuilder Pointer kopiert bei Java... aber ich habe das Tab gestern schon wieder geschlossen.
Kann ja auch sein. Ich weiß halt nur von .NET, dass die das nicht macht.

Gast

2011-12-07, 20:17:50

Watson007

2011-12-07, 20:53:38

Hat das einen bestimmten Grund, weshalb du die Datei in einzelen Zeilen einliest?
Wenn nicht geht das auch einfacher.

byte[] data = Files.readAllBytes(Paths.get("/tmp/inputfile"));
String s = new String(data);

diese Variante kenne ich noch nicht. Zuvor hatte ich die Methode loadStrings mit der Funktion join verwendet, die aber durch das umkopieren definitiv noch mehr Speicher benötigte als Stringbuilder mit Bufferedreader.

Gast

2011-12-07, 21:44:50

Es kam doch schon der richtige Hinweis: alle Fragen lassen sich sauber mit einem (Heap)-Profiler klären.

Und Java != C#.

Pinoccio

2011-12-07, 22:14:40

Ich schätze, dass dann durch ständiges instanziieren und GC 100% CPU-Last erzeugt wird und es deutlich länger dauert - so lange, bis der TE keine Lust mehr hat und das Ganze stoppt. Den niedrigeren Speicherverbrauch könnte man dadurch erklären, dass es durch einen vorzeitigen Abbruch erst gar nicht soweit kommt.

Aber das ist nur Spekulation...Ich unterstütze diese Spekulation.
Sicher? Bei .NET führt das ToString() auf StringBuilder nicht zu einem extra Speicherverbrauch. Da wird direkt das interne Array verwendet.JAVAs toString gibt immer ein neues Objekt raus, nicht einfach eine Referenz auf was internes. Alles andere würde in heilloses Chaos führen.
Steht auch so in den Docs (http://docs.oracle.com/javase/7/docs/api/java/lang/StringBuffer.html#toString%28%29).

mfg

PatkIllA

2011-12-07, 22:20:34

Ich unterstütze diese Spekulation.
JAVAs toString gibt immer ein neues Objekt raus, nicht einfach eine Referenz auf was internes. Alles andere würde in heilloses Chaos führen.
Steht auch so in den Docs (http://docs.oracle.com/javase/7/docs/api/java/lang/StringBuffer.html#toString%28%29).

mfgDas String objekt ist bei .NET auch neu, aber der eigentliche Inhalt ist direkt das Array des StringBuilders. Das gibt auch kein heilloses Chaos, da man an das interne Array des StringBuilders nicht rankommt und der StringBuilder sicherstellt, dass nach der Erstellung des Strings das Array nicht mehr verändert wird.

Monger

2011-12-07, 22:22:06

600 MB scheint mir auch enorm viel...
Wo kommt das alles her? Selbst wenn alle erzeugten String Objekte nicht disposed werden scheint mir das immer noch zu viel.

Wie auch immer: eine der Stärken des Java Frameworks ist die sehr flexible Nutzung von Streams. Wenn du tatsächlich größere Datenmengen umwälzst, lohnt es sich über Stream-Pipes nachzudenken, also wirklich nur jede String Zeile auszuwerten wenn du sie brauchst. Nur so mal als Gedankenanstoß.

Pinoccio

2011-12-07, 22:23:02

Das String objekt ist bei .NET auch neu, aber der eigentliche Inhalt ist direkt das Array des StringBuilders. Das gibt auch kein heilloses Chaos, da man an das interne Array des StringBuilders nicht rankommt und der StringBuilder sicherstellt, dass nach der Erstellung des Strings das Array nicht mehr verändert wird.Kann man den StringBuilder danach nochgebrauchen? Klingt nicht so.

mfg

PatkIllA

2011-12-07, 22:25:33

Kann man den StringBuilder danach nochgebrauchen? Klingt nicht so.Ja kann man. Wenn man ihn danach gebraucht kopiert der die Daten aber nochmal um, um eben nicht den erzeugten String zu verändern.
Bei der üblichen Vorgehensweise erst am Ende ToString() aufzurufen ist das aber schneller.

Watson007

2011-12-07, 22:28:28

Es kam doch schon der richtige Hinweis: alle Fragen lassen sich sauber mit einem (Heap)-Profiler klären.

kannst du da Software (Freeware) empfehlen?

Pinoccio

2011-12-07, 22:29:55

Ja kann man. Wenn man ihn danach gebraucht kopiert der die Daten aber nochmal um, um eben nicht den erzeugten String zu verändern.
Bei der üblichen Vorgehensweise erst am Ende ToString() aufzurufen ist das aber schneller.Hm, geschickt versteckt, den Aufwand. Aber gut, im hier vorliegenden Fall wäre das in der Tat eine Lösung.

@Topic. Speichersparend wäre auch, selber ein CHAR-Array zu verwalten.

@Watson: http://www.javaperformancetuning.com/

mfg

Watson007

2011-12-07, 22:39:19

danke. Mein Englisch ist nicht sehr gut, aber ich schaue es mir mal an.

die Performance ist schonmal gut (2-4 sekunden für eine 64-mb-testdatei), aber dadurch dass der RAM-Verbrauch 8x so hoch ist wie die Testdatei schränkt dass die Größe der Testdateien ein (bei meinem 2GB-Notebook).

hmm also durch den Java-Unicode wird der RAM-Verbrauch alleine schonmal 2x so groß?! Einen direkten Vorteil bringt mir das wegen der ANSI-Codierung ja nicht.

Soweit ich gelesen habe kann man aber nicht bei FileReadern, sondern nur bei Streams die Kodierung angeben?! Müsste man wohl auch einen anderen Datentyp als String verwenden wenn man das vermeiden will?!

----> wäre natürlich optimal wenn das Programm nicht immer die komplette Datei im RAM halten würde, habe ich damals nicht direkt dran gedacht. Vielleicht passe ich das beim RK-Algorithmus noch an.... KMP ist dafür ja auch prädestiniert, das springt niemals zurück.

EDIT: für den Performance-Test war das komplette Halten im RAM aber schon okay, denn I/O-Leistung will man ja nicht mitbewerten bei Laufzeitvergleichen....

Pinoccio

2011-12-07, 22:51:01

Wenn du auf Speicherverbruach optimieren willst/musst, dann kann es je nach Anwendungsfall ja auch machbar sein, ein Array voller byte zu nutzen. Die sind wirklich nur 1 Byte je Element groß (+etwas Overhead). Mustersuchen müssten damit auch gehen.

Tiamat

2011-12-08, 10:45:33

Nein es ist in Java nicht möglich auf Speicherverbrauch zu optimieren.
Der kleinste numerische Datentyp den die JVM kennt ist Integer(4byte).
D.h Bool, Byte,Short, Char werden in der JVM als Integer verarbeitet ^^

Ansonsten StringBuffer und StringBuilder haben einen enormen Speicherverbrauch weil mutable, sind aber aber auch viel schneller als das ganze mit immutable Strings zu handeln.

Wieso speicherst du du überhaupt den Line-Seperator? Den würd ich weglassen.

PatkIllA

2011-12-08, 10:49:22

Nein es ist in Java nicht möglich auf Speicherverbrauch zu optimieren.
Der kleinste numerische Datentyp den die JVM kennt ist Integer(4byte).
D.h Bool, Byte,Short, Char werden in der JVM als Integer verarbeitet ^^Quelle?
Ansonsten StringBuffer und StringBuilder haben einen enormen Speicherverbrauch weil mutable, sind aber aber auch viel schneller als das ganze mit immutable Strings zu handeln.
Mutable oder nicht hat erstmal keine Auswirkung auf den Speicherverbrauch.

Tiamat

2011-12-08, 11:10:29

JVM Spezifikation von Sun an. Stichwort JVM Datentypen.

Der StringBuilder braucht schon mal ein Int-Array(in JVM) als Basis. Jedes Zeichen verbraucht dann schon mal 4 byte an Platz und das macht sich dann in der Masse eben bemerkbar.
Man stelle sich vor, Mutable wäre standard, dann würde jeder String solch einen Overhead tragen. Deswegen ist String ist kaum einer Sprache mutable als standard.
Arrays haben in Java ja auch n Mords-Overhead..

PatkIllA

2011-12-08, 11:16:09

Dass ein byte Array intern für jeden Eintrag einen int hat ist so absurd, dass ich da gerne mal einen konkreten Link für hätte.
Außerdem kann man nicht den Bytecode und das was nachher konkret im Speicher stattfindet in einen Topf werfen.

Tiamat

2011-12-08, 11:23:44

Der Compiler übersetzt die absurden Schritte bereits.Die JVM kann selbst nur Bytecode ausführen. Google Stichwort "JVM Architektur" such dir einen raus.
Ansonsten landet "JVM Specification" beim Toplink auf das offizielle Dokument von sun.

Watson007

2011-12-08, 11:30:57

][immy

2011-12-08, 11:31:21

also von 64 auf 600 mb ist schon enorm.
aber probier mal folgendes. Ich weiß java ist nicht .net aber ich meine der garbage-collector arbeitet hier ähnlich.
1. Lese zeilenweise (machst du in deinem ersten beispiel ja schon) ein (wenn du alles auf einmal ließt dürftest du a einen hohe cpu-last haben und b du hast 64-mb im speicher die du ein paar sekunden später nicht mehr brauchst)
2. was möglich/sinnvoll ist, lager in eine neue methode aus. zumindest der garbage-collector von .net wird erst nach einem methodenaufruf aktiv, selbst wenn in der methode keine referenz mehr auf ein objekt exisitiert räumt er die objekte nicht ab (so müllt man schnell den speicher voll, gerade wenn man dateien hintereinander einliest)
d.h. das einlesen der Datei in einem methode auslagern und den stringbuilder zurückgeben.
3. vergess nicht den reader zu schließen

was noch sinnvoll sein kann ist, statt append(sep) den seperator per "+" hinzufügen. ich habe schon häufig die erfahrung gemacht das "+" bei kleinen um einiges schneller ist als alles andere.

wie gesagt, das wäre zumindest das was ich dir in .net raten würde, ich weiß nicht ob sich das so auf die java-welt übertragen lässt.

sogar Boolean?! kann ich mir nicht vorstellen, das ist ja Verschwendung pur.
es steht dir natürlich frei einen int wert als 32 booleans zu missbrauchen, aber ich würde davon abraten. aus performance-sicht machen kleinere einheiten keinen sinn.

Tiamat

2011-12-08, 11:33:31

Ja das ist kein Witz. Es lohnt sich wirklich, die Architektur der VM mal anzuschauen.
Deswegen gabs da ja in Vergangenheit diverse Eigenentwicklungen, weil man mit der Referenzimplementierung(Sun) in der Hinsicht nicht zufrieden war..

#44

2011-12-08, 11:35:35

[immy;9069505']ich habe schon häufig die erfahrung gemacht das "+" bei kleinen um einiges schneller ist als alles andere.
So wie die Interna des StringBuilders aussehen, könnte das tatsächlich schneller sein.

Trap

2011-12-08, 11:48:23

sogar Boolean?! :eek: kann ich mir nicht vorstellen, das ist ja Verschwendung pur.
Nö, booleans brauchen genau 1 Byte und es ist kein Problem 240 Arrays mit 1024*1024 booleans bei der default Heapgröße von 256 MB zu erzeugen.

Pinoccio

2011-12-08, 12:37:14

Nein es ist in Java nicht möglich auf Speicherverbrauch zu optimieren.
Der kleinste numerische Datentyp den die JVM kennt ist Integer(4byte).
D.h Bool, Byte,Short, Char werden in der JVM als Integer verarbeitet ^^Aufm Stack!
Im Arbeitsspeicher benötigt ein Byte-Array 1 Byte je Element. Probiers aus, falls du es nicht glaubst.

sogar Boolean?! :eek: kann ich mir nicht vorstellen, das ist ja Verschwendung pur.Das ist so. Ist wohl intern leichter umzusetzen. Und wer gaaanz viele einzelne Bits benötigt, der nimmt halt ein BitSet (http://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html).

mfg

Monger

2011-12-08, 14:13:02

sogar Boolean?! :eek: kann ich mir nicht vorstellen, das ist ja Verschwendung pur.
Ja, auch Bool.

Die CPU hat eh keine dedizierten Schaltkreise für boolesche Operationen. Da wird immer ein Register (d.h. Int) belegt. Und normalerweise schlucken ja nicht einzelne Bool Werte viel Speicher, sondern große Datenstrukturen. Macht deshalb schon Sinn was Sun da macht.

PatkIllA

2011-12-08, 15:16:37

Exxtreme

2011-12-08, 15:41:46

Im register schon, aber im Speicher doch nicht.
Da werden normalerweise die Felder noch an gewissen Grenzen ausgerichtet aber ein Bool, byte oder short braucht doch nicht mmer gleich 4 Byte?!?
Insbesondere ein ByteArray wird nicht für jeden Eintrag 4 Byte verwenden.
Ich glaube, der RAM kann auch nicht einen Byte speichern ohne Füllbytes. Ist aber schon länger her und deshalb könnte ich mich irren.

Gast

2011-12-08, 18:26:00

kannst du da Software (Freeware) empfehlen?
Netbeans, da kommt ein erstklassiger Profiler mit.

Gast

2011-12-08, 20:06:36

Lass doch mal das "sb.setLength(0)" weg. Falls es stimmt, dass das toString() optimiert wird und deshalb nachfolgende Operationen eine Kopieraktion auslösen, müsstest du so die Hälfte des Speichers sparen.

Sind in der Datei Umlaute oder so? Evtl. stimmt deswegen die Größe des StringBuilders nicht - pack einfach mal testweise 100 Zeichen drauf, vll. macht das nen Unterschied.
Oder du hängst vll einen Zeilenumbruch zuviel an.
Oder es sind Linefeeds in der Datei und du verwendest CRLF (-> größer)
-> Falls irgendwas mit der initialen Größe des StringBuilders nicht stimmt, kommt es da auch wieder zu Kopieraktionen.

Das wären die 2 Punkte, an denen ich ansetzen würde.

Watson007

2011-12-08, 21:57:58

Lass doch mal das "sb.setLength(0)" weg. Falls es stimmt, dass das toString() optimiert wird und deshalb nachfolgende Operationen eine Kopieraktion auslösen, müsstest du so die Hälfte des Speichers sparen.

hmm durch das completeString = sb.toString(); scheint er wohl doch eine Kopieraktion auszuführen, ohne habe ich reproduzierbar etwa 100 mb mehr RAM.... ich hatte aber was anderes dazu im Internet gelesen.

für die nachfolgenden Tests habe ich es wieder reingenommen.

Oder es sind Linefeeds in der Datei und du verwendest CRLF (-> größer)

der linefeed macht es tatsächlich signifikant größer. Ich habe da mal ohne hinzufügen von Zeilenumbrüchen a), mit hinzufügen eines \n als Zeilenumbruch b) und hinzufügen von \r\n (zwei Zeichen) als Zeilenumbruch getestet c).

a) benötigte etwa 330 MB, b) etwa 333 MB, aber c) dann 600 MB. Das verstehe ich nicht, dass mit zwei Zeichen als Zeilenumbruch der Speicherverbrauch auf fast das doppelte steigt.... ist doch nicht jedes zweite Zeichen ein Zeilenumbruch, das ist ein natürlichsprachiger Text. Ich lese zeilenweise aus.

-> Falls irgendwas mit der initialen Größe des StringBuilders nicht stimmt, kommt es da auch wieder zu Kopieraktionen.

die initiale größe des Stringbuilders ist entsprechend der Dateigröße, siehe File file = new File(patternFile);
int fileLength = (int) file.length();
file = null;
StringBuilder sb = new StringBuilder(fileLength);
[..]

Kleines Problem: Ich würde ja gerne die Zeilenumbrüche weglassen, aber das Patternfile (wonach ich suche) enthält ebenfalls Zeilenumbrüche. Wenn ich die ZÜ beim einlesen in den Stringbuilder weglasse oder durch \n ersetze findet er das Muster nicht mehr, weil das Muster eben \r\n verwendet.

Das ist eine unter Windows erstellte Textdatei und entsprechend hat es \r\n=Zwei Zeichen pro Zeilenumbruch.

Watson007

2011-12-08, 22:12:11

oh da ist mir ein kleiner Fehler passiert, ich hatte den Stringbuilder zwar mit der Dateigröße initialisiert, aber nicht mit der von der Gesamtdatei, sondern von der Musterdatei.

statt

File file = new File(patternFile);

muss es heissen

File file = new File(loadPath);

bei sonst unverändertem Code zur Ausgangsversion habe ich damit 540 mb statt 600 mb, macht also nicht viel aus.

Ich überlege gerade ob ich die Zuweisung vom Stringbuilder auf den completeString einsparen kann weil der Stringbuilder auch die .charAt-Methode kennt, aber dann muss ich trotzdem einiges ändern.... statt = mit add arbeiten etc.

Trap

2011-12-08, 22:25:59

Den Speicherverbrauch nachzuvollziehen ist ja ganz sinnvoll, aber meinst du wirklich, dass Optimierung bei nur 600 Mb Speicherverbrauch irgendwas bringt?

Watson007

2011-12-08, 22:30:15

mein Rechner hat nur 2 GB Ram. Außerdem will ich die Suche mit größeren Dateien testen.

die Patterndatei war übrigens 1 kb groß, daran lag es auch nicht.

ich hatte jetzt übrigens sowohl bei der Patterndatei als auch bei der Gesamtdatei beim Einlesen die Zeilenumbrüche weggelassen, dann funktioniert die Suche natürlich wieder... aber die gefundene Position im Text ist dann nicht wirklich repräsentativ, weil eigentlich haben die Dateien ja Zeilenumbrüche.

Watson007

2011-12-08, 23:42:54

hehe... ich habe das jetzt so gemacht, ich lese Gesamtdatei und Patterndatei zeilenweise ein und füge jeweils nur ein Zeichen \n als Zeichenumbruch hinzu, unabhängig von der Ausgangsdatei.

Beim Suchalgorithmus zähle ich die Zeilenumbrüche mit und addiere die dann auf die gefundene Position drauf. Funktioniert wie vorher, aber warum der 2-Zeichen-Zeilenumbruch soviel mehr RAM benötigt verstehe ich nicht - verdoppelt sich ja fast der Speicherverbrauch, wie schon gesagt.

davon ab könnte die Datei ja auch von Unix stammen, wie stelle ich denn da fest ob ich nicht umsonst das 2. Zeichen für jeden Zeilenumbruch hinzuaddiere?! Die Suchposition soll ja schon immer stimmen.

Noch sinnvoller wäre es die Datei nicht komplett im RAM zu halten, aber für Laufzeitmessungen ist das nicht so sinnvoll, denn man will ja nicht die I/O-Leistung mitmessen.

Gast

2011-12-09, 08:53:29

Ich nehme an, du hast das schon geprüft, aber sind in der Textdatei wirklich "\r\n" als Zeilenumbrüche?
Je nach Texteditor könnten da auch nur "\n"s sein (auch unter Windows).
Das war auch mein Hintergedanke.

Und wie gesagt: Falls die Datei nicht mit einem Zeilenumbruch endet, fügst du einen Umbruch zuviel hinzu, übersteigst damit die Länge und das könnte ebenfalls durch Kopieren und noch-nicht-abräumen den Speicherverbauch erklären.

Mach doch mal Debug-Ausgaben, bei denen du Dateigröße und (ganz am Ende) die Länge des Strings ausgibst.
Falls das nicht übereinstimmt, solltest du weiter nachforschen. Falls nicht ists noch was anderes.

Watson007

2011-12-09, 14:37:00

hmm interessant:

Dateigröße auf Festplatte, immer dieselbe Datei natürlich: 65784159 Bytes
Stringbuilder wird nun immer auf die genaue Dateigröße initialisiert, über den Konstruktor.

mit Ein-Zeichen-Zeilenumbruch:
Dateigröße im RAM: 64477258
1654 ms Zeit benötigt zum Datei-Laden.
RAM-Verbrauch der java.exe: ca. 330 MB

mit Zwei-Zeichen-Zeilenumbruch:
Dateigröße im RAM: 65784171
2662 ms Zeit benötigt zum Datei-Laden.
RAM-Verbrauch der java.exe: ca 540 MB

mit Zwei-Zeichen-Zeilenumbruch und jetzt Sonderfall: ich initialisiere den Konstruktor vom Stringbuilder mit Dateigröße +20 Bytes
Dateigröße im RAM: 65784171
1945 ms Zeit benötigt zum Datei-Laden.
RAM-Verbrauch der java.exe: ca. 333 MB

Schlussfolgerungen: 1. Datei muss 2-Zeichen-Zeilenumbruch enthalten da Dateigrößen sich sonst signifikant unterscheiden und 2. mit zeilenweisem Einlesen und manueller Hinzufügung eines 2-Zeichen-Zeilenumbruchs komme ich nicht genau auf die ursprüngliche Dateigröße sondern ein paar Bytes drüber, wodurch der Stringbuilder offenbar umkopiert.

12 Bytes Unterschied... wahrscheinlich noch mehr, weil am Anfang einer Textdatei ja vermutlich noch Metainformationen stehen.... aber auf welche Größe sollte man den Stringbuilder dann immer initialisieren, damit er nie umkopiert?!

#44

2011-12-09, 15:42:00

Dateigröße im RAM:
Wie hast du die bestimmt?

Watson007

2011-12-09, 16:45:22

mittels taskmanager... meinst du der Taskmanager zeigt was falsches an? Das er zuviel anzeigt kann ich mir schon vorstellen, aber die relativen Vergleichsgrößen müssten doch stimmen, oder?

er braucht auf jeden fall signifikant mehr wenn ich 2-zeichen-zeilenumbrüche verwende und der puffer des stringbuilders die 12 byte zu klein ist.

Shink

2011-12-09, 20:46:15

mittels taskmanager... meinst du der Taskmanager zeigt was falsches an?
Naja... der Taskmanager zeigt dir an wieviel Speicher Java für den Heap reserviert hat - wieviel davon belegt ist steht da nicht. Probier' doch mal JConsole.

Gast

2011-12-09, 22:11:15

Ich würde jetzt nicht auf dem taskmanager rumhacken, denn die einlesezeit und die symptome sprechen ja ne recht eindeutige sprache.

12 bytes unterschied ist tatsächlich merkwürdig - evtl. durch umlaute kombiniert mit einem falsch eingestellten encoding? (bei utf-8 werden ja umlaute zu 2 zeichen, falsch sie falsch interpretiert werden)

falls das jetzt nicht 100% akurat sein muss, würde ich einfach 100 byte auf die dateigröße draufpacken.
allerdings kann es bei einem encoding-problem sein, dass deine suchalgorithmen nicht funktionieren.
ab hier musst du wohl selbst weiterkommen. :)

][immy

2011-12-09, 22:55:58

mal ne ganze blöde frage, ist es unter java möglich den stringbuilder mit einer vorgegeben startgröße zu erstellen?
die theorie kommt jetzt wieder von meinem .net wissen. Wenn z.B. eine Liste erstellt wird (was wohl im hintegrund mehr oder minder passiert) und man keine anfangsgröße vorgibt wird eine Liste mit 0 möglichen elementen erzeugt (also entsprechend speicher reserviert).
wird dann ein element hinzugefügt, wird die alte liste verworfen, und einen neue liste erstellt, welche mindestens 1 groß. Im nächsten schritt würde dann eine neue liste erstellt die 2 groß ist und mittels array-copy in die neue liste übertragenst, dann 4, 8,..... (den rest könnt ihr euch wohl denken).
daher ist es gerade unter .net wichtig (wenn man speicher und performance sparen will) listen vorzuinitialisieren. d.h. es ist besser zu raten als gar nichts zu setzen. das spart besonders dem garbage-collector viel arbeit. zudem, wenn das alles in einer methode passiert, hat man also x listen, die noch bis zum beenden der methode im speicher liegen und erst dann vom GC abgeräumt werden.
da der stringbuilder nach einem ähnliches prinzip arbeiten dürfte, wäre es vielleicht auch hier möglich diesen vorzuinitialiseren. z.B. reservier dir doch mal direkt so viel speicher wie die datei groß ist. brauchen wirst du den so oder so.

wie gesagt, .net wissen, lässt sich vielleicht auch nicht auf java übertragen.

Pinoccio

2011-12-10, 12:11:09

[immy;9071807']mal ne ganze blöde frage, ist es unter java möglich den stringbuilder mit einer vorgegeben startgröße zu erstellen?
die theorie kommt jetzt wieder[...]

wie gesagt, .net wissen, lässt sich vielleicht auch nicht auf java übertragen.Gibt es in JAVA auch.
StringBuilder(int capacity) (http://docs.oracle.com/javase/7/docs/api/java/lang/StringBuilder.html#StringBuilder%28int%29)
Sollte man natürlich nutzen, wenn man a) weiß, wieviel Platz man benötigt und b) es auf Performance ankommt. Wird im Code aus dem ersten Post ja auch gemacht.

Ansonsten: Es gab hier doch mal (die Idee eines)/einen Programmierwettbewerb, das wäre dochw as hier. Definierte Dateien, definierte Anforderungen, Bewertung anch Speicherplatz bei geringer Zeit. Was meint ihr?

mfg

Watson007

2011-12-10, 17:44:53

ich habe jetzt eine bessere Variante zum Einlesen programmiert. Die alte Variante war schon aus zwei Gründen schlecht, zum einen wegen diesen komischen 12 Bytes Overhead und zum zweiten weil die gefundene Suchposition eines Musters falsch wäre wenn man z. b. eine Datei mit Ein-Zeichen-Zeilenumbrüchen öffnet und diese ins RAM immer zeilenweise einliest und mit Zwei-Zeichen-Zeilenumbrüchen ergänzt. Die Zeilenumbruchszeichen aus den Systemeigenschaften auszulesen und für den Stringbuilder zu benutzen wäre auch falsch, denn schlussendlich hängt es von der Datei selbst ab.

Das hier ist die klügere Variante:

completeString = new StringBuilder(fileLength);
try
{
char[] ioBuf = new char[1000];
/* buffer liefert Anzahl gelesener Zeichen zurück, siehe auch
http://www.dpunkt.de/java/Referenz/Das_Paket_java.io/4.html#read%28%29 */
int buffer = 0;

BufferedReader br = new BufferedReader(new FileReader(loadPath));
while ((buffer = br.read(ioBuf,0,1000)) == 1000)
{
/* eingelesene Zeile anhängen */
completeString.append(ioBuf);
/* Array wieder leeren falls nur weniger Zeichen eingelesen werden können */
ioBuf = new char[1000];
}
/* die letzten gelesenen Zeichen müssen auch hinzugefügt werden */
/* -1 wäre wenn von vornherein gar kein Zeichen eingelesen werden konnte */
if (buffer != -1)
{
for (int i=0;i<buffer;i++)
completeString.append(ioBuf[i]);
}
br.close();
} catch (IOException e)
{
println("Datei konnte nicht eingelesen werden!");
return;
}

Diese Variante ist übrigens in meinen Tests auch immer schneller gewesen als die mit dem zeilenweisen Einlesen. Und der StringBuilder muss keine Umkopieraktionen mehr starten, da Größe im RAM identisch zur Festplatten-Datei.

Ich habe danach die Datei im RAM wieder auf Festplatte geschrieben und sie war binär mit dem Original identisch (mit Kdiff verglichen).

Für Suchalgorithmen ist das hier die bessere Variante.

EDIT: die Variante vom Gast von Seite 1 habe ich noch gar nicht getestet:

byte[] data = Files.readAllBytes(Paths.get("/tmp/inputfile"));
String s = new String(data);

ABER: laut http://docs.oracle.com/javase/tutorial/essential/io/file.html ist das wohl eher eine Methode für kleine Dateien:

Commonly Used Methods for Small Files
Reading All Bytes or Lines from a File

If you have a small-ish file and you would like to read its entire contents in one pass, you can use the readAllBytes(Path) or readAllLines(Path, Charset) method. These methods take care of most of the work for you, such as opening and closing the stream, but are not intended for handling large files. The following code shows how to use the readAllBytes method:

Watson007

2011-12-10, 18:12:41

ich hatte übrigens auch eine Variante zum zeichenweisen Einlesen getestet:

completeString = new StringBuilder(fileLength);
try
{
int thisChar;
BufferedReader br = new BufferedReader(new FileReader(loadPath));
while ((thisChar = br.read()) != -1)
{
/* eingelesene Zeile anhängen */
completeString.append((char) thisChar);
}
br.close();
} catch (IOException e)
{
println("Datei konnte nicht eingelesen werden!");
return;
}

war aber immer 4-5x langsamer als die mit den 1000 Zeichen pro Rutsch zu lesen.... vermutlich auch wegen dem Cast, aber ohne gehts nicht.

Die Größe im RAM war damit aber auch genauso wie auf Festplatte.

Watson007

2011-12-10, 21:31:16

mit dieser Variante bin ich übrigens genau 10 Bytes im RAM über Dateigrösse:

/* eigentliches Einlesen */
String lines[] = loadStrings(loadPath);
completeString.append(trim(join(lines, sep)));
lines = null;

println("Dateigröße im RAM: " + completeString.length());

das ist die Variante die am meisten RAM benötigt, ich hatte über 700 MB gemessen für die gleiche Testdatei...

als ich noch zeilenweise eingelesen habe habe ich ja immer nachträglich einen Zeilenumbruch hinzugefügt. Nach den letzten Zeichen kam in der Datei auf Festplatte vermutlich gar kein Zeilenumbruch mehr, deswegen 12 statt 10 Bytes Überlauf beim zeilenweisen Einlesen...

PatkIllA

2011-12-11, 07:28:20

Da Java pro Zeichen 16 Bits verwendet braucht der string im RAM mindestens doppelt so viel Speicher wie in der Datei bei einer 8 Bit Kodierung.

Bei deinem letzten Beispiel wird noch viel mehr umkopiert, als beim StringBuilder.

Gast

2011-12-11, 12:38:48

Ja, vermutlich(!) ist es schneller, ein großes char[]-Array zu machen, die Datei komplett einzulesen und aus dem Array dann direkt einen String zu machen (braucht man auch keinen StringBuilder mehr)

ABER: dass du weiterhin eine Größendifferenz hast, weist auf ein Encoding-Problem hin. Ich weiß nicht, warum du das so penetrant überliest.

PatkIllA

2011-12-11, 12:49:00

Ja, vermutlich(!) ist es schneller, ein großes char[]-Array zu machen, die Datei komplett einzulesen und aus dem Array dann direkt einen String zu machen (braucht man auch keinen StringBuilder mehr)Wobei er ja beim letzten Beispiel die Zeilen einzeln einliest.

#44

2011-12-11, 13:04:03

Diese Variante ist übrigens in meinen Tests auch immer schneller gewesen als die mit dem zeilenweisen Einlesen.
Das ist nur logisch - für uns ist Zeilenweise lesen natürlich, im Computer ist der Zeilenumbruch auch nur ein Zeichen des Textes, welches erst einmal gefunden werden muss.

@Gast: Ich lese im Posting zur Methode mit dem blockweisen Einlesen nichts von einer Größendifferenz.

Watson007

2011-12-11, 14:04:08

nein, beim blockweisen Einlesen habe ich keine Größendifferenz mehr :)

das mit dem umkopieren vom StringBuilder in den String mit .toString() hatte auch so um die 100 MB RAM gefordert meine ich... kann ich gleich nochmal überprüfen.

Achja mit den Encodings kenne ich mich leider nicht aus... sollte man mal einen kurs zu belegen ;)
was wäre eigentlich wenn die Datei in 16-bit-unicode vorliegt und man liest in ein byte-Array ein, dann müsste man zwei Zeichen vom byte-Array zusammennehmen um das Zeichen wirklich auswerten zu können, oder?

Watson007

2011-12-11, 16:02:29

doch doch, die toString-Methode vom StringBuilder kostet definitiv Arbeitsspeicher.

macht bei mir gerade den Unterschied zwischen 160 und 290 MB RAM-Nutzung aus (wieder laut Taskmanager), lediglich mit dieser einen zusätzlichen Zeile:

String test=completeString.toString();

das ist ja doof, da muss man ja direkt mit dem StringBuilder weiterarbeiten :(

aber 160 MB RAM für ne 65 MB-Datei ist nun in Ordnung, schätze ich.

leider im Moment keine Zeit um mich in die Profiling-Tools einzuarbeiten die hier empfohlen wurden, vielleicht später....

Berni

2011-12-11, 23:31:03

Watson007

2011-12-11, 23:39:44

Kannst du eigtl. das PatternMatching nicht während dem Einlesen machen und dir somit das Speichern des Gesamtstrings komplett sparen? Das Pattern muss dann natürlich so vorbereitet sein, dass es nicht für jede Zeile neu gelesen werden muss aus der Datei.

dazu habe ich schon einmal etwas geschrieben, wenn man Laufzeitanalysen von Algorithmen macht will man nicht die I/O-Leistung mitmessen. Es gibt aber auch so Anwendungsfälle wo das sinnvoll ist (etwa bei einem Texteditor die suche, wenn die datei eh im ram ist), aber im Allgemeinen hast du natürlich recht. Allerdings muss man dabei auch beachten das nicht alle Suchalgorithmen nur vorwärts suchen, sondern auch mal zurückspringen - fürs teilweise Datenspeichern ist daher nicht jeder Algorithmus gleichermaßen geeignet (mit geschickter Programmierung kann mans aber sicher dennoch schaffen).

Watson007

2011-12-11, 23:44:45

Etwas anderes, Freak wie ich bin habe ich nun auch mal Tests in .NET durchgeführt: :D

Folgende Unterschiede habe ich bemerkt: 1. wenn der .NET-Stringbuilder zu klein ist braucht er fürs umkopieren deutlich weniger RAM, geht aber auch wesentlich schneller zugange als bei Java. 2. der .NET-StringBuilder benötigt für die .ToString()-Methode definitiv keinen zusätzlichen RAM, der Java-StringBuilder aber sehr wohl.

Das Problem mit den 12 Zeichen-Overhead beim zeilenweisen Einlesen mit dieser Testdatei besteht auch unter .NET, muss man daher ebenfalls beim Initialisieren des StringBuilders beachten (Konstruktor).

Allgemein ist demnach immer das blockweise Einlesen zu bevorzugen.

Dateigröße auf Festplatte, immer dieselbe Datei natürlich: 65784159 Bytes

zeilenweises Einlesen mit nötigem Overhead:
Dateigröße im RAM: 657894171
Overhead: 12 Zeichen
00:00:01.3150752 Sekunden Zeit benötigt zum Datei-Laden.
RAM-Verbrauch der ConsoleApplication1.vshost.exe: 140 MB

zeilenweises Einlesen ohne die nötigen 12 Zeichen Overhead:
Dateigröße im RAM: 657894171
Overhead: 12 Zeichen
00:00:01.5490886 Sekunden Zeit benötigt zum Datei-Laden.
RAM-Verbrauch der ConsoleApplication1.vshost.exe: 270 MB

zeichenweises Einlesen:
Dateigröße im RAM: 65784159
00:00:04.0932341 Sekunden Zeit benötigt zum Datei-Laden.
RAM-Verbrauch der ConsoleApplication1.vshost.exe: 140 MB

in 1000-Zeichen-Blöcken einlesen:
Dateigröße im RAM: 65784159
00:00:00.8660495 Sekunden Zeit benötigt zum Datei-Laden.
RAM-Verbrauch der ConsoleApplication1.vshost.exe: 140 MB

4) Lesen direkt in String mit ReadAllText-Methode.
Dateigröße im RAM: 65784159
Overhead: 0 Zeichen
00:00:01.0040574 Sekunden Zeit benötigt zum Datei-Laden.
RAM-Verbrauch der ConsoleApplication1.vshost.exe: 270 MB

Gast

2011-12-12, 17:29:18

nein, beim blockweisen Einlesen habe ich keine Größendifferenz mehr :)
oh, dann bin ich durcheinander gekommen.

GMP

2011-12-20, 09:24:36

while ((buffer = br.read(ioBuf,0,1000)) == 1000)
{
/* eingelesene Zeile anhängen */
completeString.append(ioBuf);
/* Array wieder leeren falls nur weniger Zeichen eingelesen werden können */
ioBuf = new char[1000];
}
/* die letzten gelesenen Zeichen müssen auch hinzugefügt werden */
/* -1 wäre wenn von vornherein gar kein Zeichen eingelesen werden konnte */
if (buffer != -1)
{
for (int i=0;i<buffer;i++)
completeString.append(ioBuf[i]);
}

Gott hast du wenig Vertrauen in Java :) da steht doch
while ((buffer = br.read(ioBuf,0,1000)) == 1000)
also beweist schon die Tatsache das die Zeile
/* Array wieder leeren falls nur weniger Zeichen eingelesen werden können */
ioBuf = new char[1000];
ausgeführt würde das du 1000 Chars gelesen hast :) Auch brauchst du deinen Array gar nicht leeren weil du richtigerweise an jeder Stelle nur so viel von dem Array in deinen Builder schreibst wie du auch gelesen hast. Zusätzlich sparst du dir ggf nochmal ein bischen Speicher und GC-Zeit wenn du die Zeile raus nimmst, aber ich schätze mal die Aufgabe wurde euch schon abgenommen, ansonsten sähe ggf. auch das hier eleganter aus
while ((buffer = br.read(ioBuf)) != -1) {
/* so viel wie gelesen wurde anhängen */
completeString.append(ioBuf,0,buffer);
}

Watson007

2012-01-17, 21:32:32

Auch brauchst du deinen Array gar nicht leeren weil du richtigerweise an jeder Stelle nur so viel von dem Array in deinen Builder schreibst wie du auch gelesen hast.

das weiss ich, habe ich wegen dem nachfolgenden Code NACH der Schleife gemacht. Weil im letzten Durchlauf weniger als die 1000 Zeichen gelesen werden, das heisst der Rest des Arrays ist dann noch mit den Zeichen aus dem vorletzten Durchlauf gefüllt.

den Stringbuilder.append-Befehl gibt es überladen auch mit drei Parametern?! append(char[] str, int offset, int len). Habe ich nicht gesehen, danke. Ich arbeite hier zu einem Großteil mit Processing, das auf Java basiert aber keine Befehlsvervollständigung anbietet.

Welche Variante vom read()-Befehl hast du denn da genommen? Nur mit char-Array als Parameter? Wird hier doch gar nicht aufgelistet, aber funktioniert. http://docs.oracle.com/javase/1.4.2/docs/api/java/io/BufferedReader.html Schätze er liest dadurch zeichenweise aus - was sonst wenn du keine Menge übergibst - aber davon würde ich performancetechnisch abraten, intern wird immer blockweise ausgelesen.

Grundsätzlich sind deine Änderungen aber performancetechnisch irrelevant.