Row-wise vs. column-wise image processing

[Enrique Cruiz]

Hello all,

I am currently implementing a fairly simple algorithm. It scans a
grayscale image, and computes a pixel's new value as a function of its
original value. Two passes are made, first horizontally and second
vertically. The problem I have is that the vertical pass is 3 to 4
times slower than the horizontal, although the code is _exactly_ the
same in both cases?!

The code itself is very simple. There are 2 loops to scan through rows
and colums (horizontal pass), or columns and rows (vertical pass)
depending on the pass. The processing part is simple and is contained
in a single line. 'pixel' is a pointer to the current pixel. The new
value of the current pixel is first updated, and the pointer is then
incremented to the next pixel, which is either in the next column or in
the next row depending on the pass. I should add that the image is
stored as a large 1-D vector, i.e. the values of each rows are
contiguous in memory. Here is a simplified version of the code:

############### #####
// HORIZONTAL
// loop for every row
....
// then for every column
for(col=firstCo l+1 ; col<=lastCol-1 ; ++col)
{
*pixel = (*pixel) * 2 / 3;
pixel++;
}

// VERTICAL
// loop for every column
....
// then for every row
for(row=firstRo w+1 ; row<=lastRow-1 ; ++row)
{
*pixel = (*pixel) * 2 / 3;
pixel+=imgWidth ;
}
############### ###

For this small amount of code, timings are as follow:
- horizontal = 0.035 sec.
- vertical =* *0.135 sec.

Now if we simply remove in each case the line updating the pixel
pointer (i.e. "pixel++;" and "pixel+=imgWidt h;"), the timings then
becomes equal at 0.081. This simple instruction is responsible for the
massive loss of time. And I have no idea why.

My only guess relates to memory management issues. Since the image is
stored row-wise, the current and next values are physically next in
memory during the horizontal pass. On the other hand, for the vertical
pass, the next value is stored in the next row, and the distance
between them becomes 'image_width'. My guess is that the next pixel
value in such a case is not close enough to be stored in the processor
cache or register. The processor has to fetch it from memory, hence the
massive loss in speed. This is however just a guess.

I would really appreciate if anybody could enlighten me on this topic.

Thanks in advance,
Enrique

[christian.bau]

On Jan 25, 11:00 am, Enrique Cruiz <jni6l03mdo6n.. [e-mail]>
wrote:

I am currently implementing a fairly simple algorithm. It scans a
grayscale image, and computes a pixel's new value as a function of its
original value. Two passes are made, first horizontally and second
vertically. The problem I have is that the vertical pass is 3 to 4
times slower than the horizontal, although the code is _exactly_ the
same in both cases?!

RAM is very slow, that is why your computer has cache memory. And
accessing RAM to read a single byte is very very slow compared to
transferring a whole bunch of data, that is why your computer will read
a whole bunch of consecutive bytes from RAM into cache memory when it
has to, typically 32, 64 or 128 byte at a time.

When you process data line by line, those 128 bytes are all used, so
this is very efficient. When you process data in columns, you access
one pixel, but the computer reads 128 bytes from RAM. Then you access
the next pixel, again the computer reads 128 bytes of RAM. I guess you
can see how this is inefficient.

There is also some strange effect that the speed depends on the
distance from one line to another. Run your program with different
values of imgWidth and measure the time, and you will likely see that
your computer doesn't like certain values of imgWidth (it has to do
with cache associativity - google or wikipedia should help). Figure out
which values it doesn't like and avoid them. Nice powers of two are
usually a very bad idea for numWidth.

If you process the same data repeatedly, it is best to do that in
chunks that fit into cache. Usually your computer has two kinds of
cache, L1 cache (very small, maybe 32 KB or less, and very very fast),
and L2 cache (maybe 1 MB or 2 MB if you're lucky, a bit slowish) and
then there is RAM (tons of it, slow as hell). To find out how much
cache your computer has, just measure how long the same operation
takes, depending on the data size. You should have a considerable drop
in speed at two points, so don't exceed that size.