Effizienteres CPU-Rendern

[Luk10]

Grüße,

für den LD24 greife ich dieses mal (wieder) auf "einfaches" CPU-Render zurück um meinen alten Code / Engine verwenden zu können und mich nicht in LWJGL zu verlieren.

Hab da ein bisschen rumprobiert und wollte jetzt auch Alpha-Support einbauen. In meiner Enigne verwende ich "rohe" Pixel-Daten ohne BufferedImages etc. und berechne meine Farben / Alpha also auch selbst. Dazu verwende ich ganz normal Porter-Duff Composition ? Wikipedia mit folgender Methode, die Marco13 mal freundlicherweis für mich "aufgeräumt" hat:

protected static int computeColor(int argb0, int argb1) {
	double a0 = ((argb0 >> 24) & 0xff) / 255.0;
	double r0 = ((argb0 >> 16) & 0xff) / 255.0;
	double g0 = ((argb0 >> 8) & 0xff) / 255.0;
	double b0 = ((argb0 >> 0) & 0xff) / 255.0;

	double a1 = ((argb1 >> 24) & 0xff) / 255.0;
	double r1 = ((argb1 >> 16) & 0xff) / 255.0;	
	double g1 = ((argb1 >> 8) & 0xff) / 255.0;
	double b1 = ((argb1 >> 0) & 0xff) / 255.0;

	double a = a1 + (1 - a1) * a0;

	double r = (1.0 / a) * (a1 * r1 + (1 - a1) * a0 * r0);
	double g = (1.0 / a) * (a1 * g1 + (1 - a1) * a0 * g0);
	double b = (1.0 / a) * (a1 * b1 + (1 - a1) * a0 * b0);

	int result = ((int) (a * 255) << 24) | ((int) (r * 255) << 16) | ((int) (g * 255) << 8) | ((int) (b * 255) << 0);

	return result;
}

Nun zu meinem Problem:

Wenn ich diese Methode über mehr als ca. 200.000 Pixel / Loop laufen lasse brechen mir die fps auf <60 ein ... Verwendet wird ein (einizger) Thread der nur für diese Berechnung da ist. Dennoch sind 200k Pixel nicht gerade viel.

Kann man da relativ einfach noch was tweaken um die Performance zu verbessern? Multi-Threading hab ich schon vergeblich versucht ... das ist ganz ekelhaft zu sychronisieren (für mich zumindest) und wäre jetzt keine Option.

Vielleicht kann mir ja jemand zu dieser späten Stunde noch helfen.
-Luk10-

 

[Marco13]

Warum steht das ""aufgeräumt"" in Anführungszeichen? ueh: Ich erinnerte mich dunkel an den Thread, mußte jetzt aber erst über http://www.java-forum.org/awt-swing-swt/134165-frage-farb-komposition.html und http://www.java-forum.org/awt-swing-swt/133678-alpha-composing.html drübersuchen, um dann (nach "argb1" zu suchen und) http://www.java-forum.org/softwaree...es-design-clean-code-etc-pp-3.html#post881769 zu finden.

Die Performance wurde da ja auch schon angesprochen. Man könnte "theoretische" Optimierungen machen, die darauf abzielen, die reine Instruktionszahl zu verringern, bzw. lieber "billige" Multiplikationen statt "teurer" Divisionen zu machen...

private static final float NORMALIZE = 1.0f / 255.0f;

protected static int computeColor(int argb0, int argb1) {
    double a0 = ((argb0 >> 24) & 0xff) * NORMALIZE;
    double r0 = ((argb0 >> 16) & 0xff) * NORMALIZE;
    double g0 = ((argb0 >>  8) & 0xff) * NORMALIZE;
    double b0 = ((argb0      ) & 0xff) * NORMALIZE;
 
    double a1 = ((argb1 >> 24) & 0xff) * NORMALIZE;
    double r1 = ((argb1 >> 16) & 0xff) * NORMALIZE; 
    double g1 = ((argb1 >>  8) & 0xff) * NORMALIZE;
    double b1 = ((argb1      ) & 0xff) * NORMALIZE;
 
    double factor = (1 - a1) * a0;
    double invA = 1.0f / (a1 + factor);
 
    double r = invA * (a1 * r1 + factor * r0);
    double g = invA * (a1 * g1 + factor * g0);
    double b = invA * (a1 * b1 + factor * b0);
 
    int result = ((int) (a * 255) << 24) | ((int) (r * 255) << 16) | ((int) (g * 255) << 8) | ((int) (b * 255));
 
    return result;
}

... aber man weiß nicht, was der Compiler davon ohnehin schon macht, und es dürfte nicht wirklich "viel" bringen - obwohl ich in einem ähnlichen Fall schonmal durch sowas wie das 'NORMALIZE' und 'invA' einen (in der Praxis) messbaren Geschwindigkeitsvorteil erreich zu haben glaube. Wenn so ein Teil aber als Bottleneck identifiziert wurde, sind solche Sachen aber IMHO legitim. Es kann nicht schaden, und selbst wenn es dadurch einen Hauch unübersichtlicher werden würde (was hier IMHO nichtmal der Fall ist) könnte das ja den ebenso möglichen Hauch an Geschwindigkeitszuwachs wert sein. Aber wenn's nichts bringt, wieder rausnehmen

Ansonsten wird die Luft bei der Optimierung so eines kleinen und auf's wesentliche beschränkten Codestücks aber ziemlich dünn. Nahe liegend wäre noch zu versuchen, ob man das irgendwie auf bytes oder ints umbiegen kann, aber das wäre wahrscheinlich ein ziemliches Gefrickel, damit am Ende noch das gleiche rauskommt - und OB es was bringen könnte, kann ich im Moment kaum einschätzen...

Aber... gerade bei allem, was mit der Verarbeitung einzelner Pixel zu tun hat (wie in diesem Fall) drängt sich eine Parallelisierung ja schon auf: Das ist eines der Probleme, die als Embarrassingly parallel - Wikipedia, the free encyclopedia bezeichnet werden, weil die einzelnen Aufgaben (hier: Pixel bearbeiten) keine Kommunikation oder echte Synchronisation erfordern.

Wo trat denn die Schwierigkeit beim Synchronisieren auf? Poste mal ein repräsentatives Stück rund um den Code wo diese Methode aufgerufen wird (idealerweise natürlich als KSKB, ggf. mit dummy-Daten), da kann man bestimmt recht leicht noch was rausholen.

 

[Luk10]

Sooo,

die Methode wird durchgängig für alle zeichenbare Objekte (bei mir jetzt:

CPURender

) in einer Schleife und in meinem RenderThread aufgerufen.

Deshalb denke ich, dass hier schonmal kein Multi-Threading in Frage kommen kann, da ich ja auf einen gemeinsamen Kontext zeichnen lasse und nicht Bild A halb und währendessen Bild B unkontrolliert drüberzeichen lassen kann.

Evt. kann man aber hier was Sychroniersieren: Kurz noch den Stack beim rendern zum Verständniss:

> Loop über alle zeichenbaren Objekte
> Für jedes Objekt (CPURender):
> Gehe jedes Pixel des CPURenders durch und verarbeite es ggf. mit computeColor, siehe oben

> Jeder CPURender hat width, height und die Pixel-Daten als

int[] pixels

>

CPURender render

ist mein Objekt
>

CPURender offScreenRender

ist mein Kontext "OffScreen" Render auf das alles gezeichnet wird.

@Override
	public void draw(GopRender rawRender) throws GopRenderIncompatibleException {
		if (!(rawRender instanceof CPURender)) throw new GopRenderIncompatibleException(this, rawRender);
		CPURender render = (CPURender) rawRender;

		for (int iy = 0; iy < render.height; iy++) {
			for (int ix = 0; ix < render.width; ix++) {
				// [r][c]cp represents the index in [render][offScreenRender].pixels for the current pixel
				final int rcp = iy * render.width + ix;
				final int ccp = (render.y + iy) * offScreenRender.width + render.x + ix;
				// testing whether the current pixel is within the range of offScreenRender.pixels (clipping space)
				if (ccp >= offScreenRender.pixels.length) break;
				// testing whether the current pixel is opaque which makes rendering necessary
				if (render.pixels[rcp] >>> 24 != 0) {
					// if the render says to only replace or if the pixel in render is completly opaque simply replace the pixel in offScreenRender
					if (render.renderMode == CPURender.RENDERMODE_REPLACE || render.pixels[rcp] >>> 24 == 0xff) {
						offScreenRender.pixels[ccp] = render.pixels[rcp];
						// if not compute the color of the pixel using the porter-duff formula in computeColor(...)
					} else if (render.renderMode == CPURender.RENDERMODE_BLEND) {
						offScreenRender.pixels[ccp] = computeColor(offScreenRender.pixels[ccp], render.pixels[rcp]);
					}
				}
			}
		}
	}

In schlechtem Englisch kommentiert ... sorry dafür.

 

[Spacerat]

Also ganz banal würde ich Engine weit ein Farbmodell mit floats und RGBA-Werten zwischen 0 und 1 etablieren. das hätte schon mal den Vorteil, dass Systemfarben für Berechnungen nur ein einziges mal in dieses und nur zum Rendern wieder zurück gewandelt werden müssten.

 

[Marco13]

@Spacerat: Kommt darauf an... wenn die Daten NUR für die Berechnung in float umgewandelt werden müssen (wie es im Moment in der ComputeColor angenommen wird) wäre ein ganzes Modell in floats vermutlich nicht sinnvoll. Wenn aber wirklich viele Berechnungen gemacht werden müssen, bei denen es immer vorteilhaft wäre, sie direkt auf floats zu machen, schon, klar.

@Luk10: Ein paar Sachen sind mir nicht klar. Das Clipping dort ergibt ja nicht viel Sinn: Bei einem 10x10 = 100 Pixel-Feld könnte man dort ja auf (x,y) = (99,0) zugreifen, obwohl es schon bei (x,y) = (10,0) krachen sollte.
Abgesehen davon ... WAS dort gemacht wird hängt ja offenbar in der innersten Schleife vom "Rendermode" ab. Es erschiene mir nahe liegend, diese Entscheidung (wenn es wirklich um Performance geht) nach oben zu ziehen.

for (x...)
{
    for (y...
    {
        if (mode == a) doThis();
        else doThis();
    }
}

->

if (mode == a) 
{
    for (x...)
    {
        for (y...
        {
            doThis();
        }
    }
}
else
{
    for (x...)
    {
        for (y...
        {
            doThat();
        }
    }
}

Jaaaa, bevor sich jemand beschwert: Wenn man das machen würde, würde man den Rest, also die beiden verschachtelten Schleifen, doppelt hinschreiben müssen, was unschön ist. Das andere Extrem wäre, in der innersten Schleife diese "Entscheidung" über einen Interfacemethodenaufruf zu treffen.

Performer p = null;
if (mode == a) p = new ThisPerformer();
else p = new ThatPerformer();

for (x...)
{
    for (y...
    {
        p.perform();
    }
}

Aber...das zielt auch darauf ab, das jeder, der jetzt versuchen sollte, das (ohne sonstige Umstrukturierungen, wie etwa eine Änderung des Datenmodells) testen und ggf. parallelisieren wollte, diese Änderungen zur Erstellung eines KSKB selbst machen müßte *räusper*

 

[Luk10]

Brauche nur bei dieser Berechnung floats und sonst ints.

Clipping ist totaler bullshit wie es da steht. Das ist noch work in progress ... hab vergessen es rauszunehmen!

Wieso wollte man die Entscheidung
a) rausziehen wollen?
b) unnötig? mit einer eigene Struktur regeln?

Was meinst du mit Änderung des Datenmodells?

EDIT: Mein Performance-Problem liegt denke ich nicht bei der Entscheidung welcher Render-Mode zu wählen ist, sonder wenn RENDERMODE_BLEND gewählt wird, dass dann die Berechnung sehr lange dauert

 

[Spacerat]

Also ich finde schon, dass ein solches Datenmodell in jeder Hinsicht Sinn macht.

public class Color {
	private float[] floats = new float[4];
	private int argb;
	private boolean valid;

	public Color(int argb) {
		setARGB(argb);
	}

	public void setAlpha(float value) {
		value = clamp(value);
		valid = floats[0] != value; // floats vergleicht man natuerlich anders ;)
		floats[0] = value;
	}

	public void setRed(float value) {
		value = clamp(value);
		valid = floats[1] != value;
		floats[1] = value;
	}

	public void setGreen(float value) {
		value = clamp(value);
		valid = floats[2] != value;
		floats[2] = value;
	}

	public void setBlue(float value) {
		value = clamp(value);
		valid = floats[3] != value;
		floats[3] = value;
	}

	public float getAlpha() {
		return floats[0];
	}

	public float getRed() {
		return floats[1];
	}

	public float getGreen() {
		return floats[2];
	}

	public float getBlue() {
		return floats[3];
	}

	public int getARGB() {
		if(!valid) {
			argb = 0;
			for(int n = 0; n < floats.length; n++) {
				argb <<= 8;
				argb |= (int) (floats[n] * 255.0F);
			}
			valid = true;
		}
		return argb;
	}

	public void setARGB(int argb) {
		floats[0] = ((argb >> 24) & 0xFF) / 255.0F;
		floats[1] = ((argb >> 16) & 0xFF) / 255.0F;
		floats[2] = ((argb >>  8) & 0xFF) / 255.0F;
		floats[3] = ((argb      ) & 0xFF) / 255.0F;
		this.argb = argb;
		valid = true;
	}

	private float clamp(float value) {
		if(value < 0.0F) {
			value = 0.0F;
		}
		if(value > 1.0) {
			value = 1.0F;
		}
		return value;
	}

	public static Color destinationBlend(Color a, Color b) {
		float[] a0 = a.floats;
		float[] a1 = b.floats;

		float factor = (1 - a1[0]) * a0[0];
		float invA = 1.0F / (a1[0] + factor);

		a.setRed(invA * (a1[0] * a1[1] + factor * a0[1]));
		a.setGreen(invA * (a1[0] * a1[2] + factor * a0[2]));
		a.setBlue(invA * (a1[0] * a1[3] + factor * a0[3]));

		return a;
	}
}

Man kann nun auf Fliesskommabasis soviele Berechnungen anstellen wie man möchte. Erst wenn die Farbe zum Rendern benötigt wird, kann man sie sich als Integerwert holen. Dieser muss möglicherweise nichtmal mehr neu berechnet werden, wenn die Floats und die Ints noch synchron (valid) sind. Findet ihr nicht, dass das jede Menge Performance bringen könnte und auch für zukünftige Erweiterungen recht handlich ist (HINT: Just say yes. )?
[EDIT]Da fällt mir noch ein, dass der Fliesskommateil als HSBA-Implementation (Hue, Saturation, Brightness, Alpha) von vorne herein evtl. noch mehr Sinn machen würde, dann könnte man nämlich recht schnell noch ein paar Blendeffekte (Helligkeit, Sättigung usw.) mehr implementieren. Leider finde ich für HSBA keinerlei Alphablending-Algos. [/EDIT]

 

[Marco13]

Aaalso... unten ein schnell hingehackter Test. Der hat zwei Flags, um die Implementierungen umzuschalten.

Test mit einem Bild mit ca. 2500x2000 Pixeln, auf einen Dual-CoreQ6600 @ 2.4GHz

- Single-Threaded, ursprüngliche 'computeColor': ca. 536 ms
- Single-Threaded, optimierte 'computeColor': ca. 187 ms (! Das hätte ich selbst nicht gedacht!)
- Multi-Threaded, ursprüngliche 'computeColor': ca. 159 ms
- Multi-Threaded, optimierte 'computeColor': 44 ms

Mehr als eine Größenordnung mit so wenig Aufwand, das ist doch mal was. So sollte es immer sein

import java.awt.Color;
import java.awt.Graphics2D;
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.List;
import java.util.Random;
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 ParallelAlphaBlending
{
    private static final boolean USE_OPTIMIZED_COMPUTE_COLOR = false;
    private static final boolean USE_MULTI_THREADING = false;
    
    public static void main(String[] args) throws IOException
    {
        final BufferedImage image0 = loadImage("IMG_1568.JPG");
        int w = image0.getWidth();
        int h = image0.getHeight();
        final BufferedImage image1 = createImage(w, h);
        final BufferedImage image = createImage(w, h);
     
        int pixels0[] = getPixels(image0);
        int pixels1[] = getPixels(image1);
        int pixels[] = getPixels(image);
        
        long before = 0;
        long after = 0;
        
        for (int i=0; i<5; i++)
        {
            before = System.nanoTime();
            if (USE_MULTI_THREADING)
            {
                combineMT(pixels0, pixels1, pixels, w, h);
            }
            else
            {
                combineST(pixels0, pixels1, pixels, w, h);
            }
            after = System.nanoTime();
            System.out.println("Duration "+(after-before)*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(0,2));
                f.getContentPane().add(new JLabel(new ImageIcon(image0)));
                f.getContentPane().add(new JLabel(new ImageIcon(image1)));
                f.getContentPane().add(new JLabel(new ImageIcon(image)));
                f.setSize(800,800);
                f.setVisible(true);
            }
        });
        
    }
    
    private static BufferedImage createImage(int iw, int ih)
    {
        Random random = new Random(0);
        BufferedImage image = new BufferedImage(
            iw, ih, BufferedImage.TYPE_INT_ARGB);
        Graphics2D gr = image.createGraphics();
        for (int i=0; i<10; i++)
        {
            int r = random.nextInt(256);
            int g = random.nextInt(256);
            int b = random.nextInt(256);
            int x = random.nextInt(iw/2);
            int y = random.nextInt(ih/2);
            int w = random.nextInt(iw/2)+iw/2;
            int h = random.nextInt(ih/2)+ih/2;
            gr.setColor(new Color(r,g,b,32));
            gr.fillRect(x,y,w,h);
        }
        gr.dispose();
        return image;
    }
    
    private static int[] getPixels(BufferedImage image)
    {
        DataBuffer dataBuffer = image.getRaster().getDataBuffer();
        DataBufferInt dataBufferInt = (DataBufferInt)dataBuffer;
        return dataBufferInt.getData();
    }
    
    private static BufferedImage loadImage(String fileName) throws IOException
    {
        BufferedImage tempImage=ImageIO.read(new File(fileName));
        BufferedImage image = new BufferedImage(
            tempImage.getWidth(), tempImage.getHeight(), BufferedImage.TYPE_INT_ARGB);
        Graphics2D g = image.createGraphics();
        g.drawImage(tempImage, 0, 0, null);
        g.dispose();
        return image;
    }
    
    protected static int computeColor(int argb0, int argb1) {
        double a0 = ((argb0 >> 24) & 0xff) / 255.0;
        double r0 = ((argb0 >> 16) & 0xff) / 255.0;
        double g0 = ((argb0 >> 8) & 0xff) / 255.0;
        double b0 = ((argb0 >> 0) & 0xff) / 255.0;
     
        double a1 = ((argb1 >> 24) & 0xff) / 255.0;
        double r1 = ((argb1 >> 16) & 0xff) / 255.0; 
        double g1 = ((argb1 >> 8) & 0xff) / 255.0;
        double b1 = ((argb1 >> 0) & 0xff) / 255.0;
     
        double a = a1 + (1 - a1) * a0;
     
        double r = (1.0 / a) * (a1 * r1 + (1 - a1) * a0 * r0);
        double g = (1.0 / a) * (a1 * g1 + (1 - a1) * a0 * g0);
        double b = (1.0 / a) * (a1 * b1 + (1 - a1) * a0 * b0);
     
        int result = ((int) (a * 255) << 24) | ((int) (r * 255) << 16) | ((int) (g * 255) << 8) | ((int) (b * 255) << 0);
     
        return result;
    }    

    
    private static final float NORMALIZE = 1.0f / 255.0f;
    
    protected static int computeColorOptimized(int argb0, int argb1) {
        double a0 = ((argb0 >> 24) & 0xff) * NORMALIZE;
        double r0 = ((argb0 >> 16) & 0xff) * NORMALIZE;
        double g0 = ((argb0 >>  8) & 0xff) * NORMALIZE;
        double b0 = ((argb0      ) & 0xff) * NORMALIZE;
     
        double a1 = ((argb1 >> 24) & 0xff) * NORMALIZE;
        double r1 = ((argb1 >> 16) & 0xff) * NORMALIZE; 
        double g1 = ((argb1 >>  8) & 0xff) * NORMALIZE;
        double b1 = ((argb1      ) & 0xff) * NORMALIZE;
     
        double factor = (1 - a1) * a0;
        double invA = 1.0f / (a1 + factor);
     
        double r = invA * (a1 * r1 + factor * r0);
        double g = invA * (a1 * g1 + factor * g0);
        double b = invA * (a1 * b1 + factor * b0);
     
        int result = ((int) ((1.0f / invA) * 255) << 24) | ((int) (r * 255) << 16) | ((int) (g * 255) << 8) | ((int) (b * 255));
     
        return result;
    }    
    
    private static void combine(int pixels0[], int pixels1[], int pixels[], int w, int h, int min, int max)
    {
        for (int y = min; y < max; y++) 
        {
            for (int x = 0; x < w; x++) 
            {
                int index = x + y * w;
                if (USE_OPTIMIZED_COMPUTE_COLOR)
                {
                    pixels[index] = computeColorOptimized(pixels0[index], pixels1[index]);
                }
                else
                {
                    pixels[index] = computeColor(pixels0[index], pixels1[index]);
                }
            }
        }
    }
    
    static void combineST(int pixels0[], int pixels1[], int pixels[], int w, int h)
    {
        combine(pixels0, pixels1, pixels, w, h, 0, h);
    }
    
    private static void combineMT(final int pixels0[], final int pixels1[], final int pixels[], final int w, final int h)
    {
        int numProcessors = Runtime.getRuntime().availableProcessors();
        int numBatches = numProcessors * 2;
        ExecutorService e = Executors.newFixedThreadPool(numBatches);
        int batchSize = (int)Math.ceil((double)h / numBatches);
        List<Callable<Object>> tasks = new ArrayList<Callable<Object>>();
        for (int i=0; i<numBatches; i++)
        {
            final int minLocal = (i+0)*batchSize;
            final int maxLocal = Math.min(h, (i+1)*batchSize);
            Runnable runnable = new Runnable()
            {
                @Override
                public void run()
                {
                    combine(pixels0, pixels1, pixels, w, h, minLocal, maxLocal);
                }
            };
            tasks.add(Executors.callable(runnable));
        }
        try
        {
            e.invokeAll(tasks);
        }
        catch (InterruptedException e1)
        {
            Thread.currentThread().interrupt();
        }
    }
     
}

EDIT: Da war noch ein kleiner Fehler... hui, da sollte ich nochmal ausführlicher testen...

 

[Luk10]

Vielen Dank, dass du dir soviel Zeit genommen und ein Beispiel geschrieben hast, Marco! Ich habs mir noch nicht im Detail angeschaut (was ich noch machen werde).

Sehe ich das richtig, dass du [JAVA=204]combine(pixels0, pixels1, pixels, w, h, minLocal, maxLocal);[/code] nebenläufig aufrufst? Ich verstehe jedoch nicht was in dieser Methode (nebenläufig) genau passiert?
Wie werden pixels0 und pixels1 gleichzeitig auf pixels gezeichenet, ohne dass die Threads willkürlich übereinander zeichenen?

 

[Marco13]

Sowohl die "combineST" (Single Threaded) als auch die "combineMT" (Multi Threaded) greifen auch die gleiche Methode zurück: "combine". Die bekommt die Pixel übergeben, und die Größe des Bildes. Zusätzlich (als die letzten beiden Parameter) aber auch noch einen minimalen und maximalen y-Wert. Der beschreibt, um welchen Bereich es beim jeweiligen Aufruf geht. Bei der combineST ist es einfach: Es geht um 0...h, also die gesamte Höhe des Bildes. Bei der combineMT wird (abhängig von der Prozessoranzahl) das Bild in horizontale "Streifen" aufgeteilt. Die oberen und unteren Grenzen (y-Werte) dieser Streifen werden durch "minLocal" und "maxLocal" bestimmt, die an "combine" übergeben werden. Damit kümmert sich jeder Thread nur um einen Streifen des Bildes, und kommt keinem anderen in die Quere. Sie schreiben zwar alle in den gleichen Array, aber durch die "Streifen" ja an unterschiedlichen Stellen.

 

[Luk10]

Also werden Bild1 und Bild2 nacheinander ins Array geschrieben, aber jedes Bild wird in Streifen aufgeteilt und nebenläufig gezeichent.
Nachdem Bild1 vollständig drauf ist kommt Bild2.

Ist das so korrekt?

 

[Marco13]

Hmmmm ... Wirklich auf den Bildschirm gezeichet wird da nichts nebenläufig. Die Bilder sind Repräsentiert über Pixel-Arrays (die werden Am anfang erstellt - das passiert natürlich noch sequentiell). Angenommen die haben die Größe 100x40. Dann werden (sinngemäß, bei 4 Prozessoren) 4 "Aufgaben" erstellt:
1. Fülle die obersten 100x10 Pixel
2. Fülle die nächsten 100x10 Pixel
3. Fülle die nächsten 100x10 Pixel
4. Fülle die untersten 100x10 Pixel
und die werden dann gleichzeitig ausgeführt. Der eine Thread berechnet z.B. gerade Pixel 34,5 und der andere Thread gleichzeitig den Pixel 34,13 ...
Durch das "InvokeAll" wird dort gewartet, bis alle Threads mit "ihrem" Teil des Bildes fertig sind, und danach wird es gezeichnet.

 

[Luk10]

Hm meine Frage war missverständlich aber deine Antwort beantwortet sie trotzdem.
Ich werde das versuchen mal zu implementieren und hier rein posten, falls was nicht funktionert!

Vielen Dank nochmal für deine Mühe bisher!

 

[Luk10]

Sooo um das Thema hier vorerst mal abzuschließen:

Ich hab das jetzt bei mir erfolgreich implementieren können, jedoch habe ich noch zwei kleiner Fragen:

1) Ich produziere und stampfe dann ja wahnsinnig! viele

Runnable task

wieder ein. Hat das negative Auswirkungen auf Arbeitspeicher / Performance? Kann man evt. das reduzieren umgehen?

2) Ich hab mal mit 2^x Thread gestestet um zu schaun ob ich trotz begrenzter CPU-Kern Anzahl die Performance noch steigern kann. Jedoch sinkt die Performance sogar ab 2^2 Threads. Wie kann man das erklären?

Vielen vielen Dank nochmal Marco13! Du hast mir sehr geholfen!

 

[bERt0r]

Mal angenommen du hast zwei 50kg Zementsäcke (=Threads) und zwei Bauarbeiter (=CPU Kerne). Da ist es offensichtlich dass es einfacher ist wenn jeder einen Sack trägt als wenn einer beide schleppt.
Wenn du jetzt statt den zwei 50kg Säcken vier 25kg Säcke hättest, ist und dann wieder jedem Arbeiter zwei gibst, werden die die Säcke nicht schneller tragen. Wenn du deine 100kg Zement in zu viele Säcke einteilst könnte es sogar sein, dass sie schlechter zu tragen sind als zwei große - der Bauarbeiter hat nur zwei Arme (und der CPU Kern nur begrenzten Speicher).

 

[Marco13]

Wie viel hat's denn am Ende gebracht? (Ich bin immernoch überrascht über das "optimierte" computeColor. Ich hätte gedacht, dass es was bringt, vielleicht auch "spürbar", aber dass es mehr als dreimal so schnell ist nicht...)

Die vielen Tasks zu erstellen - hmja, da führt kaum ein Weg dran vorbei. Natürlich muss der GC die irgendwann wieder wegräumen, aber das ist ja kein Problem. Wenn es dadurch spürbar schneller wird, und, was viel wichtiger ist: Wenn es mit der Anzahl der Kerne skaliert, ist das ja OK.

Die "Optimiale" Anzahl von Tasks/Threads hängt stark vom Problem ab. In der Ursprünglichen Version ist die Anzahl ja 2*anzahlKerne (wobei da die "virtuellen" Kerne genommen werden - also 4 bei einem dual code mit Hyperthreading), die Faustregel ist GROB: "Etwas mehr Threads als man Kerne hat", aber das hängt wie gesagt stark davon ab, was genau die Threads machen.

 

[Luk10]

In meinem Fall habe ich eher viele kleine (100x100 - 300x300) "Bilder" als wenige große. Hab jetzt ausführlicher geteset:

Bis vier Threads / Tasks verdoppelt sich die Geschwindigkeit bei sich verdoppelnder Thread-Anzahl. Danach kann ich keinen Anstieg in der Performance mehr messen, und ab 20 Threads nimmt diese wieder ab. Auffällig ist auch, dass ab 4 Threads die Streuung der Zeiten (die ich dann Mittle) sehr stark zunimmt. Das bedeutet, es gibt mehr langsame durchläufe und mehr schnelle als der Durchschnitt.

Getestet wurde immer mit 10e5 Durchläufen / Test und es wurden immer 5 Test gemittelt.
Ich kann auch keine Verbesserung / Verschlechterung für doppelt soviele Tasks für meine Threads verstellen.

Interessant ist auch, dass das Multithreading mit zunehmender Last effizienter wird. Aber genaue Daten hab ich da jetzt nicht gemessen.

 

[Marco13]

Hm. Bei vielen kleinen Bildern könnte/sollte man sich auch überlegen, ob man die Verarbeitung wirklich innerhalb eines Bildes in mehrere Threads aufteilt, oder ob man die Aufteilung nicht "eine Ebene hoch" zieht, so dass dann zwar in Zukunft wieder EIN Bild von EINEM Thread bearbeitet wird (so wie jetzt in der computeST-Methode), aber es eben n Theads für die n Bilder gibt. Aber ob das was bringt oder einfacher oder schwerer ist, ist schwer zu sagen, bzw. hängt wieder von den Parametern ab: Wenn es 1000 Bilder der Größe 10x10 sind, würde es natürlich keinen Sinn machen, dort für jedes einzelne Bild 4 Tasks zu erstellen, die sich dann um 5x5 Pixel kümmern - DA wäre der Overhead für das Erstellen der Tasks natürlich zu groß.

 

[Luk10]

Ja ich habe mir auch schon überlegt, die Bilder auf Threads aufzuteilen. Aber da gibt es meiner Meinung nach ein ziemlich ekelhaftes Problem:

Die Bilder müssen in einer bestimmten Reihenfolge in den gleich Kontext(array) gezeichnet werden. Wie sollte man denn sowas parallelisieren?

 

[Marco13]

Ohne genauere Infos kann man da kaum was sagen. Überlappen sich die Bilder immer? Wenn ja, wie viel (sind sie immer Deckungsgleich?) Gibt es mehrere "Ebenen", z.B. 10 Ebenen mit jeweils 100 Bildern? Könnte es sich vielleicht sogar lohnen, nicht immer zwei Bilder zu kombinieren, sondern gleich immer n Bilder auf einmal?

 

[Luk10]

Ich habe immer ein "Hintergrund" Bild auf das die anderen Bilder ("Sprites") mit einem Offset gezeichnet werden. Die Sprites bewegen sich und überlappen sich ggf. auch.

Ich habe ca. 5-10 300x200 Bilder und 0-100 Sprites im Bereich von 4x4-64x64. Dazu kommen in der Zukunft wahrscheinlich noch Partikel, aber mal schaun wie ich das lösen werde.

 

[Marco13]

OK, man könnte jetzt was ganz geschicktes machen, und erstmal die überlappenden Bereiche bestimmen, um festzustellen, welche Bilder parallel gemalt werden können und so aber ...

...


... mal ein paar Stack-Ebenen höher: Warum genau willst du das in Software machen? ???:L

 

[Luk10]

Für den LD24 wollte ich ein Rendering System hernehmen mit dem ich mich gut auskenne. Da ich alles andere als sicher in OpenGL bin habe ich eben auf CPU-Rendering zurückgegriffen.

Da mir aber die Performance relativ schlecht vorkam, hab ich dieses Topic hier eröffnet und jetzt, und obwohl der LD schon vorbei ist bin ich immer noch dran interessiert das zu optimieren

 

[Marco13]

Hmja... den Teil mit "Ich will nicht Swing verwenden, weil...." habe ich vielleicht übersehen

 

[Spacerat]

[OT]>2000 Posts und keinen blassen... Was war ein LD doch gleich?[/OT]

 

[Ark]

Ich hab' mir mal den Code von Marco13 vorgenommen und vor allem die Normalisierungen gründlich gekürzt. Ergebnis: Code, der auf meinem Rechner im Mittel nur noch etwa 51,3% der Zeit beansprucht, aber das gleiche Ergebnis liefert - denke ich jedenfalls.
[java=139] private static final float[] NORM;

static {
NORM = new float[256];
for (int i = 0; i < NORM.length; i++) {
NORM = i / 255.0f;
}
}

protected static final int computeColorOptimized(final int argb0, final int argb1) {
final int a0 = ((argb0 >> 24) & 0xff);
final int a1 = ((argb1 >> 24) & 0xff);

if (a0 == 0) return argb1;
if (a1 == 0) return argb0;

final int r0 = ((argb0 >> 16) & 0xff);
final int g0 = ((argb0 >> 8) & 0xff);
final int b0 = ((argb0) & 0xff);

final int r1 = ((argb1 >> 16) & 0xff);
final int g1 = ((argb1 >> 8) & 0xff);
final int b1 = ((argb1) & 0xff);

final float x = (1 - NORM[a1]) * a0;
final float d = 1.0f / (a1 + x);
final int r = (int) ((x * r0 + a1 * r1) * d);
final int g = (int) ((x * g0 + a1 * g1) * d);
final int b = (int) ((x * b0 + a1 * b1) * d);

return (int)x + a1 << 24 | r << 16 | g << 8 | b;
}
[/code]
Bei der parallelisierten Version kann man eventuell auch noch was rausholen.

Ark

 

[Luk10]

[OT]LD ist die Akürzung für Ludum Dare[/OT]
Vielen Dank Ark, ich werde auch deine Version mal antesten!

Soo, nach einem kurzen! Test habe ich keine Signifikante Änderung feststellen können. Ich vermute, dass

if (a0 == 0) return argb1;
if (a1 == 0) return argb0;

die 50% ausmachen, die du festgestellt hast.
Diese Zeilen habe ich aber schon bei mir anderswo im Code.

Vielleicht zeigen aber ausführlichere Tests doch einen Unterschied.

 

[Marco13]

Ich hab' mir mal den Code von Marco13 vorgenommen und vor allem die Normalisierungen gründlich gekürzt. Ergebnis: Code, der auf meinem Rechner im Mittel nur noch etwa 51,3% der Zeit beansprucht, aber das gleiche Ergebnis liefert - denke ich jedenfalls.

Irgendwo (in diesem Thread?) hatte ich schon erwähnt, dass man ggf. einiges auf int umstellen könnte ... aber so beim zweiten drüberschauen habe ich mich eben gefragt, warum ich da überall double und nicht float geschrieben hatte... ???:L :bahnhof: (aber das nur nebenbei). Wie viel diese "early returns" für a0/a1 == 0 bringen, hängt letztlich vom Bildinhalt ab, aber sie können kaum schaden, das stimmt.

 

[Spacerat]

Ich hatte mich in diesem Zusammenhang im Nachhinein auch gefragt, ob Fliesskommarithmetik überhaupt notwendig ist. Evtl. kann man ja dort wo eine 1 steht auch 255 einsetzen.

 

[Ark]

Soo, nach einem kurzen! Test habe ich keine Signifikante Änderung feststellen können. Ich vermute, dass

if (a0 == 0) return argb1;
if (a1 == 0) return argb0;

die 50% ausmachen, die du festgestellt hast.
Diese Zeilen habe ich aber schon bei mir anderswo im Code.

Jein. Wenn ich die Abkürzungen rausnehme, komme ich auf "nur" 60,6%, zumindest bei meinen Tests, bei denen die Abkürzungen so gut wie nie genommen werden können. Ich vermute deshalb eher, dass in deinen Szenarien so gut wie immer der 0%/100%-Fall eintritt - Marco13 hat das ja auch schon angedeutet. Und da du diese Abkürzung sowieso schon vorher eingebaut hast, dürften sich meine Änderungen so gut wie nie auswirken. So sehe ich das jedenfalls.

So, ich habe mich noch einmal rangemacht, noch einmal einige Identitäten ausgenutzt und nun auch die letzte Gleitkommaoperation aus der Methode entfernt:
[java=139] private static final byte[] DIV255HE;

static {
DIV255HE = new byte[255 * 255];
for (int i = 0; i < DIV255HE.length; i++) {
DIV255HE = (byte)Math.rint(i / 255.0f);
}
}

// private static final int div255(int x){
// return (x + 1 + (x >> 8)) >> 8;
// }

protected static final int computeColorOptimized(final int argb0, final int argb1) {
if ((argb0 & 0xFF000000) == 0) return argb1;
final int a1 = argb1 >> 24 & 0xFF;
if (a1 == 0xFF) return argb1;
if (a1 == 0) return argb0;

final int r0 = argb0 >> 16 & 0xFF;
final int g0 = argb0 >> 8 & 0xFF;
final int b0 = argb0 & 0xFF;

final int r1 = argb1 >> 16 & 0xFF;
final int g1 = argb1 >> 8 & 0xFF;
final int b1 = argb1 & 0xFF;

final int r = DIV255HE[a1 * (r1 - r0) + (r0 << 8) - r0] & 0xFF;
final int g = DIV255HE[a1 * (g1 - g0) + (g0 << 8) - g0] & 0xFF;
final int b = DIV255HE[a1 * (b1 - b0) + (b0 << 8) - b0] & 0xFF;

// final int r = div255(a1 * (r1 - r0)) + r0;
// final int g = div255(a1 * (g1 - g0)) + g0;
// final int b = div255(a1 * (b1 - b0)) + b0;

return r << 16 | g << 8 | b | 0xFF << 24;
}
[/code]
Der Code ist in meinen Tests jetzt noch ein klitzekleines Stückchen schneller. Na ja, auf Kosten von Speicher: 65025 Bytes Lookup-Tabelle. Oh, Mann. Die könnte man eventuell noch etwas verkleinern, aber ich bezweifle, dass sich das lohnt. (Mal davon abgesehen, dass ja im vorliegenden Fall sowieso kaum Gebrauch von dieser Methode gemacht werden wird. )

Für die Tabelle verwendete ich "round half to even" als Rundungsverfahren. Als Alternative steht im folgenden Code noch eine Methode [c]div255()[/c] (geklaut von Stackoverflow ), die aber "round to zero" verwendet und - wenn man die auskommentierten Codestücke wieder reinnimmt - wesentlich langsamer ist, sogar langsamer als die Gleitkommavariante von weiter oben. Dafür braucht man aber nicht mal für die Tabelle Gleitkommaoperationen, denn die entfällt dann ganz. (@Marco: Ja, es geht tatsächlich nur mit Ganzzahlen. )

@Luk10: Deine Problemstellung ist übrigens ein schöner Anwendungsfall für SSE2 u.ä.

Ark

EDIT: Noch eine Abkürzung eingebaut und damit einen kleinen Fehler korrigiert - hoffentlich korrekt. In meinem Test wirkt es sich kaum aus, aber vielleicht hilft es dir ja, Luk10.

 

[Marco13]

@Luk10: Deine Problemstellung ist übrigens ein schöner Anwendungsfall für SSE2 u.ä.

Ich dachte eher an die GPU, aber ... das würde dann nicht mehr zum Threadtitel passen (und wäre hier auch aus anderen Gründen unangebracht).

BTW: @Luk10, Wo hattest du denn die ursprüngliche Formel her? Ich erkenne da durch draufschauen zumindest keine der Standard-Porter-Duff-Regeln drin ???:L (was vielleicht aber auch an den Optimierungen liegen kann )

 

[Ark]

Hm, okay, ich teste gerade mal meine letzte Methode (hui, da fange ich ja früh an ) und darf feststellen, dass sie gegenüber allen vorangegangenen Methoden an vielen Stellen komplett andere Werte liefert. Vielleicht habe ich ja einen Knick in der Optik, aber so beim Draufgucken-Testen sehe ich keinen Unterschied zum Referenzbild. ???:L :bahnhof: Ob ich mich doch irgendwo verrechnet habe? Ich verrechnete mich zwar schon mal vorher, aber da war es dann im Ergebnis auch klar ersichtlich. Vielleicht taugt aber auch der Test nichts. Hm … spannend.

Ark

 

[Luk10]

@Macro13 Die hab ich mir mithilfe von Alpha compositing - Wikipedia, the free encyclopedia zusammengebastelt.

@Ark Vielen Dank für deinen Aufwand die Methode noch mehr zu optimieren. Ich habe im Moment leider keine Zeit die Methoden alle ausführlich zu testen, aber kann das hoffentlich bald nachholen!

 

[Ark]

Ich glaube, das Problem ist identifiziert: Meine letzte Implementierung funktioniert nur, wenn argb0 vollständig opak ist, also [c](argb & 0xFF000000) == 0xFF000000[/c] gilt, oder wenn argb0 vollständig transparent ist, also [c](argb & 0xFF000000) == 0[/c] gilt!

@Luk10: Wenn du also weißt, dass z.B. argb0 immer ein undurchsichtiger Hintergrund ist, sollte die Methode wie gewünscht funktionieren. Das Ergebnis ist dann natürlich wieder opak. Wenn du also nur von "hinten" nach "vorn" zeichnest (quasi Maleralgorithmus ^^), sollte alles passen. (EDIT: Dann kannst du natürlich auch die erste Zeile in meiner Methode rausnehmen, da die eh nur Sinn ergibt, wenn argb0 nicht vollständig opak ist.) Andernfalls, also wenn du transparent auf transparent zeichnen musst, musst du auf andere Implementierungen ausweichen.

Ark