Alex Rivera | Logout

How to rewrite array from row-order to column-order?

Asked 2010-01-30T13:58:43.930
9

I have this double for-loop, where I have both row-order and column-order array indexing, which should be bad for performance.

  for (int row = 0; row < height; row++) {
    for (int col = 0; col < width; col++) {

      /* Column-major order */
      d = array_a[col*height +row];

      if (d < 0) { d = 0; }

      /* Row-major order */
      /* Map from x=0,y=0 at buttom left corner to
         0,0 at top left corner */
      array_b[width*(height-1 -row) + col] = d;

    }
  }

Is there an approach/method on how to rewrite from one to the other?

When I try to rewrite the last to column-order, the data becomes skewed. Can't it be rewritten?

Sandra

c++ c
Edit
Report

1 Answer

5

This is never going to be very fast as you'll probably have a number of cache misses, you'll either have to step to the one matrix with a large pitch or the other, there's no escaping that. The problem here is that a computer likes successive memory accesses to be close together, which in your algorithm is not the case the indexing of array_a skips by height elements at a time due to the col*height term. To fix that you could switch around the for loops, but then you'd have the same problem with the width*(height-1 -row) term in array_b.

You could rewrite one of the arrays to match the ordering of the other, but then you would have the exact same problem in the code which does the rewrite, so it depends on whether you need to do this kind of thing more than once on the same data, if you do, then it makes sense to first rewrite one of the matrices like Poita_ described, otherwise you'd best leave the algorithm as is.

answered 2010-01-30T14:39:49.233

Your Answer