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]

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:

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?

[Marcin Grzębski]

Hi MariusI,

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,

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]

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:

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:

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]

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:

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:

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:

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?

[Ian Griffiths [C# MVP]]

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" <Ma*****@discus sions.microsoft .com> wrote in message
news:7E******** *************** ***********@mic rosoft.com...

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?

[Willy Denoyette [MVP]]

"MariusI" <Ma*****@discus sions.microsoft .com> wrote in message
news:7E******** *************** ***********@mic rosoft.com...

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?

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]

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:

Hi MariusI,

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,

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]

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:

"MariusI" <Ma*****@discus sions.microsoft .com> wrote in message
news:7E******** *************** ***********@mic rosoft.com...

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?

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.

[Jon Skeet [C# MVP]]

MariusI <Ma*****@discus sions.microsoft .com> wrote:

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

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 - <sk***@pobox.co m>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too