Performance of Skip (and similar functions, like Take)
Solution 1
In Jon Skeet's excellent tutorial re-implementing Linq, he discusses (briefly) that very question:
Although most of these operations can't be sensibly optimized, it would make sense to optimize Skip when the source implements IList. We can skip the skipping, so to speak, and go straight to the appropriate index. This wouldn't spot the case where the source was modified between iterations, which may be one reason it's not implemented in the framework as far as I'm aware.
That seems like a reasonable reason to hold off on that optimization, but I agree that for specific cases, it may be worthwhile to make that optimization if you can guarantee your source can't/won't be modified.
Solution 2
As ledbutter mentioned, when Jon Skeet reimplemented LINQ, he mentioned that an optimization like your Skip
"wouldn't spot the case where the source was modified between iterations". You can change your code to the following to make it check for that case. It does so by calling MoveNext()
on the collection's enumerator, even though it doesn't use e.Current
, so that the method will throw if the collection changes.
Granted, this removes a significant part of the optimization: that the enumerator needs to be created, partially stepped through, and disposed, but it still has the benefit that you don't need to pointlessly step through the first count
objects. And it might be confusing that you have an e.Current
that is not useful, since it points to list[i - count]
instead of list[i]
.
public static IEnumerable<T> Skip<T>(this IEnumerable<T> source, int count)
{
using (IEnumerator<T> e = source.GetEnumerator())
{
if (source is IList<T>)
{
IList<T> list = (IList<T>)source;
for (int i = count; i < list.Count; i++)
{
e.MoveNext();
yield return list[i];
}
}
else if (source is IList)
{
IList list = (IList)source;
for (int i = count; i < list.Count; i++)
{
e.MoveNext();
yield return (T)list[i];
}
}
else
{
// .NET framework
while (count > 0 && e.MoveNext()) count--;
if (count <= 0)
{
while (e.MoveNext()) yield return e.Current;
}
}
}
}
Related videos on Youtube
Bidou
Updated on August 22, 2022Comments
-
Bidou over 1 year
I just had a look at the source code of the
Skip
/Take
extension methods of the .NET Framework (on theIEnumerable<T>
type) and found that the internal implementation is working with theGetEnumerator
method:// .NET framework public static IEnumerable<TSource> Skip<TSource>(this IEnumerable<TSource> source, int count) { if (source == null) throw Error.ArgumentNull("source"); return SkipIterator<TSource>(source, count); } static IEnumerable<TSource> SkipIterator<TSource>(IEnumerable<TSource> source, int count) { using (IEnumerator<TSource> e = source.GetEnumerator()) { while (count > 0 && e.MoveNext()) count--; if (count <= 0) { while (e.MoveNext()) yield return e.Current; } } }
Suppose that I have an
IEnumerable<T>
with 1000 elements (underlying type isList<T>
). What happens if I'm doing list.Skip(990).Take(10) ? Will it iterate througt the 990 first elements before taking the last ten? (this is how I understand it). If yes, then I don't understand why Microsoft didn't implement theSkip
method like this:// Not tested... just to show the idea public static IEnumerable<T> Skip<T>(this IEnumerable<T> source, int count) { if (source is IList<T>) { IList<T> list = (IList<T>)source; for (int i = count; i < list.Count; i++) { yield return list[i]; } } else if (source is IList) { IList list = (IList)source; for (int i = count; i < list.Count; i++) { yield return (T)list[i]; } } else { // .NET framework using (IEnumerator<T> e = source.GetEnumerator()) { while (count > 0 && e.MoveNext()) count--; if (count <= 0) { while (e.MoveNext()) yield return e.Current; } } } }
In fact, they did that for the
Count
method for example...// .NET Framework... public static int Count<TSource>(this IEnumerable<TSource> source) { if (source == null) throw Error.ArgumentNull("source"); ICollection<TSource> collectionoft = source as ICollection<TSource>; if (collectionoft != null) return collectionoft.Count; ICollection collection = source as ICollection; if (collection != null) return collection.Count; int count = 0; using (IEnumerator<TSource> e = source.GetEnumerator()) { checked { while (e.MoveNext()) count++; } } return count; }
So what's the reason?
-
RobSiklos over 10 yearsI have found that it's always best to assume those methods are never optimized. Even for Count(), it optimizes for
ICollection<>
, but notIReadOnlyCollection<>
. If you need it to be optimized, write your own. -
Tim S. over 10 yearsBecause they never bothered to add that optimization? I don't see any problems with you doing that yourself if you find that it helps. But note that then
myList.Select(..).Skip(100)
is slower thanmyList.Skip(100).Select(..)
, even though they're functionally the same. -
D Stanley over 10 yearsAlso note that in Linq-To-SQL and EF
Skip
andTake
are pushed down to the SQL query, so it does not iterate through the prior items. (SQL might via a table/index scan, but Linq does not) -
Bidou over 10 yearsIn this case, you call the
Skip
/Take
method onIQueryable<T>
(and notIEnumerable<T>
), which has a different implementation...
-
-
Bidou over 10 yearsOk, I see the point... but they could have used
IReadOnlyList<T>
in this case... I guess this interface is just not enough used (and thus the cost of testing ifIEnumerable<T>
isIReadOnlyList<T>
is too high) ? -
Sven Grosen over 10 years@Bidou, that's what I'd guess too. For an all-encompassing
Skip()
implementation, checking for that little-used interface might have been deemed not worth it. -
glopes over 9 yearsFor functional purposes, IList is basically a cached collection. Modifying an IList between enumerator iterations generally raises exceptions anyways, so I don't see why the optimization should not be made. In fact, if you accept the possibility of random parallel side-effects modifying the list, your results will be random no matter if you directly skip or not.
-
Alezis almost 8 yearsI had a task to optimize some code that takes hours/days to complete execution. When I run Visual Studio Profiler I found few places to optimize, but profiler didn't reveal Skip/Take performance issue. When I switched to indexes and removed Skip/Take I boosted performance up to 1700 times: code was executed ~9.5 hours, now it worked for 20 seconds only, so don't use Skip/Take for IList if you need good performance.
-
Pinski over 6 yearsNew home for Jon Skeet's blog post: codeblog.jonskeet.uk/2011/01/02/…