public class Group { public string Name { get; set; } }
Test:
List<Group> _groups = new List<Group>(); for (int i = 0; i < 10000; i++) { var group = new Group(); group.Name = i + "asdasdasd"; _groups.Add(group); } Stopwatch _stopwatch2 = new Stopwatch(); _stopwatch2.Start(); foreach (var group in _groups) { var count = _groups.Count(x => x.Name == group.Name); } _stopwatch2.Stop(); Console.WriteLine(_stopwatch2.ElapsedMilliseconds); Stopwatch _stopwatch = new Stopwatch(); _stopwatch.Start(); foreach (var group in _groups) { var count = _groups.Where(x => x.Name == group.Name).Count(); } _stopwatch.Stop(); Console.WriteLine(_stopwatch.ElapsedMilliseconds);
Result: First: 2863, Second 2185
Can someone explain me why first approach is slower than second? Second should return enumerator and invoke count on it and first just invoke count. First approach should be a little faster.
EDIT: I removed counter lists to prevent using GC and changed order to check if ordering has meaning. Results are almost the same.
EDIT2: This performance problem is not related only with Count. It's related with First(),FirstOrDefault(), Any(), etc.. Where + Method is always faster than Method.
Across the array sizes the Any is roughly 1/3 faster than using Count .
LINQ syntax is typically less efficient than a foreach loop. It's good to be aware of any performance tradeoff that might occur when you use LINQ to improve the readability of your code. And if you'd like to measure the performance difference, you can use a tool like BenchmarkDotNet to do so.
No, LINQ iterators are not and will never be faster than foreach .
Count<TSource>(IEnumerable<TSource>) Returns the number of elements in a sequence.
The crucial thing is in the implementation of Where()
where it casts the IEnumerable
to a List<T>
if it can. Note the cast where WhereListIterator
is constructed (this is from .Net source code obtained via reflection):
public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) { if (source is List<TSource>) return new WhereListIterator<TSource>((List<TSource>)source, predicate); return new WhereEnumerableIterator<TSource>(source, predicate); }
I have verified this by copying (and simplifying where possible) the .Net implementations.
Crucially, I implemented two versions of Count()
- one called TestCount()
where I use IEnumerable<T>
, and one called TestListCount()
where I cast the enumerable to List<T>
before counting the items.
This gives the same speedup as we see for the Where()
operator which (as shown above) also casts to List<T>
where it can.
(This should be tried with a release build without a debugger attached.)
This demonstrates that it is faster to use foreach
to iterate over a List<T>
compared to the same sequence represented via a IEnumerable<T>
.
Firstly, here's the complete test code:
using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.Linq; namespace Demo { public class Group { public string Name { get; set; } } internal static class Program { static void Main() { int dummy = 0; List<Group> groups = new List<Group>(); for (int i = 0; i < 10000; i++) { var group = new Group(); group.Name = i + "asdasdasd"; groups.Add(group); } Stopwatch stopwatch = new Stopwatch(); for (int outer = 0; outer < 4; ++outer) { stopwatch.Restart(); foreach (var group in groups) dummy += TestWhere(groups, x => x.Name == group.Name).Count(); Console.WriteLine("Using TestWhere(): " + stopwatch.ElapsedMilliseconds); stopwatch.Restart(); foreach (var group in groups) dummy += TestCount(groups, x => x.Name == group.Name); Console.WriteLine("Using TestCount(): " + stopwatch.ElapsedMilliseconds); stopwatch.Restart(); foreach (var group in groups) dummy += TestListCount(groups, x => x.Name == group.Name); Console.WriteLine("Using TestListCount(): " + stopwatch.ElapsedMilliseconds); } Console.WriteLine("Total = " + dummy); } public static int TestCount<TSource>(IEnumerable<TSource> source, Func<TSource, bool> predicate) { int count = 0; foreach (TSource element in source) { if (predicate(element)) count++; } return count; } public static int TestListCount<TSource>(IEnumerable<TSource> source, Func<TSource, bool> predicate) { return testListCount((List<TSource>) source, predicate); } private static int testListCount<TSource>(List<TSource> source, Func<TSource, bool> predicate) { int count = 0; foreach (TSource element in source) { if (predicate(element)) count++; } return count; } public static IEnumerable<TSource> TestWhere<TSource>(IEnumerable<TSource> source, Func<TSource, bool> predicate) { return new WhereListIterator<TSource>((List<TSource>)source, predicate); } } class WhereListIterator<TSource>: Iterator<TSource> { readonly Func<TSource, bool> predicate; List<TSource>.Enumerator enumerator; public WhereListIterator(List<TSource> source, Func<TSource, bool> predicate) { this.predicate = predicate; this.enumerator = source.GetEnumerator(); } public override bool MoveNext() { while (enumerator.MoveNext()) { TSource item = enumerator.Current; if (predicate(item)) { current = item; return true; } } Dispose(); return false; } } abstract class Iterator<TSource>: IEnumerable<TSource>, IEnumerator<TSource> { internal TSource current; public TSource Current { get { return current; } } public virtual void Dispose() { current = default(TSource); } public IEnumerator<TSource> GetEnumerator() { return this; } public abstract bool MoveNext(); object IEnumerator.Current { get { return Current; } } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } void IEnumerator.Reset() { throw new NotImplementedException(); } } }
Now here's the IL generated for the two crucial methods, TestCount():
and testListCount()
. Remember that the only difference between these is that TestCount()
is using the IEnumerable<T>
and testListCount()
is using the same enumerable, but cast to its underlying List<T>
type:
TestCount(): .method public hidebysig static int32 TestCount<TSource>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!TSource> source, class [mscorlib]System.Func`2<!!TSource, bool> predicate) cil managed { .maxstack 8 .locals init ( [0] int32 count, [1] !!TSource element, [2] class [mscorlib]System.Collections.Generic.IEnumerator`1<!!TSource> CS$5$0000) L_0000: ldc.i4.0 L_0001: stloc.0 L_0002: ldarg.0 L_0003: callvirt instance class [mscorlib]System.Collections.Generic.IEnumerator`1<!0> [mscorlib]System.Collections.Generic.IEnumerable`1<!!TSource>::GetEnumerator() L_0008: stloc.2 L_0009: br L_0025 L_000e: ldloc.2 L_000f: callvirt instance !0 [mscorlib]System.Collections.Generic.IEnumerator`1<!!TSource>::get_Current() L_0014: stloc.1 L_0015: ldarg.1 L_0016: ldloc.1 L_0017: callvirt instance !1 [mscorlib]System.Func`2<!!TSource, bool>::Invoke(!0) L_001c: brfalse L_0025 L_0021: ldloc.0 L_0022: ldc.i4.1 L_0023: add.ovf L_0024: stloc.0 L_0025: ldloc.2 L_0026: callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext() L_002b: brtrue.s L_000e L_002d: leave L_003f L_0032: ldloc.2 L_0033: brfalse L_003e L_0038: ldloc.2 L_0039: callvirt instance void [mscorlib]System.IDisposable::Dispose() L_003e: endfinally L_003f: ldloc.0 L_0040: ret .try L_0009 to L_0032 finally handler L_0032 to L_003f } testListCount(): .method private hidebysig static int32 testListCount<TSource>(class [mscorlib]System.Collections.Generic.List`1<!!TSource> source, class [mscorlib]System.Func`2<!!TSource, bool> predicate) cil managed { .maxstack 8 .locals init ( [0] int32 count, [1] !!TSource element, [2] valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<!!TSource> CS$5$0000) L_0000: ldc.i4.0 L_0001: stloc.0 L_0002: ldarg.0 L_0003: callvirt instance valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<!0> [mscorlib]System.Collections.Generic.List`1<!!TSource>::GetEnumerator() L_0008: stloc.2 L_0009: br L_0026 L_000e: ldloca.s CS$5$0000 L_0010: call instance !0 [mscorlib]System.Collections.Generic.List`1/Enumerator<!!TSource>::get_Current() L_0015: stloc.1 L_0016: ldarg.1 L_0017: ldloc.1 L_0018: callvirt instance !1 [mscorlib]System.Func`2<!!TSource, bool>::Invoke(!0) L_001d: brfalse L_0026 L_0022: ldloc.0 L_0023: ldc.i4.1 L_0024: add.ovf L_0025: stloc.0 L_0026: ldloca.s CS$5$0000 L_0028: call instance bool [mscorlib]System.Collections.Generic.List`1/Enumerator<!!TSource>::MoveNext() L_002d: brtrue.s L_000e L_002f: leave L_0042 L_0034: ldloca.s CS$5$0000 L_0036: constrained [mscorlib]System.Collections.Generic.List`1/Enumerator<!!TSource> L_003c: callvirt instance void [mscorlib]System.IDisposable::Dispose() L_0041: endfinally L_0042: ldloc.0 L_0043: ret .try L_0009 to L_0034 finally handler L_0034 to L_0042 }
I think that the important lines here is where it calls IEnumerator::GetCurrent()
and IEnumerator::MoveNext()
.
In the first case it is:
callvirt instance !0 [mscorlib]System.Collections.Generic.IEnumerator`1<!!TSource>::get_Current() callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()
And in the second case it is:
call instance !0 [mscorlib]System.Collections.Generic.List`1/Enumerator<!!TSource>::get_Current() call instance bool [mscorlib]System.Collections.Generic.List`1/Enumerator<!!TSource>::MoveNext()
Importantly, in the second case a non-virtual call is being made - which can be significantly faster than a virtual call if it is in a loop (which it is, of course).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With