• C

# initialize dynamic integer array

I have an array declared as
int **int_grid;
it is properly allocated.
I need to set int_grid[x][y1] through int_grid[x][y2] (y2>y1) to some value z.
Is there a quicker way than looping through and setting each to z?
Thanks, mm
LVL 1
###### Who is Participating?

Commented:
Use memcopy to copy blocks of filled in cells:

eg: you have 100 to fill in. Loop through the first 10 setting the value. Then just memcopy (memcpy?) the first block of 10 to the remaining 9 blocks. By playing with how you break it down you can optimise it (eg: set first 10, copy that to next 10, then copy first 20 to next 20 etc, then when the assigned entries are too big to be copied to the remainder just copy the amount you need).

This is as fast as it is going to get.

Cheers,

Raymond.
0

Author Commented:
Edited text of question
0

Commented:
well, using pointer arithmetics is faster than calculating offsets into the array for every value to set.
Calcutate the offset for the first value and increment the pointer until all z were set.

0

Author Commented:
Wouldn't (or shouldn't) the compiler generate the same code for accessing int_grid[x][y2]and **(int_grid+some_offset)?
0

Commented:
You can use memset:

void *memset(void *dest,int c,size_t count);

This function will set count bytes to the value in c. So you would say:

memset(int_grid[x]+y1,z,y2-y1);

0

Author Commented:
memset() sets all the bytes to a specified value. I need each integer (in my case 4 bytes) to equal a value.
0

Commented:
Frankly squeeking, I mean frankly speaking I don't see the necessity of a quick algorithm. The compiler should generate reasonable code for for(int i=y1; i<=y2; i++) int_grid[x][i]=z;
such that only 3 instructions are needed per loop. That is to say any decent compiler.
One trick which we did in the old days was to initialise the first element of the array and then do a memcpy which copied the first element into the second. By setting the number of elements of the memcpy to n-1 we initialised all the elements to the same value irrespective of how big an element was.
But is it really necessary these days?
0

Commented:
memcpy() will probably slow you down due to the overhead of the function call, etc.

Using MSVC4.2 with speed optimizations turned on, this code:

for (i = 21; i <= 81; ++i)
array[41][i] = -1;

Produces the following assembly:

mov     eax, 84
mov     edx, DWORD PTR _array\$[esp+4]
\$L159:
mov     ecx, DWORD PTR [edx+164]
cmp     eax, 324
mov     DWORD PTR [ecx+eax-4], -1
jle     SHORT \$L159

A trivial optimization:

int* p = array[41];
for (i = 21; i <= 81; ++i)
p[i] = -1;

Produces the following:

mov     ecx, 61
mov     eax, DWORD PTR _array\$[esp+4]
mov     edi, DWORD PTR [eax+164]
mov     eax, -1
rep     stosd

Much better.

However, other compilers may perform better optimization.  My suggestion: check with a profiler to see if you REALLY have a bottleneck before manually optimizing code.
0

Commented:
If initialization is a significant part of your total processing time, is it because very few of the elements are actually being used?
If so, it may help to only initialize the elements when they are used
0

Commented:
alexo - you are right, there will be an overhead with the function call. This will mean for small arrays your method will be quicker. Though for large arrays at most only log2n +1 calls will be required (the can be reduced by log2n of the initial number of cells filled in). In these cases it will be significantly faster than looping - even with the hand optimisation you show.

ozo: I agree. Initialisation on demand is a more effective approach with large structures.

Cheers,

Raymond.
0

Author Commented:
My array is not exceptionally large, I was just looking to keep my code somewhat optimized. Initialization is not really my issue. Sections of the array need to be set to different values at different times. Thanks to all for the help.
0

Commented:
Raymond, I seriously doubt that *anything* you can write using memcpy() will be faster than a "rep stosd" (other instructions are just for setting up the loop) for *any* loop size.
No, with just a little help from the programmer the compiler will generate code that is hard to beat without resorting to hand coded assembly.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.