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 reinitialization 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.
> 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 reinitialization 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.
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 reinitialization 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,sizeof(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.)
> 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 reinitialization 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,sizeof(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.
raghu <ragavaku...@gmail.com> wrote: > 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 reinitialization 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.
On Thu, May 29, 2008 at 11:50:33PM -0700, raghu wrote: > On May 30, 11:35 am, Szabolcs Borsanyi <s.borsa...@sussex.ac.uk> > wrote: [snip]
> > 2) since you have a char array, you can do a memset(A,0,sizeof(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:
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.
raghu <ragavaku...@gmail.com> writes: > 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 reinitialization 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_Keith) ks...@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"
> 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_Keith) ks...@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"
On Fri, 30 May 2008 07:12:48 UTC, Keith Thompson <ks...@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.
"Herbert Rosenau" <os2...@pc-rosenau.de> writes: > On Fri, 30 May 2008 07:12:48 UTC, Keith Thompson <ks...@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*initialization.
(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_Keith) ks...@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"
In article <XNY0k.29194$wc2.27...@en-nntp-01.am2.easynews.com>, Mark McIntyre <markmcint...@spamcop.net> wrote:
>Herbert Rosenau wrote: >> On Fri, 30 May 2008 07:12:48 UTC, Keith Thompson <ks...@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
<markmcint...@spamcop.net> wrote: > Herbert Rosenau wrote: > > On Fri, 30 May 2008 07:12:48 UTC, Keith Thompson <ks...@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.