# Performance-Probleme



## blueJisCrap (28. Feb 2012)

Hallo zusammen,
Ich hab mich mal aus Spaß drangemacht 'Conway's Game of Life' umzusetzen. Das funktioniert prinzipiell auch ganz gut, nur läuft es mit einem 1600x800-Feld bei angestrebten 60 fps absolut nicht flüssig (Dabei wird jede Zelle mit einem Pixel dargestellt).

Nun zu meiner Frage: Gibt es eine performante Möglichkeit ein sehr großes zweidimensionales boolean-Array grafisch zu repräsentieren, oder anders gesagt ca. 1,3 Mio. Pixel mit 60fps zu rendern?

Falls ich in meinen Ausführungen irgendwas wichtiges vergessen habe, weist mich bitte darauf hin.


----------



## Gast2 (28. Feb 2012)

Ohne zu wissen wie du das bisher machst kann man nicht sagen wie es besser zu machen ist. Du solltest auf jedenfall zuerst alles auf nen BufferedImage zeichnen und das dann immer wieder auf dein JPanel malen falls du das nicht schon machst.


----------



## blueJisCrap (28. Feb 2012)

Dem zufolge müsste ich das BufferedImage in der Klasse Map erstellen.
Nachdem ich momentan nicht weiss wie ich das genau anstelle würde ich mich über etwas Hilfestellung freuen.

Bisher sieht die Klasse so aus:


```
import java.util.Random;
import java.awt.*;

public class Map{
    private boolean[][] map;
    private int width, height;
    private Random rnd;

    public Map(int x, int y){
        map = new boolean[x][y];
        width = x;
        height = y;
        rnd = new Random();
        if (Conway.RANDOMIZED){
            for(int i = 0; i < width; i++){
                for (int j = 0; j < height; j++){
                    map[i][j] = rnd.nextBoolean();
                }
            }
        }
    }

    private int getAmountOfNeighbors(int x, int y){
        int n = 0;
        if ((x < width) && (y < height) && (y >= 0) && (x >= 0)){
            for(int i =  x-1; i <= x+1; i++){
                for(int j =  y-1; j <= y+1; j++){
                    if(getState(i, j)){
                        n++;
                    }
                }
            }
        }
        return n;
    }

    private boolean getState(int x, int y){
        if ((x < width) && (y < height) && (y >= 0) && (x >= 0)){
            return map[x][y];
        }
        else if (Conway.RANDOMIZED){
            return false;
        }
        else{
            return true;
        }
    }

    private boolean getNextState(int x, int y){
        if ((x < width) && (y < height) && (y >= 0) && (x >= 0)){
            if(getState(x, y)){
                switch(getAmountOfNeighbors(x, y) - 1){
                    case 2: case 3: {return true;}
                    default: {return false;}
                }
            }
            else{
                if(getAmountOfNeighbors(x, y) == 3){
                    return true;
                }
                return false;
            }
        }
        return false;
    }

    private boolean[][] nextStep(){
        boolean[][] mapN = new boolean[width][height];
        for(int i = 0; i < width; i++){
            for (int j = 0; j < height; j++){
                mapN[i][j] = getNextState(i, j);
            }
        }
        return mapN;
    }

    public void tick(){
        map = nextStep();
    }

    public int getX(){
        return width;
    }

    public int getY(){
        return height;
    }

    public void paint(Graphics g){
        int a = Conway.SCALE;
        int b = Conway.BORDER;
        for(int i = 0; i < width; i++){
            for (int j = 0; j < height; j++){
                if(map[i][j]){
                    g.setColor(Color.GREEN);
                }
                else{
                    g.setColor(Color.DARK_GRAY);
                }
                g.fillRect(i*a + b , j*a + b, a, a);
            }
        }
    }
}
```

Ergänzung: Map verwendet 3 Konstanten der Klasse Conway:

RANDOMIZED: boolean, gibt an ob ich ein zufällig generiertes Ausgangsfeld will oder nicht
SCALE: int, Kantenlänge der einzelnen Quadrate für die Zellen
BORDER: int, Abstand vom Fensterrand


----------



## Gast2 (28. Feb 2012)

Also zunächst mal solltest du deine Klasse umbenennen, es in der Java API schon ne Klasse mit dem Namen Map. So wies ausschaut malst du bei jedem mal das komplette Feld, das dauert natürlich immer länger je größer das Feld wird.
Ich würde das mal so probieren:

- Sobald sich an deinem Spielfeld was ändert malst du das auf nen BufferedImage (nach möglichkeit änderst du dann auch nur die Bereiche die sich ändern
- in der paintComponent Methode deines Panels malst du dann nur noch das BufferedImage, das sollte dann recht flott gehn.

Wenns dann immernoch Probleme gibt muss man mal schauen wo die Zeit verloren geht.


----------



## blueJisCrap (28. Feb 2012)

Das Problem mit Conway's Game of Life ist, dass ich schlecht voraussagen kann was sich ändert. Ich könnte höchstens das Ergebnis von nextStep() mit dem aktuellen Feld vergleichen.

Damit bin ich aber immer noch nicht am Ziel: Wie zeichne ich denn eigentlich in ein BufferedImage?


----------



## Airborne (29. Feb 2012)

Läuft das alles in einem Thread? Dann rechnet die Maschine "zwischendurch". 
Threads könnten helfen das etwas flüssiger zu gestalten: Lesson: Concurrency (The Java™ Tutorials > Essential Classes)

Zudem könntest du der JRE mehr Arbeitsspeicher gönnen, dann tut sie sich leichter mit dem Rumschaufeln der Daten: Increase the available memory


----------



## Marco13 (29. Feb 2012)

Die Zellen mit fillRect zu malen ist der Performance-Killer. Mit einem BufferedImage dürfte das um Größenordnungen schneller sein. (Da kann man, wenn man das letzte rausholen will, auch noch auf setRGB verzichten, oder, wenn's ganz crank sein soll, den Conway direkt auf dem int-Array des BufferedImages laufen lassen...)


----------



## blueJisCrap (29. Feb 2012)

Hm, ich verwenda zwar jetzt ein BufferedImage, schneller ist es aber immernoch nicht, sieht lediglich besser aus. Marco, könntest du mir anhand eines Beispiels erläutern wie du fillRect umgehen willst?

Threads sind in Arbeit.

Vielen Dank für die bisherigen Tips und Hinweise.


----------



## Gast2 (29. Feb 2012)

Du kannst dir per createGraphics() ein Graphics Objekt des BufferedImage geben lassen. Darauf kannst du dann per setRGB die Farbe des Pixels setzen (Ich würde für jede Zelle einen Pixel reservieren, dann sparst du dir fillRect). Wenn setRGB immernoch zu langsam ist kannst du, wie von Marco13 schon gesagt, direkt das int[] Array manipulieren. Aber ich würde erstmal mit setRGB anfangen, das sollte eigentlich schon reichen.


----------



## Marco13 (29. Feb 2012)

setRGB klappt sogar ohne Graphics


----------



## Gast2 (29. Feb 2012)

Oh danke, da hätte ich mal nen Blick in die API werfen sollen


----------



## blueJisCrap (1. Mrz 2012)

Also schön, Threads sind drin, BufferedImage auch. Es läuft zwar jetzt schneller, aber noch nicht so schnell wie ich mir das vorstelle.

Wie stell ich das denn an, dass ich eine zuverlässige anzeige der FPS bekomme? Bei mir zeigt er auch bei einem Feld von 1800x900 ca. 60fps an, nur glauben kann ich das nicht so recht.

Ach, für die die es interessiert oder Verbesserungsvorschläge haben mal der gesamte Code:

Game:

```
import java.awt.event.*;
import java.awt.*;
import javax.swing.*;

public class Game extends JFrame
{
    public static final String prefix = "Beta";
    public static final String edition = "MT";
    public static final String version = "1.5.1";

    public static final boolean RANDOMIZED = false;
    public static final int SCALE = 1;
    public static final int BORDER = 20;
    private Level map;
    private boolean drawn;
    
    private double framerate = 60;
    private int fps;

    private Thread ticker, drawer;

    public Game(int x, int y)
    {
        super("Conway's Game of Life" + " " + edition + " " + prefix + " " + version);
        map = new Level(x, y);
        setSize(x*SCALE + 2*BORDER, y*SCALE + 4*BORDER);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        getContentPane().setBackground(Color.WHITE);
        setLocationRelativeTo(getParent());
        setResizable(false);
        ticker = new Thread()
        {
            private boolean running;

            public void run()
            {
                running = true;
                while(running)
                {
                    tick();
                }
            }

            public void quit()
            {
                running = false;
            }
        };
        drawer = new Thread()
        {
            private boolean running;

            public void run()
            {
                running = true;
                int frames = 0;
                long timeBefore = System.currentTimeMillis();
                long nanosPerTick = (long) (1000000000 / framerate);
                while(running)
                {
                    repaint();
                    frames++;
                    try
                    {
                        sleep(nanosPerTick/1000000, (int) (nanosPerTick%1000000));
                    }
                    catch(InterruptedException e)
                    {
                        e.printStackTrace();
                    }
                    if(System.currentTimeMillis() - timeBefore >= 1000)
                    {
                        timeBefore += 1000;
                        fps = frames;
                        frames = 0;
                    }
                }
            }

            public void quit()
            {
                running = false;
            }
        };
        setVisible(true);
        ticker.start();
        drawer.start();
    }

    public static void main(String[] args)
    {
        new Game(1800, 900);
    }

    public void tick()
    {
        map.tick();
    }

    public void paint(Graphics g)
    {
        g.setColor(Color.GREEN);
        g.fillRect(2*BORDER - 2, 2*BORDER - 12, 120, 14);
        g.setColor(Color.BLACK);
        g.drawString("FPS: " + fps,(int) 2*BORDER,(int) 2*BORDER);
        map.paint(g);
    }
}
```

Level:

```
import java.util.Random;
import java.awt.*;
import java.awt.image.BufferedImage;

public class Level
{
    private boolean[][] map;
    private int width, height;
    private Random rnd;
    private boolean drawn;
    private BufferedImage bImage;
    private boolean built;

    public Level(int x, int y)
    {
        map = new boolean[x][y];
        width = x;
        height = y;
        rnd = new Random();
        if (Game.RANDOMIZED)
        {
            for(int i = 0; i < width; i++)
            {
                for (int j = 0; j < height; j++)
                {
                    map[i][j] = rnd.nextBoolean();
                }
            }
        }
    }

    private int getAmountOfNeighbors(int x, int y)
    {
        int n = 0;
        if ((x < width) && (y < height) && (y >= 0) && (x >= 0))
        {
            for(int i =  x-1; i <= x+1; i++)
            {
                for(int j =  y-1; j <= y+1; j++)
                {
                    if(getState(i, j))
                    {
                        n++;
                    }
                }
            }
        }
        return n;
    }

    private boolean getState(int x, int y)
    {
        if ((x < width) && (y < height) && (y >= 0) && (x >= 0))
        {
            return map[x][y];
        }
        else if (Game.RANDOMIZED)
        {
            return false;
        }
        else
        {
            return true;
        }
    }

    private boolean getNextState(int x, int y)
    {
        if ((x < width) && (y < height) && (y >= 0) && (x >= 0))
        {
            if(getState(x, y))
            {
                switch(getAmountOfNeighbors(x, y) - 1)
                {
                    case 2: case 3: {return true;}
                    default: {return false;}
                }
            }
            else
            {
                if(getAmountOfNeighbors(x, y) == 3)
                {
                    return true;
                }
                return false;
            }
        }
        return false;
    }

    private boolean[][] nextStep()
    {
        boolean[][] mapN = new boolean[width][height];
        for(int i = 0; i < width; i++)
        {
            for (int j = 0; j < height; j++)
            {
                mapN[i][j] = getNextState(i, j);
            }
        }
        return mapN;
    }

    public synchronized void tick()
    {
        while(built)
        {
            try
            {
                wait();
            }
            catch(InterruptedException e)
            {
                e.printStackTrace();
            }
        }
        
        int a = Game.SCALE;
        int b = Game.BORDER;

        bImage = new BufferedImage(a*width, a*height, BufferedImage.TYPE_4BYTE_ABGR); 
        Graphics2D g2 = bImage.createGraphics();

        g2.setColor(Color.RED);
        g2.fillRect(0 , 0, width*a, height*a);
        boolean[][] mapN = nextStep();
        for(int i = 0; i < width; i++)
        {
            for (int j = 0; j < height; j++)
            {
                if(map[i][j] != mapN[i][j])
                {
                    map[i][j] = mapN[i][j];
                }
                if(map[i][j])
                {
                    //g2.setColor(Color.BLACK);
                    //g2.fillRect(i*a, j*a, a, a);
                    
                    for(int k = 0; k < a; k++)
                    {
                        for(int n = 0; n < a; n++)
                        {
                            bImage.setRGB(i*a + k, j*a + n, 0xff000000); //black
                        }
                    }
                    
                }
            }
        }
        built = true;
        notify();
    }
    
    public static void black()
    {
        System.out.println(Integer.toHexString(Color.BLACK.getRGB()));
    }
    
    public synchronized void paint(Graphics g)
    {
        while(!built)
        {
            try
            {
                wait();
            }
            catch(InterruptedException e)
            {
                e.printStackTrace();
            }
        }
        int b = Game.BORDER;
        g.drawImage(bImage, b, 3*b, null);
        built = false;
        notify();
    }
}
```

Ich könnte mir vorstellen, dass die verschachtelten Schleifen noch die Performance beeinflussen.
Auf der anderen Seite weiss ich auch nicht ob es nicht einfach daran liegen könnte, dass es ein wenig dauert bis so ein relativ großes BufferedImage angezeigt wird.


----------



## Marco13 (1. Mrz 2012)

So einiges ist mir nicht klar .... das mit dem "Built" und dem Warten dort...?! 

Sowas wie Skalierung und Rand sollte man vermutlich rausziehen. D.h. die Skalierung sollte dort immer 1 sein, und wenn nötig, kann das Bild größer gezeichnet werden (mit g.drawImage(image,x,y,w,h,null)). Naja, und noch weitere mehr oder weniger wichtige Punkte, aber...
was ist genau die Frage?


----------



## parabool (1. Mrz 2012)

Eigentlich bräuchte man nur die aktiven Zellen in einer Datenstruktur zu halten 
um diese dann zu durchlaufen, statt die ganze Matrix durchzugehen.
Dabei muss man auch jeweils den Status der 8 umgebenden Zellen abfragen.

Könnte zumindest Geschwindigkeitsvorteile bringen, wenn die Population rel. klein ist.

Was mir noch aufgefallen ist:


```
boolean[][] mapN = new boolean[width][height];
```

Du erzeugst bei jedem Durchlauf eine neues Array, was notwendig ist weil die neu berechnete
Population die alte nicht überschreiben darf. Weiss nicht ob das performancerelevant ist aber ich
denke schon. Vielleicht das Array als Instanzvariable ?


----------



## Marco13 (1. Mrz 2012)

Einer der angedeuteten "wichtigen Punkte"  (Wobei das von den Ansprüchen abhängt...)

Man könnte zumindest zwei Arrays erstellen, und immer hin- und her schalten. Wie viel das bringt ist schwer zu sagen...


----------



## blueJisCrap (1. Mrz 2012)

Abgesehen von der Bitte um weitere Verbesserungsvorschläge hatte ich auch nach einer zuverlässigen Möglichkeit zur FPS-Ermittlung gefragt.
EDIT: Bei 1800x900 läuft der Spaß mit herausgezogener Skalierung in der Anfangsphase mit ~16FPS, angezeigt werden 59.

Der Gedanke hinter dem "built" ist relativ simpel: Ich habe 2 Threads, die abwechselnd arbeiten.
Der eine zeichnet das Bild und wartet dann eine gewisse Zeit.Während dieser Wartezeit erstellt ('baut') der andere Thread die nächste Generation.
Und um die untereinander zu synchronisieren hab ich diese Variable built, die angibt ob die nächste Generation schon fertig ist.
Das war in meinen Augen die sinnvollste Umsetzung mehrerer Threads (sollte ich damit falsch liegen korrigiert mich bitte).



			
				parabool hat gesagt.:
			
		

> Eigentlich bräuchte man nur die aktiven Zellen in einer Datenstruktur zu halten
> um diese dann zu durchlaufen, statt die ganze Matrix durchzugehen.
> Dabei muss man auch jeweils den Status der 8 umgebenden Zellen abfragen.


Das wäre auch eine Idee, allerdings könnte es kontraproduktiv sein wenn die Population sehr groß ist, da viele Zellen dann mehrfach abgefragt werden.

Die Skalierung könnte ich momentan höchstens in Level.paint(g) ziehen, werde das aber mal machen (EDIT: schon erledigt).


----------



## Marco13 (1. Mrz 2012)

Hmja, das mit dem built könnte sogar Sinn machen, aber wohl nicht in genau dieser Form: Wenn das Bauen jetzt z.B. SEHR lange dauert, ist (falls ich das richtig überflogen habe) der Event-Dispatch-Thread im "paint" ja blockiert... Je nachdem, was genau man erreichen will, könnte man überlegen, das Zeichnen (der Component) nochmal vom Füllen des Bildes zu entkoppeln. Sonstige Verbesserungsvorschläge... mja, das ist immer so viel, wenn man pedantisch ist  Das GUI sollte mit SwingUtilities.invokeLater im EDT erstellt werden, die "quit"-Methoden der Threads kann man nicht aufrufen, und wenn man es könnte, müßte "running" noch "volatile" sein, und und und...


----------



## parabool (1. Mrz 2012)

> Population sehr groß ist, da viele Zellen dann mehrfach abgefragt werden


Ja, habe ich mir auch schon gedacht.
Habe mal das mit den 2 Arrays (membervariable) die hin und her schalten getestet - bringt kaum mehr Geschwindigkeit.

Ansonsten läuft es eigentlich ziemlich flüssig, finde ich.


----------

