# Textdatei (1GB) einlesen und verarbeiten



## heffernan (10. Nov 2010)

Hi,

ich möchte eine ca. 1GB große Textdatei einlesen die im Prinzip das folgende Format aufweist:

Name1 [tab] wert1 [tab2] wert3 [tab] ...
Name2 [tab] wert1 [tab2] wert3 [tab] ...

Es handelt sich hier um eine Größenordnung von ca. 50.000 Objekten mit je 1.300 Werten. Sofern ich die zugehörigen Instanzen mit Zufallszahlen fülle, funktioniert das tadellos. Wenn ich die Daten aber aus einer Datei einlese, reichen 4GB RAM dafür nicht aus. Die Fehlermeldung ist zum einen ein voller Heapspace und zum anderen diese GC Warnung, da selbiger mit dem Aufräumen nicht hinterherkommt. Heapspace wurden bereits auf ein Maximum gesetzt und auch die GC Unterdrückung wurde probiert.

Wie kann ich diesen Flaschenhals umgehen?

Folgend der abgespeckte Code. Jede Zeile repräsentiert also ein Objekt, die zugehörige Klasse ist die folgende:


```
public class Probeset {

	public String id = "";
	public double [] values = new double[1500]; 
	
	public Probeset() {}	
}
```

Diese Objekte möchte ich zur späteren Weiterverarbeitung speichern:


```
public class Probesets {
	
	public Probeset [] content 	= new Probeset[60000];
	
	public Probesets() {}
}
```



Das Hauptprogramm sieht wie folgt aus:


```
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.LineNumberReader;
import java.util.Random;

import v4.model.Probesets;
import v4.model.Probeset;

public class programm {
	
	static Probesets probesets = new Probesets();
	
	public static void main(String[] args) {		
		
		final String FILENAME = "data/tempfile_54000-1360.csv";	

		try {
			BufferedReader br = new BufferedReader(new FileReader(FILENAME));
			
			int counter = 0;
		    
			while (br.ready()) {		    	
				
		    	String current_line = br.readLine();
		    	
		    	// erste Zeile enthält Ueberschriften
		    	if(counter  > 1)
		    		fetch(current_line, counter);
		    	
		    	// Statusmeldung
		    	if(counter % 500 == 0)
		    			System.out.println(counter);	
		    
		    	counter++;
			} 
		    br.close();
		} catch ( IOException e ) { 
	    	System.out.println("Datei nicht vorhanden!");	    
	    } 

	}
	
	public static void fetch(String _input, int counter){
		
		String [] tmp = _input.split("\t");
		Probeset probeset = new Probeset(); 

		probeset.id = tmp[0];

		for (int i = 2; i < tmp.length; i++){
			probeset.values[i-2] = Double.parseDouble(tmp[i]);
		}
		
		probesets.content[counter] = probeset;
	}
}
```


----------



## MySelV (10. Nov 2010)

Hi,

da du mit den Daten sicher etwas vorhast (manipulieren / in DB speichern), ist die einzige (schöne) Variante die mir einfällt, die Verarbeitung sofort durchzuführen und das Objekt zu persistieren / in eine neue Datei zu schreiben. Ansonsten hält deine Liste ja alle erstellten Objekte.

Wenn du allerdings die Gesamtheit deiner Elemente auf einmal brauchst, habe ich auch keine Idee.

Gruß


----------



## Michael... (10. Nov 2010)

Bei 50.000 Objekten mit jeweils 1500 doubles kannst Du ja mal durchrechnen, wie viel Speicher du bräuchtest.
Man könnte sich überlegen, ob nicht float statt double ausreichen würde. Das würde den Speicherbedarf halbieren. Bin mir aber sicher, dass Dein Rechner trotzdem noch zu wenig Speicher besitzt.

Grundsätzlich wäre für solche Datenmengen eine Datenbank interessant.
Wenn das nicht in Frage kommt, stellt sich die Frage: Brauch man alle Daten gleichzeitig im Speicher? Kann man nicht Daten nach Bedarf auslesen, was auch immer damit machen und danach wieder verwerfen?


----------



## Ark (10. Nov 2010)

Michael... hat gesagt.:


> Grundsätzlich wäre für solche Datenmengen eine Datenbank interessant.
> Wenn das nicht in Frage kommt, stellt sich die Frage: Brauch man alle Daten gleichzeitig im Speicher? Kann man nicht Daten nach Bedarf auslesen, was auch immer damit machen und danach wieder verwerfen?


Diesen Ansatz würde ich ebenfalls verfolgen.

Unabhängig davon aber eine wichtige Bemerkung: Wenn Lesbarkeit für einen Menschen nicht zwingend notwendig ist, solltest du darauf verzichten, double-Werte in Textform zu speichern. Das hat mehrere gute Gründe:

Die Genauigkeit nimmt durch solche Umwandlungen tendenziell ab.
Das Parsen der Zahlen dauert relativ lange.
Wahrscheinlich braucht die String-Repräsentation mehr Speicher als die 8 Byte fürs double.
Schau dir mal java.io.DataInputStream und java.io.DataOutputStream an. Damit kannst du auch primitive Werte wie double oder float direkt (ohne Genauigkeitsverlust) binär speichern. Intern verwenden die Klassen übrigens Double.longBitsToDouble(), Float.intBitsToFloat() usw., diese Methoden kannst du dir auch mal anschauen. Falls du nämlich nicht binär speichern kannst, dann kannst du immerhin mit diesen Methoden z.B. die Hexadezimaldarstellung der Bitmuster speichern.

Wenn es eine DB Marke Eigenbau sein soll, hier ein paar Denkanstöße, was man berücksichtigen muss:

Wie lang ist das, was du "Name" nennst? Könntest du dafür sorgen, dass alle Namen in Bytes gemessen(!) gleich lang sind?
Wie viele Werte stehen in einer Zeile? Immer gleich viele?
Brauchst du Direktzugriff auf einzelne Datensätze ("Zeilen"), oder wäre es denkbar, alle Operationen "on the fly" durchzuführen? Anders: Gibt es irgendwelche Abhängigkeiten in der Reihenfolge, wann welcher Datensatz verarbeitet werden soll, oder wäre auch ein stures von-oben-nach-unten-Abbarbeiten möglich? (Siehe hierzu auch das Zitierte am Anfang dieses Beitrags.)
Müssen die Namen in irgendeiner Art und Weise geordnet vorliegen?
Müssen Datensätze entfernt werden?
Ist genügend dauerhafter Speicher (Plattenplatz) verfügbar, um das Doppelte der aktuellen Datei/Datenbank zu speichern?
Ark


----------



## heffernan (11. Nov 2010)

Hallo,

erst einmal vielen Dank für die Antworten. Eine Anmerkung meinerseits vorweg. Sofern ich die oben beschriebenen Objekte zufällig mit Werten fülle, sind solche Größenordnungen kein Problem und auch in Bezug auf den Speicher einigermaßen tragbar. Der Flaschenhals hier ist also das Einlesen und mir fehlt das Verständnis, warum die entsprechenden Speicherbereiche nicht wieder frei gegeben werden, sobald eben genau dieser Schritt abgearbeitet wurde. Oder anders formuliert. Warum wird durch das Programm nach dem Einlesen der Daten nicht genausoviel Speicher belegt wie beim testweisen Füllen mit Zufallsdaten?

Die einzelnen Objekte (durch jeweils eine Zeile repräsentiert) müssen jeweils alle gegeneinander paarweise betrachtet werden. Die Reihenfolge ist egal. In dieser Größenordnung ergeben sich also (55k)² Dateizugriffe. Meine Idee war nun, dass ein einmaliges Einlesen zu Beginn Geschwindigkeitsvorteile bringt.

Die Datei binär zu speichern ist eine Idee. Nur bekomme ich diese Ausgangsdatei selbst von Dritten. Auch ein Abspeichern in einer Datenbank ist denkbar. Möchte den Aufwand möglichst gering halten. Ist SQL Lite eine Option?

Zu deinen Fragen Ark:

    * Wie lang ist das, was du "Name" nennst? Könntest du dafür sorgen, dass alle Namen in Bytes gemessen(!) gleich lang sind?

Nein, aber ich kann ja einen Index verwenden auf den dies zutrifft.

* Wie viele Werte stehen in einer Zeile? Immer gleich viele?

Ja..

    * Brauchst du Direktzugriff auf einzelne Datensätze ("Zeilen"), oder wäre es denkbar, alle Operationen "on the fly" durchzuführen? Anders: Gibt es irgendwelche Abhängigkeiten in der Reihenfolge, wann welcher Datensatz verarbeitet werden soll, oder wäre auch ein stures von-oben-nach-unten-Abbarbeiten möglich? (Siehe hierzu auch das Zitierte am Anfang dieses Beitrags.)

Die Reihenfolge ist egal. Jedes Objekt mit jedem Objekt (beidseitig), wobei die Objekte je eine Zeile in der Ausgangsdatei beanspruchen.

    * Müssen die Namen in irgendeiner Art und Weise geordnet vorliegen?

Nein.

    * Müssen Datensätze entfernt werden?

Nein.

    * Ist genügend dauerhafter Speicher (Plattenplatz) verfügbar, um das Doppelte der aktuellen Datei/Datenbank zu speichern?

Ja.

lG und vielen Dank einstweilen,
Stephan


----------



## fastjack (11. Nov 2010)

Ich würde immer grüppchenweise und zeilenweise lesen und verarbeiten. Also z.B. 100 Zeilen lesen, dann verarbeiten, dann alte Daten frei machen ("vergessen"), wieder 100 Zeilen lesen etc. Eeventuell macht es auch ein CSV-Framework performanter, z.B. flatpack, einfach mal googeln.


----------



## heffernan (11. Nov 2010)

Hallo fastjack,

wie mach ich den die alten Daten "frei"? Wenn ich den Ablauf aufteile und die Datei blockweise einlese, zeigt sich keine Veränderung im Speicherverbrauch. Es scheint, als wenn die Objekte - die im try-catch-Block verwendet werden - im Speicher verbeliben, auch wenn der Block beendet und mit dem nächsten Paket neu gestartet wurde.

Ich bekomme ja auch ab und an diese GC Fehlermeldung, dass der GarbageCollector nicht hinterherkommt.

lG


----------



## FArt (11. Nov 2010)

heffernan hat gesagt.:


> Hallo fastjack,
> 
> wie mach ich den die alten Daten "frei"? Wenn ich den Ablauf aufteile und die Datei blockweise einlese, zeigt sich keine Veränderung im Speicherverbrauch. Es scheint, als wenn die Objekte - die im try-catch-Block verwendet werden - im Speicher verbeliben, auch wenn der Block beendet und mit dem nächsten Paket neu gestartet wurde.
> 
> ...



Halte den Scope deiner temporären Objektinstanzen möglichst klein und verarbeite wenig Daten auf einmal. Den Rest erledigt der GC. 

Für Fortgeschrittene: wenn trotztdem sehr viele kleine neue Objekte oder mehrere große Objekte angelegt werden, sollte man per Profiler sicherstellen, dass der Speicherbereich für die "young generation" groß genug ist und die neuen Objekte somit da rein passen. Ein GC über die "young generation" ist relativ billig, ein GC über den restlichen Heap im Verhältnis dazu relativ teuer, in der Regel aber auch kein Beinbruch.

Deine Aufgabe lässt sich eigentlich mit sehr geringem Speicherverbrauch lösen.


----------



## Ark (11. Nov 2010)

Hm, Mist, ich habe vergessen zu fragen, ob Datensätze hinzugefügt werden müssen oder nicht, weil ich gar nicht in Betracht zog, dass man das alles vielleicht problemlos im Arbeitsspeicher unterkriegt. ^^

Also, hier ein sehr einfacher Ansatz:

```
import java.io.*;


public final class ValueDatabase{

	private double[] buf;
	private int rows;
	private int cols;
	public ValueDatabase(int rows,int cols,File data) throws IOException{
		this.rows=rows;
		this.cols=cols;
		buf=new double[rows*cols];
		DataInputStream dis=new DataInputStream(
			new BufferedInputStream(
				new FileInputStream(data)
			)
		);
		for(int i=0;i<buf.length;i++){
			buf[i]=dis.readDouble();
		}
		dis.close();
	}

	public void store(File data) throws IOException{
		/*
		 * In dieser Methode (oder beim Aufrufer) sind Anpassungen erforderlich,
		 * falls man verhindern möchte, dass aufgrund eines Fehlers der
		 * Datenbestand zerstört wird.
		 * Lösungsansatz: erst in eine Datei daten.new schreiben, dann die alte
		 * in daten.old umbenennen und dann die neue in daten umbenennen, erst
		 * dann die alte daten.old löschen.
		 */
		DataOutputStream dos=new DataOutputStream(
			new BufferedOutputStream(
				new FileOutputStream(data)
			)
		);
		for(int i=0;i<buf.length;i++){
			dos.writeDouble(buf[i]);
		}
		dos.close();
	}

	public double getValue(int row,int column){
		checkBounds(row,column);
		return buf[row*cols+column];
	}
	public void setValue(int row,int column,double value){
		checkBounds(row,column);
		buf[row*cols+column]=value;
	}

	private void checkBounds(int row,int column){
		if(row>=rows||row<0||column<0||column>cols){
			throw new IllegalArgumentException("illegal row or column: "+row+", "+column);
		}
	}
}
```
Das Ding ist momentan dafür gedacht, nur im Arbeitsspeicher zu operieren. Es sollte aber ein Leichtes sein, Anpassungen reinzubringen, um die Daten direkt auf der Datei zu verarbeiten (siehe java.io.RandomAccessFile), falls der Arbeitsspeicher dennoch nicht reichen sollte. Aktuell schätze ich den Speicherverbrauch auf knapp 500 MB.

Vorteil der Variante "im Arbeitsspeicher": maximale Geschwindigkeit.
Nachteile dieser Variante: Einfügen neuer Datensätze sehr aufwendig, Größe auf verfügbaren Arbeitsspeicher begrenzt.

Entsprechend ergeben sich daraus die Vor- und Nachteile der Variante "auf Festplatte".

Der Code oben geht davon aus, dass in der Datei die Daten binär gespeichert sind, nur die double-Werte in der Datei enthalten sind und keine Zeilen oder Spalten hinzugefügt werden müssen. Das Einlesen der Namen fehlt hier. Sollte nämlich die Variante "nur Festplatte" doch attraktiver erscheinen, ist es leichter, wenn unterschiedliche Namenslängen (in Bytes) kein Problem sind, deshalb habe ich die Namen hier einfach mal wegabstrahiert. 

Hilft das weiter?

Was du dich auch fragen solltest: Gibt es andere Programme, die darauf zugreifen können müssen, oder andere Programme, die diese Daten schreiben? Sind diese Programme in der Lage, genau in dem hier angenommenen Format zu schreiben/lesen? Stimmt die Byte-Reihenfolge (Big-Endian, Little-Endian)?

Ark

EDIT: Ach, ja, hier werden nur die Daten gespeichert. Irgendwelche Objekte, die woanders (wegen der Schnittstellen) benötigt werden, habe ich ebenfalls wegabstrahiert. Man kann sich aber vorstellen, dass die Objekte nur "on the fly" aus dem Datenbestand erzeugt, verarbeitet und dann wieder in den Datenbestand zurückgeführt werden.


----------



## heffernan (11. Nov 2010)

@Ark,

dein Vorschlag ist interessant und einleuchtend. Wollte mir gerade einen Parser schreiben, der mir die Textdatei in eine Binärdatei umschreibt und nunja, es benötigt noch eine Weile  In jedem Fall bleibt der Speicherverbrauch angenehm niedrig. Bisher 

Ich denke es ist ratsam die Daten im Speicher zu halten. Kann aber erst morgen berichten ob es (performant) funktioniert hat.

@FArt:
Auch wenn ich die Datei Blockweise einlesen lasse - unter Verwendung des BufferReaders entsprechend einfach Zeilen überspringe - ist kein großer Unterschied zum vorherigen Ansatz zu erkennen. Die RAM Obergrenze wird ungefähr in der gleichen Zeile erreicht. Auch ein "nullen" der entsprechenden Variablen hilft hier nicht weiter.



FArt hat gesagt.:


> Halte den Scope deiner temporären Objektinstanzen möglichst klein und verarbeite wenig Daten auf einmal. Den Rest erledigt der GC.



Ist damit überhaupt das von mir verwendete Prinzip gemeint? Der Scope des BufferReaders ist doch im Endeffekt nur die aktuelle Zeile.

lG und vielen Dank,
Stephan


----------



## FArt (11. Nov 2010)

heffernan hat gesagt.:


> Ist damit überhaupt das von mir verwendete Prinzip gemeint?


Nein, das ist eine allgemeine Aussage. Wenn deine Verarbeitung diesem Prinzip nicht entspricht, kann es eher vorkommen, dass der GC unnötig viel zu leisten hat oder der Speicherverbrauch unnötig hoch ist.
Unter Umständen muss man dann natürlich die Art und Weise, wie die Daten verarbeitet werden, überdenken. Ein Algorithmus ist (wenn es gut geht) einfach, performant und ressourcenschonend. Manchmal kann es passieren, dass ein Parameter aus dem Ruder läuft. Ein Gegensteuern beeinflusst gerne auch die anderen Faktoren, in der Regel negativ. Man muss dann halt den optimalen Weg für seine Bedürfnisse finden, was keine allgemeingültige Regel ist.


----------



## Ark (11. Nov 2010)

Es gibt einige mögliche Performance-Problemstellen in der alten Einlesemethode. Ich habe das mal kommentiert:

```
public static void main(String[] args) {		
		
		    	String current_line = br.readLine();
			// Jedes mal ein neuer String.
	}
	
	public static void fetch(String _input, int counter){
		
		String [] tmp = _input.split("\t");
		// Jedes mal ein neues Pattern und ein neuer Matcher plus
		// Daten zum Splitten selbst,
		// und für jede Zahl ein neuer String
		// und für jede Zeile ein neues Array.


		Probeset probeset = new Probeset();
		// Kann ich nicht beurteilen.

	}
```
Man sollte bedenken, dass der Heap-Speicher durch ständiges Erzeugen und Löschen von Objekten Fragmentierungen erfährt. Zwar kann da der GC etwas aufräumen, aber dazu braucht er selbst Platz (und Zeit).

@heffernan: Mein Ansatz hat vor allem zum Ziel, den minimalen Speicherverbrauch zu garantieren, wenn die Daten vollständig im Arbeitsspeicher gehalten werden sollen. Aber Vorsicht, mein Vorschlag ist (zumindest in der aktuellen Version) nicht sehr flexibel. Am schwierigsten wird das Einfügen neuer Datensätze, aber wenn du das nicht vorhaben solltest, sollte alles okay sein. 

Ark


----------



## heffernan (11. Nov 2010)

@Ark:

Mit der Unflexibilität kann ich leben 

Die Brisanz der von dir angemerkten Punkte ist mir klar. Nur wie kann ich diese umgehen? Einmal global deklarieren und immer wieder die gleiche Variable verwenden? Also sprich Überschreiben anstatt neu zu initialisieren?

In diesem Fall bekomm ich die schon angemerkte GC Fehlermeldung:
Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded

In jedem Schritt werden ja so 1500 neue String-Objekte erstellt. Dass das bei zichtausend Durchläufen Probleme macht, sollte doch eigentlich der GC verhindern?! Kann man hier unterstützdend eingreifen? 

lG


----------



## FArt (11. Nov 2010)

heffernan hat gesagt.:


> Einmal global deklarieren und immer wieder die gleiche Variable verwenden? Also sprich Überschreiben anstatt neu zu initialisieren?
> 
> lG



Es geht nicht um deklarieren einer Variable sondern um instanziieren eines Objekts. Auf jeden Fall vergrößert man damit den Scope der Variable und das kann negativen Einfluß auf den GC haben.


----------



## heffernan (11. Nov 2010)

FArt hat gesagt.:


> Es geht nicht um deklarieren einer Variable sondern um instanziieren eines Objekts. Auf jeden Fall vergrößert man damit den Scope der Variable und das kann negativen Einfluß auf den GC haben.



Okay, nur muss ich auf die Bereiche der Datei zugreifen. Kannst du konkreter werden, was ich im oberen - ersten - Beispiel bzgl. der Instanzierung verbessern kann?

lG und vielen Dank,
Stephan


----------



## heffernan (23. Nov 2010)

Ich habe nun allerhand getestet und bin bei SQLite hängen geblieben. Die Handhabung ist wesentlich komfortabler als bei der  Verwendung von Binärdateien und der Speicherverbrauch bleibt schön niedrig.

Ich parse im Prinzip die Textdatei in die SQLite DB und ziehe mir dann zu Beginn den gesamten Datensatz von dort raus.

Klappt wunderbar. Vielen Dank einstweilen.


----------

