Tuesday, June 9, 2009

Code Generator Oddity

The following is a exerpted example of my implementation of a well-known permutation algorithm. Note the code generation oddity flagged by the comment. This occurs in .NET 3.5 and Visual C# 2008. I leave the solution to the mystery to readers who like to disassemble and read MSIL, and think about what the JIT compiler may do to it.

protected static void Permute <TDatum> (
int beginIn,
int endIn,
TDatum[] dataIn,
Action<TDatum[]> dataActionIn)
where TDatum : IComparable
{
TDatum xDatumBegin;

if ((endIn-beginIn)<=1)
{
dataActionIn(dataIn);
}
else
{
Permute(
beginIn+1,
endIn,
dataIn,
dataActionIn);

for (int i=beginIn+1; i<endIn; i++)
{
xDatumBegin = dataIn[beginIn];

dataIn[beginIn] = dataIn[i];
dataIn[i] = xDatumBegin;

Permute(
beginIn+1,
endIn,
dataIn,
dataActionIn);

// Believe it or not, the compiler/loader
// will optimize the first block below
// to be almost 10% faster than the second.

#if thisIsFasterInDotNet
xDatumBegin = dataIn[beginIn];
dataIn[beginIn] = dataIn[i];
dataIn[i] = xDatumBegin;
#else
dataIn[i] = dataIn[beginIn];
dataIn[beginIn] = xDatumBegin;
#endif
}
}
}

No comments: