#

Java Performance in Microbenchmarks

Neulich wollte ich ein Programm schreiben, dass viele Berechnungen durchführt und hierzu u. a. Matrizen Operationen durchführt. Da ich recht kleine Matritzen hatte, die aber häufig bearbeitet werden müssen, habe ich einige Microbenchmarks durchgeführt, um die tatsächliche Performanz verschiedener Umsetzungen auszuprobieren, welches sich nicht nur auf Matrizenoperationen beschränkte.

Meine erste Frage war, wie man Matrizen so umsetzt, dass sie schnell gelesen / beschrieben werden können.
Die einfachste Lösung: mit einem zweidimensionalen Arrays. Doch die Alternative dazu, ein eindimensionales Array zu benutzen und mit entsprechenden Offsets darauf zuzugreifen, erschien mir genauso plausibel.

Vorweg: Ich habe meine Microbenchmarks einfach mit System.currentTimeMillis() durchgeführt, was von vielen als ungenau beachtet wird, da Faktoren, wie der Garbagecollector, Hintergrundtasks etc. einen Einfluss auf das Ergebnis haben können. Auch haben Java-Version, JVM Implementierung etc. riesigen Einfluss darauf. Nichts desto trotz. Irgendwie muss ich mir ja eine Entscheidungsgrundlage schaffen…

Zweidimensionale Arrays:

double [][] java = new double[10][10];
t = 0;
start = System.currentTimeMillis();
for (c=0; c<cycles; c++){
	for (x=0; x<10; x++){
		for (y=0; y<10; y++){
			t += java[x][y];
		}
	}
}
javaDur = System.currentTimeMillis()-start;

Die Ausführung dieses Codefragmentes ergab 4157 (ms).

Die entsprechende Aufgabe mit einem eindimensionalen Array:

double [] custom = new double [100];
t = 0;
start = System.currentTimeMillis();
for (c=0; c<cycles; c++){
	cx = 0;
	for (x=0; x<10; x++){
		for (y=0; y<10; y++){
			t += custom[cx+y];
		}
		cx += 10;
	}
}
customDur = System.currentTimeMillis()-start;

Dieses Codefragment hingegen ergab 2734 (ms), also braucht nur 0.66 mal so viel Zeit.

Eine weiter Frage, die sich stellte, war das Kopieren von Daten aus einer zu einer Matrix. Javakennern ist System.arraycopy() ein Begriff, doch ist es auch wirklich schneller als der manuelle Weg?

final int dataSize = 100;
final double [] data = new double[dataSize];
final double [] dataInit = new double[dataSize];
final int cycles = 100000000;
start = System.currentTimeMillis();
for (c=0; c<cycles; c++){
	System.arraycopy(dataInit, 0, data, 0, dataSize);
}
syscopy = System.currentTimeMillis()-start;

Das Fragment ergab 9656 (ms)

Die Alternative

start = System.currentTimeMillis();
for (c=0; c<cycles; c++){
	for (i=dataSize; - -i>=0;){
		data[i]=dataInit[i];
	}
}
manual = System.currentTimeMillis()-start;

hingegen 17297 (ms), was um den Faktor 1.79 langsamer ist.

Als drittes stellte sich mir die Frage, wie es mit dem Befüllen von Arrays mit Startwerten aussieht. Meist muss man das Array mit 0-Werten befüllen, was die Option ein neues Array zu erzeugen erlaubt. Eine weitere, jedoch etwas Platz verschwendende Variante, ist es, ein statisches Array mit selber Größe vorzuhalten, aus dem die Initialwerte kopiert werden. Zu letzt gibt es noch die Möglichkeit via Object.clone() ein Array zu klonen.

Neues Array erstellen via new:

double [] created;
start = System.currentTimeMillis();
for (c=0; c<cycles; c++){
	created = new double[size];
}
newed = System.currentTimeMillis()-start;

Vorhandenes Array manuell befüllen:

final double [] existing = new double[size];
start = System.currentTimeMillis();
for (c=0; c<cycles; c++){
	for (i=existing.length; - -i>=0;){
		existing[i] = 0D;
	}
}
reinit = System.currentTimeMillis()-start;

Vorhandenes Array mit Initialwerten clonen:

start = System.currentTimeMillis();
for (c=0; c<cycles; c++){
	created = existing.clone();
}
cloned = System.currentTimeMillis()-start;

Vorhandenes Array mit Initialwerten aus Templatearray kopieren via System.arraycopy:

start = System.currentTimeMillis();
for (c=0; c<cycles; c++){
	System.arraycopy(existing, 0, copied, 0, size);
}
sysarrcopy = System.currentTimeMillis()-start;

Arrays.fill() benutzen:

start = System.currentTimeMillis();
for (c=0; c<cycles; c++){
	Arrays.fill(existing, 0D);
}
arrays = System.currentTimeMillis()-start;

Bei verschiedenen Durchläufen mit verschiedenen Arraygrößen ergaben sich hierbei auch verschiedene schnellste Möglichkeiten:

variante arraysize: 100, cycles: 10000000 arraysize: 1000, cycles: 1000000 arraysize: 10000, cycles: 100000
new 5719 5250 5297
manual init 1391 1328 1500
clone 7860 6484 7266
sys.arraycopy 968 703 1844
Arrays.fill 1454 1328 1500

Die Zeiten von Arrays.fill und dem manuellen Befüllen sind fast gleich. Das liegt u. a. daran, dass Arrays.fill genau diese Operation macht, jedoch vorher mit einem Boundscheck (daher minimal langsamer). Schade, dass diese Funktion nicht wie System.arraycopy durch eine native und schnelle Implementierung ersetzt wurde.

Es zeigt sich, das man mit System.arraycopy bis zu einer bestimmen Arraygröße, am besten bedient ist, zum Nachteil, dass man auch ein Templatearray mit entsprechender Größe vorliegen hat. Am schlechtesten schneidet clone ab und ist für eindimensionale Arrays wohl nicht wirklich zu brauchen.

Bei meinen Benchmarks fiel mir auf, dass üblicherweise nur einer meiner beiden CPU-Kerne ausgelastet wurde. Und da jeder aktuelle PC einen Mehrkern-Prozessor besitzt, lag die Idee nahe, Operationen auf einen Array zu parallelisieren, damit jeder Kern etwas davon hat. Als Operation diente eine etwas zeitaufwändigere Berechnung mit Math.sqrt() und Math.sin().
Für die multithreaded Varianten habe ich zuerst eine naive Variante mit new Thread() pro Durchlauf und eine verbesserte mit einem Executor-Pool benutzt. CyclicBarrier hilft hier die verschiedenen Worker nach erledigter Arbeit wieder zu synchronisieren. Es wurden pro CPU Kern ein Thread erstellt (automatisch via Runtime.getRuntime().availableProcessors()).

Single threaded:

start = System.currentTimeMillis();
for (int c = 0; c<cycles; c++){
	for (i=sourceData.length;- -i>=0;){
		targetData[i] = Math.sin(Math.sqrt(sourceData[i]));
	}
}
duration = System.currentTimeMillis()-start;

Multi Threaded Vorlage:

static class Worker implements Runnable{
	public int startIndex; /* inclusive */
	public int endIndex; /* exclusive */
	public double [] sourceData;
	public double [] targetData;
	public CyclicBarrier barrier;
 
	public void run() {
		for (int i=endIndex; - -i>=startIndex;){
			targetData[i] = Math.sin(Math.sqrt(sourceData[i]));
		}
		try {
			barrier.await();
		}
		catch (InterruptedException e) {
			e.printStackTrace();
		}
		catch (BrokenBarrierException e) {
			e.printStackTrace();
		}
	}
}
...
final int cores = Runtime.getRuntime().availableProcessors();
final CyclicBarrier barrier = new CyclicBarrier(cores+1);
final Worker [] workers = new Worker[cores];
final int dataPerWorker = sourceData.length/cores;
for (i=0; i<cores; i++){
	workers[i] = new Worker();
	workers[i].barrier = barrier;
	workers[i].sourceData = sourceData;
	workers[i].targetData = targetData;
	workers[i].startIndex = dataPerWorker*i;
	workers[i].endIndex = dataPerWorker*(i+1);
}

Neuer Thread pro Durchlauf:

start = System.currentTimeMillis();
for (int c = 0; c<cycles; c++){
	for (i=cores;--i>=0;){
		new Thread(workers[i]).start();
	}
	try {
		barrier.await();
	}
	catch (InterruptedException e) {
		e.printStackTrace();
	}
	catch (BrokenBarrierException e) {
		e.printStackTrace();
	}
	barrier.reset();
}
duration = System.currentTimeMillis()-start;

ExecutorPool:

final ExecutorService pool = Executors.newFixedThreadPool(cores);
start = System.currentTimeMillis();
for (int c = 0; c<cycles; c++){
	for (i=cores;- -i>=0;){
		pool.execute(workers[i]);
	}
	try {
		barrier.await();
	}
	catch (InterruptedException e) {
		e.printStackTrace();
	}
	catch (BrokenBarrierException e) {
		e.printStackTrace();
	}
	barrier.reset();
}
duration = System.currentTimeMillis()-start;

Bei verschiedenen Anzahlen für Durchläufe und Datengrößen ergab sich folgendes:

variante arraysize: 1000, cycles: 100000 arraysize: 10000, cycles: 10000 arraysize: 100000, cycles: 1000
single thread 6934 7141 7187
2 threads (new thread) 33933 7163 4535
2 threads (pool) 7472 5621 4252

Es zeigt sich, dass sich die Aufteilung der Arbeit an einem Array erst für sehr große Arrays lohnt. Und dann auch am Besten mit einem Worker Pool.

Der Einsatz von mehreren Threads wird bei mir also auf einer anderen Anwendungsebene benutzt.

Tags:, ,

Leave a Reply »»

Note: All comments are manually approved to avoid spam. So if your comment doesn't appear immediately, that's ok. Have patience, it can take some days until I have the time to approve my comments.