Java Single Array beste Wahl für den Zugriff auf Pixel zur Manipulation?

Ich schaue mir gerade dieses Tutorial an https://www.youtube.com/watch?v=HwUnMy_pR6A und der Typ (der ziemlich kompetent zu sein scheint) verwendet ein einzelnes Array, um die Pixel seines zu rendernden zu speichern und darauf zuzugreifen Bild.

Ich habe mich gefragt, ob dies wirklich der beste Weg ist, dies zu tun. Die Alternative von Multi-Array hat zwar einen Zeiger mehr, aber Arrays haben ein O (1) für den Zugriff auf jeden Index und die Berechnung des Index in einem einzelnen Array scheint eine Addition und eine Multiplikationsoperation pro Pixel zu erfordern.

Und wenn Multi-Arrays wirklich schlecht sind, können Sie mit Hashing nicht etwas verwenden, um diese Additions- und Multiplikationsoperationen zu vermeiden?

EDIT: hier ist sein Code ...

public class Screen {
private int width, height;
public int[] pixels;

public Screen(int width, int height) {
    this.width = width;
    this.height = height;

    // creating array the size of one index/int for every pixel
    // single array has better performance than multi-array
    pixels = new int[width * height];
}

public void render() {
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            pixels[x + y * width] = 0xff00ff;
        }
    }
}
}

Es ist immer schwierig, über die "beste Wahl" zu sprechen, solange Sie die Aufgabe , die Sie ausführen möchten, nicht im Detail angegeben haben.

Hier sind jedoch einige Aspekte zu berücksichtigen. Zuallererst: Java ist nicht C. Die Speicherverwaltung ist völlig anders, daher muss man sehr vorsichtig sein, wenn man versucht, Erkenntnisse aus einer Programmierumgebung auf eine andere anzuwenden.

Zum Beispiel Ihre Aussage:

Die Alternative von Multi-Array hat zwar einen Zeiger mehr, aber Arrays haben ein O (1) für den Zugriff auf jeden Index und die Berechnung des Index in einem einzelnen Array scheint eine Addition und eine Multiplikationsoperation pro Pixel zu erfordern.

Wie bereits in einer der verknüpften Antworten ausgeführt: Ein "2D-Array" in C ist hauptsächlich eine syntaktische Annehmlichkeit für die Adressierung eines einzelnen (1D) Speicherblocks. Also wenn du so etwas schreibst

array[y][x] = 123; // y comes first because y corresponds to rows and x to columns

in C könnte dies tatsächlich äquivalent zu sein

array[x+columns*y] = 123;

Das Argument, eine Multiplikation zu speichern, ist hier also zumindest fraglich. Ein Sonderfall ist hier, wenn Sie tatsächlich ein Array von Zeigern haben , denen jede Zeile manuell zugewiesen wird malloc. Dann ist das Adressierungsschema anders (und tatsächlich kann dies als näher an dem angesehen werden, was Java tut).

Darüber hinaus ist Java eine Sprache mit einem Just-In-Time-Compiler, was Vergleiche auf der Ebene einzelner Anweisungen (wie Multiplikationen) sehr schwierig macht. Sie wissen kaum, was die JIT mit Ihrem Code macht. Aber auf jeden Fall können Sie davon ausgehen, dass es schneller wird, und die schlimmsten Tricks anwenden, die Sie sich (nicht) vorstellen können.

In Bezug auf die allgemeine Strategie, ein 1D-Array für Pixel zu verwenden, gibt es einen Grund, dies in Java zu tun (und da das verknüpfte Video schnell überflogen wird, scheint dieser Grund hier zuzutreffen): Ein 1D-Array kann bequem in ein übertragen werden BufferedImage.

Dies ist ein Grund aus der Sicht der "Bequemlichkeit". Aber wenn es um Leistung geht , gibt es andere Aspekte, die weitaus wichtiger sind als ein paar Multiplikationen. Die ersten, die mir in den Sinn kommen, sind

• Cache-Effekte
• Implementierungsdetails

Zwei Beispiele zeigen, wie sie die Leistung beeinflussen können:

Cache-Effekte

Für das erste Beispiel können Sie das folgende Beispiel betrachten: Es zeigt den signifikanten Leistungsunterschied zwischen dem Zugriff auf Pixel mit

for (int x = 0; x < width; x++) {
    for (int y = 0; y < height; y++) {
        pixels[x + y * width] = ...
    }
}

und mit

for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
        pixels[x + y * width] = ...
    }
}

In einem kleinen Testprogramm zusammengefasst:

public class PixelTestButNoBenchmark
{
    public static void main(String[] args)
    {
        long before = 0;
        long after = 0;
        double readTime = 0;
        double writeTime = 0;

        for (int size = 1000; size<=10000; size+=1000)
        {
            Screen s0 = new Screen(size, size);

            before = System.nanoTime();
            s0.writeRowMajor(size);
            after = System.nanoTime();
            writeTime = (after-before)/1e6;

            before = System.nanoTime();
            int r0 = s0.readRowMajor();
            after = System.nanoTime();
            readTime = (after-before)/1e6;

            System.out.printf(
                "Size %6d Row    major " +
                "write: %8.2f " +
                "read: %8.2f " +
                "result %d\n", size, writeTime, readTime, r0);

            Screen s1 = new Screen(size, size);

            before = System.nanoTime();
            s1.writeColumnMajor(size);
            after = System.nanoTime();
            writeTime = (after-before)/1e6;

            before = System.nanoTime();
            int r1 = s1.readColumnMajor();
            after = System.nanoTime();
            readTime = (after-before)/1e6;

            System.out.printf(
                "Size %6d Column major " +
                "write: %8.2f " +
                "read: %8.2f " +
                "result %d\n", size, writeTime, readTime, r1);

        }
    }
}

class Screen
{
    private int width, height;
    public int[] pixels;

    public Screen(int width, int height)
    {
        this.width = width;
        this.height = height;
        pixels = new int[width * height];
    }

    public void writeRowMajor(int value)
    {
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                pixels[x + y * width] = value;
            }
        }
    }

    public void writeColumnMajor(int value)
    {
        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                pixels[x + y * width] = value;
            }
        }
    }

    public int readRowMajor()
    {
        int result = 0;
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                result += pixels[x + y * width];
            }
        }
        return result;
    }

    public int readColumnMajor()
    {
        int result = 0;
        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                result += pixels[x + y * width];
            }
        }
        return result;
    }
}

Die Details variieren und hängen stark vom Zielsystem (und seiner Cache-Größe) ab. Dies ist also KEIN "Benchmark", zeigt jedoch, dass es möglicherweise einen großen Unterschied gibt. Auf meinem System kann eine Größenordnung, z.

Size   7000 Row    major write:    46,73 read:    28,09 result -597383680
Size   7000 Column major write:   528,46 read:   500,53 result -597383680

Der zweite Einfluss kann noch schwieriger sein:

Implementierungsdetails

Die Java- BufferedImageKlasse ist sehr praktisch, und Operationen mit dieser Klasse können unglaublich schnell sein.

Die erste Bedingung hierfür ist, dass der Bildtyp für das Zielsystem "geeignet" sein muss. Insbesondere bin ich noch nie auf ein System gestoßen, bei dem BuferedImagedie von int[]Arrays unterstützten Typen nicht die schnellsten waren. Das bedeutet, dass Sie immer sicherstellen sollten, dass Sie Bilder des Typs TYPE_INT_ARGBoder verwenden TYPE_INT_RGB.

Die zweite Bedingung ist subtiler. Die Ingenieure von Sun / Oracle setzten einige böse Tricks ein, um das Malen BufferedImagesso schnell wie möglich zu gestalten. Eine dieser Optimierungen besteht darin, dass sie erkennen, ob das Image vollständig im VRAM gespeichert werden kann oder ob sie das Image mit dem Inhalt eines Arrays synchronisieren müssen, das sich in der Java-Welt befindet. Ein Bild, das im VRAM gespeichert werden kann, wird als "verwaltetes" Bild bezeichnet. Und es gibt einige Operationen, die die "Verwaltbarkeit" eines Bildes zerstören . Eine dieser Operationen besteht darin, das DataBufferaus Rasterdem Bild zu erhalten.

Wieder ein Programm, in dem ich versucht habe, den Effekt zu demonstrieren. Es werden zwei BufferedImageInstanzen erstellt. Bei einem von ihnen erhält es das DataBufferund bei dem anderen nicht. Beachten Sie, dass dies auch KEIN "Benchmark" ist und mit einem großen Salzkorn eingenommen werden sollte . Es zeigt sich jedoch, dass das Erhalten des DataBufferBilds die Malleistung erheblich verringern kann.

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.awt.image.DataBuffer;
import java.awt.image.DataBufferInt;
import java.beans.Transient;
import java.util.Random;

import javax.swing.JComponent;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;


public class ImagePaintingTestButNoBenchmark
{
    public static void main(String[] args)
    {
        SwingUtilities.invokeLater(new Runnable()
        {
            @Override
            public void run()
            {
                createAndShowGUI();
            }
        });
    }

    private static void createAndShowGUI()
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        int size = 1200;
        BufferedImage managedBufferedImage = createImage(size);
        BufferedImage unmanagedBufferedImage = createImage(size);
        makeUnmanaged(unmanagedBufferedImage);

        final ImagePaintingPanel p = new ImagePaintingPanel(
            managedBufferedImage, unmanagedBufferedImage);
        f.add(p);

        startRepaintingThread(p);

        f.pack();
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }

    private static void startRepaintingThread(final JComponent c)
    {
        Thread t = new Thread(new Runnable()
        {
            @Override
            public void run()
            {
                while (true)
                {
                    c.repaint();
                    try
                    {
                        Thread.sleep(50);
                    }
                    catch (InterruptedException e)
                    {
                        Thread.currentThread().interrupt();
                    }
                }
            }
        });
        t.setDaemon(true);
        t.start();
    }

    private static BufferedImage createImage(int size)
    {
        BufferedImage bufferedImage = 
            new BufferedImage(size, size, BufferedImage.TYPE_INT_ARGB);
        Graphics2D g = bufferedImage.createGraphics();
        Random r = new Random(0);
        for (int i=0; i<size; i++)
        {
            int x = r.nextInt(size);
            int y = r.nextInt(size);
            int w = r.nextInt(size);
            int h = r.nextInt(size);
            int c0 = r.nextInt(256);
            int c1 = r.nextInt(256);
            int c2 = r.nextInt(256);
            g.setColor(new Color(c0,c1,c2));
            g.fillRect(x, y, w, h);
        }
        g.dispose();
        return bufferedImage;
    }

    private static void makeUnmanaged(BufferedImage bufferedImage)
    {
        DataBuffer dataBuffer = bufferedImage.getRaster().getDataBuffer();
        DataBufferInt dataBufferInt = (DataBufferInt)dataBuffer;
        int data[] = dataBufferInt.getData();
        System.out.println("Unmanaged "+data[0]);
    }

}


class ImagePaintingPanel extends JPanel
{
    private final BufferedImage managedBufferedImage;
    private final BufferedImage unmanagedBufferedImage;

    ImagePaintingPanel(
        BufferedImage managedBufferedImage,
        BufferedImage unmanagedBufferedImage)
    {
        this.managedBufferedImage = managedBufferedImage;
        this.unmanagedBufferedImage = unmanagedBufferedImage;
    }

    @Override
    @Transient
    public Dimension getPreferredSize()
    {
        return new Dimension(
            managedBufferedImage.getWidth()+
            unmanagedBufferedImage.getWidth(),
            Math.max(
                managedBufferedImage.getHeight(), 
                unmanagedBufferedImage.getHeight()));
    }

    @Override
    protected void paintComponent(Graphics g)
    {
        super.paintComponent(g);

        long before = 0;
        long after = 0;

        before = System.nanoTime();
        g.drawImage(managedBufferedImage, 0, 0, null);
        after = System.nanoTime();
        double managedDuration = (after-before)/1e6;

        before = System.nanoTime();
        g.drawImage(unmanagedBufferedImage, 
            managedBufferedImage.getWidth(), 0, null);
        after = System.nanoTime();
        double unmanagedDuration = (after-before)/1e6;

        System.out.printf("Managed   %10.5fms\n", managedDuration);
        System.out.printf("Unanaged  %10.5fms\n", unmanagedDuration);
    }

}

Die tatsächlichen Auswirkungen werden hier wahrscheinlich noch stärker von der Hardware (und der VM-Version!) Abhängen, aber von meinem System wird gedruckt

Managed      0,05151ms
Unanaged     6,27663ms

Dies bedeutet, dass das Erhalten des DataBuffervon a BufferedImagedas Bild um einen Faktor von mehr als 100 verlangsamen kann .

(Nebenbei: Um diese Verlangsamung zu vermeiden, kann man die setRGBMethode wie in verwenden

image.setRGB(0, 0, w, h, pixels, 0, w);

Dazu gehört natürlich auch das Kopieren. Am Ende gibt es also einen Kompromiss zwischen der Geschwindigkeit der Manipulation der Pixel und der Geschwindigkeit des Malens des Bildes.

In meiner Erfahrung mit Java-Arrays habe ich durch die Verwendung eines 1D-Arrays erhebliche Geschwindigkeitsverbesserungen festgestellt. Ihre Ergebnisse können variieren, daher ist es wichtig, dass Sie selbst Tests durchführen.

Bedenken Sie, dass Ihre primäre Verwendung dieses Arrays im Wesentlichen auf die gleiche Weise erfolgt, wie die Daten im RAM gespeichert werden. Dies macht die Speicherzuordnung eines 1D-Arrays vorteilhafter. Für ein mehrdimensionales Array sind ebenfalls Indexierungsberechnungen erforderlich. Sie werden nur hinter den Kulissen durchgeführt.

Mit der richtigen Abstraktionsebene können Sie problemlos zwischen den beiden Methoden wechseln und einige eigene Leistungstests durchführen.