Zeroing out a dynamicaly allocated bi-dimensional array

[jamessan]

I'm looking for a bi-dimensional equivalent ofint *A=new int[10](0);I realize that I could easily run through a nested for loop and actually assign zero to each cell, but that would add a section of code to my program that is O(n) (because the matrix is 2 by n+1) instead of O(1). This is for a program I'm writing for my Optimization Methods class. Thanks in advance for any help.

[sedarious]

Well, whether you zero it or have C++ zero the array, it's still going to take O(n). Even in the case of int *A=new int[10](0);, you are still doing O(n) once its in executable form. The C/C++ code may not elude to this, but in the end something has to go through unit by unit and zero memory. I would start looking for the fastest way of doing this. The only time you can get 0(1) is when its a staticly generated array (and that is still sketchy).

[bwkaz]

int *A=new int[10](0);

Now, I'm not sure, but I would hazard a guess that this is O(n) as well, regardless of what it looks like. The only way it could possibly be anything different is if the compiler knew your initializer (which it does if this is a static array -- it's zero automatically -- but not otherwise, since it has to zero the stack out) and the state of memory that comes back from the brk() syscall, so that it can do the initialization at compile time rather than run time.

If you're initializing O(n) things that are on the stack, at runtime, the cost will be O(n) time (assuming one processor, of course). There's no way to do it other than visit each item and initialize it. If you look at the assembly output for that initialization, $10 says it's the equivalent of a for loop.

Edit: sedarious beat me, it seems.

[jamessan]

One of the benefits of Big-Oh notation is that it can hide the actual time it takes to do certain things. In this case, int *A=new int[10](0); is considered to be a native initializer which takes constant time. Hence why I would like to know if there is a why to do the same thing with a bi-dimensional array. I'd also like to know just for the sake of knowing whether or not it can be done.

[sedarious]

question...

are you going to be doing

int *a=new int[10][10];

or

int *a=new int[var1][var2];

in the first case, you can just specify as a single dimensional array of 100 and address as a[x*10+y] which will come out to almost exactly the same code. In the second case, of a dynamic array, there is no possible way to do a 0(1) initilization regardless of whether its 1 dimension or multidimension. This is hardware limitation not a software limitation.

note: sorry if I am jumping between [H] and here. I am having problems posting to [H] right now.

[jamessan]

It'll be

int *a=new int[2][n+1];

Forget I mentioned the whole Big-Oh thing. I just wanna know if it's possible to have a one liner to zero this array.

[sedarious]

try

int (*a)[2] = new int [var2][2] (0);


I found out that

int *a=new int[10][10];

should actually be declared as

int (*a)[10]=new int[10][10];

so MAYBE you can do initialization the way mentioned...

[stuka]

Well, there's always memset() or bzero(), which are one-function memory erasers/setters. My guess is that on an x86 architecture, you get a bit better than O(n) performance, due to the string instructions on the chip.

[sedarious]

Originally posted by Stuka
Well, there's always memset() or bzero(), which are one-function memory erasers/setters. My guess is that on an x86 architecture, you get a bit better than O(n) performance, due to the string instructions on the chip.

what x86 instuctions do these translate to because I didn't know they existed. The best thing i know of is mov/stoX

[bwkaz]

"rep stosd" (store some reg. that I don't remember (eax?) to the dword at es:edi, inc edi, dec ecx, and repeat until ecx == 0) is the last one I remember seeing, though that was back when the 386 was new. There's probably a stosq instruction for quad-words now, though. Well, maybe, I don't know.

Although you aren't going to get an order of magnitude difference using these -- the improvement will still be "hidden" by the big-Oh notation.

And sorry to bring this back up, but I'm not sure what you mean:

int *A=new int[10](0); is considered to be a native initializer which takes constant time.

Considered by whom? Because the amount of time it takes will be proportional to n, the size of the array (which is 10 here), not constant. O(n) means time is directly proportional to size. O(1) means no matter how big the size gets, it takes the same amount of time to do whatever you're doing.

[stuka]

The ones I'm thinking of are the stosb/stosw instructions. memset() would basically bemov al, val
cld
mov cx, size
mov es, seg ptr
mov di, offset ptr
rep stosb
Which, since the stosb instruction is a bit quicker than repetitive mov's, should be a bit quicker than what would be a "true" O(n), but, in reality, it realy IS O(n) at the lowest level.

[sedarious]

int *A=new int[10](0);

could be considered equivalent to

a dd 0,0,0,0,0,0,0,0,0,0

in NASM which doesn't require any clocks since it is built into the code and therefore added to memory by the loader. This assumes that the compiler will optimize for a static array which it very well may not since its using the new operator. something like

int a[]={0,0,0,0,0,0,0,0,0,0}

would most likely be a better canidate for this. In regards to the stosb (via memset or whatever). This will not really be any faster than a for loop since compilers are damn good at optimizing them. In my mind this is what should happen...


for(i=10;!i;i--) {a[i]=0; }

should goto

mov eax, 0
mov ecx, 10
les di,a
repnz stosd


But I am not a compiler. This also assumes that you use 4byte ints. I just realized when doing this that the above code would lend itself better to assembly since it converges to zero instead of N. Meh.

[jamessan]

memset() doesn't seem to be working the way I'm using it. Can someone see what I'm doing wrong?int (*a)[10]=new int[4][10];
memset(a,'0',40);When I do this, every cell is zero except a[4][1], a[4][2], and a[4][3]. That's probably coincidence, but I thought it might help.

[stuka]

Well, yeah, if the compiler's smart, you're right - but shouldn't your repnz be just a rep, since ecx holds the rep count?

[stuka]

The problem is that memset is expecting a byte count , and an integer byte value. Your call should be:memset(a, 0, 40 * sizeof(int))In fact, if ANY of the first 10 int-sized cells were 0, I'd be surprised.

[jamessan]

Thanks for all the help. Here's the final function that I was working on, in case anyone is interested:int binomialCoefficient(int n,int k)
{
if (k==0 || k==n)
return 1;

int (*A)[n+1] = new int[2][n+1];
memset(A,0,(2*n+2)*sizeof(int));
int i,j;
A[0][0]=1;
A[1][0]=1;
for(i=0; i<=n; i++)
for(j=1; j<=1; j++)
A[i%2][j] = A[!(i%2)][j-1] + A[!(i%2)][j];

delete [] A;
return A[!(i%2)][k];
}I realized earlier today, after I had slept some, that zeroing out the array would not add to the time complexity since the actual calculation is already O(n*n), but now I know about memset(). :)

[sedarious]

repnz will decrement cx by 1 until its zero then leave... assuming flags are all set correctly and whatnot.

edit: also, the most efficient method would we to use stosd instead of stosb since stosd will drop 32bit zero's into memory instead of 8 bit ones. I am guessing you are using 16bit ints and since your arrays size is always 2bytes*2*n, you are guarenteed to have a multiple of 4 bytes (32 bits).

[bwkaz]

Why would int's be only 2 bytes? That should only be true on a 16-bit compiler, which are pretty much obsolete these days... aren't they? Or did someone say "turbo c for dos" and I wasn't paying attention?

And, not that it matters, but just plain rep will repeat until ecx is zero. repnz will repeat until either ecx is zero, or the zero flag gets set by whatever instruction is getting repeated. ;)

There should be no difference if the instruction is just stos[qdwb], because AFAIK those can't set the zero flag. You would, however, have to make sure zero was clear before you started. I also believe movs[qdwb] can set the zero flag (which makes for an easy way to copy a null-terminated string), but I could be wrong on that.

[stuka]

sedarious: you're right about efficiency, but I went with bytes, since memset is byte-oriented, and it's already compiled - though it may have built-in optimizations based on the size of the memory block.

[sedarious]

good point on the repnz/rep. I just started asm again about 2 weeks ago - still a little fuzzy.

[stuka]

/me cheated and looked at his ref. book :D
bwkaz: you're right on there - in fact I remember (was it on this board many moons ago, or another one?) a discussion where someone posted the assembly code for strcpy and memcpy, and the difference was in the rep instruction.

[sedarious]

The size of variables depends on your compiler. In Studio 6.0, ints are 2 bytes and longs are 4 bytes (if I remember correctly).

[bwkaz]

Originally posted by sedarious
The size of variables depends on your compiler. In Studio 6.0, ints are 2 bytes and longs are 4 bytes (if I remember correctly).

Seriously?!

I'm sure that VC++ is a 32-bit compiler... maybe I should take a look at my installation at work a second... hmm...

Ah, here we go. From C:\Program Files\Microsoft Visual Studio\vc98\Include\limits.h:

#define INT_MIN (-2147483647 - 1) /* minimum (signed) int value */
#define INT_MAX 2147483647 /* maximum (signed) int value */
#define UINT_MAX 0xffffffff /* maximum unsigned int value */
#define LONG_MIN (-2147483647L - 1) /* minimum (signed) long value */
#define LONG_MAX 2147483647L /* maximum (signed) long value */
#define ULONG_MAX 0xffffffffUL /* maximum unsigned long value */ Seems that ints are 32 bits to me... ;)

[sedarious]

Just pulled this from google.

The 'int' data type is defined to be at least 2 bytes, and generally the unit of addressing on the machine, the most common representation for these are 4 bytes...

It goes on to say that ints are generally used internally for addressing and therefore tend to be the same bit size as cpu. It would seem as though I remembered incorrectly on Studio 6 (maybe i was thinking 4.0 - which is where I learned C++). Unfortunatly, the only guarentee you have is that ints are, at minimum, 2 bytes.

[bwkaz]

Right. 2 bytes is the minimum, but you can inspect UINT_MAX in limits.h to find the actual length.

Or, you could do like Unix/Linux configure scripts do, and just compile a dummy program that prints out sizeof(unsigned int). Then you grab what you need to know from the output of that.