Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am just watching this tutorial https://www.youtube.com/watch?v=HwUnMy_pR6A and the guy (who seems to be pretty competent) is using a single array to store and access the pixels of his to-be-rendered image.

I was wondering if this really is the best way to do this. The alternative of Multi-Array does have one pointer more, but Arrays do have an O(1) for accessing each index and calculating the index in a single array seems to take one addition and one multiplication operation per pixel.

And if Multi-Arrays really are bad, can't you use something with Hashing to avoid those addition and multiplication operations?

EDIT: here is his 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;
        }
    }
}
}
share|improve this question
    
Read the answer to this question, it may help. stackoverflow.com/questions/7051100/2d-array-vs-1d-array –  Savlon May 26 at 12:48

2 Answers 2

up vote 8 down vote accepted

Talking about the "best choice" is always difficult, as long as you did not specify the task that you intend to perform in all detail.

But here are several aspects to consider. First of all: Java is not C. The memory management is completely different, so one has to be very careful when trying to apply insights from one programming environment to another.

For example, your statement:

The alternative of Multi-Array does have one pointer more, but Arrays do have an O(1) for accessing each index and calculating the index in a single array seems to take one addition and one multiplication operation per pixel.

As already pointed out in one of the linked answers: A "2D array" in C is mainly a syntactical convenience for addressing a single (1D) memory block. So when you write something like

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

in C, then this might actually be eqivalent to

array[x+columns*y] = 123;

So the argument of saving a multiplication is at least questionable here. A special case here is when you actually have an array of pointers, where each row is allocated manually with malloc. Then, the addressing scheme is different (and in fact, this may be considered as being closer to what Java does).

Additionally, Java is a language with a Just-In-Time-compiler, which makes comparisons at the level of single instructions (like multiplications) very difficult. You hardly ever know what the JIT does with your code. But in any case, you can assume that it will make it faster, and use the nastiest tricks that you can (not) imagine to do so.


Concerning the general strategy to use a 1D array for pixels, there is one reason to do this in Java (and from quickly skimming over the linked video, this reason seems to apply here) : A 1D array can conveniently be transferred into a BufferedImage.

This is one reason from a pure "convenience" point of view. But when talking about performance, there are other aspects that are far more important than a few multiplications. The first ones that come to my mind are

  • Cache effects
  • Implementation details

Two examples showing how they may affect performance:

Cache effects

For the first one, you might consider the following example: It demonstrates the significant difference in performance between accessing pixels with

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

and with

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

Summarized in a small test program:

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;
    }
}

The details will vary, and heavily depend on the target system (and its cache size), so this is NOT a "benchmark", but shows that there may be a large difference. On my system, an order of magnitude, eg.

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

The second influence may be even more tricky:

Implementation details

The Java BufferedImage class is very convenient, and operations using this class can be blazingly fast.

The first condition for this is that the type of the image must be "appropriate" for the target system. In particular, I have never encountered a system where the BuferedImage types that are backed by int[] arrays have not been the fastest. That means that you should always make sure to use images of the type TYPE_INT_ARGB or TYPE_INT_RGB.

The second condition is more subtle. The engineers at Sun/Oracle employed some nasty tricks to make painting of BufferedImages as fast as possible. One of these optimizations is that they detect whether the image can be held in VRAM completely, or whether they have to sync the image with the contents of an array that resides in the Java world. An image that can be held in VRAM is called a "managed" image. And there are some operations that destroy the "managedness" of an image. One of these operations is obtaining the DataBuffer from the Raster of the image.

Again, a program where I tried to demonstrate the effect. It creates two BufferedImage instances. On one of them, it obtains the DataBuffer, and on the other one, it doesn't. Note that this is also NOT a "benchmark", and should be taken with a huge grain of salt. But it shows that obtaining the DataBuffer from an image can significantly reduce painting performance.

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);
    }

}

The actual impacts will here probably be even more dependent on the hardware (and the VM version!), but on my system, it prints

Managed      0,05151ms
Unanaged     6,27663ms

which means that obtaining the DataBuffer from a BufferedImage may slow down the painting by a factor of more than 100.

(An aside: In order to avoid this slowdown, one can use the setRGB method, like in

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

but of course, this involves some copying. So in the end, there is a trade-off between the speed of manipulating the pixels and the speed of painting the image)

share|improve this answer

In my experience with Java arrays, I saw significant speed improvements by using a 1D array. Your results may vary, so it's important you do some testing of your own.

Consider that your primary use of this array is going to be essentially in the same way the data will be stored in RAM. This makes the memory allocation of a 1D array more beneficial. A multi-dimensional array is also going to require indexing calculations as well, they're just done behind the scenes.

With the correct level of abstraction, you can easily swap between the two methods and do some performance tests of your own.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.