reinitialization an array

[raghu]

Hello

I am working on a project where code optimization plays a
vital role to get the required performance.
I would like to know is there any possible to reinitializatio n an
array of big size to zero with a single statement.


For example
main()
{
int i =0;
char A[30];
while(condition )
{
//Start
for( i = 0; i < 30; i++)
{
A[i] = 0;
}
//End

for(i = 0; i < 30; i++)
{
printf(" enter a value in the index %d:\n",i);
scanf("%d", &A[i]);
}
/*followed by few other statements*/
} //End of while
}

from the above code I want to remove the for inbetween //start and //
End and replace with a single statement(which should not be a
function) which will assign A contents to zero. Or is there any other
approach that will reduce the time complexity than this.

waiting for reply
Raghu

[akbar]

Re: reinitializatio n an array

On May 30, 11:19 am, raghu <ragavaku...@gm ail.comwrote:

Hello
>
        I am working on a project where code optimization plays a
vital role to get the required performance.
I would like to know is there any possible to reinitializatio n an
array of big size to zero with a single statement.
>
For example
main()
{
        int i =0;
        char A[30];
while(condition )
{
//Start
for( i = 0; i < 30; i++)
{
    A[i] = 0;}
>
//End
>
       for(i = 0; i < 30; i++)
      {
          printf(" enter a value in the index %d:\n",i);
          scanf("%d", &A[i]);
      }
/*followed by few other statements*/
>
} //End of while
}
>
from the above code I want to remove the for inbetween //start  and //
End and replace with a single statement(which should not be a
function) which will assign A contents to zero. Or is there any other
approach that will reduce the time complexity than this.
>
waiting for reply
Raghu

Hello Raghu,

try using memset ..

#include <string.h>
memset(A, 0, sizeof(A));

I hope this should work :)

[Szabolcs Borsanyi]

Re: reinitializatio n an array

On Thu, May 29, 2008 at 11:19:06PM -0700, raghu wrote:

Hello
>
I am working on a project where code optimization plays a
vital role to get the required performance.
I would like to know is there any possible to reinitializatio n an
array of big size to zero with a single statement.

There are (at least) two things you can do.

1) place the array declaration inside of a block (while block in this case)
and give an initialiser.
char A[30]={0};
This will set all the elements to zero (not just the first one), whenever
the path of execution enters the block.

2) since you have a char array, you can do a memset(A,0,size of(A)),
which is just equivalent to your for loop:

for( i = 0; i < 30; i++)
{
A[i] = 0;
}

(If you had non-integer types, this equivalence is no longer guaranteed.)
(If you receive A as a function argument, then watch out with sizeof(A))

Using either of these may or may not improve the performance, but will
simplify the source code. Measure the times and check if zeroing out
an arry is the actual bottleneck or some something else. (Use a profiler,
if you have not already been using one yet.)

Szabolcs

[raghu]

Re: reinitializatio n an array

On May 30, 11:35 am, Szabolcs Borsanyi <s.borsa...@sus sex.ac.uk>
wrote:

On Thu, May 29, 2008 at 11:19:06PM -0700, raghu wrote:

Hello

>

I am working on a project where code optimization plays a
vital role to get the required performance.
I would like to know is there any possible to reinitializatio n an
array of big size to zero with a single statement.

>
There are (at least) two things you can do.
>
1) place the array declaration inside of a block (while block in this case)
and give an initialiser.
char A[30]={0};
This will set all the elements to zero (not just the first one), whenever
the path of execution enters the block.
>
2) since you have a char array, you can do a memset(A,0,size of(A)),
which is just equivalent to your for loop:for( i = 0; i < 30; i++)

{
A[i] = 0;
}

>
(If you had non-integer types, this equivalence is no longer guaranteed.)
(If you receive A as a function argument, then watch out with sizeof(A))
>
Using either of these may or may not improve the performance, but will
simplify the source code. Measure the times and check if zeroing out
an arry is the actual bottleneck or some something else. (Use a profiler,
if you have not already been using one yet.)
>
Szabolcs

But memset is a function which will perform same operation but it will
take some time to execute
like function calling, stack allocation etc. Is there any other
approach with out calling the function.

[Richard Bos]

Re: reinitializatio n an array

raghu <ragavakumar@gm ail.comwrote:

I am working on a project where code optimization plays a
vital role to get the required performance.
I would like to know is there any possible to reinitializatio n an
array of big size to zero with a single statement.
>
For example
main()

_First_ get it right, _then_ get it efficient. That should be

int main(void)

Your version was outdated even in C89.

char A[30];

{
//Start
for( i = 0; i < 30; i++)
{
A[i] = 0;
}
//End

from the above code I want to remove the for inbetween //start and //
End and replace with a single statement(which should not be a
function) which will assign A contents to zero.

For chars, and in most cases[1] for other integers and the value 0, have
a look at memset().

Richard

[1] I believe this has now been fixed, but for a while it was
theoretically possible for all-bits-zero to be a trap value for
integers other than unsigned char. I wouldn't worry about it.

[Szabolcs Borsanyi]

Re: reinitializatio n an array

On Thu, May 29, 2008 at 11:50:33PM -0700, raghu wrote:

On May 30, 11:35 am, Szabolcs Borsanyi <s.borsa...@sus sex.ac.uk>
wrote:

[snip]

2) since you have a char array, you can do a memset(A,0,size of(A)),
which is just equivalent to your for loop:

for( i = 0; i < 30; i++)
{
A[i] = 0;
}

[snip]

Szabolcs

>
But memset is a function which will perform same operation but it will
take some time to execute
like function calling, stack allocation etc. Is there any other
approach with out calling the function.

Is this a prejudice or have you measured your implementation' s performance
on memset.

On the platform I have at hand (linux/x86_64/gcc 4.1 -O) I compiled the
following program:

#include <string.h>
enum { N = 32 };
void dummy(char *);

void a()
{
char a[N]={0};
dummy(a);
}

void b()
{
char b[N];
memset(b,0,size of(b));
dummy(b);
}

void c()
{
char b[N];
int i;
for(i=0;i<N;i++ ) b[i]=0;
dummy(b);
}

The functions a() and b() have been compiled to identical(!) assembly code,
which did not involve any function calls (other than to dummy()), and the
compiler used quadwords for the assignments. It was important that N is
known at compile time. The function c() was compiled to a loop in the
assembly output.

N=32 is likely to be faster than N=30.

How my implementation was managing with this code sniplet is irrelevant,
of course. But it illustrates that the function calls, loops that one
has in mind when programming, are not in one-to-one correspondence with
the machine-code-level function calls and loops. The C standards deliberately
allow the implementations to do 'as if' they did what the programmer meant.

Szabolcs

[Keith Thompson]

Re: reinitializatio n an array

raghu <ragavakumar@gm ail.comwrites:

I am working on a project where code optimization plays a
vital role to get the required performance.
I would like to know is there any possible to reinitializatio n an
array of big size to zero with a single statement.
>
>
For example
main()
{
int i =0;
char A[30];
while(condition )
{
//Start
for( i = 0; i < 30; i++)
{
A[i] = 0;
}
//End
>
for(i = 0; i < 30; i++)
{
printf(" enter a value in the index %d:\n",i);
scanf("%d", &A[i]);
}
/*followed by few other statements*/
} //End of while
}
>
from the above code I want to remove the for inbetween //start and //
End and replace with a single statement(which should not be a
function) which will assign A contents to zero. Or is there any other
approach that will reduce the time complexity than this.

Just use memset().

I know you said you didn't want a function call, but nothing you can
come up with is likely to be faster than calling memset().

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Keith Thompson]

Re: reinitializatio n an array

raghu <ragavakumar@gm ail.comwrites:
[...]

But memset is a function which will perform same operation but it
will take some time to execute like function calling, stack
allocation etc. Is there any other approach with out calling the
function.

*Anything* will take some time to execute.

If your array is large, any overhead from the function call will be
insignificant. If your array is small, the time spent for the entire
operation will probably be insignificant.

For that matter, since memset() is a standard function, the compiler
is permitted to use its knowledge of memset()'s semantics to generate
special-case code to perform the equivalent actions. There might not
even be a function call.

I can think of one possible alternative that doesn't use either an
explicit loop or an explicit function call:

#define ARRAY_LEN 1000
struct s {
int arr[ARRAY_LEN];
};
struct s s_zero = { 0 };
struct s obj;

/* ... code that works with obj.arr ... */

obj = s_zero;

This works because struct assignment is built into the language,
whereas array assignment isn't. (Note: don't try to use pointer casts
to apply this to an array object; the struct assignment will also copy
any padding bytes, and if the array isn't part of a struct that could
clobber other memory.)

*However*, when I compiled the above code using one particular
compiler, the initialization of s_zero was implemented as a call to
memset(), and the assignment was implemented as a call to memcpy().

You're assuming that the overhead of a function call is going to be
unacceptable, but *how do you know*? Have you actually measured your
code's performance and found it to be unacceptably slow? If not,
don't waste your time trying to improve it until and unless you know
there's a problem to be solved.

The two rules of program optimization are:

Rule 1: Don't do it.

Rule 2 (experts only): Don't do it yet.

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Herbert Rosenau]

Re: reinitializatio n an array

On Fri, 30 May 2008 07:12:48 UTC, Keith Thompson <kst-u@mib.org>
wrote:

I know you said you didn't want a function call, but nothing you can
come up with is likely to be faster than calling memset().
>

Not true. Using static ininitialiser is much quicker as it costs no
time in runtime.

memset is only useable on arraays of type char. For any other type
you'll enter undefined behavior because this is the only type memset
accepts and there is no other type available that can set type int,
float, double and theyr modifications to the right type of 0. Any type
except char can contain padding bits. Having all padding bits set to 0
may end up in trap when accessing the value.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2R Deutsch ist da!

[Keith Thompson]

Re: reinitializatio n an array

"Herbert Rosenau" <os2guy@pc-rosenau.dewrite s:

On Fri, 30 May 2008 07:12:48 UTC, Keith Thompson <kst-u@mib.org>
wrote:

>I know you said you didn't want a function call, but nothing you can
>come up with is likely to be faster than calling memset().

>
Not true. Using static ininitialiser is much quicker as it costs no
time in runtime.

The question was specifically about *re*initializat ion.

(And I imagine a static initializer might have some cost when the
program is being loaded, but it's probably ok to ignore that.)

Using two separate objects rather than reinitializing one and using it
again might be faster, at some cost in memory usage. It's unlikely to
be significantly helpful.

memset is only useable on arraays of type char. For any other type
you'll enter undefined behavior because this is the only type memset
accepts and there is no other type available that can set type int,
float, double and theyr modifications to the right type of 0. Any type
except char can contain padding bits. Having all padding bits set to 0
may end up in trap when accessing the value.

This was changed in one of the Technical Corrigenda to C99.
See n1256 6.2.6.2p5:

For any integer type, the object representation where all the bits
are zero shall be a representation of the value zero in that type.

I believe that all existing implementations (happen to) obey this rule
anyway, so for practical purposes you're safe in assuming that
all-bits-zero is a representation of 0 for any integer type (but not
for floating-point or pointer types).

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Mark McIntyre]

Re: reinitializatio n an array

Herbert Rosenau wrote:

On Fri, 30 May 2008 07:12:48 UTC, Keith Thompson <kst-u@mib.org>
wrote:
>

>I know you said you didn't want a function call, but nothing you can
>come up with is likely to be faster than calling memset().
>>

>
Not true. Using static ininitialiser is much quicker as it costs no
time in runtime.

How do you imagine that the runtime loader sets the value of statically
initialised objects?

memset is only useable on arraays of type char.

more accurate to say "portably usable". On many implementations , many
other types can be safely memset.

>For any other type you'll enter undefined behavior

Only if you access the value and it happens to be a trap.

[Walter Roberson]

Re: reinitializatio n an array

In article <XNY0k.29194$wc 2.27127@en-nntp-01.am2.easynews .com>,
Mark McIntyre <markmcintyre@s pamcop.netwrote :

>Herbert Rosenau wrote:

>On Fri, 30 May 2008 07:12:48 UTC, Keith Thompson <kst-u@mib.org>
>wrote:

>Not true. Using static ininitialiser is much quicker as it costs no
>time in runtime.

>How do you imagine that the runtime loader sets the value of statically
>initialised objects?

System dependant and value dependant. On -some- (common) systems,
objects that are statically initialized to 0 are placed in
"demand-zero paging" -- pages that are never explicitly initialized
to anything, but are flagged in such a way that when a reference is
made to the memory page, the hardware brings in a page that it quick-wipes
to 0.

I believe I've heard of a (relatively small number of) systems
that also have demand non-initialized pages -- pages that are
never explicitly initialized to anything, but which are flagged in such
a way that when a reference is made to the memory page, the hardware
brings in a page that it quick-sets to some repeated value such as
0xDEADBEEF or one of the signalling-NaN values.
--
"If there were no falsehood in the world, there would be no
doubt; if there were no doubt, there would be no inquiry; if no
inquiry, no wisdom, no knowledge, no genius."
-- Walter Savage Landor

[Herbert Rosenau]

Re: reinitializatio n an array

On Mon, 2 Jun 2008 20:32:55 UTC, Mark McIntyre
<markmcintyre@s pamcop.netwrote :

Herbert Rosenau wrote:

On Fri, 30 May 2008 07:12:48 UTC, Keith Thompson <kst-u@mib.org>
wrote:

I know you said you didn't want a function call, but nothing you can
come up with is likely to be faster than calling memset().
>

Not true. Using static ininitialiser is much quicker as it costs no
time in runtime.

>
How do you imagine that the runtime loader sets the value of statically
initialised objects?

Where have I sayed that the loader has to set values? It is the right
of the compiler (and many compilers do so) to set values to theyr
defaults. So the loader will have to do noting as
- reserve memory for uninitialised variables
this may or may not result in filling this space with
some values depending on the security features of the OS
- expand/copy binary data from object files
to theyr location in memory
- relocate when there is something to relocate
but that is outside the scope of C.

memset is only useable on arraays of type char.

>
more accurate to say "portably usable". On many implementations , many
other types can be safely memset.
>

For any other type you'll enter undefined behavior

>
Only if you access the value and it happens to be a trap.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2R Deutsch ist da!