Int array test for all values zero

[mm]

Hi,

Say you have an Int32[] with 8 elements. What is the 'best' ie: fastest and
most effiicent way to check if all elements are zero? Thanks, Matt.

 

[Arne Vajhøj]

Say you have an Int32[] with 8 elements. What is the 'best' ie: fastest and
most effiicent way to check if all elements are zero? Thanks, Matt.

I would be relative sure that there efficiency of this operation
does not matter for a real world program.

Make your own for loop or use an implicit loop like in Array.Exists,
but don't waste too much time on the problem.

Arne

 

[Arto Viitanen]

mm kirjoitti:

Hi,

Say you have an Int32[] with 8 elements. What is the 'best' ie: fastest and
most effiicent way to check if all elements are zero? Thanks, Matt.

It depends, does it? I mean if you do the test hundreds of times but set
the array only once, then sorting the array and checking that first and
last element are same and zero might be suitable. Or counting bits, or
storing the information once and for all to some other variable.

 

[Arial]

Hi,

Say you have an Int32[] with 8 elements. What is the 'best' ie: fastest
and most effiicent way to check if all elements are zero? Thanks, Matt.

Interesting question

I suggest this:

bool IsAllZero(int[] list)
{
sum=0
foreach(int i in list) sum+=i;
return sum==0;
}

Add all values in array in sum and check if sum is zero.
From the machine code point of view that should be much faster
than checking each value with if
or sorting as someone suggested.

Do your own performance tests and let us know the results.

Happy coding!
Arial

 

[kndg]

Hi,

Say you have an Int32[] with 8 elements. What is the 'best' ie: fastest
and most effiicent way to check if all elements are zero? Thanks, Matt.

Interesting question

I suggest this:

bool IsAllZero(int[] list)
{
sum=0
foreach(int i in list) sum+=i;
return sum==0;
}

Add all values in array in sum and check if sum is zero.
From the machine code point of view that should be much faster
than checking each value with if
or sorting as someone suggested.

Do your own performance tests and let us know the results.

Happy coding!
Arial

IsAllZero(new[] {-1,1}) => true : which is wrong

bool IsAllZero(int[] list)
{
int sum=0;
foreach(int i in list) sum |= i;
return sum==0;
}

 

[Arial]

Hi,

Say you have an Int32[] with 8 elements. What is the 'best' ie: fastest
and most effiicent way to check if all elements are zero? Thanks, Matt.

Interesting question

I suggest this:

bool IsAllZero(int[] list)
{
sum=0
foreach(int i in list) sum+=i;
return sum==0;
}

Add all values in array in sum and check if sum is zero.
From the machine code point of view that should be much faster
than checking each value with if
or sorting as someone suggested.

Do your own performance tests and let us know the results.

Happy coding!
Arial

IsAllZero(new[] {-1,1}) => true : which is wrong

bool IsAllZero(int[] list)
{
int sum=0;
foreach(int i in list) sum |= i;
return sum==0;
}

Tnx. for code patching
Your version works even for negatives, positives mix
The question remains, is there a faster way?

 

[kndg]

Hi,

Say you have an Int32[] with 8 elements. What is the 'best' ie: fastest
and most effiicent way to check if all elements are zero? Thanks, Matt.
Interesting question

I suggest this:

bool IsAllZero(int[] list)
{
sum=0
foreach(int i in list) sum+=i;
return sum==0;
}

Add all values in array in sum and check if sum is zero.
From the machine code point of view that should be much faster
than checking each value with if
or sorting as someone suggested.

Do your own performance tests and let us know the results.

Happy coding!
Arial

IsAllZero(new[] {-1,1}) => true : which is wrong

bool IsAllZero(int[] list)
{
int sum=0;
foreach(int i in list) sum |= i;
return sum==0;
}

Tnx. for code patching
Your version works even for negatives, positives mix
The question remains, is there a faster way?

I think using if is the most performant.
It can escape the loop early.

bool IsAllZero(int[] list)
{
foreach(int i in list)
{
if (i != 0) return false;
}
return true;
}

 

[Göran Andersson]

Arial wrote:
Hi,

Say you have an Int32[] with 8 elements. What is the 'best' ie:
fastest and most effiicent way to check if all elements are zero?
Thanks, Matt.
Interesting question

I suggest this:

bool IsAllZero(int[] list)
{
sum=0
foreach(int i in list) sum+=i;
return sum==0;
}

Add all values in array in sum and check if sum is zero.
From the machine code point of view that should be much faster
than checking each value with if
or sorting as someone suggested.

Do your own performance tests and let us know the results.

Happy coding!
Arial
IsAllZero(new[] {-1,1}) => true : which is wrong

bool IsAllZero(int[] list)
{
int sum=0;
foreach(int i in list) sum |= i;
return sum==0;
}

Tnx. for code patching
Your version works even for negatives, positives mix
The question remains, is there a faster way?

I think using if is the most performant.
It can escape the loop early.

bool IsAllZero(int[] list)
{
foreach(int i in list)
{
if (i != 0) return false;
}
return true;
}

If the array is always the same size, you could save a few nanoseconds
by unraveling the loop:

bool IsAllZero(int[] list) {
return
list[0] == 0 &&
list[1] == 0 &&
list[2] == 0 &&
list[3] == 0 &&
list[4] == 0 &&
list[5] == 0 &&
list[6] == 0 &&
list[7] == 0;
}

As it uses the short circuit operator &&, it will also escape from the
expression as early as possible.

Making it faster than that would require some statistics about the data.
If it for example is most likely that the fourth element is non-zero,
that value could be checked first.

 

[Cor Ligthert[MVP]]

Do you mean in processing time or in program writting time?

Cor

 

[Cor Ligthert[MVP]]

Goran,

I am in doubt, this was my first thought too, but mostly is simple adding
withouth evealuating or looping (as you use) the most efficient code at
hardware level,

a(0)+a(1)+a(2)etc == 0

In my idea should a 1Mghz computer be able to do this in less than 12
nanoseconds, the logic of the consequent comps will need probably more.

Cor

Arial wrote:
Hi,

Say you have an Int32[] with 8 elements. What is the 'best' ie:
fastest and most effiicent way to check if all elements are zero?
Thanks, Matt.
Interesting question

I suggest this:

bool IsAllZero(int[] list)
{
sum=0
foreach(int i in list) sum+=i;
return sum==0;
}

Add all values in array in sum and check if sum is zero.
From the machine code point of view that should be much faster
than checking each value with if
or sorting as someone suggested.

Do your own performance tests and let us know the results.

Happy coding!
Arial
IsAllZero(new[] {-1,1}) => true : which is wrong

bool IsAllZero(int[] list)
{
int sum=0;
foreach(int i in list) sum |= i;
return sum==0;
}


Tnx. for code patching
Your version works even for negatives, positives mix
The question remains, is there a faster way?

I think using if is the most performant.
It can escape the loop early.

bool IsAllZero(int[] list)
{
foreach(int i in list)
{
if (i != 0) return false;
}
return true;
}

If the array is always the same size, you could save a few nanoseconds by
unraveling the loop:

bool IsAllZero(int[] list) {
return
list[0] == 0 &&
list[1] == 0 &&
list[2] == 0 &&
list[3] == 0 &&
list[4] == 0 &&
list[5] == 0 &&
list[6] == 0 &&
list[7] == 0;
}

As it uses the short circuit operator &&, it will also escape from the
expression as early as possible.

Making it faster than that would require some statistics about the data.
If it for example is most likely that the fourth element is non-zero, that
value could be checked first.

 

[Joe Greer]

Goran,

I am in doubt, this was my first thought too, but mostly is simple
adding withouth evealuating or looping (as you use) the most efficient
code at hardware level,

a(0)+a(1)+a(2)etc == 0

In my idea should a 1Mghz computer be able to do this in less than 12
nanoseconds, the logic of the consequent comps will need probably
more.

Cor


"Göran Andersson" <[email protected]> wrote in message

The sum of all a-s could be 0, so just adding won't work. ( -1 + 1 == 0
for example)

Even with uint, once the value overflows you can still sum up to 0.

joe

 

[Pavel Minaev]

Say you have an Int32[] with 8 elements. What is the 'best' ie: fastestand
most effiicent way to check if all elements are zero? Thanks, Matt.

In addition to aforementioned snippets in this case of finite array I
suggest using for-loop instead of foreach - it produces less IL code and
runs about 5% faster.

Are you sure about that? I had a strong impression that C# unrolls
foreach loops on arrays to precisely the same code as a hand-written
for loop (i.e. it won't use enumerators etc).

 

[Göran Andersson]

Goran,

I am in doubt, this was my first thought too, but mostly is simple
adding withouth evealuating or looping (as you use) the most efficient
code at hardware level,

a(0)+a(1)+a(2)etc == 0

In my idea should a 1Mghz computer be able to do this in less than 12
nanoseconds, the logic of the consequent comps will need probably more.

Cor

Yes, that is faster, but you are forgetting one of the fundamental rules
of optimisation. If the code no longer works properly, it doesn't matter
how fast it is.

 

[mm]

In processing time - the values are changing constatntly and all zero
represents a special condition that I want to detect and flag. Thus I want
to block access to the array for as short a time as possible while checking
it.

Thanks for all the replies - really awesome! Matt.

Do you mean in processing time or in program writting time?

Cor

Hi,

Say you have an Int32[] with 8 elements. What is the 'best' ie: fastest
and most effiicent way to check if all elements are zero? Thanks, Matt.

 

[Cor Ligthert[MVP]]

I did not forget, I agree very much with the first reply from Arne.

As I know that you have seen so much from my replies in different newsgroup,
you know that it could have been my reply



Cor

 

[Göran Andersson]

I did not forget, I agree very much with the first reply from Arne.

Now you don't make any sense. Did Arne say that the code doesn't have to
work, as long as it's fast?

As I know that you have seen so much from my replies in different
newsgroup, you know that it could have been my reply



Cor

 

[AA2e72E]

I've been following this with some interest; in APL, I can just test for an
array being all zeros with relational operator .. that is probably besides
the point.

I am intrigued by this:

int[] abc = new int[8]; // this can be changed dynamically
int[] xyz = new int[] { 0, 0, 0, 0, 0, 0, 0, 0 };
abc.Equals(xyz);

Why does the last expression return false?

 

[Göran Andersson]

I did test with 1000 calls to:
foreach(int i in list) {
if (i != 0) return false;
}
return true;
using just Stopwatch. I pefromed several tests and I can still reproduce
this 5% gain on my machine - not Debug but Release compile in VS2008
Regarding produced IL code just take a look. There's also difference in
amount of local variables - in case of foreach CS compiler produces two
extra variables.

Regards

The loop itself creates a bit more code, but you get a local variable
that contains the value so that you don't have to access the array to
get the value inside the loop. If you use the value a few times in the
loop (which is common in actual code), using foreach should actually be
faster.

 

[kndg]

The loop itself creates a bit more code, but you get a local variable
that contains the value so that you don't have to access the array to
get the value inside the loop. If you use the value a few times in the
loop (which is common in actual code), using foreach should actually be
faster.

I didn't challenge what You wrote. But in the context of given example I
propose the following experiment:
#v+
static void Main() {
int[] list = new int[] { 0, 0, 0, 0, 0, 0, 0, 1 };
Stopwatch sw = Stopwatch.StartNew();
for (int j = 0; j < 100000; j++) {
//IsAllZeroV2(list);
//choose one
//IsAllZeroV1(list);
}
sw.Stop();
Console.WriteLine("{0:d}", sw.Elapsed.Ticks);
}
static bool IsAllZeroV1(int[] list) {
foreach (int i in list) {
if (i != 0) return false;
}
return true;
}
static bool IsAllZeroV2(int[] list) {
for (int i = 0; i < list.Length; i++) {
if (list != 0) return false;
}
return true;
}
#v-
compiled with csc version 3.5.30729.1 /noconfig /unsafe- /platform:AnyCPU
/debugdbonly /filealign:512 /optimize+ (...)

then I ran each version 10 times skipping several first results to bypass
JIT time. Here are my results as copied from Excell sheet:
No V1 V2
1 17638 15710
2 17035 15667
3 16768 15900
4 16879 15759
5 17172 15898
6 16970 16014
7 16882 15649
8 17653 15792
9 17546 16013
10 18544 15739
AVG 17309 15814
ERR 517 128

So I still insist that in _practice_ for-loop is 5% faster than foreach for
the example considered in current thread.

I would like to talk about particular example.

Regards

Just did the test myself using different compiler
Test for 1M iteration

1. Microsoft (R) Visual C# 2008 Compiler version 3.5.30729.1 (csc /o+)
Result:
Average [V1]: 90540
Average [V2]: 86874

2. Mono C# compiler, Copyright 2001 - 2008 Novell, Inc. (gmcs /o+)
Result:
Average [V1]: 74275
Average [V2]: 74077

3. Microsoft (R) Visual Basic Compiler version 9.0.30729.1 (vbc /optimize+)
Result:
Average [V1]: 74284
Average [V2]: 74030

It seems that vbc and mono produce faster code than csc.
There is only a slight performance different when compile using mono or
vbc. Upon examination, mono unrolls foreach loop to for loop but vbc
does not (but still produce faster code).
I think it is time for Microsoft to concentrate on optimizing their c#
compiler rather than keep adding features.

 

[Göran Andersson]

Hi,

Say you have an Int32[] with 8 elements. What is the 'best' ie: fastest and
most effiicent way to check if all elements are zero? Thanks, Matt.

Here's an efficient method that actually works:

bool zero = (
data[0] |
data[1] |
data[2] |
data[3] |
data[4] |
data[5] |
data[6] |
data[7] ) == 0;

The result of or-ing the values is that any bit that is set in any of
the items is set in the result, therefore the result is only zero if all
bit in all items are zero.

My tests shows that it's between 5 and 25 times faster than looping
through the items.