Which 2D array of 2D array addressing method?
Author |
Message |
F. H #1 / 4
|
 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 |
|
 |
Barry Schwar #2 / 4
|
 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. 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. 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 |
|
 |
Eric G. Mille #3 / 4
|
 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 |
|
 |
F. H #4 / 4
|
 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 |
|
|
|