For-loop expression?

[Dave Veeneman]

In a for-loop, is a calculated expression re-calculated on each pass through
the loop, or only once, when the loop is initialized? For example, assume
the following loop:

for (int i = 0; i < myArray.Length - 1; i++)
{
// code here
}

Is "myArray.Le ngth - 1" calculated once, or on each pass through the loop?
Or, to put it another way, is there any advantage to:

int n = myArray.Length - 1;
for (int i = 0; i < n; i++)
{
// code here
}

Thanks in advance.

--
Dave Veeneman
Chicago

[MuZZy]

Re: For-loop expression?

"Dave Veeneman" <davidv@nospam. com> wrote in message
news:OwIxy2n%23 DHA.3384@TK2MSF TNGP11.phx.gbl. ..[color=blue]
> In a for-loop, is a calculated expression re-calculated on each pass[/color]
through[color=blue]
> the loop, or only once, when the loop is initialized? For example, assume
> the following loop:
>
> for (int i = 0; i < myArray.Length - 1; i++)
> {
> // code here
> }
>
> Is "myArray.Le ngth - 1" calculated once, or on each pass through the loop?
> Or, to put it another way, is there any advantage to:
>
> int n = myArray.Length - 1;
> for (int i = 0; i < n; i++)
> {
> // code here
> }
>
> Thanks in advance.
>
> --
> Dave Veeneman
> Chicago[/color]

Well, in C++ it would calculate on each loop, unless this value stays
unchanged and compiler has code optimisation.
I am a newbie for C#, so i can't guaranty accuracy of my answer, but i would
rather do:

int len = Array.Lenght() - 1;
for (int i = 1 ; i < n ; i++ )

Regards,
Andrey aka MuZZy

[Derek Harmon]

Re: For-loop expression?

"Dave Veeneman" <davidv@nospam. com> wrote in message news:OwIxy2n#DH A.3384@TK2MSFTN GP11.phx.gbl...[color=blue]
> In a for-loop, is a calculated expression re-calculated on each pass through
> the loop, or only once, when the loop is initialized?[/color]

The conditional to break out of the for-loop is executed every pass through
the loop. So to answer your question,
[color=blue]
> for (int i = 0; i < myArray.Length - 1; i++)[/color]

Performs a subtraction myArray.Length - 1 times.
[color=blue]
> int n = myArray.Length - 1;
> for (int i = 0; i < n; i++)[/color]

Performs a subtraction once.

In general, its advisable to move invariant logic out of the loop conditional.

Normally, it makes little difference when you're looping over the .Length of
an array, because the IL is optimized for this situation:

for ( int i = 0; i < myArray.Length; ++i)

If you look at the difference between this statement, and what you might
think would be a faster statement in,

for ( int i = 0, iMax = myArray.Length; i < iMax; ++i)

You'll find that the IL of the former executes the IL instruction, ldlen, once
each time through the loop, whereas the latter executes ldlen once before
entering the loop and stores it on the stack. Instead of calling ldlen, the
second loop looks-up the length in the stack on each iteration.

On the other hand, as soon as you start doing arithmetic operations on
the length, the iterations of the loop multiply the number of operations
being performed. Thus, whenever operations on the length must be
performed, and the length if fixed, it's a good idea to move it outside
of the loop.

What's more, take a quantity that many developers might think of as being
equivalent to an array's Length -- the Count property of a Collection like
ArrayList. What is the cost of having Count in the conditional of a for-loop
you may ask?

Count is a virtual property, so there is very little in the way of optimization of
IL here. A callvirt operation has to walk the vtable of (potentially) several
accessor methods. Thus, the innocuous-looking access of the Count on
a collection is easily one of the more expensive choices a developer can
undertake in their for-loop conditionals.


Derek Harmon

[Jon Skeet [C# MVP]]

Re: For-loop expression?

Derek Harmon <loresayer@msn. com> wrote:

<snip>
[color=blue]
> In general, its advisable to move invariant logic out of the loop conditional.[/color]

Well, unless it harms readability...
[color=blue]
> Normally, it makes little difference when you're looping over the .Length of
> an array, because the IL is optimized for this situation:
>
> for ( int i = 0; i < myArray.Length; ++i)[/color]

I don't believe it's the IL which is optimised here - it's the JIT
compiler which can optimise things appropriately.

Indeed, I believe that when you're using simple code such as the above,
you can actually get a performance *hit* by moving the invariant out of
the loop. I believe the JIT compiler can (in certain situations)
recognise the IL generated from a construct such as the above and do
clever things like removing bounds checks if it knows that the variable
used to access the array won't change value. I believe such
optimisations aren't performed when the length is hoisted out of the
loop.

Here's a sample program:

using System;

public class Test
{
static void Main()
{
int[] x = new int[100000];

Hoisted(x);
NotHoisted(x);
}

static void Hoisted(int[] foo)
{
int n = foo.Length;
for (int i=0; i < n; i++)
{
foo[i] = foo[i]*2;
}
}

static void NotHoisted(int[] foo)
{
for (int i=0; i < foo.Length; i++)
{
foo[i] = foo[i]*2;
}
}
}

Using cordbg with JIT optimisations on, here's the code for Hoisted and
NotHoisted:


Hoisted:
[0000] push esi
[0001] mov esi,dword ptr [ecx+4]
[0004] xor edx,edx
[0006] cmp esi,0
[0009] jle 00000016
[000b] cmp edx,dword ptr [ecx+4]
[000e] jae 00000013
[0010] mov eax,dword ptr [ecx+edx*4+8]
[0014] add eax,eax
[0016] mov dword ptr [ecx+edx*4+8],eax
[001a] inc edx
[001b] cmp edx,esi
[001d] jl FFFFFFEE
[001f] pop esi
[0020] ret
[0021] xor ecx,ecx
[0023] call 724FF980
[0028] int 3

NotHoisted:
[0000] xor edx,edx
[0002] cmp dword ptr [ecx+4],0
[0006] jle 00000012
[0008] mov eax,dword ptr [ecx+edx*4+8]
[000c] add eax,eax
[000e] mov dword ptr [ecx+edx*4+8],eax
[0012] inc edx
[0013] cmp edx,dword ptr [ecx+4]
[0016] jl FFFFFFF2
[0018] ret

Here, it looks like the JIT compiler hasn't done the hoisting for us,
but it's removed the array bounds checking. In both cases, you still
end up with a single length check on each iteration, but (to my mind)
the NotHoisted C# code is more readable. Basically, you can't gauge
performance based on IL alone. (It's hard to do it from assembly, too,
but there we go...)
[color=blue]
> What's more, take a quantity that many developers might think of as being
> equivalent to an array's Length -- the Count property of a Collection like
> ArrayList. What is the cost of having Count in the conditional of a for-loop
> you may ask?
>
> Count is a virtual property, so there is very little in the way of optimization of
> IL here. A callvirt operation has to walk the vtable of (potentially) several
> accessor methods. Thus, the innocuous-looking access of the Count on
> a collection is easily one of the more expensive choices a developer can
> undertake in their for-loop conditionals.[/color]

It's still unlikely to end up being a bottleneck, and I view
readability as being *much* more important. To me, it's more
immediately clear what

for (int i=0; i < collection.Coun t; i++)
{
....
}

does than

int n = collection.Coun t;
for (int i=0; i < n; i++)
{
....
}

--
Jon Skeet - <skeet@pobox.co m>

http://www.pobox.com/~skeet

If replying to the group, please do not mail me too

[Michael S]

Re: For-loop expression?


"Derek Harmon" <loresayer@msn. com> wrote in message
news:%23Tah6Jo% 23DHA.3384@TK2M SFTNGP11.phx.gb l...[color=blue]
> "Dave Veeneman" <davidv@nospam. com> wrote in message[/color]
news:OwIxy2n#DH A.3384@TK2MSFTN GP11.phx.gbl...[color=blue][color=green]
> > In a for-loop, is a calculated expression re-calculated on each pass[/color][/color]
through[color=blue][color=green]
> > the loop, or only once, when the loop is initialized?[/color]
>
> Derek Harmon[/color]

Great reading Derek.

I would like to continue on this subject by taking it from another angle.

The overhead of having calculations in the for statement or calculating an
invariant result only once, may be tiny. But there is also a matter of
understandabili ty and maintainability .

If you calculate the invarant result before the loop people maintaining your
code wiill immediately understand that the value is invariant. If you do the
calculation inside the for-statement you are signaling that the value may
very well vary. The coder must check whether the result is invariant or not.

This is not really an issue on something as typical like taking Length - 1
on a list. It's quite obvious. But I always try to write code that is
instantly obvious at first glance. Hence it is my recommendation to never
evaluate invariant expressions inside for- or while-loops.

This is also why I try to use foreach whenever a can parse a vector without
using an index.

happy coding

- Michael S

[Jon Skeet [C# MVP]]

Re: For-loop expression?

Michael S <a@b.c> wrote:[color=blue]
> I would like to continue on this subject by taking it from another angle.
>
> The overhead of having calculations in the for statement or calculating an
> invariant result only once, may be tiny. But there is also a matter of
> understandabili ty and maintainability .[/color]

Absolutely, but...
[color=blue]
> If you calculate the invarant result before the loop people maintaining your
> code wiill immediately understand that the value is invariant. If you do the
> calculation inside the for-statement you are signaling that the value may
> very well vary. The coder must check whether the result is invariant or not.[/color]

I don't think that's actually very likely - it's certainly not
something I've come across often. The length of an actual array never
changes, so you'd have to change which array you were using in order
for the length to change. A collection's size may change, but in that
case you almost always have to use a different construct anyway to
avoid problems.

If the upper bound of the loop *could* change, I'd probably highlight
that with a comment instead.
[color=blue]
> This is not really an issue on something as typical like taking Length - 1
> on a list. It's quite obvious. But I always try to write code that is
> instantly obvious at first glance. Hence it is my recommendation to never
> evaluate invariant expressions inside for- or while-loops.[/color]

However, I find it's more instantly obvious what

for (int i=0; i < array.Length; i++)
{
....
}

means than

int n = array.Length;
for (int i=0; i < n; i++)
{
....
}

So while we agree that readability is very important, we certainly
*disagree* on which is the more readable form :)
[color=blue]
> This is also why I try to use foreach whenever a can parse a vector without
> using an index.[/color]

Agreed on that front.

--
Jon Skeet - <skeet@pobox.co m>

http://www.pobox.com/~skeet

If replying to the group, please do not mail me too

[Michael S]

Re: For-loop expression?


"Jon Skeet [C# MVP]" <skeet@pobox.co m> wrote in message
news:MPG.1aa529 652f063dae98a1f a@msnews.micros oft.com...[color=blue]
> Michael S <a@b.c> wrote:[color=green]
> > I would like to continue on this subject by taking it from another[/color][/color]
angle.[color=blue][color=green]
> >
> > The overhead of having calculations in the for statement or calculating[/color][/color]
an[color=blue][color=green]
> > invariant result only once, may be tiny. But there is also a matter of
> > understandabili ty and maintainability .[/color]
>
> Absolutely, but...
>[color=green]
> > If you calculate the invarant result before the loop people maintaining[/color][/color]
your[color=blue][color=green]
> > code wiill immediately understand that the value is invariant. If you do[/color][/color]
the[color=blue][color=green]
> > calculation inside the for-statement you are signaling that the value[/color][/color]
may[color=blue][color=green]
> > very well vary. The coder must check whether the result is invariant or[/color][/color]
not.[color=blue]
>
> I don't think that's actually very likely - it's certainly not
> something I've come across often. The length of an actual array never
> changes, so you'd have to change which array you were using in order
> for the length to change. A collection's size may change, but in that
> case you almost always have to use a different construct anyway to
> avoid problems.
>
> If the upper bound of the loop *could* change, I'd probably highlight
> that with a comment instead.
>[color=green]
> > This is not really an issue on something as typical like taking Length -[/color][/color]
1[color=blue][color=green]
> > on a list. It's quite obvious. But I always try to write code that is
> > instantly obvious at first glance. Hence it is my recommendation to[/color][/color]
never[color=blue][color=green]
> > evaluate invariant expressions inside for- or while-loops.[/color]
>
> However, I find it's more instantly obvious what
>
> for (int i=0; i < array.Length; i++)
> {
> ...
> }
>
> means than
>
> int n = array.Length;
> for (int i=0; i < n; i++)
> {
> ...
> }
>
> So while we agree that readability is very important, we certainly
> *disagree* on which is the more readable form :)
>[color=green]
> > This is also why I try to use foreach whenever a can parse a vector[/color][/color]
without[color=blue][color=green]
> > using an index.[/color]
>
> Agreed on that front.
>[/color]

For simple statements I also agree. Especially for calculating typical
things like i < arr.Lengthor i < myColumn.Count. But for more complex
calculations I move them outside the loop.

In the end, performance should be the least factor as the overhead is so
slight. It's more important to choose one coding style and stick to it for
all code in on project, one development-team or company.

It's when you interchange coding-styles you confuse programmers.

- Michael S

[Jon Skeet [C# MVP]]

Re: For-loop expression?

Michael S <a@b.c> wrote:[color=blue]
> For simple statements I also agree. Especially for calculating typical
> things like i < arr.Lengthor i < myColumn.Count. But for more complex
> calculations I move them outside the loop.[/color]

It would depend on the calculation, but yes - if the calculation wasn't
immediately obvious in intent, it would help to hoist it just so that
there was a variable name associated with it, so that the name could
end up being the thing which increased readability.
[color=blue]
> In the end, performance should be the least factor as the overhead is so
> slight. It's more important to choose one coding style and stick to it for
> all code in on project, one development-team or company.
>
> It's when you interchange coding-styles you confuse programmers.[/color]

Agreed - although of course some style changes are more confusing than
others. (Colleagues of mine put member variables in different places to
me. That's not a problem. If they started using different naming
conventions, that would be much more of an issue.)

--
Jon Skeet - <skeet@pobox.co m>

http://www.pobox.com/~skeet

If replying to the group, please do not mail me too

[Shawn B.]

Re: For-loop expression?

I ran some tests. I'm interested in the same information for some projects
being worked on. It appears that the difference in performance between the
two is so negligable that if I run the test numerous times, intermittenly,
one or the other will be better in performance but never just one of them.
Here's the source to my test:


Just place a multiline text field on the form called "txtResults ".

----------------------------------
Code in Form1
----------------------------------
private void button4_Click(o bject sender, System.EventArg s e) {
IntervalTimer timer = new IntervalTimer() ;

int[] x = new int[1000000];
int j;
float average1 = 0;
float average2 = 0;
int count = 100;

txtResults.Text = "";

for (j=0; j<count; j++) {
timer.Start();
for (int i=0; i<x.Length-1; i++) {
x[i] = i*2;
}
timer.Stop();

average1 += timer.GetSecond s();
txtResults.Text += "Inlined: " + timer.GetSecond s().ToString() +
"\r\n";
}

txtResults.Text += "Inlined Average: " + Convert.ToStrin g(average1
/ j) + "\r\n";

for (j=0; j<count; j++) {
timer.Start();

int k = x.Length-1;

for (int i=0; i<k; i++) {
x[i] = i*2;
}
timer.Stop();

average2 += timer.GetSecond s();
txtResults.Text += "Outlined: " + timer.GetSecond s().ToString()
+ "\r\n";
}


txtResults.Text += "Outlined Average: " + Convert.ToStrin g(average2
/ j) + "\r\n";

float delta = 0;
if (average1 > average2) {
delta = 1 - (average2 / average1);
txtResults.Text = "Outlining is " + delta.ToString( ) + "%
faster" + "\r\n" + txtResults.Text ;
}
else {
delta = 1 - (average1 / average2);
txtResults.Text = "Inlining is " + delta.ToString( ) + "% faster"
+ "\r\n" + txtResults.Text ;
}
}

-------------------------------------------
Code in Timer.cs
-------------------------------------------

using System;
using System.Runtime. InteropServices ;


namespace Processor
{

/* Code originally from "Advanced .NET" (WROX). Modified according to my
needs.
*
* Description:
*
* Using the Windows high-performance query counter API's, we can measure
the length
* of time an operation executed. Simply call Start() and Stop() then
get the time
* with Seconds(), Ticks(), or ToString()...
*
*/
public class IntervalTimer {
[DllImport("kern el32.dll")]
static extern private int QueryPerformanc eCounter(out long count);

[DllImport("kern el32.dll")]
static extern private int QueryPerformanc eFrequency(out long count);

public enum TimerState {
NotStarted,
Stopped,
Started
}

private TimerState state;
private long ticksAtStart;
private long intervalTicks;
private static long frequency;
private static int decimalPlaces;
private static string formatString;
private static bool initialized = false;



public IntervalTimer() {
if (!initialized) {
QueryPerformanc eFrequency(out frequency);
decimalPlaces = (int)Math.Log10 (frequency);

formatString = String.Format(" Interval: {{0:F{0}}} seconds
({{1}} MiliSeconds)", decimalPlaces);
initialized = true;
}
state = TimerState.NotS tarted;
}

public void Start() {
state = TimerState.Star ted;
ticksAtStart = CurrentTicks;
}

public void Stop() {
intervalTicks = CurrentTicks - ticksAtStart;
state = TimerState.Stop ped;
}

public float GetSeconds() {
if (state != TimerState.Stop ped)
throw new TimerNotStopped Exception();

return (float)interval Ticks/(float)frequenc y;
}

public float GetRealTimeSeco nds() {
if (state == TimerState.Star ted) {
intervalTicks = CurrentTicks - ticksAtStart;
return (float)interval Ticks/(float)frequenc y;
}

return GetSeconds();
}

public void Reset() {
ticksAtStart = 0;
intervalTicks = 0;
}

public int GetMilliSeconds () {
if (state != TimerState.Stop ped)
throw new TimerNotStopped Exception();

return (int)Math.Round ((decimal)(GetS econds()*1000), 0);
}


public long GetTicks() {
if (state != TimerState.Stop ped)
throw new TimerNotStopped Exception();

return intervalTicks;
}

private long CurrentTicks {
get {
long ticks;
QueryPerformanc eCounter(out ticks);
return ticks;
}
}

public override string ToString() {
if (state != TimerState.Stop ped)
return "Interval timer, state: " + state.ToString( );

return String.Format(f ormatString, GetSeconds(),
GetMilliSeconds ());
}
}



public class TimerNotStopped Exception : ApplicationExce ption {

public TimerNotStopped Exception()
: base("Timer is either still running or has not been started") {
}
}
}












"MuZZy" <leyandrew@yaho o.com> wrote in message
news:HTy_b.1110 18$jk2.493574@a ttbi_s53...[color=blue]
> "Dave Veeneman" <davidv@nospam. com> wrote in message
> news:OwIxy2n%23 DHA.3384@TK2MSF TNGP11.phx.gbl. ..[color=green]
> > In a for-loop, is a calculated expression re-calculated on each pass[/color]
> through[color=green]
> > the loop, or only once, when the loop is initialized? For example,[/color][/color]
assume[color=blue][color=green]
> > the following loop:
> >
> > for (int i = 0; i < myArray.Length - 1; i++)
> > {
> > // code here
> > }
> >
> > Is "myArray.Le ngth - 1" calculated once, or on each pass through the[/color][/color]
loop?[color=blue][color=green]
> > Or, to put it another way, is there any advantage to:
> >
> > int n = myArray.Length - 1;
> > for (int i = 0; i < n; i++)
> > {
> > // code here
> > }
> >
> > Thanks in advance.
> >
> > --
> > Dave Veeneman
> > Chicago[/color]
>
> Well, in C++ it would calculate on each loop, unless this value stays
> unchanged and compiler has code optimisation.
> I am a newbie for C#, so i can't guaranty accuracy of my answer, but i[/color]
would[color=blue]
> rather do:
>
> int len = Array.Lenght() - 1;
> for (int i = 1 ; i < n ; i++ )
>
> Regards,
> Andrey aka MuZZy
>
>[/color]