Parallel programmieren mit ExecutorService

[Kaschina]

Hallo, ich hoffe, ihr könnt mir mal wieder helfen.

Oder mir sagen, ob ich auf dem Holzweg bin

Und zwar habe ich ein Bildbearbeitungsprogramm, das ein Mosaikbild erstellen soll.
Langsam und sequentiell ist das auch kein Problem.

Allerdings soll es jetzt parallel werden, mit einer begrenzten, aber variablen (heisst, ich möchte es auf einen Knopfdruck ändern können) Anzahl an Threads.

Mein erster Ansatz war, dass ich jeden einzelnen Bearbeitungspunkt (Anzahl der "Unterbilder" bestimmen, Durchschnittsfarbwerte aller Unterbilder bestimmen, für jedes Unterbild das passende Ersatzbild finden und entsprechend zu verkleinern) eine beliebige (für den Anfang erstmal entsprechend der Anzahl der Unterbilder) Anzahl an Threads laufen habe lassen. Am Ende von jedem Bearbeitunspunkt wurde mit einem join() gewartet, bis alle Threads fertig sind und weiter zum nächsten Bearbeitungspunkt.
Dass das wohl zu einfach gedacht war, ist mir bewusst, aber so dauert die Berechnung sogar 3 Sekunden länger als bei der sequentiellen Berechnung.

Jetzt die eigentliche Frage:

Ich möchte mit der Auswertung der Durchschnittswerte anfangen und bei jedem fertig erstellten Wert das entsprechende Unterbild weiterreichen, um es ersetzen zu lassen.
Also im Prinzip Producer und Consument.

Daher die Idee, einen Pool zu erstellen mit x möglichen Threads.
Die Klasse, die meinen Durchschnittswert erstellt, würde ich Callable implementieren lassen, damit das Ergebnis der Berechnung an den Pool weitergereicht wird.

Dazu gibt es noch eine Klasse, die von Runnable abgeleitet ist, die dann alle Ergebnisse auffängt und weiterverarbeitet.
So wie ich das aber bisher habe, wird immer erst die ganze Liste von Callable abgearbeitet, bis Runnable rangelassen wird.

Codeschnipsel:

// berechne Durchschnittsfarbwert von BufferedImage

class MyCallable implements Callable<String> {
			private BufferedImage buffIm;
			private int jobnummer;

			MyCallable(BufferedImage b, int jobnummer) {
				this.buffIm = b;
				this.jobnummer = jobnummer;
			}

			public String call() {
				System.out.println("Nr: " + jobnummer + " es wird gearbeitet! " );
				//mach viel Zeugs und berechne den durchschnittlichen Farbwert vom Bild
				return averageRgb.toString() + " erstellt von Jobnummer: " + jobnummer;
			}
		}

		Set<MyCallable> callables = new HashSet<MyCallable>();
		for (BufferedImage image : buffImages) {
			MyCallable c = new MyCallable(image, buffImages.indexOf(image));
			callables.add(c);
		}
                
                // es sollen nur drei Threads parallel laufen
		ExecutorService executor = Executors.newFixedThreadPool(3);
		
		
		/**
		 * 
		 */
		List<Future<String>> result = executor.invokeAll(callables);

		/**
		 * soll später ein Bild finden, dass dem (noch nicht) übergebenen entspricht.
		 */
		class MyRunnable implements Runnable {
			String bs;

			public MyRunnable(Future<String> future)
			        throws InterruptedException, ExecutionException,
			        TimeoutException {

				bs = future.get(2, TimeUnit.SECONDS);
			}

			public void run() {
				System.out.println("Soeben traf diese Meldung ein:  " + bs);
			}
		}

		/**
		 * hier wird der lesethread aufgerufen.
		 */
		for (Future<String> future : result) {
			MyRunnable my = new MyRunnable(future);
			Thread thread = new Thread(my);
			thread.start();
		}

		executor.shutdown();
	}
}

Wie bekomme ich das jetzt dazu, dass MyRunnable aufgerufen wird, sobald das erste Ergebnis vorhanden ist? (notify()?, aber wie?)

Ist es überhaupt sinnvoll, verschiedene Bearbeitungsschritte gleichzeitig loslaufen zu lassen?
Mein erster Gedanke wäre gewesen, die einzelnen Bearbeitungen möglichst schnell laufen zu lassen, da bis zu 10.000 Unterbilder entstehen können.
Aber wie eingangs gesagt: Aus irgendeinem Grund ist da die sequentielle Verarbeitung bei mir schneller...

 

[timbeau]

Du kannst z.B. die Threads im Executor-Pool starten bevor irgendeine Berechnung läuft. Diese können sich dann die Bilder aus einer threadsicheren Collection holen und diese ebenfalls wieder zurückschreiben. Dann hättest du eine Job-Collection und eine Ergebnis-Collection.

Mehr als CPU-Kerne * " Threads bringen mE aber nichts mehr.

Herunterfahren kannst du den Threadpool ja zentral wenn alles fertig ist.

 

[Kaschina]

Dankeschön für die Antwort.
So ganz konnte ich es allerdings nicht umsetzen - bzw es wird ein Gefrickel.
Daher habe ich mich jetzt darauf beschränkt, die einzelnen Bearbeitungspunkte mit Threads zu versehen (wenn mans richtig macht, ist es auch schneller ), die Threads nach jedem Punkt wieder einzusammeln und so weiter.

Allerdings soll ich das Ganze ja mit einer unterschiedlichen Anzahl an Threads testen.
Bis zu 64 Stück funktionieren - 64 aber schon fast langsamer als 4. Die gewünschte Höchstzahl liegt bei 280 und da geht bei mir gar nichts mehr...
Ist das dann einfach nur ein Rechnerproblem, oder sollte ich das nochmal überarbeiten (ist für die Uni...)

Und nächste Frage:
Wenn das Bild sich fünfmal bearbeiten lässt ohne zu meckern und auch noch schnell und beim 6. mal der Heapspeicher ächzt, das gleiche nochmal. Liegts am zu langsamen PC, oder am Programm?

 

[timbeau]

Also oben hat die Caps-Taste zugeschlagen...

Mehr als CPU-Kerne*2 Threads machen kaum Sinn bei Berechnungen die eh nur die CPU-Kerne machen. Wenn also der Thread keine I/O hat sondern nur CPU braucht wirst du keine Verbesserung sehen. Jeder Thread hat ja auch Overhead. Irgendwann rattert der Sheduler nur noch zwischen den Threads hin und her ohne das die wirklich arbeiten können.

Wenn du keinen 64Core-CPU hast gehe ich jede Wette ein, dass 64Threads langsamer sind.

 

[Kaschina]

Ich habs trotz caps Taste verstanden
Heisst, wenn ich einen Dualprozessor hab, dann komm ich tatsächlich nur auf 4 nützliche Threads?

Was ich nicht verstanden hab: 64Core-CPU?? 64bit System, oder tatsächlich 64 Kerne?

Mit I/O arbeite ich schon, es werden eine Reihe von Bildern eingelesen.

Das wurde aber auch nur unwesentlich schneller - finde ich. Genau testen kann ichs nicht, weil das sequentielle Programm grad auf dem falschen Rechner ist.

Mein Punkt ist:
Um ein Bild zu erzeugen (4925x2025Pixel) mit 15497 Unterbildern, brauche ich 9 Sekunden wenn ich das programm mit einem Thread laufen lasse. Mit 2 immerhin eine Sekunde weniger, mit 4 bleibt die Dauer gleich und mit 8 wirds schon wieder minimal langsamer. Die genaue Zeit schwankt aber auch..

Von "unglaublicher Beschleunigung" im Programm merke ich einfach überhaupt nichts und ich weiß nicht, obs an dummer Implementierung liegt, oder schlicht und einfach am Rechner.

Deswegen nochmal bisschen Code, vielleicht stichts ja jemand anders ins Auge

Aus dem ursprünglich sequentiellem Programm habe ich die for-Schleifen genommen, bei denen ein paartausend mal das gleiche passiert und den Vorgang jeweils an eine Callable-Klasse übergeben.
Während dem Schleifendurchlauf werden alle callables gesammelt (siehe addworker...) und nach beenden der Schleife wird das Abarbeiten dann gestartet.
Sobald das ergebnis fertig ist, wird dieses dann an die nächste Schleife weitergeleitet (das geht nicht anders, weil ich mit den Ergebnissen weiterarbeite).

Wenns dumm ist, bitte sagen. Ich hab mich jetzt zwei Tage eingelesen und verstehe evtl auch, was warum wieso wann und wie gemacht wird, aber die eigene Umsetzung ist dann doch wackelig...

Um die Ergebnisse sortiert zu bekommen - sonst wirds ein kunterbuntes Durcheinander - habe ich eine Pair-Klasse geschrieben, damit zu jedem Ergebnis der Index zugeordnet werden kann - hashmap fand ich dann doch zu hochgegriffen, weil ich dann als Endergebnis eine Hashmap voller Hashmaps mit je einem Schlüssel+Wert hätte.
Geht das auch einfacher??

public class MyThreadPoolExecutor {

	private HashSet<WorkerMyFitting> fittingCallables;
	private HashSet<WorkerMyAverage> averageCallables;

	private List<Future<Pair<Integer, MyBufferedImage>>> resultImageAndIndex;
	private List<Future<Pair<Integer, short[]>>> resultShorts;

	private ArrayList<MyBufferedImage> images;
	private ArrayList<short[]> averages;

	// Parallel running Threads(Executor) on System
	private int corePoolSize = Runtime.getRuntime().availableProcessors();

	// Maximum Threads allowed in Pool
	private final int maxPoolSize;

	// Keep alive time for waiting threads for jobs(Runnable)
	 private final long keepAliveTime = 10;

	
	ThreadPoolExecutor threadPool = null;

	
	final ArrayBlockingQueue<Runnable> workQueue;

	private ExecutorService executor;
	private ArrayList<WorkerMyMosaique> runners;

	public MyThreadPoolExecutor(int max) {

		this.maxPoolSize = max;
		workQueue = new ArrayBlockingQueue<Runnable>(100);
		if (maxPoolSize == 1) {
			corePoolSize = 1;
		}
		threadPool = new ThreadPoolExecutor(corePoolSize, maxPoolSize, keepAliveTime, TimeUnit.MILLISECONDS, workQueue);
		executor = Executors.newFixedThreadPool(maxPoolSize);

		fittingCallables = new HashSet<WorkerMyFitting>();
		averageCallables = new HashSet<WorkerMyAverage>();

		images = new ArrayList<MyBufferedImage>();
		averages = new ArrayList<short[]>();
		
		runners = new ArrayList<WorkerMyMosaique>();
	}

	public void shutdown() {
		threadPool.shutdown();
	}
	public void addFittingWorker(WorkerMyFitting workerMyFitting) {
		fittingCallables.add(workerMyFitting);
	}

	public ArrayList<MyBufferedImage> getFittingResult() {
		HashMap<Integer, MyBufferedImage> sortMe = new HashMap<Integer, MyBufferedImage>();
		for (Future<Pair<Integer, MyBufferedImage>> fmbi : resultImageAndIndex) {
			try {
				Pair<Integer, MyBufferedImage> pair = fmbi.get();
				sortMe.put(pair.getIndex(), pair.getItem());
			} catch (InterruptedException e) {
				System.out.print(e.getMessage());
				e.printStackTrace();
			} catch (ExecutionException e) {
				System.out.print(e.getLocalizedMessage());
				e.printStackTrace();
			}
		}
		ArrayList<Integer> sortedList = new ArrayList<Integer>();
		/**
		 * Hashmap sortieren, mybuffIm an images übergeben!
		 */
		sortedList.addAll(sortMe.keySet());
		Collections.sort(sortedList);

		for (int i = 0; i < sortedList.size(); i++) {
			images.add(sortMe.get(sortedList.get(i)));
		}
		return images;
	}
public void startMakingImage() {

		for (WorkerMyMosaique wmm : runners) {
			Thread x = new Thread(wmm);
			x.start();
			try {
				x.join();
			} catch (InterruptedException e) {
				System.out.println("error bei startmakingimage an der "
				        + runners.indexOf(wmm));
				e.printStackTrace();
			}
		}
	}
}

der "leicht verkürzte" Ausschnitt.


Und nochmal: Ja, ich verstehe, warum so viele Threads keinen Sinn machen. Ändert aber nicht daran, dass ich es mit 1 - 228 Threads testen muss...

 

[Marco13]

Ich habe im Moment noch etwas Schwierigkeiten, das ganze (bzw. die Intention) nachzuvollziehen (der Morgenkaffee wirkt noch nicht so richtig).

Nochmal: Du hast ein großes Bild (z.B. 3000 * 3000). Daraus soll ein "Mosaikbild" erstellt werden. Das läuft ab, indem das große Bild z.B. in 100*100 Unterbilder der Größe 30x30 zerlegt wird, für jedes einzelne Unterbild der Durchschnittsfarbwert berechnet wird, und daraus dann ein 100x100-Bild erzeugt wird (bzw. eins mit 100x100 "großen" Pixeln, aber das ist ja nur eine Frage des Zeichnens, und deswegen egal)

Ein paar Kommentare oder sprechendere Namen im Code wären vielleicht hilfreich ("My" sagt GARnichts!)

Noch kurz zu den Threads an sich: Der ThreadPoolExecutor verwaltet die Threads ziemlich effizient. Es geht dabei ja nicht nur darum, dass es auf einem 2-Core-Rechner "doppelt so schnell" ist, sondern auch um Skalierbarkeit, d.h. dass es auf den kommenden 8, 16 und 32-core-Rechnern (im Idealfall, ETWA) 8, 16 oder 32mal so schnell ist. Wenn man sich mit Runtime (Java Platform SE 6) die Anzahl der Prozessoren holt, ist ein Threadpool mit ca. [c]2*availableProcessors[/c] (oder zumindest "etwas mehr threads als verfügbare Prozessoren") sicher nicht verkehrt.

Beim Überfliegen des Codes ist mir als erstes das hier aufgefallen:

      /**
         * Hashmap sortieren, mybuffIm an images übergeben!
         */
        sortedList.addAll(sortMe.keySet());
        Collections.sort(sortedList);

Wenn da irgendwas sortiert wird, dauert das u.U. lange. WAS wird da genau WARUM sortiert? Sieh' auf jeden Fall zu, dass du das wegbekommst.

Was die eigentliche Frage ist, habe ich noch nicht ganz kapiert. Es klang jetzt, als wolltest du bei jedem Callable, das fertig ist, benachrichtigt werden. Wie timbeau schon sagte: Das klingt ein bißchen als könnte man da ein ganz normales Producer-Consumer Pattern verwenden. Vielleicht suchst du aber auch sowas wie einen ExecutorCompletionService. Ich habe den selbst nur einmal verwendet, und das kann ein bißchen fummelig sein, aber ... weil das, was da gemacht wird, vielleicht nicht ganz unähnlich ist, zu dem, was du machen willst, kannst du vielleicht mal in http://www.java-forum.org/codeschni...-asynchron-nachladender-cache.html#post880329 schauen, vielleicht hilft das ein bißchen...

 

[Kaschina]

Dankeschön für die ausführliche Antwort...

An sich ist die Ausführung ungefähr so, wie du es eben beschrieben hast.
Ich zerlege erst das Original in seine zukünftigen "Pixel", Kacheln oder Unterbilder.
Dann werden die Durchschnittsfarbwerte berechnet für jede einzelne Kachel errechnet.

Als nächstes wird diese Liste durchgegangen und aus einer Datei Bilder herausgesucht, die diesem Farbwert so nah wie möglich kommen. Die Farbwerte dieser Bilder und deren Pfade sind in dieser Datei gespeichert.

Als letzter Schritt werden dann die entprechenden Bilder verkleinert - in deinem Beispiel auf 100x100 Pixel und an der entsprechenden Stelle im Originalbild eingebaut.

Dann noch Speichern (das muss man doch noch vereinfachen können, das dauert momentan 2 Sekunden) und fertig.

Zu meiner Umsetzung:
Ich hab mir, wie schon beschrieben, immer einen Arbeitsschritt vorgenommen und für alle Kacheln ausgeführt.
Die Hauptmethode - in dem gezeigten Code nicht sichtbar - erzeugt für jede einzelne Kachel einen "Worker - Callable", der die Arbeit für jeweils eine Kachel ausführen soll. Sobald alle Kacheln vergeben sind (das ist wahrscheinlich auch schon Quatsch??) lasse ich die Callables als Liste ausführen.
Da die Callables in unterschiedlicher Reihenfolge zurückgegeben werden, sind sie für mich erstmal unbrauchbar, weil ich sie doch nach meinen Kacheln sortiert brauche.
Deswegen habe ich die "Pair" Klasse eingebaut, die den Index der Kachel speichert und das Ergebnis.
Das Ganze dann an eine Hashmap übergeben, die Indexe wieder sortieren lassen und die Ergebnisse in der neuen, richtig sortierten Reihenfolge zurückgegeben.
mir ist schlicht und einfach nichts anderes eingefallen, dass das nicht gut ist, weiß ich aber...


Wenn ich daraus ein Producer - Consumer Pattern machen möchte, kann ich die Threads dann immer noch begrenzen (wie?)
Und wie kann sich das Programm die Reihenfolge der Teilbilder merken, ohne dass ich umständlich mit Hashmaps und sortieren arbeiten muss?

Meine eigentliche Frage ist, wie ich meinen Code sinnvoll umgestalten könnte, damit er nicht so unglaublich langsam ist.
(wobei er aber schon eine halbe Minute schneller ist, als mein erster Versuch).

UND! Frage Nr. 2: Sobald ich das Bild gleichzeitig anzeigen lasse - als ImageIcon - kommt der outofmemory error...
Das Fenster mit dem Bild ploppt bei Programmbeginn auf und zum Schluss sollte noch das erstellte Mosaikbild zu sehen sein... Wenn ich das Ganze ohne Oberfläche ausführen lasse, ist er überhaupt nicht überlastet. => Das müsste ich auch noch in den Griff bekommen.

 

[Marco13]

Zu meiner Umsetzung:
Ich hab mir, wie schon beschrieben, immer einen Arbeitsschritt vorgenommen und für alle Kacheln ausgeführt.
Die Hauptmethode - in dem gezeigten Code nicht sichtbar - erzeugt für jede einzelne Kachel einen "Worker - Callable", der die Arbeit für jeweils eine Kachel ausführen soll. Sobald alle Kacheln vergeben sind (das ist wahrscheinlich auch schon Quatsch??) lasse ich die Callables als Liste ausführen.
Da die Callables in unterschiedlicher Reihenfolge zurückgegeben werden, sind sie für mich erstmal unbrauchbar, weil ich sie doch nach meinen Kacheln sortiert brauche.
Deswegen habe ich die "Pair" Klasse eingebaut, die den Index der Kachel speichert und das Ergebnis.
Das Ganze dann an eine Hashmap übergeben, die Indexe wieder sortieren lassen und die Ergebnisse in der neuen, richtig sortierten Reihenfolge zurückgegeben.

Mir fehlt noch ein bißchen der Überblick, insbesondere habe ich noch nicht verstanden, warum du die Ergebnisse dann wieder in einer sortierten Liste brauchst. Aber das mit der Map klingt an sich nicht so verkehrt: Wenn man zu jeder Kachel speichert, an welcher Position sie liegt, ist die Reihenfolge egal (deswegen: Warum sortiert?).

Wegen dieser Unklarheiten, und auch wegen...

UND! Frage Nr. 2: Sobald ich das Bild gleichzeitig anzeigen lasse - als ImageIcon - kommt der outofmemory error...
Das Fenster mit dem Bild ploppt bei Programmbeginn auf und zum Schluss sollte noch das erstellte Mosaikbild zu sehen sein... Wenn ich das Ganze ohne Oberfläche ausführen lasse, ist er überhaupt nicht überlastet. => Das müsste ich auch noch in den Griff bekommen.

... könnte es hilfreich sein, wenn du das ganze als KSKB posten könntest, falls möglich.

(BTW: Schon die Frage, wie du die "Unterbilder" erstellst und verwendest könnte dramatischen Einfluß auf die Performance haben)

 

[Paddelpirat]

Versuch es mal so umzustellen, dass du zuerst einen Threadpool erstellst, mit vielleicht 4 Workern drin. Die Worker sind deine Callables, die eigentlich immer das gleiche machen, also den Mittelwert der Farbe aus einem kleineren Quadrat berechnen.
D.h. ein Worker erwartet zwei Dinge: eine Matrix mit Farbwerten aus denen der Durchschnitt berechnet werden soll und einen Index, der dir sagt, zu welchem Quadrat du gerade den Wert berechnest.

Dann musst du in deiner Hauptklasse eigentlich nur noch den Threadpool mit Daten füttern. Das machst du dann z.b. mit der Submit-Methode, die ein Callable erwartet, welchem du dann ein Quadrat (Matrix) aus dem großen Bild und eben den Index übergibst.

Den ThreadPool (Executor) kannst du noch an einen CompletionService hängen, der darauf wartet, dass ein Worker fertig geworden ist mit seiner Berechnung und den Rückgabewert des Workers abgreift. (Siehe Java-Dokumentation, um zu sehen wie das geht. Eigentlich ganz einfach.)
Da du die Größe des Mosaikbildes kennst, kannst du jedes einzelne Ergebnis direkt in dein Fenster malen, bzw. abspeichern.
Das Sortieren kannst du dir dann auch sparen.

 

[Kaschina]

Warum ich die Liste sortieren muss, verstehe ich gerade auch nicht mehr
"manchmal hilfts, einfach nur drüber zu reden"

KSKB kann ich gern posten, wird aber dann wohl eher morgen früh, es liegen noch soo viele Sachen auf dem Schreibtisch.

Completion-Service werd ich mir anschauen.
Ganz zu Beginn hatte ich noch die Idee, dass mein "erstes Ergebnis", also der Farbwert, von einem Callable-Worker ausgeführt wird und sobald er fertig ist, dann von dem Completion-service direkt an ein runnable weitergeschickt wird, dass mir das entsprechende Bild sucht und sofort malt.
Das hatte ich verworfen, weil es so verstrickt ausgesehen hat. Aber so wie es bei dir, Paddelpirat, klingt, müsste das machbar sein?

Wie ich meine Unterbilder erstelle:
Erstmal habe ich nur den Farbwert und den Pfad.
Ein benötigtes Bild wird nicht gleich erstellt, sondern über das Flyweight Pattern realisiert.
Es wird also eine Factory abgefragt, ob das entsprechende Bild schon gespeichert ist.
Falls nicht, wird ein "MyBufferedImage" erzeugt.
Diese Klasse kann bei Bedarf eine verkleinerte Kopie vom original erstellen und speichert die dann auch, damit Bilder nicht mehrmals erzeugt werden.

Danke erstmal für eure Hilfe und - hoffentlich mit Completion-service überarbeiteter Code und KSKB kommen!

 

[Paddelpirat]

Also parallelisieren würde ich erstmal nur die Berechnung des Durchschnittswertes durch die Worker im Threadpool.

Der CompletionService wartet dann darauf, dass der erste Worker seine Arbeit getan hat und bekommt von diesem einen Farbwert, sowie den Index als Resultat zurückgeliefert. Das läuft dann über das Future.take() (evtl. noch ein .get() dahinter).

Mit diesem Resultat kannst du in deiner Tabelle nach einem relativ nahem Farbwert suchen und das zugehörige Bild in deinem Fenster an der durch den Index festgelegten Position anzeigen.

Während du das machst, arbeiten die Worker weiter und du kannst das nächste Resultat abwarten und wie vorher weiter verarbeiten.

Vielleicht kannst du später noch mehr parallelisieren, aber ich würde es erst einmal dabei belassen und ausprobieren.

 

[Marco13]

Warum ich die Liste sortieren muss, verstehe ich gerade auch nicht mehr
"manchmal hilfts, einfach nur drüber zu reden"

Das nennt sich "Rubberducking": Rubber Ducking

Das mit den Unterbildern ist (mir) noch nicht ganz klar. Auch dazu wäre ein bißchen Beispielcode nicht schlecht. Ich hätte jetzt (im Pseudocode!!!) pragmatisch sowas gemacht wie

BufferedImage image = ...
int w = image.getWidth();
int h = image.getHeight();

BufferedImage output = ...

for (every 10x10-Tile of the input image)
{
    worker = createWorkerFor(tile);
    list.add(worker);
}
executorService.invokeAll(list);

wobei jeder Worker das input-Bild und "seine" Koordinaten übergeben bekommt, und das Ergebnis-Pixel direkt ins output-Image schreibt. Vielleicht bastel' ich da in den nächsten Tagen mal was, das würde mich ggf. auch mal interessieren.

 

[Paddelpirat]

Vielleicht bastel' ich da in den nächsten Tagen mal was, das würde mich ggf. auch mal interessieren.

*Schmunzel* irgendwie find ich die Idee auch lustig. Hab mir gerade mal eine erste Version (noch ohne Multithreading) gebastelt. Da es mir aber an Bildern mangelt, berechne ich nur die Durschnittsfarbe eines Bildausschnittes und setze diese Farbe dann als Basisfarbe für den gleichen Bereich im Mosaikbild. Dafür aber mit JavaFX, wobei man ja hier nicht viel machen muss...

 

[Kaschina]

Gut, ich dachte ja eigentlich, das wäre mein ganz persönliches eigenes Phänomen, aber dann teile ich es eben...

Das stößt ja auf mehr Interesse, als ich dachte
Hätte ich das bloß mal ein wenig früher gepostet, ich bin ja schon länger am Überlegen, wie die geschickteste Umsetzung wäre. "Zeit lassen" ist halt sehr relativ, weil ichs am Dienstag abgeben muss...

createMosaique(BufferedImage sourceImage) {
.
.
.
.
.
            // Ersatzbild erstellen für ein bestimmtes Unterbild
            // Durchschnittsfarbwert wurde bereits erstellt und das dazu passende Bild aus einer  //vorgefertigten Datei ausgesucht. pathOfFittingImage ist der Pfad zur Datei..

for (int index = 0; index < numberOfTiles; index++) {
			short[] rgbTile = rgbOfTiles.get(index);
			mtpe.addFittingWorker(new WorkerMyFitting(this, rgbTile, index));
		}
		mtpe.startWorkFittingImage();

//die Arbeiterklasse dazu:
public WorkerMyFitting(CreateMosaique cm, short[] rgb, int jobnummer) {
		this.rgb = rgb;
    // die Liste, die die Farbwerte und Pfade aller verfügbaren Bilder enthält
		this.mosaiqueList = cm.getMosaiqueList();
		this.jobnummer = jobnummer;
		this.imgFactory = Factory.getInstance();
	}

	public Pair<Integer, MyBufferedImage> call() {
    // der Pfad zum passenden Bild wird in der Mosaikliste gesucht.
	        String pathOfFittingImag = calculateFitting();
    // das Bild wird anhand von seinem Pfad von der ImageFactory geholt.
		MyBufferedImage myFittingImage = imgFactory
		        .getMyBufferedImage(pathOfFittingImage);
		return new Pair<Integer, MyBufferedImage>(jobnummer, myFittingImage);
	}

// entsprechende Methode in der Fabrik:
/**
 * returns an existing mybufferedImage or creates a new one, if not existing yet.
 * @param pathOfFittingImage the path of the mybufferedImage
 * @return mybufferedImage
 */
	public MyBufferedImage getMyBufferedImage(String pathOfFittingImage) {
	   
		
		if (pool.containsKey(pathOfFittingImage)) {
			return pool.get(pathOfFittingImage);
		} else {
			MyBufferedImage im = new MyBufferedImage(pathOfFittingImage);
			pool.put(pathOfFittingImage, im);
			return im;
		}
		
    }

// und MyBufferedImage sieht so aus.

public MyBufferedImage(String path)  {
		this.path = path;
		try {
	        this.original = ImageIO.read(new File(path));
        } catch (IOException e) {
        	System.err.println("Bild nicht lesbar!");
	        e.printStackTrace();
        }
	}

	public String getPath() {
		return path;
	}

	public BufferedImage getResizedImage(int tileSize, int type) {
		if (resizedImage == null) {
			setResizedImage(tileSize, type);
		}
		return resizedImage;
	}

	private void setResizedImage(int tileSize, int type) {

		resizedImage = new BufferedImage(tileSize, tileSize, type);
		Graphics2D g = resizedImage.createGraphics();
		g.drawImage(original, 0, 0, tileSize, tileSize, 0, 0,
		        original.getWidth(), original.getHeight(), null);
    }

Den completionservice hab ich gerade kurz angeschaut;
ich lasse den also alle meine Callables abfangen, die den Durchschnittswert berechnen.
Die Anzahl an Callables, die eingehen müssen, kenne ich ja vorher, also würde ich das mit einer while-Schleife umsetzen?

(while angekommen < müssenAnkommen) {
    try {
        Future<Pair<Integer>, short[]> result = completionService.take();
        angekommen++;
    } catch(Exception e) {
        System.out.println("nix angekommen");
    }
}

 

[Paddelpirat]

kannst auch eine einfache for-Schleife benutzen:

for(int i=0; i<müssenAnkommen; i++) {
    try {
        Future<Pair<Integer>, short[]> result = completionService.take();
    } catch(Exception e) {
        System.out.println("nix angekommen");
    }
}

Edit: Statt

short[]

müsste da doch eigentlich

MyBufferedImage

stehen, oder? War da jetzt eigentlich noch eine Frage offen? Funktioniert es, oder wo hapert es?

 

[Kaschina]

Ohweia, vielleicht isses auch einfach gut für heut...
Dankeschön und Feierabend!!!! Morgen dann wieder mit mehr Kopf bei der Sache und schlaueren Fragen

Vielen vielen Dank nochmal für die Hilfe!

 

[Kaschina]

jein, ich habe mich verschrieben. short[] steht für den Durchschnittsfarbwert, den ich doch auch so berechnen möchte, weil das mein allererster Arbeitsschritt ist.

Ich fang nur grad an, alles durcheinanderzuwerfen, war ein wenig zu lang am PC heut

 

[Kaschina]

Um es auch für die Nachwelt zu erhalten:
Man sollte nie nie nie (zumindest meiner neuen Erfahrung nach) das Flyweight Pattern anwenden, damits schneller geht und man weniger Speicherplatz verbraucht und das dann versuchen mit Threads umzusetzen...

Fazit: 2 Sekunden kürzere Arbeitszeit und kein outofmemory Fehler mehr mit graphischer Oberfläche
Und das erklärt auch mein Gejammer vom Eingangspost, dass die sequentielle Abarbeitung fast schneller funktioniert.

 

[Paddelpirat]

Das hat dir aber keine Ruhe mehr gelassen, was? 00:43 Uhr .... tze ;-)

Fazit: 2 Sekunden kürzere Arbeitszeit und kein outofmemory Fehler mehr mit graphischer Oberfläche
Und das erklärt auch mein Gejammer vom Eingangspost, dass die sequentielle Abarbeitung fast schneller funktioniert.

Wie ist denn die gesamte Laufzeit, damit man mal einen Eindruck bekommt, ob 2 Sekunden nun gut oder schlecht sind? Und wie viele Worker-Threads hast du verwendet?

 

[Kaschina]

Guten morgen,

ne mich hats gewurmt

Gesamtlaufzeit - habs noch ein klein wenig gedrückt ist jetzt mit 4 Threads bei 5,02 Sekunden. Sequentiell sind es +-6,8.
Und wie einer von euch schon gesagt hat, im Idealfall soll doch die Laufzeit doppelt so schnell sein?
Oder wäre der Unterschied nur so gravierend, wenn ich das sequentielle Programm auf einem Ein-Kern-Prozessor laufen hab?

Die Anzahl an Worker Threads stelle ich schon im Exectutor-service ein, oder?

 

[Paddelpirat]

Ja, die Anzahl der Worker-Threads stellst du im ExecutorService ein. Wenn du zum Beispiel

Executors.newFixedThreadPool(int poolSize)

benutzt, bestimmt die poolSize die Anzahl deiner Worker-Threads. Bei

newCachedThreadPool()

wird die Anzahl der Threads durch das System flexibel gewählt (damit habe ich aber auch schonmal schlechte Erfahrungen gemacht).

Zu dem im besten Falle doppelt so schnell: Jein ;-) Da darfst du erst einmal nur die Zeit für die eigentlichen Berechnungen messen und zusätzlich musst du noch berücksichtigen, dass je nach verwendeter CPU auch ein einzelner CPU-Kern höher getaktet werden kann als wenn du mehrere Kerne gleichzeitig verwendest (Stichwort TurboBoost bei Intel-CPUs).
Außerdem sind 5 Sekunden generell nicht wirklich viel. Da würdest du bessere Vergleichsergebnisse bekommen, wenn eine Berechnung z.B. mal eine Minute braucht und mal 30 Sekunden Multithreaded.

Aber da es ja jetzt stabil läuft kannst du den aktuellen Stand ja einfach mal gut sichern und dann in einer Kopie davon versuchen weitere Programmteile zu parallelisieren. (Hast ja noch bis Dienstag Zeit ;-))

 

[Kaschina]

Wunderbar, dann hab ichs richtig gemacht
Ich hab schon zwei weitere Teile zusätzlich parallel gemacht, mehr finde ich gerade nicht...
Bei Interesse würde ich das gute Stück am Dienstag posten.

 

[Paddelpirat]

Bei Interesse würde ich das gute Stück am Dienstag posten.

Kannst du gerne machen, damit wir mal wieder etwas zum Zerpflücken haben. *gg*
Nein, Spaß beiseite, würde mich schon interessieren wie du es dann letztendlich gemacht hast. Werde dann wahrscheinlich auch mal ausprobieren, was sich da laufzeittechnisch noch verbessern lässt.

 

[Marco13]

Also ich hab' das jetzt mal an einer steinalten Single-Core (!) Kiste getestet, und mit einem 500x2000-Bild dauert es von vornherein nur ca. 300ms :bahnhof: Werd' ggf. mal schauen, wie es bei einem (viel viel) größeren Bild auf dem Quadcore aussieht...

 

[Kaschina]

Das Berechnen von den einzelnen durchschnittswerten + malen dauert bei mir auch "nur" 1 knappe sekunde. Dann nochmal zwei, um die richtigen bilder aus der liste zu suchen, zu verkleinern und zu malen + knapp 2 sekunden, um das neue bild zu speichern.

Was genau hast du denn laufen lassen, marko?
Edit: mein momentanes testbild hat 5000x2000 pixel und eine kachelgroesse von 20x20. Ich werds nachher mal mit einem kleineren laufen lassen...

 

[Kaschina]

Das Berechnen von den einzelnen durchschnittswerten + malen dauert bei mir auch "nur" 1 knappe sekunde. Dann nochmal zwei, um die richtigen bilder aus der liste zu suchen, zu verkleinern und zu malen + knapp 2 sekunden, um das neue bild zu speichern.

Was genau hast du denn laufen lassen, marko?
Edit: mein momentanes testbild ha 5000x2000 pixel und eine kachelgroesse von 20x20. Ich werds nachher mal mit einem kleineren laufen lassen...

 

[Marco13]

Hmnaja, da ich erst am Sonntag weiter testen kann, hier mal der erste, kommentarfrei und weitgehend unüberlegt und un-optimiert hingehackte Schnellschuss:

import java.awt.Graphics;
import java.awt.GridLayout;
import java.awt.image.BufferedImage;
import java.awt.image.DataBuffer;
import java.awt.image.DataBufferInt;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

import javax.imageio.ImageIO;
import javax.swing.ImageIcon;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.SwingUtilities;

public class Mosaic
{
    private static final boolean MULTITHREADED = true;
    
    public static void main(String[] args) throws IOException
    {
        final BufferedImage inputImage = ImageIO.read(new File("testImage01.jpg"));
        long beforeNanoTime = System.nanoTime();
        final BufferedImage outputImage = create(inputImage, 10, 10);
        long afterNanoTime = System.nanoTime();
        System.out.println("Duration "+(afterNanoTime-beforeNanoTime)*1e-6);
        
        
        SwingUtilities.invokeLater(new Runnable()
        {
            @Override
            public void run()
            {
                JFrame f = new JFrame();
                f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                f.getContentPane().setLayout(new GridLayout(1,0));
                f.getContentPane().add(new JLabel(new ImageIcon(inputImage)));
                f.getContentPane().add(new JLabel(new ImageIcon(outputImage)));
                f.pack();
                f.setVisible(true);
            }
        });
    }
    
    
    private static BufferedImage create(BufferedImage inputImage, int tileSizeX, int tileSizeY)
    {
        int w = inputImage.getWidth();
        int h = inputImage.getHeight();
        BufferedImage image = new BufferedImage(w, h, BufferedImage.TYPE_INT_ARGB);
        Graphics g = image.createGraphics();
        g.drawImage(inputImage, 0, 0, null);
        g.dispose();
        DataBuffer dataBuffer = image.getRaster().getDataBuffer();
        DataBufferInt dataBufferInt = (DataBufferInt)dataBuffer;
        int data[] = dataBufferInt.getData();
        
        BufferedImage result = new BufferedImage(w, h, BufferedImage.TYPE_INT_ARGB);
        DataBuffer resultDataBuffer = result.getRaster().getDataBuffer();
        DataBufferInt resultDataBufferInt = (DataBufferInt)resultDataBuffer;
        int resultData[] = resultDataBufferInt.getData();
        
        if (MULTITHREADED)
        {
            computeMosaicMT(data, resultData, w, h, tileSizeX, tileSizeY);
        }
        else
        {
            computeMosaicST(data, resultData, w, h, tileSizeX, tileSizeY);
        }
        
        return result;
    }
    
    private static void computeMosaicST(
        int[] data, int[] resultData, 
        int w, int h, 
        int tileSizeX, int tileSizeY)
    {
        int numTilesX = (int)Math.ceil((float)w / tileSizeX);
        int numTilesY = (int)Math.ceil((float)h / tileSizeY);
        for (int y=0; y<numTilesY-1; y++)
        {
            for (int x=0; x<numTilesX-1; x++)
            {
                handleTile(data, resultData, w, h, x, y, tileSizeX, tileSizeY);
            }
        }
    }
    
    private static void computeMosaicMT(
        final int[] data, final int[] resultData, 
        final int w, final int h, 
        final int tileSizeX, final int tileSizeY)
    {
        int numProcessors = Runtime.getRuntime().availableProcessors();
        System.out.println("Processors: "+numProcessors);
        int numBatches = numProcessors * 2;
        ExecutorService e = Executors.newFixedThreadPool(numBatches);
        List<Callable<Object>> tasks = new ArrayList<Callable<Object>>();
        int numTilesX = (int)Math.ceil((float)w / tileSizeX);
        int numTilesY = (int)Math.ceil((float)h / tileSizeY);
        for (int y=0; y<numTilesY-1; y++)
        {
            for (int x=0; x<numTilesX-1; x++)
            {
                final int fx = x;
                final int fy = y;
                Runnable runnable = new Runnable()
                {
                    @Override
                    public void run()
                    {
                        handleTile(data, resultData, w, h, fx, fy, tileSizeX, tileSizeY);
                    }
                };
                tasks.add(Executors.callable(runnable));
            }
        }
        try
        {
            e.invokeAll(tasks);
        }
        catch (InterruptedException e1)
        {
            Thread.currentThread().interrupt();
        }
    }    
    
    
    private static void handleTile(
        int[] data, int[] resultData, 
        int w, int h, int x, int y, 
        int tileSizeX, int tileSizeY)
    {
        int x0 = x * tileSizeX;
        int x1 = x0 + tileSizeX;
        int y0 = y * tileSizeY;
        int y1 = y0 + tileSizeY;
        int argb = computeAverage(data, w, h, x0, y0, x1, y1);
        fill(resultData, w, h, x0, y0, x1, y1, argb);
    }


    private static void fill(int data[], int w, int h, int x0, int y0, int x1, int y1, int argb)
    {
        for (int y=y0; y<y1; y++)
        {
            Arrays.fill(data, y*w+x0, y*w+x1, argb);
        }
    }
    
    private static int computeAverage(int data[], int w, int h, int x0, int y0, int x1, int y1)
    {
        int sumA = 0;
        int sumR = 0;
        int sumG = 0;
        int sumB = 0;
        
        for (int y=y0; y<y1; y++)
        {
            for (int x=x0; x<x1; x++)
            {
                //System.out.println("At "+x+" "+y+" of "+w+" "+h);
                int argb = data[x+y*w];
                int a = ((argb >> 24) & 0xFF);
                int r = ((argb >> 16) & 0xFF);
                int g = ((argb >>  8) & 0xFF);
                int b = ((argb >>  0) & 0xFF);
                
                sumA += a;
                sumR += r;
                sumG += g;
                sumB += b;
            }
        }
        
        int n = (x1-x0)*(y1-y0);
        int avgA = sumA / n;
        int avgR = sumR / n;
        int avgG = sumG / n;
        int avgB = sumB / n;
        int result = 
            (avgA << 24) |
            (avgR << 16) |
            (avgG <<  8) |
            (avgB <<  0);
        return result;
    }
    
}

 

[Kaschina]

Euch beschäftigt das thema also auch

Das wäre dann ungefähr die knappe zusammenfassung von meiner ersten Hälfte.
Ich beisse noch ein wenig auf meiner Bilderzuordnung herum, die zwar schneller geworden ist, aber immer noch doof.

Kann man eigentlich den speichervorgang irgendwie beschleunigen?
ImageIO.write(image, "png", new File(path)); dauert die besagten 2 sekunden...

 

[Marco13]

Theoretisch, vielleicht man könnte mal schauen ob man die Komprimierung ändern/weglassen kann... wie lange braucht's denn als JPG? (Das ist Verlustbehaftet und die default-Komprimierung sehr hoch, aber ... bei einem Mosaikbild sollte JPG sich eigentlich freuen )

 

[Kaschina]

Ich hab gerade nochmal nachgesehen, ich muss es als png abspeichern.
Außerdem - so wie ich es verstehe, würde jpg nur dann funktionieren, wenn ich die Unterbilder nur durch die Farbdurchschnitte ersetze, ich ersetze es aber durch andere Bilder, damit hilft doch dann auch kein jpg? Oder verstehe ich es falsch?

Zwecks Verständnis mal ein Originalbild

Uploaded with ImageShack.us


und das Mosaikbild dazu:


Uploaded with ImageShack.us

Ist halt jetzt groß gekachelt, aber so im Prinzip...

 

[Paddelpirat]

Bilder im jpg-Format sind halt in der Regel kleiner vom Speicherplatzverbrauch, d.h. du könntest sie schneller laden, speichern und evtl. auch skalieren.

 

[Kaschina]

Hachja, mein schönes Halbwissen immer... Aber hilft mir trotzdem nichts, wenn ich in einem anderen Format speichern muss.

Und nochmal eine - schon wieder - Zwischenfrage:
das ist der "Endaufruf" nach dem Neumalen des Bildes.

		threadPool.shutdown();
		if (threadPool.isTerminated()) {
			frame.repaint();
		}

Sollte eigentlich das komplett neue Bild zeichnen. Scheinbar ist isTerminated() manchmal aber auch schon true, wenn noch gearbeitet wird, sprich: Es wird nicht immer ein ganz fertiges Bild angezeigt, sondern teilweise fehlen noch die letzten paar Kachelreihen.
Gibts dafür einen sinnvolleren Befehl, oder benutze ich ihn falsch?

(Ich will anfangs das Originalbild anzeigen und nach den Berechnungen dann das Fenster neuzeichnen mit dem "neuen" Bild)

 

[Paddelpirat]

Wie wäre es mit

isShutdown()

statt

isTerminated()

?

 

[Kaschina]

mmmh, nein.
Es geht 10mal gut und beim 11. mal zeigt er wieder ein halbfertiges Bild an...

int index = 0;
		for (int x = 0; x < sourceWidth; x += tilesWidth) {
			for (int y = 0; y < sourceHeight; y += tilesHeight) {
				try {
					MyBufferedImage now = fittingImages.get(index);
					BufferedImage tile = now.getResizedImage(tilesHeight, type);
					mtpe.add(source, tile, x, y);
				} catch (Exception e) {
					System.out.println("hier stimmts nicht !" + index);
				}
				index++;
			}
		}
		mtpe.shutdown();
		if (mtpe.paintIsComplete()) {
			frame.repaint();
		}

mal alles, inklusive den Schleifendurchläufen.
dieses "paintIsComplete()" gibt "threadPool.isShutdown()" zurück, wie du gerade geschrieben hast.
mtpe.add(....) startet einen Worker der die entsprechende Stelle im Originalbild (also source) malt.

Das gespeicherte Bild stimmt aber dann wieder.

 

[Paddelpirat]

Wundert mich jetzt aber auch, dass das gespeicherte Bild dann stimmt. In wiefern unterscheidet sich denn bei dir das Bild zum Anzeigen von dem, welches du abspeicherst? Eigentlich sollte das ja dasselbe Objekt sein.

 

[Marco13]

Warum verwendest du nicht "invokeAll", wie oben in dem Code den ich gepostet hatte? Das wartet automatisch, bis alle fertig sind.

 

[Kaschina]

Das hatte ich übersehen :/

Ich werds später ausprobieren.. Erstmal noch was Anderes fertigmachen.

Danke nochmal für eure Geduld

 

[Paddelpirat]

Warum verwendest du nicht "invokeAll", wie oben in dem Code den ich gepostet hatte? Das wartet automatisch, bis alle fertig sind.

Das könnte aber evtl. schneller laufen mit dem CompletionService, oder kann man sicher stellen, das die CPU beim vorbereiten der einzelnen Quadrate, die den Workern übergeben werden, voll ausgelastet ist?

Sonst könnte man den Ansatz verfolgen, dass der ThreadPool schon einzelne Datensätze an seine Worker weiter gibt, während weitere Datensätze erst vorbereitet werden.

 

[Kaschina]

Was mir gerade noch einfällt... Mit invokeAll() hatte ich zu Beginn gearbeitet, bevor ich gefragt habe, wie ich das Programm schneller bekomme.


Ich werde morgen weiterfrickeln und das invokeAll einbinden , gerade gibt's noch ein anderes Problem. Es lebe die Informatik am Samstag Abend!
*Ironie aus*

 

[Paddelpirat]

Hab auch eben nochmal an einer eigenen Version gefrickelt ^^. Funktioniert zwar, ist aber unendlich lahm trotz dauerhafter 100% Auslastung. Könnte aber auch etwas an den Bildern liegen, die die jar Datei auf ca 600MB aufgebläht haben

Der Nachteil von invokeAll dürfte dann eigentlich sein, dass du die Kacheln nicht sofort anzeigen kannst, wenn sie fertig Berechnet wurden, sondern dann am Ende von invokeAll alle Resultate gleichzeitig zur Verfügung stehen.

 

[Kaschina]

Dur hast die Bilder in der jar gespeichert?
Ich hab einfach nur ein kleines Programm, das aus einem / mehreren Verzeichnissen die Bilder ausliest und die Durchschnittswerte + Pfade in einer Liste speichert. Liste speichern, beim Programmstart vom "großen Programm" aufrufen, schon ist alles schlanker...

Genau das war das Problem. Andererseits gehts nur noch ums malen, alles Andere ist da schon fertig.
Gemalt ist glaub ich in 300ms, also eigentlich dürft es nicht mehr so viel Zeit kosten.
Ich lass Eclipse trotzdem heute aus, sonst ist es 4 Uhr morgens und die anderen Abgaben immer noch nicht erledigt

 

[Paddelpirat]

Hehe, ja ist nicht ganz optimal, dass die Sachen da drin sind. Ansonsten habe ich auch eine Tabelle mit den Durchschnittswerten zu den jeweiligen Bildern, die werden also nicht jedesmal berechnet. Was bei mir im Moment lange dauert ist das verkleinern der Bilder (Jedes hat die Auflösung 3968x2976) und das anschließende Zeichnen in das große Bild.