Solved

# initialize dynamic integer array

Posted on 1998-12-01
207 Views
Last Modified: 2011-09-20
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
0
Question by:marvinm
• 4
• 2
• 2
• +4
12 Comments

LVL 1

Author Comment

Edited text of question
0

LVL 2

Expert Comment

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

LVL 1

Author Comment

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

LVL 16

Expert Comment

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

LVL 1

Author Comment

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

LVL 27

Expert Comment

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

LVL 12

Accepted Solution

rwilson032697 earned 100 total points
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

LVL 11

Expert Comment

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]
add     eax, 4
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
add     edi, 84
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

LVL 84

Expert Comment

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

LVL 12

Expert Comment

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

LVL 1

Author Comment

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

LVL 11

Expert Comment

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

## Join & Write a Comment Already a member? Login.

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

#### 771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

#### Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!