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