Java Perfomance fragen zum BufferedReader und string parsing

[Zespire]

Bin gerade dabei ein paar relativ große Dateien aus zu lesen dabei bin ich mit der Performance unzufrieden jetzt stellt sich mir die Frage was genau ich falsch mache oder wo der Flaschenhals liegt.

Was ich auch gerne wissen würde ist weshalb bei Zeile 18 das Programm ohne Rückmeldung den Dienst quittiert...

public class Main 
{
	public static void main(String[] args) throws IOException 
	{
		File file = new File("E:/Games/No Man's Sky/mod/NMSARC.1A1B4C22/MODELS/COMMON/SPACECRAFT/DRONE/DRONESHIP.GEOMETRY.MBIN.exml");
		BufferedReader in = new BufferedReader( new InputStreamReader(new FileInputStream(file), "UTF8"));
		
		GetVertices(in);
		
		in.close();
	}

	private static void GetVertices(BufferedReader _in) throws IOException
	{
		String currentLin = "";
		String result = "";
		int count = 0;
		//long totalLines =  _in.lines().count();	program stops without error
		String totalLines = "?";
		int currentPosition = 0;
		boolean gettingVertices = false;
		
 		while((currentLin = _in.readLine()) != null) 
		{
 			
			if(!gettingVertices && currentLin.equals("  <Property name=\"VertexStream\">"))
				gettingVertices = true;
	
			if(gettingVertices && currentLin.equals("  <Property name=\"SmallVertexStream\">"))
				return;//string

			if(gettingVertices)
			{
				currentLin = currentLin.replace("    <Property value=\"", "");
				currentLin = currentLin.replace("\" />","");
				if(count == 0)
					result += " v";
				result += " " + currentLin;
				count ++;
			}
			
			if(count == 3)
			{
				count = 0;
				result += "\n";
			}
			
			currentPosition ++;
			if(currentPosition % 5000 == 0)
			{
				System.out.println("current line =" + currentPosition + "total lines = " + totalLines);
			}
		}
	    System.out.println(result);
	}
}

 

[Burfi]

Das Performanceproblem liegt daran, dass du in der while Schleife jedes mal mehrfach neue String Objekte instanziierst und in die Variable result speicherst. Der Fehler ist also

result += "some String"

Es gibt hierfür die Klasse StringBuilder, die zum aufbauen von langen Strings gedacht ist. Das Problem ist, dass bei der += String Operation das komplette String Objekt neu aufgebaut werden muss und deshalb jedes Mal auch der Speicher neu alloziert wird.

Bezüglich dem Absturz, solltest du vorher prüfen ob _in.lines() nicht null ist.

Allgemeine Anmerkung: Du schreibst deinen Code aktuell so wie in C#. in Java werden z. B. Methoden klein geschrieben; Variablen haben keinen Unterstrich; geschweifte Klammern stehen in der Zeile der Abfrage

if (gettingVertices) {
// do sth
}

 

[WingX]

Der Umgang mit Readern in Java ist nicht ganz einfach. Zunächst mal gibt es die Funktion lines() des BufferedReader nur in Java 8. Dann liefert diese Funktion auch den Stream des BufferedReader zurück, daher ist eine weitere Operation auf dem Reader bzw. auf dem Stream nicht mehr möglich. Nachzulesen hier bzw. hier. Alternativ würde ich mit einem Filereader und einem File arbeiten anstatt mit einem InputStreamReader und einem FileInputStream.

 

[Zespire]

Tausend dank hätte nicht gedacht dass das so eine große Auswirkung hat läuft mit dem StringBuilder in wenigen Sekunden durch.

_in.lines() ist nicht Null wobei das eigentlich nur Spielerei ist und mit dem Performance Zugewinn
brauche ich nicht einmal mehr die Information wie weit er ist .

 

[Redirion]

ich würde lines() nicht benutzen. Das ist irgendein neues Java 8 Feature für Streams. Siehe auch die Javadoc dazu.

Zum Zählen der Zeilen würde ich mir mal diese Antwort auf stackoverflow anschauen.

Ich würde an deiner Stelle auch genau diese Kombination aus der stackoverflow-Antwort nutzen. LineNumberReader, FileReader, File.
Du liest aktuell einen Binärstream, der dann erst wieder in Zeichen umgewandelt wird (Stream vs. Reader!). Bitte beim Lesen von Text immer Reader nutzen, niemals Streams.

edit: @Burfi: Super Hinweis mit dem StringBuilder!

 

[Zespire]

Allgemeine Anmerkung: Du schreibst deinen Code aktuell so wie in C#. in Java werden z. B. Methoden klein geschrieben; Variablen haben keinen Unterstrich; geschweifte Klammern stehen in der Zeile der Abfrage

Bezüglich der Großschreibung wurde ich bereits von Eclipse freundlich drauf hingewiesen aber ich finde das ganze so leserlicher genau so wie die Unterstriche bei Variablen die übergeben werde hatte damit bei glsl oder hlsl angefangen und finde das so Toll/Übersichtlich das ich das jetzt überall mache...

 

[Piktogramm]

Du hast je Schleifendurchlauf allerhand If-Statements drinnen stehen, die für die Sprungvorhersage wohl auch noch schwer vorhersagbar sind.

Die Bedingungen auf recht große Strings sind vergleichsweise aufwendig. Je häufiger in der zu durchsuchenden Datei sehr ähnliche Strings auftauchen, desto länger dauert im Mittel jeder Test ob der String in der Datei mit dem vorgegebenem String übereinstimmt.



Mein Ansatz wäre eine Bibliothek zu suchen, die eine optimierte und parametrisierbare Suche anbietet. Entsprechende dann etwa dieser Ablauf.

1. Suche am Anfang der Zeile
   [**] nach String xxx
   [**] nach String yyy
   [**] Rückgabe Zeilennummer und gegebenenfalls welcher String gefunden wurde (Zuordnung als integer).
2. Verwende Zeilennummer für direkten Zugriff

Das Suchen sollte schneller gehen als der Vergleich deinem umfangreichem Test, ob die Strings übereinstimmen. Wenn du die Zeilennummern in ein Array packst kann die Suche in einer sehr kurzen Schleife arbeiten. Was in der Regel viel schneller ist als große Schleife wie bei dir. Zudem bringt die kleine Schleife über die ganze Datei gut vorhersagbare Zugriffsmuster für den Speicher und der Prefetcher kann seine Magie anbringen.
Die Bearbeitung der Strings xxx und yyy kann in kleinen, getrennten Schleifen erfolgen und die Sprungvorhersage sollte auch wesentlich besser klappen, da die Suche ja nur relevante Zeilen enthält.

Ergänzung (22. November 2016)

[...] finde das so Toll/Übersichtlich das ich das jetzt überall mache...

Wenn du mal Java in einem Team schreiben solltest, solltest du nicht erwarten, dass deine Vorliebe zu win32 Formatierung von irgendwem geteilt wird.

 

[Zespire]

Ist eigentlich immer nur ein If Statement das einen String abfrage macht zuerst wird ja der Boolean „gettingVertices“ geprüft falls der true/false ist entfällt doch die String.equals Abfrage in Zeile 26 oder 29.

Genau so durchsucht er nicht jedes mal die ganze Datei sondern prüft die Aktuelle Zeile ob sie mit einem String übereinstimmt und eine Suche ist doch im Endeffekt das Selbe und wäre dann doppelt gemoppelt.

 

[Piktogramm]

gettingVertices = true; wird nach dem ersten Fund in der Schleife gesetzt. Solang die Schleife also läuft (mir scheint bis zum Ende der Datei) steht da dann jede Bedigung mit
if ( true && <Test auf großen String>

Ergo, wenn die erste Bedingung einmal erfüllt ist muss mit jeder Iteration der Schleife der große Test ausgeführt werden und die 3. Bedingung in der Schleife ist auch immer wahr. Jenachdem wo und wie oft der entsprechende String vorkommt und wie groß die Datei ist, geht da reichlich Rechenzeit flöten.


Was Suche gegen große Schleife mit (vielen) Bedingungen angeht. Das hatte ich eigentlich schon beschrieben. Eine Suche ist mit einer recht kompakten Schleife abwickelbar. Entsprechend gut lässt sich das optimieren, die Suche passt in der Regel in den L1 Cache der CPU, ein zeitintensiver Zugriff auf höhere Cachelevel bleibt aus, der Zugriff auf den Arbeitsspeicher ist gut vorhersagbar und der Prefetcher kann entsprechend die (enormen) Latenzen des Rams sehr gut kompensieren. Zudem reduziert so eine einfache Suche die Datenmenge die der "große" Algorithmus bearbeiten muss enorm.

Vergleich Suche zu "equals auf String", die meisten Bibliotheken sind nach meiner Erfahrung besser optimiert als Funktionen "equals String". Während die einfachen Vergleichsfunktionen den String oft einfach nur linear durchgehen und abbrechen wenn der erste Mismatch kommt sind Suchen meist mindestens so gut optimiert, dass die zu vergleichenden Strings binär durchwandert werden. Also Test auf das erste Zeichen, danach Test auf das letzte Zeichen, danach Test auf die Mitte etc. also quasi eine Binärsuche innerhalb der Strings. Das sorgt im Mittel für eine deutlich gesenkten Rechenbedarf von O(n) für linearen Vergleich zu O(log n) bei der Binärsuche. Das wird real bei einer Vergleichsmessung zwar nicht zu 100% klappen, aber für wie bei dir n~30 ist der Unterschied wohl groß genug.

 

[Rossie]

Alternativ würde ich mit einem Filereader und einem File arbeiten anstatt mit einem InputStreamReader und einem FileInputStream.

Schau Dir mal den Code von FileReader an! Um einen InputStreamReader kommt man nicht herum, wenn man die Konvertierung nicht selbst macht. Im Gegenteil. Es kann sogar falsch sein, FileReader zu verwenden, da dieser immer das Standard-Encoding der Plattform verwendet.

Um das eigentliche Problem zu lösen, könnte man anstatt dem Low-Level-Approach XML einsetzen. Je nachdem wie die Datei aussieht, könnte es ausreichen, die Datei einzulesen und dann mittels XPath-Ausdruck die notwendigen Daten zu ziehen. Wäre vielleicht nicht schneller, aber einfacher zu programmieren und für Dritte vermutlich einfacher nachzuvollziehen.

 

[Zespire]

gettingVertices = true; wird nach dem ersten Fund in der Schleife gesetzt. Solang die Schleife also läuft (mir scheint bis zum Ende der Datei) steht da dann jede Bedigung mit
if ( true && <Test auf großen String>

Ergo, wenn die erste Bedingung einmal erfüllt ist muss mit jeder Iteration der Schleife der große Test ausgeführt werden und die 3. Bedingung in der Schleife ist auch immer wahr. Jenachdem wo und wie oft der entsprechende String vorkommt und wie groß die Datei ist, geht da reichlich Rechenzeit flöten.


Was Suche gegen große Schleife mit (vielen) Bedingungen angeht. Das hatte ich eigentlich schon beschrieben. Eine Suche ist mit einer recht kompakten Schleife abwickelbar. Entsprechend gut lässt sich das optimieren, die Suche passt in der Regel in den L1 Cache der CPU, ein zeitintensiver Zugriff auf höhere Cachelevel bleibt aus, der Zugriff auf den Arbeitsspeicher ist gut vorhersagbar und der Prefetcher kann entsprechend die (enormen) Latenzen des Rams sehr gut kompensieren. Zudem reduziert so eine einfache Suche die Datenmenge die der "große" Algorithmus bearbeiten muss enorm.

Vergleich Suche zu "equals auf String", die meisten Bibliotheken sind nach meiner Erfahrung besser optimiert als Funktionen "equals String". Während die einfachen Vergleichsfunktionen den String oft einfach nur linear durchgehen und abbrechen wenn der erste Mismatch kommt sind Suchen meist mindestens so gut optimiert, dass die zu vergleichenden Strings binär durchwandert werden. Also Test auf das erste Zeichen, danach Test auf das letzte Zeichen, danach Test auf die Mitte etc. also quasi eine Binärsuche innerhalb der Strings. Das sorgt im Mittel für eine deutlich gesenkten Rechenbedarf von O(n) für linearen Vergleich zu O(log n) bei der Binärsuche. Das wird real bei einer Vergleichsmessung zwar nicht zu 100% klappen, aber für wie bei dir n~30 ist der Unterschied wohl groß genug.

Dauert aktuell 0.4 Sek falls du es auf 0.3 schaffst mit einer vorherigen Suche spendiere ich dir ein Kasten Bier im Anhang ist die Datei.(natürlich in java)

Spoiler

 import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main 
{
	
	private static String vertStart = "  <Property name=\"VertexStream\">";
	private static String vertEnd = "  <Property name=\"SmallVertexStream\">";
	
	public static void main(String[] args) throws IOException 
	{
		File file = new File("E:/Games/No Man's Sky/mod/NMSARC.1A1B4C22/MODELS/COMMON/SPACECRAFT/DRONE/DRONESHIP.GEOMETRY.MBIN.exml");
		BufferedReader in = new BufferedReader( new InputStreamReader(new FileInputStream(file), "UTF8"));
		long time = System.currentTimeMillis();
		GetVertices(in);
 		in.close();
		System.out.println(System.currentTimeMillis() - time);
	}

	private static void GetVertices(BufferedReader _in) throws IOException
	{
		String currentLine = "";
		StringBuilder result = new StringBuilder();
		result.append("# WaveFront *.obj file");
		int count = 0;
		int verticesCount = 0;
		
		boolean gettingVertices = false;
		
 		while((currentLine = _in.readLine()) != null) 
		{
			if(!gettingVertices && currentLine.equals(vertStart))
			{
				gettingVertices = true;
				continue;
			}
			
			if(gettingVertices && currentLine.equals(vertEnd))
			{
 				result.append("\n");
  				for(int i = 0; i < verticesCount ; i += 3)
 				{
 					result.append("\n" + "f " + i + " " + (i + 1) + " " + (i + 2));
 				}
 				return;
			}
	
			if(gettingVertices)
			{
				
				currentLine = currentLine.replace("    <Property value=\"", "");
				currentLine = currentLine.replace("\" />","");
 				if(count == 0)
					result.append(" v");
				result.append(" " + currentLine);
				count ++;
			}
			
			if(count == 3)
			{
				verticesCount ++;
				result.append("\n");
				count = 0;
			}
		}
	}
}

 

[Rossie]

Eine einfache Optimierung wäre, weniger Strings zu erzeugen. Ich komme alleine damit von ca. 300 ms auf etwa 100 ms.

 

[Zespire]

Keine Ahnung wie genau du das machst aber denke mal hat was mit "currentLine = currentLine.replace"
zu tuen.
Wäre super wen du mir zeigst was genau du anders machst.

 

[Rossie]

Genau. Die replace() Calls sind nicht optimal. In mehrfacher Hinsicht. Die Implementierung verwendet reguläre Ausdrücke. Wenn man oft nach dem gleichen sucht, ist es besser den Regex wieder zu verwenden. Das würde hier schon gut was bringen.

Aber Du willst ja einfach den Text in Anführungszeichen. Da ist es schneller, die Position der Anführungszeichen zu bestimmen und den gewünschten Text dazwischen dem StringBuilder anzufügen (nicht String#subsequence verwenden, sondern ein CharArray erstellen, die gewünschten Zeichen kopieren und dann dem Buffer dieses Array hinzufügen, das ist ein klein wenig schneller).

So wirst Du auch darauf kommen, dass Deine Implementierung einen Fehler hat...

 

[Zespire]

Ist zwar nicht schön mit 21 und -4 aber sind jetzt 70ms... ;D

		if(gettingVertices)
			{
   				if(count == 0)
					result.append(" v ");
   				//Edit: Leerzeichen vergessen
   				result.append(" ");
  				result.append(currentLine, 21, currentLine.length() - 4);
				count ++;
			}

 

[mental.dIseASe]

Ich habe zwar fachlich nichts beizutragen, aber du schuldest ihm einen Kasten Bier!

 

[Zespire]

Noch hat hier keiner gezeigt das es schneller ist die Datei erst zu durchsuchen und dann auszulesen anstelle davon es parallel zu machen .

 

[Piktogramm]

Von mir wirst du das nicht bekommen. Ich gebe dir Tips die so in sogut wie jedem Leitfaden zur Optimierung von Programmabläufen stehen und was dir als Erwiderung einfällt ist ein "ja mach mal".

In deinem Programm wird nichts parallel ausgeführt.

 

[Zespire]

Hast recht parallel nicht aber in einem Durchlauf und ich kann mir noch immer nicht erklären wie es mit zwei schneller gehen soll.

 

[Piktogramm]

https://en.wikipedia.org/wiki/Loop_optimization