In-memory pixel data layout?
I am writing a C ++ library for a PNG based image format. One stop for me is that I am not sure how I should lay out the pixel data in memory; as far as I know there are two practical approaches:
- Array of size (width * height); each pixel can be accessed by the array [y * width + x].
- An array of size (height) containing pointers to arrays of size (width).
The standard reference implementation for PNG (libpng) uses method 2 above, while I've seen others use method 1. Is it better than the other, or each has its own pros and cons, where should there be a tradeoff? Also, what format do most graphics display systems use (perhaps to make it easier to use my library's output in other APIs)?
a source to share
Off the top of my head:
- One thing that will make me pick # 2 is the fact that your memory requirements are a little relaxed. If you need to go to # 1, the system will have to allocate an
height * width
amount of contiguous memory. Whereas, in case # 2, it has the right to allocate smaller chunks of contiguous memory in sizewidth
(can also beheight
) free areas. (When you factor in channels per pixel, # 1 can fail even for moderately sized images.) - Also, it might be slightly better at replacing rows (or columns) if needed for image manipulation purposes (enough pointers).
- The downside to # 2 is, of course, the extra level of indirection that leaks out for every access and array of pointers to be stored. But this is unlikely to be a question of today's processor and memory speed.
- The second drawback for # 2 is that the data is not necessarily next to each other, making it difficult for the processor to load the desired pages of memory into the cache.
a source to share
The advantage of method 2 (slicing the array in strings) is that you can perform memory operations in stages, for example. resizing or moving an image without reallocating the entire piece of memory at once. For really large images, this can be an advantage.
The advantage of a single array is that you do the calculations easier, i.e. go down one line
pos += width;
instead of pointer references. For small to medium sized images, this is probably faster. Unless you are dealing with images of hundreds of megabytes, I would go with method 1.
a source to share
I suspect libpng does this (style 2) for several reasons:
- Avoid large allocations (as mentioned) and can make it easier to handle VERY large PNGs, especially on non-VM systems
- (possibly) allow interleaving ala decoding with interleaving JPEG (if PNG supports it)
- Ease of some transformations (vertical click) (unlikely)
- Ease of scaling (insert or delete lines without having to fill a second buffer or expand / narrow lines) (unlikely, but possible)
The problem with this approach (assuming each row is an allocation) is a LOT more allocation / free overhead and possibly encourages memory fragmentation.
Unless you have a good reason, use style 1 (single emphasis) and perhaps round up to a "good" boundary for the architecture being used (maybe 4, 8, 16, or maybe even more bytes). Note that many library functions can look for style 1 without padding - think about how you will use this and where you will pass them.
a source to share