Lacking for-loop optimization in C#

[MariusI]

I stumbled over an optimization (or lack of one, to be specific) when viewing
IL opcodes generated by the compiler using ms .net 2003. I was testing fast
pixel manipulation using Bitmap.LockBits and unsafe pointers to iterate over
an image's pixels. The inner-loop looked like this:

for (int x = 0; x < _buffer.Width*_ buffer.Height; x++)
{
// do manipulations here..
}

I noticed how the for-loop performed extremely slow, and ildasm revealed
that the "x < _buffer.Width*_ buffer.Height" was computed at each iteration,
resulting in two virtual calls and one mul. The use of /optimize did not
improve the matter, so the solution was to calculate
_buffer.Width*_ buffer.Height outside of the for-loop. I was under the
impression that the compiler performed hoisting automatically, am I missing
something here?

[David Anton]

RE: Lacking for-loop optimization in C#

If the compiler can't guarantee that the value of
_buffer.Width*_ buffer.Height changes during any loop iteration, then it'll
have to be calculated each time. That is the nature of a C/C++/C# for-loop.
It's quite common to have for-loops where you want this to occur. (note that
VB never recalculates the ending condition)

David Anton

https://www.tangiblesoftwaresolutions.com

Home of the Instant C# VB.NET to C# converter
and the Instant VB C# to VB.NET converter

"MariusI" wrote:
[color=blue]
> I stumbled over an optimization (or lack of one, to be specific) when viewing
> IL opcodes generated by the compiler using ms .net 2003. I was testing fast
> pixel manipulation using Bitmap.LockBits and unsafe pointers to iterate over
> an image's pixels. The inner-loop looked like this:
>
> for (int x = 0; x < _buffer.Width*_ buffer.Height; x++)
> {
> // do manipulations here..
> }
>
> I noticed how the for-loop performed extremely slow, and ildasm revealed
> that the "x < _buffer.Width*_ buffer.Height" was computed at each iteration,
> resulting in two virtual calls and one mul. The use of /optimize did not
> improve the matter, so the solution was to calculate
> _buffer.Width*_ buffer.Height outside of the for-loop. I was under the
> impression that the compiler performed hoisting automatically, am I missing
> something here?[/color]

[Marcin Grzębski]

Re: Lacking for-loop optimization in C#

Hi MariusI,
[color=blue]
> for (int x = 0; x < _buffer.Width*_ buffer.Height; x++)
> {
> // do manipulations here..
> }
>
> I noticed how the for-loop performed extremely slow, and ildasm revealed
> that the "x < _buffer.Width*_ buffer.Height" was computed at each iteration,[/color]

I think that it is working as it should be.
How do you say about that code:

for (int x = 0; x < _buffer.Width*_ buffer.Height; x++)
{
// do manipulations here..
if( _buffer.Height> 1 ) {
_buffer.Height= _buffer.Height-1;
}
}

Of course there is no sense to shrink a "_buffer" but
the loop expression should work in this case too.
Why the compiler have to guess what you have in mind?

Regards
Marcin

[MariusI]

RE: Lacking for-loop optimization in C#

Thanks for the reply. When you say "can't guarantee" do you mean that a
multithreaded system could alter the _buffer size and width? (There is no
code inside the for-loop which refers to the buffer).

"David Anton" wrote:
[color=blue]
> If the compiler can't guarantee that the value of
> _buffer.Width*_ buffer.Height changes during any loop iteration, then it'll
> have to be calculated each time. That is the nature of a C/C++/C# for-loop.
> It's quite common to have for-loops where you want this to occur. (note that
> VB never recalculates the ending condition)
>
> David Anton
> www.tangiblesoftwaresolutions.com
> Home of the Instant C# VB.NET to C# converter
> and the Instant VB C# to VB.NET converter
>
> "MariusI" wrote:
>[color=green]
> > I stumbled over an optimization (or lack of one, to be specific) when viewing
> > IL opcodes generated by the compiler using ms .net 2003. I was testing fast
> > pixel manipulation using Bitmap.LockBits and unsafe pointers to iterate over
> > an image's pixels. The inner-loop looked like this:
> >
> > for (int x = 0; x < _buffer.Width*_ buffer.Height; x++)
> > {
> > // do manipulations here..
> > }
> >
> > I noticed how the for-loop performed extremely slow, and ildasm revealed
> > that the "x < _buffer.Width*_ buffer.Height" was computed at each iteration,
> > resulting in two virtual calls and one mul. The use of /optimize did not
> > improve the matter, so the solution was to calculate
> > _buffer.Width*_ buffer.Height outside of the for-loop. I was under the
> > impression that the compiler performed hoisting automatically, am I missing
> > something here?[/color][/color]

[David Anton]

RE: Lacking for-loop optimization in C#

Not knowing the contents of your loop, I assumed that the compiler may have
determined that _buffer may possibly be changed.

If there is no way that _buffer could have been altered during loop
execution, then this is indeed probably a shortcoming of the compiler.

"MariusI" wrote:
[color=blue]
> Thanks for the reply. When you say "can't guarantee" do you mean that a
> multithreaded system could alter the _buffer size and width? (There is no
> code inside the for-loop which refers to the buffer).
>
> "David Anton" wrote:
>[color=green]
> > If the compiler can't guarantee that the value of
> > _buffer.Width*_ buffer.Height changes during any loop iteration, then it'll
> > have to be calculated each time. That is the nature of a C/C++/C# for-loop.
> > It's quite common to have for-loops where you want this to occur. (note that
> > VB never recalculates the ending condition)
> >
> > David Anton
> > www.tangiblesoftwaresolutions.com
> > Home of the Instant C# VB.NET to C# converter
> > and the Instant VB C# to VB.NET converter
> >
> > "MariusI" wrote:
> >[color=darkred]
> > > I stumbled over an optimization (or lack of one, to be specific) when viewing
> > > IL opcodes generated by the compiler using ms .net 2003. I was testing fast
> > > pixel manipulation using Bitmap.LockBits and unsafe pointers to iterate over
> > > an image's pixels. The inner-loop looked like this:
> > >
> > > for (int x = 0; x < _buffer.Width*_ buffer.Height; x++)
> > > {
> > > // do manipulations here..
> > > }
> > >
> > > I noticed how the for-loop performed extremely slow, and ildasm revealed
> > > that the "x < _buffer.Width*_ buffer.Height" was computed at each iteration,
> > > resulting in two virtual calls and one mul. The use of /optimize did not
> > > improve the matter, so the solution was to calculate
> > > _buffer.Width*_ buffer.Height outside of the for-loop. I was under the
> > > impression that the compiler performed hoisting automatically, am I missing
> > > something here?[/color][/color][/color]

[Ian Griffiths [C# MVP]]

Re: Lacking for-loop optimization in C#

Did it actually get any faster when you hoisted the code out of the loop?

I ask, because in general, these kinds of optimizations are done by the JIT
compiler, not the C# compiler. One reason for that is this enables all
languages to take advantage of these kinds of optimization, without every
single compiler having to repeat the same work all the other compilers do.

Most .NET compilers do very little optimization for this reason.

So I'm wondering if this really is slow for the reason you think it is. The
actual compiled code that runs at run time doesn't necessarily have the same
structure as the IL shown by ILDASM. It often doesn't. Indeed there are
certain cases where it definitely will hoist invariants outside of loops at
JIT compile time.

But if the change really did improve things, then it's probably, as others
have suggested, either because the compiler was unable to be absolutely
certain that the values wouldn't change (e.g. because you are calling
virtual accessors), or because the JIT compiler failed to optimize in this
case.

--
Ian Griffiths - http://www.interact-sw.co.uk/iangblog/

"MariusI" <MariusI@discus sions.microsoft .com> wrote in message
news:7E6A931D-B8CA-411D-8E91-31BDAA47445B@mi crosoft.com...[color=blue]
>I stumbled over an optimization (or lack of one, to be specific) when
>viewing
> IL opcodes generated by the compiler using ms .net 2003. I was testing
> fast
> pixel manipulation using Bitmap.LockBits and unsafe pointers to iterate
> over
> an image's pixels. The inner-loop looked like this:
>
> for (int x = 0; x < _buffer.Width*_ buffer.Height; x++)
> {
> // do manipulations here..
> }
>
> I noticed how the for-loop performed extremely slow, and ildasm revealed
> that the "x < _buffer.Width*_ buffer.Height" was computed at each
> iteration,
> resulting in two virtual calls and one mul. The use of /optimize did not
> improve the matter, so the solution was to calculate
> _buffer.Width*_ buffer.Height outside of the for-loop. I was under the
> impression that the compiler performed hoisting automatically, am I
> missing
> something here?[/color]

[Willy Denoyette [MVP]]

Re: Lacking for-loop optimization in C#


"MariusI" <MariusI@discus sions.microsoft .com> wrote in message
news:7E6A931D-B8CA-411D-8E91-31BDAA47445B@mi crosoft.com...[color=blue]
>I stumbled over an optimization (or lack of one, to be specific) when
>viewing
> IL opcodes generated by the compiler using ms .net 2003. I was testing
> fast
> pixel manipulation using Bitmap.LockBits and unsafe pointers to iterate
> over
> an image's pixels. The inner-loop looked like this:
>
> for (int x = 0; x < _buffer.Width*_ buffer.Height; x++)
> {
> // do manipulations here..
> }
>
> I noticed how the for-loop performed extremely slow, and ildasm revealed
> that the "x < _buffer.Width*_ buffer.Height" was computed at each
> iteration,
> resulting in two virtual calls and one mul. The use of /optimize did not
> improve the matter, so the solution was to calculate
> _buffer.Width*_ buffer.Height outside of the for-loop. I was under the
> impression that the compiler performed hoisting automatically, am I
> missing
> something here?[/color]

It's not the C# compiler that performs hoisting, it's the JIT compilers that
does a limited form of hoisting but this depends on what's been done in the
loop. Mind to share the code in the loop?

Willy.

[MariusI]

Re: Lacking for-loop optimization in C#

Yes, that is a good point, but as long as there is no code within the
for-loop which refers to the buffer, the compiler should optimize away the
buffer.Width*_b uffer.Height calculation (move it outside) at compile time. In
my case there was no code inside the for-loop refering to the buffer which
mean that the compiler should have moved the calculation outside.

"Marcin Grzębski" wrote:
[color=blue]
> Hi MariusI,
>[color=green]
> > for (int x = 0; x < _buffer.Width*_ buffer.Height; x++)
> > {
> > // do manipulations here..
> > }
> >
> > I noticed how the for-loop performed extremely slow, and ildasm revealed
> > that the "x < _buffer.Width*_ buffer.Height" was computed at each iteration,[/color]
>
> I think that it is working as it should be.
> How do you say about that code:
>
> for (int x = 0; x < _buffer.Width*_ buffer.Height; x++)
> {
> // do manipulations here..
> if( _buffer.Height> 1 ) {
> _buffer.Height= _buffer.Height-1;
> }
> }
>
> Of course there is no sense to shrink a "_buffer" but
> the loop expression should work in this case too.
> Why the compiler have to guess what you have in mind?
>
> Regards
> Marcin
>[/color]

[MariusI]

Re: Lacking for-loop optimization in C#

To be honest there isn't any, but i found an old graphical effect which i had
coded which suffered from the same problems. I hoisted all for-loop variables
and the performance increase was truly impressive. I'll give you the code
whole code for the class, just cut'n paste :-)

// --- Field.cs

using System;
using System.Drawing;
using System.Drawing. Imaging;
using System.Collecti ons;
using System.Componen tModel;
using System.Windows. Forms;
using System.Threadin g;

namespace Field
{
public unsafe sealed class Field : System.Windows. Forms.Form
{
private const int MAXAMP=20, MINAMP=5;

private System.Componen tModel.Containe r components = null;
private Graphics _hDC;
private Bitmap _buffer;
private int _numPixelsInbuf fer;
private int _bufferWidth, _bufferHeight;
private uint [] _palette;
private int [] _hBaseMap, _hRunnerMap;
private Thread _runner;
private bool _done;

public Field()
{
InitializeCompo nent();
this.SetStyle(C ontrolStyles.Al lPaintingInWmPa int | ControlStyles.U serPaint
| ControlStyles.O paque, true);
}

/// <summary>
/// Clean up any resources being used.
/// </summary>
protected override void Dispose( bool disposing )
{
if( disposing )
{
if(components != null)
{
components.Disp ose();
}
}
base.Dispose( disposing );
}

/// <summary>
/// Generates a heightmap
/// </summary>
/// <param name="map">Map to generate</param>
private void generateHeightM ap(ref int [] map, int minamp, int maxamp)
{
Random r = new Random();
int [] xBaseSine = new int[_bufferWidth];

double freqX = r.Next((_buffer Width-10)/5)+10;
int amplitudeX = r.Next(maxamp-minamp)+minamp;
double freqY = r.Next((_buffer Height-10)/5)+10;
int amplitudeY = r.Next(maxamp-minamp)+minamp;

fixed (int* pMap = map, pBase = xBaseSine)
{
int* pM = pMap;
int* pB = pBase;

for (int x = 0; x < _bufferWidth; x++ )
{
*pB = (int)(Math.Sin( x/freqX)*amplitud eX);
pB++;
}

for ( int y = 0; y < _bufferHeight; y++ )
{
pB = pBase;
int yBaseSine = (int)(Math.Sin( y/freqY)*amplitud eY);
for ( int x = 0; x < _bufferWidth; x++ )
{
*pM = yBaseSine+*pB;
pM++; pB++;
}
}
}

}

/// <summary>
/// Initializes our palette with shades of blue
/// </summary>
private uint[] initializePalet te(int size)
{
uint[] palette = new uint[size];
double blueDecrPrStep = 255f/size;
for (int i = 0; i < size; i++)
palette[i] = 0xFF000000 | (byte)(255f-i*blueDecrPrSte p);

return palette;
}

private void run()
{
const int FADE=1, ZEROPOINT = 2*MAXAMP;

bool regenerate = true;
int[] tmpArrayPointer ;

_palette = initializePalet te(4*MAXAMP);
_hRunnerMap = new int[_numPixelsInbuf fer];
_hBaseMap = new int[_numPixelsInbuf fer];

generateHeightM ap(ref _hRunnerMap, MINAMP, MAXAMP);

while(!_done)
{
if (regenerate)
{
tmpArrayPointer = _hBaseMap;
_hBaseMap = _hRunnerMap;
_hRunnerMap = tmpArrayPointer ;
generateHeightM ap(ref _hRunnerMap, MINAMP, MAXAMP);
}
regenerate = true;

fixed (int* pBaseMap = _hBaseMap, pRMap = _hRunnerMap)
{
int* pB = pBaseMap; // phMap is read only
int* pR = pRMap; // prHMap is read only

BitmapData bData = _buffer.LockBit s(new Rectangle(0, 0, _buffer.Width,
_buffer.Height) ,
ImageLockMode.W riteOnly, _buffer.PixelFo rmat);

uint* pPixel = (uint*)bData.Sc an0.ToPointer() ;

for ( int i = 0; i < _numPixelsInbuf fer; i++ )
{
*pPixel = _palette[*pB+ZEROPOINT];
++pPixel;

if (*pR > *pB)
{
*pB += FADE;
regenerate = false;
}
else if (*pR < *pB)
{
*pB -= FADE;
regenerate = false;
}
pB++;
pR++;
}

_buffer.UnlockB its(bData);
}

_hDC.DrawImage( _buffer,0,0);
}
}

#region Windows Form Designer generated code
/// <summary>
/// Required method for Designer support - do not modify
/// the contents of this method with the code editor.
/// </summary>
private void InitializeCompo nent()
{
//
// Field
//
this.AutoScaleB aseSize = new System.Drawing. Size(5, 13);
this.ClientSize = new System.Drawing. Size(492, 371);
this.Name = "Field";
this.Text = "Field";
this.Closing += new
System.Componen tModel.CancelEv entHandler(this .Field_Closing) ;
this.Load += new System.EventHan dler(this.Field _Load);

}
#endregion

private void Field_Load(obje ct sender, System.EventArg s e)
{
_hDC = this.CreateGrap hics();
_buffer = new Bitmap(this.Cli entSize.Width, this.ClientSize .Height, _hDC);
_numPixelsInbuf fer = _buffer.Width*_ buffer.Height;
_bufferWidth = _buffer.Width;
_bufferHeight = _buffer.Height;
_runner = new Thread(new ThreadStart(thi s.run));
_runner.Start() ;
}

private void Field_Closing(o bject sender,
System.Componen tModel.CancelEv entArgs e)
{
_done = true;

// wait for thread to end naturally
while (_runner.IsAliv e) {}
}
}


}


"Willy Denoyette [MVP]" wrote:
[color=blue]
>
> "MariusI" <MariusI@discus sions.microsoft .com> wrote in message
> news:7E6A931D-B8CA-411D-8E91-31BDAA47445B@mi crosoft.com...[color=green]
> >I stumbled over an optimization (or lack of one, to be specific) when
> >viewing
> > IL opcodes generated by the compiler using ms .net 2003. I was testing
> > fast
> > pixel manipulation using Bitmap.LockBits and unsafe pointers to iterate
> > over
> > an image's pixels. The inner-loop looked like this:
> >
> > for (int x = 0; x < _buffer.Width*_ buffer.Height; x++)
> > {
> > // do manipulations here..
> > }
> >
> > I noticed how the for-loop performed extremely slow, and ildasm revealed
> > that the "x < _buffer.Width*_ buffer.Height" was computed at each
> > iteration,
> > resulting in two virtual calls and one mul. The use of /optimize did not
> > improve the matter, so the solution was to calculate
> > _buffer.Width*_ buffer.Height outside of the for-loop. I was under the
> > impression that the compiler performed hoisting automatically, am I
> > missing
> > something here?[/color]
>
> It's not the C# compiler that performs hoisting, it's the JIT compilers that
> does a limited form of hoisting but this depends on what's been done in the
> loop. Mind to share the code in the loop?
>
> Willy.
>
>
>[/color]

[Jon Skeet [C# MVP]]

Re: Lacking for-loop optimization in C#

MariusI <MariusI@discus sions.microsoft .com> wrote:[color=blue]
> To be honest there isn't any, but i found an old graphical effect which i had
> coded which suffered from the same problems. I hoisted all for-loop variables
> and the performance increase was truly impressive. I'll give you the code
> whole code for the class, just cut'n paste :-)[/color]

Ah, I see these are member variables. I suspect that the compiler is
indeed concerned (not unreasonably) about the possibility of them being
modified in a
multi-threaded environment.

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

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

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

[Bruce Wood]

Re: Lacking for-loop optimization in C#

Or, more likely, the compiler has no way of knowing what might cause
the .Width and .Height properties to change, so it did the conservative
thing and left the property fetches in the loop. If you were to change
it to this:

int wid = _buffer.Width;
int high = _buffer.Height;
for (int i = 0; i < wid * high; i++)
{
}

I would be very surprised if the compiler did not optimize and do the
multiply only once. The compiler should know that the _buffer reference
isn't changing, but what it can't know is whether something inside the
loop might not affect the values that _buffer chooses to return for
Width and Height.