Find the lowest value in an array

[=?Utf-8?B?VGhvbWFzVDIy?=]

Hello,

I have an array that holds 4 values ( they contain random numbers). I would
like to find the lowest value (if there is a tie i would like to find one of
the tie.) then remove that value. I am new to Programming and C#.
Thanks for any help you can provide

Thomas

[=?UTF-8?B?QXJuZSBWYWpow7hq?=]

ThomasT22 wrote:

I have an array that holds 4 values ( they contain random numbers). I would
like to find the lowest value (if there is a tie i would like to find one of
the tie.) then remove that value. I am new to Programming and C#.

If it is always 4 elements then maybe:

minval = Math.Min(Math.Min(a[0], a[1]), Math.Min(a[2], a[3]));

Arne

[=?Utf-8?B?TW9kZWxCdWlsZGVy?=]

When you say "...then remove that value.", do you mean that after the
process, you should have a low value, and an array with only three elements?
Lilith and Arne answered the sorting issue.

"ThomasT22" wrote:

Hello,

I have an array that holds 4 values ( they contain random numbers). I would
like to find the lowest value (if there is a tie i would like to find one of
the tie.) then remove that value. I am new to Programming and C#.
Thanks for any help you can provide

Thomas

[Hilton]

ModelBuilder wrote:

When you say "...then remove that value.", do you mean that after the
process, you should have a low value, and an array with only three
elements?
Lilith and Arne answered the sorting issue.

Yeah, but sorting is destructive and a very inefficient way to find the
lowest of four numbers. Since the 'remove' requirement was well specified,
I'm going to ignore it here. To find the lowest value, I definitely
wouldn't use a Sort or Math.Min or Max. To maximize efficiency, something
along the lines of:

int a = x[0];
int b = x[1];
int c = x[2];
int d = x[3];

// Effectively "a = Math.Min (a, b)"
if (b < a)
{
a = b;
}

// Effectively "a = Math.Min (c, d)"
if (d < c)
{
c = d;
}

// Effectively "Math.Min (a, c)" which in summary is really "Math.Min (a,
b, c, d)"
return (a < c) ? a : c;

Hilton

[Jon Skeet [C# MVP]]

Hilton <no****@nospam.comwrote:

ModelBuilder wrote:

When you say "...then remove that value.", do you mean that after the
process, you should have a low value, and an array with only three
elements?
Lilith and Arne answered the sorting issue.

Yeah, but sorting is destructive and a very inefficient way to find the
lowest of four numbers. Since the 'remove' requirement was well specified,
I'm going to ignore it here. To find the lowest value, I definitely
wouldn't use a Sort or Math.Min or Max.

Why wouldn't you use Math.Min but keep the same overall structure? I
can't see how your code is more readable, and I highly doubt that this
is a likely bottleneck.
Alternatively, I'd possibly just write a separate method:

int FindMin(params int[] values)
{
int min = int.MaxValue;
foreach (int value in values)
{
if (value < min)
{
min = value;
}
}
return min;
}

That individual method is pretty readable, and the calling code is
going to be very easy to understand.

Fortunately with .NET 3.5 it's all built in:

int min = values.Min();

(And that works with any IEnumerable<int>.)

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Wole Ogunremi]

That's a fantastic new method! Thanks for sharing that Jon... I really need
to dig into .NET 3.5 and learn the new tricks!

:)

Wole

"Jon Skeet [C# MVP]" <sk***@pobox.comwrote in message
news:MP*********************@msnews.microsoft.com. ..

Hilton <no****@nospam.comwrote:

>ModelBuilder wrote:

When you say "...then remove that value.", do you mean that after the
process, you should have a low value, and an array with only three
elements?
Lilith and Arne answered the sorting issue.

Yeah, but sorting is destructive and a very inefficient way to find the
lowest of four numbers. Since the 'remove' requirement was well
specified,
I'm going to ignore it here. To find the lowest value, I definitely
wouldn't use a Sort or Math.Min or Max.

Why wouldn't you use Math.Min but keep the same overall structure? I
can't see how your code is more readable, and I highly doubt that this
is a likely bottleneck.
Alternatively, I'd possibly just write a separate method:

int FindMin(params int[] values)
{
int min = int.MaxValue;
foreach (int value in values)
{
if (value < min)
{
min = value;
}
}
return min;
}

That individual method is pretty readable, and the calling code is
going to be very easy to understand.

Fortunately with .NET 3.5 it's all built in:

int min = values.Min();

(And that works with any IEnumerable<int>.)

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[=?UTF-8?B?R8O2cmFuIEFuZGVyc3Nvbg==?=]

ThomasT22 wrote:

Hello,

I have an array that holds 4 values ( they contain random numbers). I would
like to find the lowest value (if there is a tie i would like to find one of
the tie.) then remove that value. I am new to Programming and C#.
Thanks for any help you can provide

Thomas

Loop through the values to find the smallest:

int low = int.MaxValue;
int index = -1;
for (int i = 0; i < items.Length; i++) {
if (items[i] < low) {
low = items[i];
index = i;
}
}

Now you have the lowest value in "low" and the index of the item
containing the value in "index".

You can't remove an item from an array, so you have to create a new array:

int[] n = new int[items.Length - 1];
int pos = 0;
for (int i = 0; i < items.Length; i++) {
if (i != index) {
n[pos] = items[i];
pos++;
}
}

Now you have a new array "n" with one less value than "items". You can
throw away the old array and use the new one instead:

items = n;

--
Göran Andersson
_____
http://www.guffa.com

[Hilton]

Jon,

Why wouldn't you use Math.Min but keep the same overall structure? I
can't see how your code is more readable, and I highly doubt that this
is a likely bottleneck.

I never claimed it was more readable, I claimed "to maximize efficiency".
Your method and my method are the same, except mine has been (kinda) "loop
unrolled" again "to maximize efficiency". I certainly wouldn't use my
method for larger arrays.

FWIW: Unrolling the loop as I did was 20% faster. As Jon pointed out, I
would only use my method if the method was in a CPU bottleneck piece of
code.

Hilton

[=?Utf-8?B?TW9kZWxCdWlsZGVy?=]

I refered to Arne's post, which in my view is pretty much the same as you are
suggesting. My question to the OP was with regards to whether they wanted a
function to return a new array with only 3 items (destructive), or just
"blank" the item entry (non-destructive).

"Hilton" wrote:

Jon,

Why wouldn't you use Math.Min but keep the same overall structure? I
can't see how your code is more readable, and I highly doubt that this
is a likely bottleneck.

I never claimed it was more readable, I claimed "to maximize efficiency".
Your method and my method are the same, except mine has been (kinda) "loop
unrolled" again "to maximize efficiency". I certainly wouldn't use my
method for larger arrays.

FWIW: Unrolling the loop as I did was 20% faster. As Jon pointed out, I
would only use my method if the method was in a CPU bottleneck piece of
code.

Hilton

[=?Utf-8?B?VGhvbWFzVDIy?=]

Thank you all for your help. The array.sort was the trick I needed.

"Göran Andersson" wrote:

ThomasT22 wrote:

Hello,

I have an array that holds 4 values ( they contain random numbers). I would
like to find the lowest value (if there is a tie i would like to find one of
the tie.) then remove that value. I am new to Programming and C#.
Thanks for any help you can provide

Thomas

Loop through the values to find the smallest:

int low = int.MaxValue;
int index = -1;
for (int i = 0; i < items.Length; i++) {
if (items[i] < low) {
low = items[i];
index = i;
}
}

Now you have the lowest value in "low" and the index of the item
containing the value in "index".

You can't remove an item from an array, so you have to create a new array:

int[] n = new int[items.Length - 1];
int pos = 0;
for (int i = 0; i < items.Length; i++) {
if (i != index) {
n[pos] = items[i];
pos++;
}
}

Now you have a new array "n" with one less value than "items". You can
throw away the old array and use the new one instead:

items = n;

--
Göran Andersson
_____
http://www.guffa.com

[Jon Skeet [C# MVP]]

Hilton <no****@nospam.comwrote:

Why wouldn't you use Math.Min but keep the same overall structure? I
can't see how your code is more readable, and I highly doubt that this
is a likely bottleneck.

I never claimed it was more readable, I claimed "to maximize efficiency".

But that was never requested.

You said:

<quote>
To find the lowest value, I definitely wouldn't use a Sort or Math.Min
or Max.
</quote>

If Sort/Min/Max are more readable and performance isn't an issue (which
for most code it isn't), why use a less readable form?

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Hilton]

Jon,

I'm not going to get into a p-match here, but I clearly stated the solution
I was giving was for maximum efficiency, and secondly, I still wouldn't use
Sort or Math.Min - neither did you.

Hilton
"Jon Skeet [C# MVP]" <sk***@pobox.comwrote in message
news:MP*********************@msnews.microsoft.com. ..

Hilton <no****@nospam.comwrote:

Why wouldn't you use Math.Min but keep the same overall structure? I
can't see how your code is more readable, and I highly doubt that this
is a likely bottleneck.

I never claimed it was more readable, I claimed "to maximize efficiency".

But that was never requested.

You said:

<quote>
To find the lowest value, I definitely wouldn't use a Sort or Math.Min
or Max.
</quote>

If Sort/Min/Max are more readable and performance isn't an issue (which
for most code it isn't), why use a less readable form?

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Jon Skeet [C# MVP]]

Hilton <no****@nospam.comwrote:

I'm not going to get into a p-match here, but I clearly stated the solution
I was giving was for maximum efficiency, and secondly, I still wouldn't use
Sort or Math.Min - neither did you.

No, I didn't use Math.Min - but not due to efficiency, but due to
finding a better overall solution.

If I *did* write a version which just compared a few versions, I
*would* use Math.Min because it's more readable than your alternative.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Jon Skeet [C# MVP]]

Jon Skeet [C# MVP] <sk***@pobox.comwrote:

If I *did* write a version which just compared a few versions, I
*would* use Math.Min because it's more readable than your alternative.

Sorry, that should have been "compared a few values".

I'd also run benchmarks if I really needed ultimate efficiency (which
is unlikely). I wouldn't be surprised if the call to Math.Min got
inlined into the same code anyway.

Basically, I'm concerned about people getting the impression that it's
worth writing long and less readable code for the sake of efficiency
when:

a) there's no indication that this is a bottleneck
b) there's no evidence that the longer version is more efficient

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Jon Skeet [C# MVP]]

Hilton <no****@nospam.comwrote:

So I did some testing:
Hilton's 'unreadable' version took: 23 seconds
Jon's looping "if" version took: 30 seconds
The Math.Min version took: 37 seconds

Just did some myself for the sake of interest. I tested four different
sets of values, and here were the results for a US billion (1 thousand
million) iterations:

{1, 2, 3, 4}:
Hilton: 9s
Jon: 12s
Math.Min: 13s

{4, 3, 2, 1}:
Hilton: 10s
Jon: 12s
Math.Min: 12s

{4, 1, 3, 2}:
Hilton: 10s
Jon: 12s
Math.Min: 11s

Much closer than your measurements give... I wonder if this is a .NET
framework version problem? My results are from .NET 2.0.
The important thing is just how fast this is for *any* algorithm. It
takes about 10 nanoseconds to do this computation, even on my laptop
which is a couple of years old. You'd have to be doing a *hell* of a
lot of these for it to be the performance bottleneck.
My code is below, if anyone else wants to try it...

using System;
using System.Diagnostics;

public class Test
{
const int Iterations = 1000000000;
static void Main()
{
int[] vals = new int[] {1, 2, 3, 4};

Stopwatch watch = Stopwatch.StartNew();
for (int i=0; i < Iterations; i++)
{
FindMinHilton(vals);
}
Console.WriteLine (watch.ElapsedMilliseconds);

watch = Stopwatch.StartNew();
for (int i=0; i < Iterations; i++)
{
FindMinJon(vals);
}
Console.WriteLine (watch.ElapsedMilliseconds);

watch = Stopwatch.StartNew();
for (int i=0; i < Iterations; i++)
{
FindMinMathMin(vals);
}
Console.WriteLine (watch.ElapsedMilliseconds);
}

static int FindMinHilton(int[] x)
{
int a = x[0];
int b = x[1];
int c = x[2];
int d = x[3];

// Effectively "a = Math.Min (a, b)"
if (b < a)
{
a = b;
}

// Effectively "a = Math.Min (c, d)"
if (d < c)
{
c = d;
}

// Effectively "Math.Min (a,bmc)" which in summary
// is really "Math.Min (a,b, c, d)"
return (a < c) ? a : c;
}

static int FindMinJon(params int[] values)
{
int min = int.MaxValue;
foreach (int value in values)
{
if (value < min)
{
min = value;
}
}
return min;
}

static int FindMinMathMin(int[] a)
{
return Math.Min(Math.Min(a[0], a[1]), Math.Min(a[2], a[3]));
}
}

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Hilton]

Jon,

It would be interesting seeing your numbers using 2.5 billion - that would
give times close to mine, For example, in your first test, the 12s and 13s
might really be closer to 11.5s and 13.49s (assuming it does rounding), and
there's roughly the 20% (i.e. rounding grossly affecting the outcome). BTW:
I'm running 'release', CF 2.0. My array was {1, 3, 2, 4}.

Now you've got me wondering how these run times would vary if run on the CF,
especially the Math.Min one.

Hilton
"Jon Skeet [C# MVP]" <sk***@pobox.comwrote in message
news:MP*********************@msnews.microsoft.com. ..

Hilton <no****@nospam.comwrote:

>So I did some testing:
Hilton's 'unreadable' version took: 23 seconds
Jon's looping "if" version took: 30 seconds
The Math.Min version took: 37 seconds

Just did some myself for the sake of interest. I tested four different
sets of values, and here were the results for a US billion (1 thousand
million) iterations:

{1, 2, 3, 4}:
Hilton: 9s
Jon: 12s
Math.Min: 13s

{4, 3, 2, 1}:
Hilton: 10s
Jon: 12s
Math.Min: 12s

{4, 1, 3, 2}:
Hilton: 10s
Jon: 12s
Math.Min: 11s

Much closer than your measurements give... I wonder if this is a .NET
framework version problem? My results are from .NET 2.0.
The important thing is just how fast this is for *any* algorithm. It
takes about 10 nanoseconds to do this computation, even on my laptop
which is a couple of years old. You'd have to be doing a *hell* of a
lot of these for it to be the performance bottleneck.
My code is below, if anyone else wants to try it...

using System;
using System.Diagnostics;

public class Test
{
const int Iterations = 1000000000;
static void Main()
{
int[] vals = new int[] {1, 2, 3, 4};

Stopwatch watch = Stopwatch.StartNew();
for (int i=0; i < Iterations; i++)
{
FindMinHilton(vals);
}
Console.WriteLine (watch.ElapsedMilliseconds);

watch = Stopwatch.StartNew();
for (int i=0; i < Iterations; i++)
{
FindMinJon(vals);
}
Console.WriteLine (watch.ElapsedMilliseconds);

watch = Stopwatch.StartNew();
for (int i=0; i < Iterations; i++)
{
FindMinMathMin(vals);
}
Console.WriteLine (watch.ElapsedMilliseconds);
}

static int FindMinHilton(int[] x)
{
int a = x[0];
int b = x[1];
int c = x[2];
int d = x[3];

// Effectively "a = Math.Min (a, b)"
if (b < a)
{
a = b;
}

// Effectively "a = Math.Min (c, d)"
if (d < c)
{
c = d;
}

// Effectively "Math.Min (a,bmc)" which in summary
// is really "Math.Min (a,b, c, d)"
return (a < c) ? a : c;
}

static int FindMinJon(params int[] values)
{
int min = int.MaxValue;
foreach (int value in values)
{
if (value < min)
{
min = value;
}
}
return min;
}

static int FindMinMathMin(int[] a)
{
return Math.Min(Math.Min(a[0], a[1]), Math.Min(a[2], a[3]));
}
}

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Jon Skeet [C# MVP]]

Hilton <no****@nospam.comwrote:

It would be interesting seeing your numbers using 2.5 billion - that would
give times close to mine, For example, in your first test, the 12s and 13s
might really be closer to 11.5s and 13.49s (assuming it does rounding)

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.

and there's roughly the 20% (i.e. rounding grossly affecting the outcome). BTW:
I'm running 'release', CF 2.0. My array was {1, 3, 2, 4}.

Now you've got me wondering how these run times would vary if run on the CF,
especially the Math.Min one.

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.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Willy Denoyette [MVP]]

"Jon Skeet [C# MVP]" <sk***@pobox.comwrote in message
news:MP*********************@msnews.microsoft.com. ..

Hilton <no****@nospam.comwrote:

>It would be interesting seeing your numbers using 2.5 billion - that
would
give times close to mine, For example, in your first test, the 12s and
13s
might really be closer to 11.5s and 13.49s (assuming it does rounding)

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.

>and there's roughly the 20% (i.e. rounding grossly affecting the
outcome). BTW:
I'm running 'release', CF 2.0. My array was {1, 3, 2, 4}.

Now you've got me wondering how these run times would vary if run on the
CF,
especially the Math.Min one.

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)

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

Willy.

[Willy Denoyette [MVP]]

"Ben Voigt [C++ MVP]" <rb*@nospam.nospamwrote in message
news:em**************@TK2MSFTNGP06.phx.gbl...

>>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

>as the C++ optimizing compiler)

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.

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.

[Jon Skeet [C# MVP]]

Ben Voigt [C++ MVP] <rb*@nospam.nospamwrote:

(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?

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.)

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Willy Denoyette [MVP]]

"Jon Skeet [C# MVP]" <sk***@pobox.comwrote in message
news:MP*********************@msnews.microsoft.com. ..

Ben Voigt [C++ MVP] <rb*@nospam.nospamwrote:

>(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?

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.)

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

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]]

"Jon Skeet [C# MVP]" <sk***@pobox.comwrote in message
news:MP*********************@msnews.microsoft.com. ..

Ben Voigt [C++ MVP] <rb*@nospam.nospamwrote:

>(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?

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.)

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]]

Ben Voigt [C++ MVP] <rb*@nospam.nospamwrote:

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 :)

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Ben Voigt [C++ MVP]]

"Jon Skeet [C# MVP]" <sk***@pobox.comwrote in message
news:MP********************@msnews.microsoft.com.. .

Ben Voigt [C++ MVP] <rb*@nospam.nospamwrote:

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?

>
--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Jon Skeet [C# MVP]]

Ben Voigt [C++ MVP] <rb*@nospam.nospamwrote:

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.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Willy Denoyette [MVP]]

"Ben Voigt [C++ MVP]" <rb*@nospam.nospamwrote in message
news:u2**************@TK2MSFTNGP06.phx.gbl...

>
"Jon Skeet [C# MVP]" <sk***@pobox.comwrote in message
news:MP********************@msnews.microsoft.com.. .

>Ben Voigt [C++ MVP] <rb*@nospam.nospamwrote:

>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?

>>
--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

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.

[Willy Denoyette [MVP]]

"Ben Voigt [C++ MVP]" <rb*@nospam.nospamwrote in message
news:uH**************@TK2MSFTNGP03.phx.gbl...

>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.

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.

>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.

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]]

"Willy Denoyette [MVP]" <wi*************@telenet.bewrote in message
news:u%******************@TK2MSFTNGP02.phx.gbl...

"Ben Voigt [C++ MVP]" <rb*@nospam.nospamwrote in message
news:uH**************@TK2MSFTNGP03.phx.gbl...

>>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.

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.

>>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.

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....

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

>
Willy.