Find the lowest value in an array

[Willy Denoyette [MVP]]

I was doing the rounding myself - I remember that your version was
actually about 8900ms, but I can't remember the other ones.

Here are the results for 2 billion, in ms - 2.5 billion takes us over
int.MaxValue, and changing the loop variables to be longs changes the
results significantly.

Hilton: 18675
Jon: 25219
Math.Min: 26844

A larger proportional difference than before, but still less than your
results.


Yes, that would be interesting. I'm still surprised that Math.Min
doesn't end up being the same speed as your code though - I'd expect
inlining to take care of it all.

Currently on v2, defining this:
return Math.Min( Math.Min(a[0], a[1]), Math.Min(a[2], a[3]));
in general stops the JIT from optimizing the arguments, make it look like:
int x = Math.Min(a[0], a[1]);
int y = Math.Min(a[2], a[3]);
return Math.Min(x, y);

and watch the results.
Also, note that running these tests in sequence produce different results
from running them separately (one per process).

Willy.

 

[Ben Voigt [C++ MVP]]

Yes, that would be interesting. I'm still surprised that Math.Min

doesn't end up being the same speed as your code though - I'd expect
inlining to take care of it all.

Currently on v2, defining this:
return Math.Min( Math.Min(a[0], a[1]), Math.Min(a[2], a[3]));
in general stops the JIT from optimizing the arguments, make it look like:
int x = Math.Min(a[0], a[1]);
int y = Math.Min(a[2], a[3]);
return Math.Min(x, y);

(scratches head remembering hearing claims that the .NET JIT was as good as
the C++ optimizing compiler)

 

[Willy Denoyette [MVP]]

Yes, that would be interesting. I'm still surprised that Math.Min
doesn't end up being the same speed as your code though - I'd expect
inlining to take care of it all.

Currently on v2, defining this:
return Math.Min( Math.Min(a[0], a[1]), Math.Min(a[2], a[3]));
in general stops the JIT from optimizing the arguments, make it look
like:
int x = Math.Min(a[0], a[1]);
int y = Math.Min(a[2], a[3]);
return Math.Min(x, y);

(scratches head remembering hearing claims that the .NET JIT was as good
as the C++ optimizing compiler)

For what it's worth, I never made such claim, did I?
As you know, the JIT is time constrained while the C++ back-end optimizer is
not (or say less). The result is that in some cases the result is less
optimal. Maybe one day when MS stops adding features and starts to
prioritize on JIT quality we may see better code generated for these corner
cases as well.

Willy.

 

[Ben Voigt [C++ MVP]]

(scratches head remembering hearing claims that the .NET JIT was as good

For what it's worth, I never made such claim, did I?

Several C# MVPs were doing so but I don't think you were among them.

 

[Jon Skeet [C# MVP]]

Several C# MVPs were doing so but I don't think you were among them.

I can't remember any such claims. There have been *other* claims, such
as the JIT being "good enough" in most cases, and supporting the notion
that improving the optimisation in the JIT is more important than
improving it in the C# compiler (which I'd agree with for most
situations but not all).

Certainly if I ever made such a statement I retract it wholeheartedly -
as Willy said, the JIT just doesn't have enough time to perform as many
optimisations. (That's where Sun's Hotspot technology wins out - it can
be really agressive in a few places. It comes with its own downsides,
of course.)

 

[Willy Denoyette [MVP]]

I can't remember any such claims. There have been *other* claims, such
as the JIT being "good enough" in most cases, and supporting the notion
that improving the optimisation in the JIT is more important than
improving it in the C# compiler (which I'd agree with for most
situations but not all).

Certainly if I ever made such a statement I retract it wholeheartedly -
as Willy said, the JIT just doesn't have enough time to perform as many
optimisations. (That's where Sun's Hotspot technology wins out - it can
be really agressive in a few places. It comes with its own downsides,
of course.)

In general , the JIT performs really well and can compete with a native C
back-end because the JIT takes (some, but not enough IMO) advantage of the
CLR's knowledge of the runtime environment (OS, CPU hardware and Memory
system). However there are domains where the JIT team could have done
better, notably loop optimization is poor in .NET and I don't believe that
this is only due to JIT time constraints.
Note also that the JIT64 does a better job than the JIT32 in terms of code
generation, but here we take a penalty because of the larger working set of
64 bit code, the net result is that 64 bit code is sometimes faster
(+10/20%) than 32 bit code, but in general 32bit code runs just as fast or
even faster.

Willy.

 

[Ben Voigt [C++ MVP]]

I can't remember any such claims. There have been *other* claims, such
as the JIT being "good enough" in most cases, and supporting the notion
that improving the optimisation in the JIT is more important than
improving it in the C# compiler (which I'd agree with for most
situations but not all).

Certainly if I ever made such a statement I retract it wholeheartedly -
as Willy said, the JIT just doesn't have enough time to perform as many
optimisations. (That's where Sun's Hotspot technology wins out - it can
be really agressive in a few places. It comes with its own downsides,
of course.)

Hotspot does speculative optimization, doesn't it? Where the first time a
virtual call is compiled, the target is inlined, and only if another runtime
type is seen is it recompiled to use the v-table? I think .NET could
benefit from a healthy dose of this sort of thing. Also there are an awful
lot of cases where generics should be reinstantiated for different reference
types to enable inlining.

 

[Jon Skeet [C# MVP]]

Hotspot does speculative optimization, doesn't it? Where the first time a
virtual call is compiled, the target is inlined, and only if another runtime
type is seen is it recompiled to use the v-table?
Yup.

I think .NET could benefit from a healthy dose of this sort of thing. Also
there are an awful lot of cases where generics should be reinstantiated
for different reference types to enable inlining.

I think the inlining is slightly less important in .NET than in Java,
where everything is virtual by default. In theory that shouldn't matter
- developers should decide whether or not something should be virtual,
and apply the right modifier or not regardless of the defaults. In
practice though, inlining would be *incredibly* rare in Java without
HotSpot

To be honest, anything I could write about how advantageous a HotSpot-
like runtime for .NET might be would only pure speculation. It's hard
to second-guess this kind of thing.

When it comes to generics, I see your point - I don't know how it would
be best to proceed with it, however. I suspect that giving the
developer some manual control would be the right way to go, probably
with attributes... but should those attributes be applied to the type
used as the type argument, or to the generic class itself? In other
words, do you think the developer ought to be able to write:

[AlwaysGenerateConcreteType]
public class Foo<T>

or

[AlwaysGenerateConcreteTypeWhenUsedInGenerics]
public class Bar

(with better names, of course

 

[Ben Voigt [C++ MVP]]

Hotspot does speculative optimization, doesn't it? Where the first time
a
virtual call is compiled, the target is inlined, and only if another
runtime
type is seen is it recompiled to use the v-table?
Yup.

I think .NET could benefit from a healthy dose of this sort of thing.
Also
there are an awful lot of cases where generics should be reinstantiated
for different reference types to enable inlining.

I think the inlining is slightly less important in .NET than in Java,
where everything is virtual by default. In theory that shouldn't matter
- developers should decide whether or not something should be virtual,
and apply the right modifier or not regardless of the defaults. In
practice though, inlining would be *incredibly* rare in Java without
HotSpot

To be honest, anything I could write about how advantageous a HotSpot-
like runtime for .NET might be would only pure speculation. It's hard
to second-guess this kind of thing.

When it comes to generics, I see your point - I don't know how it would
be best to proceed with it, however. I suspect that giving the
developer some manual control would be the right way to go, probably
with attributes... but should those attributes be applied to the type
used as the type argument, or to the generic class itself? In other
words, do you think the developer ought to be able to write:

[AlwaysGenerateConcreteType]
public class Foo<T>

or

[AlwaysGenerateConcreteTypeWhenUsedInGenerics]
public class Bar

(with better names, of course

Do you happen to know if the JIT can inline "through" a generic collection?
For example, List<T>.Contains is simple enough that it should be inlined,
but does the specific T.Equals(T other) method get inlined as well because
it's exactly known at the call site?

 

[Jon Skeet [C# MVP]]

Do you happen to know if the JIT can inline "through" a generic collection?
For example, List<T>.Contains is simple enough that it should be inlined,
but does the specific T.Equals(T other) method get inlined as well because
it's exactly known at the call site?

I don't know, I'm afraid. I guess it's not too hard to test, but I
don't have time at the moment.

It would be nice if there was some really easy way of trying this kind
of thing - getting a log of JIT optimisations performed as it goes, for
instance.

 

[Willy Denoyette [MVP]]

Certainly if I ever made such a statement I retract it
wholeheartedly -
as Willy said, the JIT just doesn't have enough time to perform as
many
optimisations. (That's where Sun's Hotspot technology wins out - it
can
be really agressive in a few places. It comes with its own downsides,
of course.)

Hotspot does speculative optimization, doesn't it? Where the first time
a
virtual call is compiled, the target is inlined, and only if another
runtime
type is seen is it recompiled to use the v-table?
Yup.

I think .NET could benefit from a healthy dose of this sort of thing.
Also
there are an awful lot of cases where generics should be reinstantiated
for different reference types to enable inlining.

I think the inlining is slightly less important in .NET than in Java,
where everything is virtual by default. In theory that shouldn't matter
- developers should decide whether or not something should be virtual,
and apply the right modifier or not regardless of the defaults. In
practice though, inlining would be *incredibly* rare in Java without
HotSpot

To be honest, anything I could write about how advantageous a HotSpot-
like runtime for .NET might be would only pure speculation. It's hard
to second-guess this kind of thing.

When it comes to generics, I see your point - I don't know how it would
be best to proceed with it, however. I suspect that giving the
developer some manual control would be the right way to go, probably
with attributes... but should those attributes be applied to the type
used as the type argument, or to the generic class itself? In other
words, do you think the developer ought to be able to write:

[AlwaysGenerateConcreteType]
public class Foo<T>

or

[AlwaysGenerateConcreteTypeWhenUsedInGenerics]
public class Bar

(with better names, of course

Do you happen to know if the JIT can inline "through" a generic
collection? For example, List<T>.Contains is simple enough that it should
be inlined, but does the specific T.Equals(T other) method get inlined as
well because it's exactly known at the call site?


T.Equals like in:
....
int a;
int b;
....
if(a.Equals(b))
b = ...;
is inlined and possibly optimized away.
However, List<T>.Contains is NOT inlined. This method is not as simple as
you may think, it's size is 96 bytes in IL, and methods larger than 32 are
not inlined by the JITters. Note that this class is part of the PRE_JIT'd
library mscorlib_ni, so the JIT doesn't have to JIT compile the method at
the first call, after checking the size (and quite some other stuff) he can
directly call the pre-jitted code from mscorlib_ni.

Willy.

 

[Ben Voigt [C++ MVP]]

T.Equals like in:

...
int a;
int b;
...
if(a.Equals(b))
b = ...;
is inlined and possibly optimized away.

Only because int is a value type. It can't be optimized away if T is a
generic type argument where the static type (compile-time actual argument)
is a reference type.

However, List<T>.Contains is NOT inlined. This method is not as simple as
you may think, it's size is 96 bytes in IL, and methods larger than 32 are
not inlined by the JITters. Note that this class is part of the PRE_JIT'd
library mscorlib_ni, so the JIT doesn't have to JIT compile the method at
the first call, after checking the size (and quite some other stuff) he
can directly call the pre-jitted code from mscorlib_ni.

Even TrueForAll and ForEach, which are very short, aren't that short.

I think 32 instructions would probably be more reasonable...

 

[Willy Denoyette [MVP]]

Only because int is a value type. It can't be optimized away if T is a
generic type argument where the static type (compile-time actual argument)
is a reference type.

True I should have said:
"T.Equals like in?",
T.Equals(T other) ends as a virtual call (callvirt in IL) and these aren't
inlined by the JIT.

Even TrueForAll and ForEach, which are very short, aren't that short.

They aren't that short, and they contain loops, so they aren't inlined.

I think 32 instructions would probably be more reasonable...

That would mean that the JIT should count the instructions while compiling,
hmmm....

Willy.

 

[Ben Voigt [C++ MVP]]

True I should have said:
"T.Equals like in?",
T.Equals(T other) ends as a virtual call (callvirt in IL) and these
aren't inlined by the JIT.


They aren't that short, and they contain loops, so they aren't inlined.

That would mean that the JIT should count the instructions while
compiling, hmmm....

I would think that decoding bytecode into an instruction stream is the first
step in JIT, or no?