I've been implementing numerical libraries in .NET and have come to some conclusions about iteration performance. My classes have to hold a large amount of data and be able to iterate through that data as quickly as possible. In order to compare various methods, I created a simple class called Data that encapsulates an array of doubles.
Download source - 6 Kb
Method #1: Enumeration
Data implements IEnumerable. It contains GetEnumerator which returns its own DataEnumerator, an inner class.
public IEnumerator GetEnumerator()
{
returnnew DataEnumerator(this);
}
internalclass DataEnumerator : IEnumerator
{
private Data internal_=null;
privateintindex=-1;
public DataEnumerator( Data data)
{
internal_=data;
}
publicobject Current
{
get
{
returninternal_.Array[index];
}
}
publicbool MoveNext()
{
index++;
if(index >=internal_.Array.Length )
{
returnfalse;
}
returntrue;
}
publicvoid Reset()
{
index=-1;
}
}
Method #2: Indexing
I implemented an index operator on the class which simply calls the index operator on the array.
publicdoublethis[intposition]
{
get
{
returnarray_[position];
}
}
Method #3: Indirect Array
I created a property to access the array.
publicdouble[] Array
{
get
{
returnarray_;
}
}
When iterating, I called the Array property and then its index operator.
d = data.Array[j];
Method #3: Direct Array
I created a reference to the array.
double[] array = data.Array;
Then, I iterate through that reference.
d = array[j];
Method #4: Pointer Math
Finally, I tried improving performance by iterating through the array in Managed C++ using pointer manipulation.
staticvoiditerate( Data&data)
{
double d;
double__pin*ptr=&(data.Array[0]);
for(int i =0; i < data.Array.Length; i++)
{
d =*ptr;
++ptr;
}
}
I called it this way:
Pointer.iterate( data );
Conclusions
To test the different methods, I allocated 1,000,000 doubles into an array and indexed over all of them. I repeated this 1,000 times to minimize randomness. Here are the results...
Enumeration is always slow. That's not surprising as I'm using a general data structure to hold the doubles. Each access performs a cast. The three operator/property methods differed very slightly. These are probably all optimized similarly. Using pointer math to traverse over the raw data was significantly faster. This is probably due to the fact that there's no bounds checking. In summary, if you have large amounts of data and performance is critical, consider using managed C++.
超级collection类:
using System;
using System.Collections;
namespace Iterations
{
public class Data : IEnumerable
{
private double[] array_;
public Data(int size)
{
array_ = new double[size];
Random random = new Random();
for ( int i = 0; i < size; i++ )
{
array_[i] = random.Next();
}
}
public double this[int position]
{
get
{
return array_[position];
}
}
public double[] Array
{
get
{
return array_;
}
}
public IEnumerator GetEnumerator()
{
return new DataEnumerator( this );
}
internal class DataEnumerator : IEnumerator
{
private Data internal_ = null;
private int index = -1;
public DataEnumerator( Data data )
{
internal_ = data;
}
public object Current
{
get
{
return internal_.Array[index];
}
}
public bool MoveNext()
{
index++;
if ( index >= internal_.Array.Length )
{
return false;
}
return true;
}
public void Reset()
{
index = -1;
}
}
}
}test code:
using System;
using System.Collections;
using Iterations;
namespace Test
{
class Test
{
private double d;
private int reps;
private int size;
private double seconds;
private Data data = null;
private DateTime before;
private TimeSpan total;
[STAThread]
static void Main(string[] args)
{
Test test;
if ( args.Length > 1 )
{
test = new Test( int.Parse( args[0] ), int.Parse( args[1] ));
}
else
{
test = new Test();
}
test.TestAll();
}
public Test() : this( 1000, 1000000 )
{
}
public Test( int reps, int size )
{
this.reps = reps;
this.size = size;
data = new Data( size );
}
private void TestAll()
{
System.Console.WriteLine();
System.Console.WriteLine( "repetitions: " + reps );
System.Console.WriteLine( "iterations: " + size.ToString( "e" ));
System.Console.WriteLine();
TestEnumeration();
TestIndexing();
TestIndirectArrays();
TestDirectArrays();
TestPointerMath();
System.Console.WriteLine();
}
private void TestEnumeration()
{
total = new TimeSpan( 0 );
for ( int i = 0; i < reps; i++ )
{
before = DateTime.Now;
IEnumerator enumerator = data.GetEnumerator();
while ( enumerator.MoveNext() )
{
d = (double) enumerator.Current;
}
total += DateTime.Now - before;
}
seconds = total.Seconds + ( total.Milliseconds / 1000.0 );
System.Console.WriteLine( "Enumeration: \t\t" + seconds + " seconds" );
}
private void TestIndexing()
{
total = new TimeSpan( 0 );
for ( int i = 0; i < reps; i++ )
{
before = DateTime.Now;
for ( int j = 0; j < size; j++ )
{
d = data[j];
}
total += DateTime.Now - before;
}
seconds = total.Seconds + ( total.Milliseconds / 1000.0 );
System.Console.WriteLine( "Indexing: \t\t" + seconds + " seconds" );
}
private void TestIndirectArrays()
{
total = new TimeSpan( 0 );
for ( int i = 0; i < reps; i++ )
{
before = DateTime.Now;
for ( int j = 0; j < size; j++ )
{
d = data.Array[j];
}
total += DateTime.Now - before;
}
seconds = total.Seconds + ( total.Milliseconds / 1000.0 );
System.Console.WriteLine( "Indirect Arrays: \t" + seconds + " seconds" );
}
private void TestDirectArrays()
{
total = new TimeSpan( 0 );
for ( int i = 0; i < reps; i++ )
{
before = DateTime.Now;
double[] array = data.Array;
for ( int j = 0; j < size; j++ )
{
d = array[j];
}
total += DateTime.Now - before;
}
seconds = total.Seconds + ( total.Milliseconds / 1000.0 );
System.Console.WriteLine( "Direct Arrays: \t\t" + seconds + " seconds" );
}
private void TestPointerMath()
{
total = new TimeSpan( 0 );
for ( int i = 0; i < reps; i++ )
{
before = DateTime.Now;
Pointer.iterate( data );
total += DateTime.Now - before;
}
seconds = total.Seconds + ( total.Milliseconds / 1000.0 );
System.Console.WriteLine( "Pointer Math: \t\t" + seconds + " seconds" );
}
}
}