Proposal : IEnumerable iteration performance enhancement #3138
Replies: 17 comments
-
|
You could solve the covariance issue by changing the signature to return |
Beta Was this translation helpful? Give feedback.
-
|
I would suggest using BenchmarkDotNet for your benchmarks. In my opinion home grown benchmarking Frameworks are useless. As it happens your benchmark results are clearly impossible:
|
Beta Was this translation helpful? Give feedback.
-
|
@HaloFour Yes, I know that, that why this proposal have request for making covariance type support out parameter As I know (may be wrong, if wrong please clarify) Actually CPU instruction for this 2 method is same(refer from assembly language and c language)
but I'm not sure is C# compiler make it same or not. And Yes, I know this proposal has been discussed before but this proposal has different coding detail. and Yes, struct enumeration can eliminate performance issue, I used it too, but struct has limitation for fast productivity and good scalability language like C#, Java, Python, …. this proposal is concentrate on IEnumerator interface that can give better performance that current one. |
Beta Was this translation helpful? Give feedback.
-
|
@YairHalberstadt normally I test it by my own benchmarking library, it will take shorter time while benchmarking and coding but this is result from BenchmarkDotNet. BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
This is code for benchmarking namespace Benchmark
{
public class Tester
{
const int size = 1_000_000;
int[] array = new int[size];
List<int> list;
OptimizedList<int> oList;
[GlobalSetup]
public void Array_Setup()
{
for (int i = 0, len = size; i < len; ++i)
{
array[i] = i;
}
list = new List<int>(array);
oList = new OptimizedList<int>(array);
}
[Benchmark]
public void Array_For()
{
long result = 0;
var array = this.array;
for (var i = 0; i < size; ++i)
{
result += array[i];
}
}
[Benchmark]
public void Array_Foreach()
{
long result = 0;
foreach (var item in array)
{
result += item;
}
}
[Benchmark]
public void Array_IEnumerable_Foreach()
{
long result = 0;
var e = array.AsEnumerable();
foreach (var item in e)
{
result += item;
}
}
[Benchmark]
public void Foreach_List()
{
double value = 0;
foreach (var v in list)
{
value += v;
}
}
[Benchmark]
public void Foreach_List_IEnumerable()
{
int value = 0;
IEnumerable<int> e = list;
foreach (var v in e)
{
value += v;
}
}
[Benchmark]
public void OptimizedList_Iteration()
{
long result = 0;
using (var e = oList.GetEnumerator())
{
while (e.TryGetNext(out int value))
{
result += value;
}
}
}
[Benchmark]
public void OptimizedList_Interface_Iteration()
{
long result = 0;
IFastEnumerable<int> fe = oList;
using (var e = fe.GetEnumerator())
{
while (e.TryGetNext(out int value))
{
result += value;
}
}
}
}
}Yes, This optimized interface still cannot be inlined but it take less virtual method calling for each iteration, so it take less overhead, this optimized IEnumeration call only 1 virtual method(TryGetNext) for each iteration but current IEnumerator call 2 virtual methods(MoveNext and get_Current) for each iteration. |
Beta Was this translation helpful? Give feedback.
-
|
Thanks for that - as you can see the results are significantly different compared to the previous results, and make much more sense. However you're not comparing apples to apples here. The list iterator has some logic to make sure it doesn't update the list during iteration. That is why it's so much slower than array. Your enumerator doesn't do that, so isn't comparable to the list enumerator. |
Beta Was this translation helpful? Give feedback.
-
|
Also, in some cases you're adding to a long, in others an int, and in one a double. They have to be consistent. |
Beta Was this translation helpful? Give feedback.
-
BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
namespace Benchmark
{
public class Tester
{
const int size = 1_000_000;
int[] array = new int[size];
List<int> list;
OptimizedList<int> oList;
[GlobalSetup]
public void Array_Setup()
{
for (int i = 0, len = size; i < len; ++i)
{
array[i] = i;
}
list = new List<int>(array);
oList = new OptimizedList<int>(array);
}
[Benchmark]
public void Array_For()
{
long result = 0;
var array = this.array;
for (var i = 0; i < size; ++i)
{
result += array[i];
}
}
[Benchmark]
public void Array_Foreach()
{
long result = 0;
foreach (var item in array)
{
result += item;
}
}
[Benchmark]
public void Array_IEnumerable_Foreach()
{
long result = 0;
var e = array.AsEnumerable();
foreach (var item in e)
{
result += item;
}
}
[Benchmark]
public void Foreach_List()
{
long value = 0;
foreach (var v in list)
{
value += v;
}
}
[Benchmark]
public void Foreach_List_IEnumerable()
{
long value = 0;
IEnumerable<int> e = list;
foreach (var v in e)
{
value += v;
}
}
[Benchmark]
public void OptimizedList_Iteration()
{
long result = 0;
using (var e = oList.GetEnumerator())
{
while (e.TryGetNext(out int value))
{
result += value;
}
}
}
[Benchmark]
public void OptimizedList_Interface_Iteration()
{
long result = 0;
IFastEnumerable<int> fe = oList;
using (var e = fe.GetEnumerator())
{
while (e.TryGetNext(out int value))
{
result += value;
}
}
}
}
}
namespace ExtremeCore.Collections
{
public class OptimizedList<T> : IFastEnumerable<T>
{
private const int defaultCapacity = 4;
private T[] items;
private int size;
private int version;
public OptimizedList()
{
items = new T[defaultCapacity];
}
public OptimizedList(T[] source)
{
int size = source.Length;
items = new T[size];
Array.Copy(source, 0, items, 0, size);
this.size = size;
}
public int Size => size;
public T this[int index]
{
get
{
if ((uint)index >= (uint)size)
ThrowIndexOutOfRange();
return items[index];
}
set
{
if ((uint)index >= (uint)size)
ThrowIndexOutOfRange();
items[index] = value;
++version;
}
}
public void Add(T item)
{
int size = this.size;
if (size >= items.Length)
{
int newCapacity = size * 2;
if (newCapacity < 0)
{
if (size < int.MaxValue)
newCapacity = int.MaxValue;
else
ThrowExceedLimitedSize();
}
Array.Resize(ref items, newCapacity);
}
items[size] = item;
this.size = size + 1;
++version;
}
public void InsertAt(T item, int index)
{
int size = this.size;
if ((uint)index >= (uint)size)
ThrowIndexOutOfRange();
if (size >= items.Length)
{
int newCapacity = size * 2;
if (newCapacity < 0)
{
if (size < int.MaxValue)
newCapacity = int.MaxValue;
else
ThrowExceedLimitedSize();
}
Array.Resize(ref items, newCapacity);
}
Array.Copy(items, index, items, index + 1, size - index);
items[index] = item;
this.size = size + 1;
++version;
}
public bool RemoveFirst(T item)
{
T[] items = this.items;
for (int i = 0, size = this.size; i < size; ++i)
{
if (EqualityComparer<T>.Default.Equals(item, items[i]))
{
--size;
if (i < size)
{
Array.Copy(items, i + 1, items, i, size - i);
}
items[size] = default;
this.size = size;
++version;
return true;
}
}
return false;
}
public bool RemoveLast(T item)
{
T[] items = this.items;
for (int size = this.size, i = size - 1; i > 0; --i)
{
if (EqualityComparer<T>.Default.Equals(item, items[i]))
{
--size;
if (i < size)
{
Array.Copy(items, i + 1, items, i, size - i);
}
items[size] = default;
this.size = size;
++version;
return true;
}
}
return false;
}
public bool RemoveAll(T item)
{
bool isRemoved = false;
T[] items = this.items;
for (int i = 0, size = this.size; i < size; ++i)
{
if (EqualityComparer<T>.Default.Equals(item, items[i]))
{
--size;
if (i < size)
{
Array.Copy(items, i + 1, items, i, size - i);
}
items[size] = default;
this.size = size;
isRemoved = true;
}
}
if (isRemoved)
{
++version;
return true;
}
return false;
}
public ValueEnumerator GetEnumerator()
{
return new ValueEnumerator(this);
}
IFastEnumerator<T> IFastEnumerable<T>.GetEnumerator()
{
return new Enumerator(this);
}
private static void ThrowIndexOutOfRange()
{
throw new IndexOutOfRangeException("Access fault, Index is out of range.");
}
private static void ThrowExceedLimitedSize()
{
throw new OverflowException("Addition fault, Size is already reached the limited.");
}
private static void ThrowMismatchedVersion()
{
throw new InvalidOperationException("Iteration fault, Source element has been changed while iterating.");
}
IFastEnumerator IFastEnumerable.GetEnumerator()
{
return new Enumerator(this);
}
public ref struct ValueEnumerator
{
private OptimizedList<T> source;
private int index, version;
public ValueEnumerator(OptimizedList<T> source)
{
index = 0;
this.source = source;
version = source.version;
}
public void Dispose() { }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public bool TryGetNext(out T next)
{
if (source.version != version)
ThrowMismatchedVersion();
int i = index;
if (i < source.size)
{
index = i + 1;
next = source.items[i];
return true;
}
else
{
next = default;
return false;
}
}
}
public sealed class Enumerator : IFastEnumerator<T>
{
private OptimizedList<T> source;
private int index, version;
public Enumerator(OptimizedList<T> source)
{
index = 0;
this.source = source;
version = source.version;
}
public void Dispose() { }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public bool TryGetNext(out T next)
{
if (source.version != version)
ThrowMismatchedVersion();
int i = index;
if (i < source.size)
{
index = i + 1;
next = source.items[i];
return true;
}
else
{
next = default;
return false;
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public bool TryGetNext(out object next)
{
if (source.version != version)
ThrowMismatchedVersion();
int i = index;
if (i < source.size)
{
index = i + 1;
next = source.items[i];
return true;
}
else
{
next = default;
return false;
}
}
}
}
} |
Beta Was this translation helpful? Give feedback.
-
|
Thanks @NutzNK that's much better. Next precisely what language changes are you requesting? Am I right they are:
Do you think generator support is necessary as well? I think my chief problem here is that the cost of enumerating is small enough that you need to make sure that IFastEnumerator is used everywhere to see much of a gain. Just adding it is not enough - you need to try to migrate existing code towards using it. I tried to suggest such a path here, but I don't think that would actually work. In terms of improving Linq performance, I would suggest something closer to this would actually have a far bigger impact. |
Beta Was this translation helpful? Give feedback.
-
Interface is public interface IFastEnumerator<out T>
{
T TryGetNext(out bool success);
}then Iteration code behind will be like this using (var enumerator = object.GetEnumerator())
{
T value = enumerator.TryGetNext(out bool hasNext);
while (hasNext)
{
//code in loop here
}
}but my code will iterate like this using(var enumerator = object.GetEnumerator())
{
while(enumerator.TryGetNext(out var value))
{
//code in loop here
}
}this code gain better performance on struct Enumerator
|
Beta Was this translation helpful? Give feedback.
-
|
Note that out parameters don't actually exist in the runtime - they exist in C# only. From the runtime perspective they are just ordinary ref parameters. Thus this proposal would require runtime and language changes. |
Beta Was this translation helpful? Give feedback.
-
|
@YairHalberstadt |
Beta Was this translation helpful? Give feedback.
-
|
@NutzNK covariance is defined by the runtime, and ref in general is not covariant. So the runtime would need to recognize out, and make it covariant. I imagine that's not a small amount of work. |
Beta Was this translation helpful? Give feedback.
-
|
@YairHalberstadt ok, if it need to much work for work around this interface then I also have alternative way to do that but I'm not sure is it easier way to change or not. use abstract instead of interface, it should be like this public abstract class Enumerator
{
public abstract object Current { get; }
public abstract bool MoveNext();
}
public abstract class Enumerator<T> : Enumerator, IDisposable
{
protected T current;
public new T Current
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
get => current;
}
public override object Enumerator.Current => current;
public void Dispose() { }
}but problem is Abstract class still not be able to declare method like this "public override object Enumerator.Current => current;" this code will override only base class like interface. |
Beta Was this translation helpful? Give feedback.
-
|
i belive that the shapes proposal would likely subsume this. |
Beta Was this translation helpful? Give feedback.
-
|
@CyrusNajmabadi For me so many issues will be solved if C# can make same thing as "Trait" in Rust language. |
Beta Was this translation helpful? Give feedback.
-
|
@YairHalberstadt Now I found better way to do it. This is Benchmarking table BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
The key is these code public interface IEnumerator
{
object Current { get; }
bool MoveNext();
}
public interface IEnumerator<out T> : IEnumerator
{
new T Current { get; }
}
public unsafe abstract class Enumerator : IEnumerator
{
protected Reference current;
public object Current
{
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
get
{
return current.ToValue();
}
}
public abstract bool MoveNext();
}
public unsafe abstract class Enumerator<T> : Enumerator, IEnumerator<T>
{
public new T Current
{
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
get
{
return current.ToValue<T>();
}
}
}
public interface IEnumerable
{
Enumerator GetEnumerator();
}
public interface IEnumerable<T>
{
Enumerator<T> GetEnumerator();
}
public static class EnumerableExtension
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static IEnumerable<T> AsEnumerable<T>(this IEnumerable<T> source)
{
return source;
}
}I create new struct And this is Enumerator inside public ref struct ValueEnumerator
{
private Reference<T> current, end;
private Reference<int> source_version;
private int version;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public ValueEnumerator(ExtremeList<T> source)
{
current = new Reference<T>(ref source.items[0]);
end = current + source.size;
--current;
source_version = new Reference<int>(ref source.version);
version = source.version;
}
public T Current
{
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
get
{
return current.Value;
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
public bool MoveNext()
{
if (source_version.Value != version)
ThrowMismatchedVersion();
++current;
if (current < end)
{
return true;
}
--current;
return false;
}
}
public unsafe sealed class Enumerator : Enumerator<T>
{
private Reference end;
private Reference<int> source_version;
private int version;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public Enumerator(ExtremeList<T> source)
{
var origin = Reference.New(ref source.items[0]);
end = origin.Add<T>(source.size);
current = origin.Previous<T>();
source_version = new Reference<int>(ref source.version);
version = source.version;
}
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
public override bool MoveNext()
{
if (source_version.Value != version)
ThrowMismatchedVersion();
var next = current.Next<T>();
if (next < end)
{
current = next;
return true;
}
return false;
}
} |
Beta Was this translation helpful? Give feedback.
-
|
Nice proposal, but I can't help but wonder about coupling MoveNext() and Current property into a single unit, because there are many cases in the framework, where MoveNext() is called repeatedly without any use of the Current item (e.g., Enumerable.Count(), Skip(), etc.). Since most of the LINQ iterators do a lot of work in MoveNext(), including getting the value of the Current property from the input/source, it may not matter much. However, I have diverged from that pattern, and use a lazy pattern for producing the value of the Current property, which has a noticeable effect on Count() and other cases where MoveNext() is repeatedly called without the use of the Current property. The example above also uses this pattern to some extent, as it doesn't do any needless work in its MoveNext(). A distilled example of the pattern: Have you tested the time of an equivalent of Count() on your prototype? |
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
-
We have performance issue on IEnumerable interface.
because IEnumerable take several times slower than array iteration.
problem is when collection has been casted to IEnumerable or return IEnumerable by some function, foreach iteration will iterate IEnumerator interface from method "MoveNext" and property "Current", these methods and property cannot do inlining and there are overhead for 2 methods calling.
I would suggest supported equivalent code for "Foreach" like this
with this optimized enumerator
This is example of collection class with optimized enumerator
this class iteration performance is close to array iteration and better than standard IEnumerator when it casted to IEnumerable().
but the next problem is this optimized enumerator interface contains method with "out" parameter(s) that mean this interface is not support co-variant type yet.
then I would suggest to co-variant type should support type that contains method with "out" parameter(s).
These are test performance on .NET core 3.1 with 1,000,000 loop of int accumulation.
Array_For => Min : 0.495 msec, Average : 0.530 msec, Median : 0.519 msec.
Array_Foreach => Min : 0.997 msec, Average : 1.082 msec, Median : 1.035 msec.
IEnumerable(Array)_Foreach => Min : 3.267 msec, Average : 4.115 msec, Median : 4.135 msec.
List_Foreach => Min : 2.247 msec, Average : 2.337 msec, Median : 2.300 msec.
IEnumerable(List)_Foreach => Min : 5.397 msec, Average : 5.693 msec, Median : 5.669 msec.
OptimizedList_Foreach => Min : 0.495 msec, Average : 0.528 msec, Median : 0.509 msec.
IEnumerable(OptimizedList)_Foreach => Min : 1.979 msec, Average : 2.090 msec, Median : 2.025 msec.
Beta Was this translation helpful? Give feedback.
All reactions