为什么名单＆LT; T＆GT; .Enumerator比我更快的实现？ [英] Why is List<T>.Enumerator faster than my implementation?
问题描述
我发现自己在一个位置，我必须推出自己的动态数组实现，因为各种大型演出的好处（对我来说）。但是，对于我的版本创建一个枚举，并比较效率的一个列表使用后，我有点不知所措;列表中的一个是aproximately比我的版本快30％-40％，即使它要复杂得多。
I've found myself in a position where I have to roll my own dynamic array implementation, due to various large performance benefits (in my case). However, after creating an enumerator for my version, and comparing the efficiency with the one List uses, I'm a bit bewildered; the List one is aproximately 30-40% faster than my version, even though it's much more complex.
下面的列表枚举实施的重要组成部分：
Here's the important part of the List enumerator implementation:
public struct Enumerator : IEnumerator<T>, IDisposable, IEnumerator
{
private List<T> list;
private int index;
private int version;
private T current;
internal Enumerator(List<T> list)
{
this.list = list;
this.index = 0;
this.version = list._version;
this.current = default(T);
return;
}
public bool MoveNext()
{
List<T> list;
list = this.list;
if (this.version != list._version)
{
goto Label_004A;
}
if (this.index >= list._size)
{
goto Label_004A;
}
this.current = list._items[this.index];
this.index += 1;
return 1;
Label_004A:
return this.MoveNextRare();
}
public T Current
{
get { return this.current; }
}
}
这是我非常准系统版本：
And here's my very barebone version:
internal struct DynamicArrayEnumerator<T> : IEnumerator<T> where T : class
{
private readonly T[] internalArray;
private readonly int lastIndex;
private int currentIndex;
internal DynamicArrayEnumerator(DynamicArray<T> dynamicArray)
{
internalArray = dynamicArray.internalArray;
lastIndex = internalArray.Length - 1;
currentIndex = -1;
}
public T Current
{
get { return internalArray[currentIndex]; }
}
public bool MoveNext()
{
return (++currentIndex <= lastIndex);
}
}
我知道这是微优化，但我理解真正感兴趣，为什么名单枚举比我快多了。有任何想法吗？谢谢！
I know this is micro-optimization, but I'm actually interested in understanding why the List enumerator is so much faster than mine. Any ideas? Thanks!
编辑： 按照要求;在DynamicArray类（相关部分）： 调查员在这个内部类。
As requested; the DynamicArray class (the relevant parts): The enumerator is an inner class in this.
public struct DynamicArray<T> : IEnumerable<T> where T : class
{
private T[] internalArray;
private int itemCount;
internal T[] Data
{
get { return internalArray; }
}
public int Count
{
get { return itemCount; }
}
public DynamicArray(int count)
{
this.internalArray = new T[count];
this.itemCount = 0;
}
public IEnumerator<T> GetEnumerator()
{
return new DynamicArrayEnumerator<T>(this);
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
至于我是如何测试：
As for how I'm testing:
List<BaseClass> list = new List<BaseClass>(1000000);
DynamicArray<BaseClass> dynamicArray = new DynamicArray<BaseClass>(1000000);
// Code for filling with data omitted.
int numberOfRuns = 0;
float p1Total = 0;
float p2Total = 0;
while (numberOfRuns < 100)
{
PerformanceAnalyzer p1 = new PerformanceAnalyzer(() =>
{
int u = 0;
foreach (BaseClass b in list)
{
if (b.B > 100) // Some trivial task
u++;
}
});
p1.ExecuteAndClock();
p1Total += p1.TotalElapsedTicks;
PerformanceAnalyzer p2 = new PerformanceAnalyzer(() =>
{
int u = 0;
foreach (BaseClass b in dynamicArray)
{
if (b.B > 100) // Some trivial task
u++;
}
});
p2.ExecuteAndClock();
p2Total += p2.TotalElapsedTicks;
numberOfRuns++;
}
Console.WriteLine("List enumeration: " + p1Total / totalRuns + "\n");
Console.WriteLine("Dynamic array enumeration: " + p2Total / totalRuns + "\n");
在PerformanceAnalyzer类基本启动秒表，执行所提供的Action委托，然后随后停止秒表。
The PerformanceAnalyzer class basically starts a Stopwatch, execute the supplied Action delegate, and then stop the Stopwatch afterwards.
编辑2（快速回答瑞恩·盖茨）： 有几个原因，我想推出自己的，最重要的是我需要一个非常快的RemoveAt（INT指数）的方法。
Edit 2 (Quick answer to Ryan Gates): There's a few reasons why I would want to roll my own, most importantly I need a very fast RemoveAt(int index) method.
由于我不担心在我的具体情况列表元素的顺序，我能避免这样做的净内置列表的方式：
Since I don't have to worry about the order of the list elements in my particular case, I can avoid the .Net built-in list's way of doing it:
public void RemoveAt(int index)
{
T local;
if (index < this._size)
{
goto Label_000E;
}
ThrowHelper.ThrowArgumentOutOfRangeException();
Label_000E:
this._size -= 1;
if (index >= this._size)
{
goto Label_0042;
}
Array.Copy(this._items, index + 1, this._items, index, this._size - index);
Label_0042:
this._items[this._size] = default(T);
this._version += 1;
return;
}
和使用，而不是沿着线的东西：
And instead using something along the lines of:
public void RemoveAt(int index)
{
// overwrites the element at the specified index with the last element in the array and decreases the item count.
internalArray[index] = internalArray[itemCount];
itemCount--;
}
Potencially节省了我的情况下大量的时间，如果说，在很长的列表中的第1000个元素都被索引中删除。
Potencially saving enormous amounts of time in my case, if say the first 1000 elements in a long list have to be removed by index.
推荐答案
好了，除了基准的问题，这里是你如何让你的 DynamicArray 类更像列表＆LT; T＆GT; ：
Okay, aside from benchmarking problems, here's how you can make your DynamicArray class more like List<T>:
public DynamicArrayEnumerator<T> GetEnumerator()
{
return new DynamicArrayEnumerator<T>(this);
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
return GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
现在，code其中的知道的它是一个动态数组的工作可以用 DynamicArrayEnumerator＆LT迭代; T＆GT; 的没有任何拳击，没有虚拟调度的。这正是名单，其中，T＆GT; 一样。编译器通知，当一个类型实现的模式的在一个自定义的方式，而且将使用参与，而不是接口类型。
Now, code which knows it's working with a dynamic array can iterate with a DynamicArrayEnumerator<T> without any boxing, and without virtual dispatch. This is exactly what List<T> does. The compiler notices when a type implements the pattern in a custom manner, and will use the types involved instead of the interfaces.
使用您的电流的code，你得到任何好处从创建一个结构 - 因为你拳击它的GetEnumerator（）。
With your current code, you're getting no benefit from creating a struct - because you're boxing it in GetEnumerator().
尝试上述变化的和的固定基准工作更长的时间。我希望看到一个很大的区别。
Try the above change and fix the benchmark to work for longer. I'd expect to see a big difference.
这篇关于为什么名单＆LT; T＆GT; .Enumerator比我更快的实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
