Layout of Pixel-data in Memory?

Question

I'm writing a C++ library for an image format that is based on PNG. One stopping point for me is that I'm unsure as to how I ought to lay out the pixel data in memory; as far as I'm aware, there are two practical approaches:

1. An array of size (width * height); each pixel can be accessed by array[y*width + x].
2. An array of size (height), containing pointers to arrays of size (width).

The standard reference implementation for PNG (libpng) uses method 2 of the above, while I've seen others use method 1. Is one better than the other, or is each a method with its own pros and cons, to where a compromise must be made? Further, which format do most graphical display systems use (perhaps for ease of using the output of my library into other APIs)?

Answer 1

The advantage of method 2 (cutting up the array in rows) is that you can perform memory operations in steps, e.g. resizing or shuffling the image without reallocating the entire chunk of memory at once. For really large images this may be an advantage.

The advantage of a single array is that you calculations are simpler, i.e. to go one row down you do

pos += width;

instead of having to reference pointers. For small to medium images this is probably faster. Unless you're dealing with images of hundreds of Mb, I would go with method 1.

Answer 2

Off the top of my head:

• The one thing that would make me choose #2 is the fact that your memory requirements are a little relaxed. If you were to go for #1, the system will need to be able to allocate height * width amount of contiguous memory. Whereas, in case of #2, it has the freedom to allocate smaller chunks of contiguous memory of size width (could as well be height) off of areas that are free. (When you factor in the channels per pixel, the #1 may fail for even moderately sized images.)
• Further, it may be slightly better when swapping rows (or columns) if required for image manipulation purposes (pointer swap suffices).
• The downside for #2 is of course an extra level of indirection that seeps in for every access and the array of pointers to be maintained. But this is hardly a matter given todays processor speed and memory.
• The second downside for #2 is that the data isn't necessarily next to each other, which makes it harder for the processor the load the right memory pages into the cache.

Answer 3

Windows itself uses a variation of method 1. Each row of the image is padded to a multiple of 4 bytes, and the order of the colors is B,G,R instead of the more normal R,G,B. Also the first row of the buffer is the bottom row of the image.

Answer 4

I suspect that libpng does that (style 2) for a few possible reasons:

1. Avoid large allocations (as mentioned), and may ease handling VERY large PNGs, especially in systems without VM
2. (perhaps) allow for interleaved decode ala interleaved JPEG (if PNG supports that)
3. Ease of certain transformations (vertical flip) (unlikely)
4. Ease of scaling (insert or remove lines without needing a full second buffer, or widen/narrow lines) (unlikely but possible)

The problem with this approach (assuming each line is an allocation) is a LOT more allocation/free overhead, and perhaps encourage memory fragmentation.

Unless you have a good reason, use style 1 (single allocation), and perhaps round to a "good" boundary for the architecture you're using (could be 4, 8, 16 or perhaps even more bytes). Note that many library functions may look for style 1 with no padding - think about how you'll be using this and where you'll be passing them to.