Which 2D array of 2D array addressing method? 
Author Message
 Which 2D array of 2D array addressing method?

Okay, before I write anything else, let me mention that I checked
question 6.16 of the C FAQ and it was very helpful but it didn't
completely address my question.

Let's suppose that at runtime I need to allocate an array---let's
call it raster---of type int. It will have size w * h (we won't
know w and h until runtime), which is initialized by calling a
function I can't modify the source of (it's a library call).

  int *raster = malloc(w * h * sizeof *raster);
  /* ... */
  get_next_raster(raster, w, h);

Suppose that for my application I need to address raster as if it
were a 2D array of 2D blocks, and let's let bw and bh be the block
width and block height. If we knew what w, h, bw, and bh
were at compile time we could declare

  int raster2[h][w][bh][bw];

and then access the k,lth pixel of the i,jth block (using row
major order) like

  raster2[i][j][k][l]

But we still would have to copy raster's data into raster2
because get_next_raster() wouldn't know how to initialize raster2,
and this would waste space and especially time (my application
needs to be really fast).

We could manually get the k,lth pixel of the i,jth block doing a
calculation like

  raster[bh*w*i + bw*j + w*k + l]

but I'm posting here to ask if there is a better way. I should
mention that I'll most likely be processing one block at a time,
e.g. something like

  for (i = 0; i < h/bh; i++)
      for (j = 0; j < w/bw; j++) {
          /* Process i,jth block, probably using further nested
           * for loops to access particular k,lth pixels. */
      }

If I'm doing one block at a time then the

  raster[bh*w*i + bw*j + w*k + l]

approach seems inefficient unless the compiler can arrange to only
do the multiplications and adds when they absolutely have to be
done. (It occured to me that I could calculate bh*w*i in the outer
for loop on i and save the result for the inner loop if the
compiler can't be trusted to do in for me, but all of this seems
like such a pain.)

I should also mention that my program will be doing huge numbers
of rasters, though only one at any given time. They will,
fortunately, always be the same size and the same bw and bh will
always be used once they are known. So I'm also wondering if any
programmer more skillful than myself could comment as to whether
doing something like the following could offer better performance
in the long run.  (It would also allow a nicer syntax to be used.)

We declare r like

  int ****r;

and then we set r to be displaced to the raster so that

  r[i][j][k][l] == raster[bh*w*i + bw*j + w*k + l]

then random accesses only involve following pointers and addition
and no multiplication. (But my block by block accesses aren't
exactly random, so I don't know if I'm gaining or losing speed
with this method.) Additionally, r only needs to be set up once
because when get_next_raster() overwrites raster's contents with
the contents of the next raster, the addresses r has been set up
to point to still work.

From question 6.16 of the C FAQ, there are different ways to set
up such an r, but I'm wondering which would be best for my
application. (Is there an advantage to contiguous allocation?)

If I haven't screwed up, I think below is how to do the
non-contiguous version but I'm not sure as all this
pointer-to-pointer-to-pointer-to-pointer stuff is really
starting to confuse me. Help!

Thank you very much in advance for any advice!

  r = malloc(h/bh * sizeof *r);
  for (i = 0; i < h/bh; i++) {
      r[i] = malloc(w/bw * sizeof *r[i]);
      for (j = 0; j < w/bw; j++) {
          r[i][j] = malloc(bh * sizeof *r[i][j]);
          for (k = 0; k < bh; k++) {
              r[i][j][k] = &raster[bh*w*i + bw*j + w*k];
          }
      }
  }

(There doesn't seem to be an equally concise way to free all those
pointers once finished with them. Argh....)



Tue, 15 Mar 2005 08:12:21 GMT  
 Which 2D array of 2D array addressing method?

Quote:
>Okay, before I write anything else, let me mention that I checked
>question 6.16 of the C FAQ and it was very helpful but it didn't
>completely address my question.

>Let's suppose that at runtime I need to allocate an array---let's
>call it raster---of type int. It will have size w * h (we won't
>know w and h until runtime), which is initialized by calling a
>function I can't modify the source of (it's a library call).

>  int *raster = malloc(w * h * sizeof *raster);
>  /* ... */
>  get_next_raster(raster, w, h);

>Suppose that for my application I need to address raster as if it
>were a 2D array of 2D blocks, and let's let bw and bh be the block
>width and block height. If we knew what w, h, bw, and bh
>were at compile time we could declare

>  int raster2[h][w][bh][bw];

>and then access the k,lth pixel of the i,jth block (using row
>major order) like

>  raster2[i][j][k][l]

>But we still would have to copy raster's data into raster2
>because get_next_raster() wouldn't know how to initialize raster2,
>and this would waste space and especially time (my application
>needs to be really fast).

>We could manually get the k,lth pixel of the i,jth block doing a
>calculation like

>  raster[bh*w*i + bw*j + w*k + l]

Not quite.  Let's put some numbers to the dimensions to make life
easier:  bh=2, bw=3, w=4, and h =5.  From this, we see there are w*h
pixels per block (20 using the sample numbers).  These means that the
first pixel of block 0,1 should be 20 beyond the first pixel of block
0,0.  Look at another way, the expression in brackets should increment
by 20 whenever j increments by 1.  For i, the ratio is 60 to 1 since
there are three blocks per row.

        2*4*0 + 3*0 +4*0 + 0 is 0 but
        2*4*0 + 3*1 +4*0 + 0 is 3 and the increment is not 20.

The correct formula for the pixel k,l of block i,j is
        raster[w*h*(i*bw+j) + (w*k+l)]

Testing as above:

        4*5*(0*3+0) + (4*0+0) is 0 and
        4*5*(0*3+1) + (4*0+0) is 20 (good increment) and
        4*5*(1*3+0) + (4*0+0) is 60 (another good increment)

Notice that bh never appears in the first term for the same reason h
never appears in the second term.  It is not a factor in computing the
offset; it is a limit in how large the computed offset can be.

Quote:

>but I'm posting here to ask if there is a better way. I should
>mention that I'll most likely be processing one block at a time,
>e.g. something like

>  for (i = 0; i < h/bh; i++)
>      for (j = 0; j < w/bw; j++) {

I don't understand the division in the second expressions.  You want
to process all bh*bw blocks and there is no apparent relationship
between the number of blocks and the number of pixels per block.

- Show quoted text -

Quote:
>          /* Process i,jth block, probably using further nested
>       * for loops to access particular k,lth pixels. */
>      }

>If I'm doing one block at a time then the

>  raster[bh*w*i + bw*j + w*k + l]

>approach seems inefficient unless the compiler can arrange to only
>do the multiplications and adds when they absolutely have to be
>done. (It occured to me that I could calculate bh*w*i in the outer
>for loop on i and save the result for the inner loop if the
>compiler can't be trusted to do in for me, but all of this seems
>like such a pain.)

>I should also mention that my program will be doing huge numbers
>of rasters, though only one at any given time. They will,
>fortunately, always be the same size and the same bw and bh will
>always be used once they are known. So I'm also wondering if any
>programmer more skillful than myself could comment as to whether
>doing something like the following could offer better performance
>in the long run.  (It would also allow a nicer syntax to be used.)

>We declare r like

>  int ****r;

If you do this, then you must arrange for r to point to bh int***.
Each of those bh pointers must point to bw int**.  Each of those bh*bw
pointers must point to h int*.  Finally, each of those bh*bw*h
pointers must point to w int.  This does have the benefit of being
done only once and there after you can treat r as if it were an
int[][][][] array.

Quote:

>and then we set r to be displaced to the raster so that

>  r[i][j][k][l] == raster[bh*w*i + bw*j + w*k + l]

>then random accesses only involve following pointers and addition
>and no multiplication. (But my block by block accesses aren't

Chances are the compiler will be able to optimize the subscript
expression better than the computation expression but both involve
multiplication (at least at the conceptual stage).  Many subscript
computations that would be multiplications get replace by shifts which
are usually faster but this is getting a little off topic for clc.

- Show quoted text -

Quote:
>exactly random, so I don't know if I'm gaining or losing speed
>with this method.) Additionally, r only needs to be set up once
>because when get_next_raster() overwrites raster's contents with
>the contents of the next raster, the addresses r has been set up
>to point to still work.

>From question 6.16 of the C FAQ, there are different ways to set
>up such an r, but I'm wondering which would be best for my
>application. (Is there an advantage to contiguous allocation?)

>If I haven't screwed up, I think below is how to do the
>non-contiguous version but I'm not sure as all this
>pointer-to-pointer-to-pointer-to-pointer stuff is really
>starting to confuse me. Help!

>Thank you very much in advance for any advice!

>  r = malloc(h/bh * sizeof *r);
>  for (i = 0; i < h/bh; i++) {
>      r[i] = malloc(w/bw * sizeof *r[i]);
>      for (j = 0; j < w/bw; j++) {
>          r[i][j] = malloc(bh * sizeof *r[i][j]);
>          for (k = 0; k < bh; k++) {
>              r[i][j][k] = &raster[bh*w*i + bw*j + w*k];
>      }
>      }
>  }

>(There doesn't seem to be an equally concise way to free all those
>pointers once finished with them. Argh....)

<<Remove the del for email>>


Tue, 15 Mar 2005 09:56:10 GMT  
 Which 2D array of 2D array addressing method?

Quote:
> Okay, before I write anything else, let me mention that I checked
> question 6.16 of the C FAQ and it was very helpful but it didn't
> completely address my question.

> Let's suppose that at runtime I need to allocate an array---let's
> call it raster---of type int. It will have size w * h (we won't
> know w and h until runtime), which is initialized by calling a
> function I can't modify the source of (it's a library call).

>   int *raster = malloc(w * h * sizeof *raster);
>   /* ... */
>   get_next_raster(raster, w, h);

> Suppose that for my application I need to address raster as if it
> were a 2D array of 2D blocks, and let's let bw and bh be the block
> width and block height. If we knew what w, h, bw, and bh
> were at compile time we could declare

>   int raster2[h][w][bh][bw];

Not quite the same but...

  int blk_size   = bh * bw;
  int total_size = h * w;
  int *raster = malloc (total_size * sizeof *raster);
  get_next_raster (raster, w, h);
  for (i = 0; i < total_size; i += blk_size) {
      for (j = 0; j < blk_size; j += bw) {
         for (k = 0; k < bw; k++) {
            blk_ptr[i+j+k] = i+j+k;
         }
      }
  }
  free (raster);

Anyway, I wouldn't worry about it too much until you're sure there's
a performance problem.  Precomputing your offsets will help; an
optimizing compiler might figure out when to do such, but I wouldn't
guarantee it...



Tue, 15 Mar 2005 11:56:54 GMT  
 Which 2D array of 2D array addressing method?

[...]

Quote:
> >Let's suppose that at runtime I need to allocate an array---let's
> >call it raster---of type int. It will have size w * h (we won't
> >know w and h until runtime), which is initialized by calling a
> >function I can't modify the source of (it's a library call).

> >  int *raster = malloc(w * h * sizeof *raster);
> >  /* ... */
> >  get_next_raster(raster, w, h);

> >Suppose that for my application I need to address raster as if it
> >were a 2D array of 2D blocks, and let's let bw and bh be the block
> >width and block height. If we knew what w, h, bw, and bh
> >were at compile time we could declare

> >  int raster2[h][w][bh][bw];

[...]

Quote:
> >  raster[bh*w*i + bw*j + w*k + l]

> Not quite.

Okay, I fudged on the raster2 declaration. It should be

  int raster2[h/bh][w/bw][bh][bw];

From the proceeding context, I mentioned that the flat raster had
dimensions of w * h. For example, with w=640, h=480, bw=8, and bh=6,
the above declaration makes sense. This explains why the h/bh and w/bw
stuff later on didn't make sense to you.

Quote:
> Let's put some numbers to the dimensions to make life
> easier:  bh=2, bw=3, w=4, and h =5.
> From this, we see there are w*h
> pixels per block (20 using the sample numbers).  These means that the
> first pixel of block 0,1 should be 20 beyond the first pixel of block
> 0,0.  Look at another way, the expression in brackets should increment
> by 20 whenever j increments by 1.  For i, the ratio is 60 to 1 since
> there are three blocks per row.

>    2*4*0 + 3*0 +4*0 + 0 is 0 but
>    2*4*0 + 3*1 +4*0 + 0 is 3 and the increment is not 20.

> The correct formula for the pixel k,l of block i,j is
>    raster[w*h*(i*bw+j) + (w*k+l)]

I'm sorry I screwed up the raster2 declaration.

[Rest of the useful info snipped.]



Tue, 15 Mar 2005 15:19:56 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. 2D array of pointers to 2D arrays

2. address of 2D array elements?

3. scanf() w/ 2D-array address offsets: HELP!

4. use 1d array + macro or 2d array?

5. Multiply and Add matrices with 2d array WITHOUT ARRAY INDEXING

6. How To pass 2D String array to VB from VC++ Using Safe array

7. Fast array transfer with 2D arrays...?

8. Passing a 2d array from .NET to COM

9. Passing 2D arrays to functions with const.

10. passing 2d arrays by reference

11. Text Data File to 2D Array?

12. 2D arrays...

 

 
Powered by phpBB® Forum Software