Runtime: Make Enumerable.Any use the same optimizations that Count has (ICollection checks)

Created on 12 Jul 2015 · 25Comments · Source: dotnet/runtime

Enumerable.Count uses ICollection and ICollection<T> to perform a fast and allocation-free computation. Enumerable.Any should do that as well.

The fact that Any does not check ICollection is pretty much the only downside to using Any vs. Count() != 0. This downside should be eliminated.

This missing optimization causes confusion:

area-System.Linq enhancement tenet-performance up-for-grabs

Source

GSPP

👍4

All 25 comments

This seems a reasonable thing to include in the stuff I'm going to move from dotnet/corefx#2237 into a separate PR. I'll include it when I do so.

JonHanna on 13 Jul 2015

Great! It seems you are doing amazing work on LINQ. I was not aware of that.

GSPP on 13 Jul 2015

How common is something that implements IEnumerable<T> and ICollection but does not implement ICollection<T>? Maybe there's a common collection type I can't think of that does, but it seems an obscure case and the check therefore a waste of time. (Or possibly even harmful; if such an obscure case was doing something unusual and implementing IEnumerable<T> for two different T with two different counts; unlikely, but we're already talking about obscure cases).

Possibly if anything ICollection collection = source as ICollection; should be removed from Count as busy-work unlikely to benefit anyone.

JonHanna on 14 Jul 2015

I agree that the ICollection check probably is a waste of time. I think the behavior should be exactly the same everywhere. I'm for removing it in all locations.

That said Reflector shows an enormous number of classes implementing ICollection. MatchCollection and other legacy collections never were upgraded. The best fix would be to make them implement the generic collection interfaces as well. On Stack Overflow people often are doing things like for (var i = 0; i < myWinFormsControl.Children.Count(); i++)...

What about the case where the collection implemented ICollection<Derived> and our LINQ method targets ICollection<Base>. This interface is not covariant. The cast will fail. ICollection could save us here.

It would be ideal if the BCL had an ICountable interface that was retroactively added to everything. This probably would be a simple Roslyn-based refactoring that would target like 500 classes in one go. Mechanically add this interfaces to all classes that have an int Count member and implement any of the common collection classes as well. Make the collection interfaces derive from ICountable which does not add another member. Recompilation is always enough to satisfy the interface. Is there compatibility risk for doing something like that? There should be mainly Reflection-access risk in which code finds an interface it does not expect. That's rare.

GSPP on 14 Jul 2015

A yes. The covariance is the thing.

Meanwhile it's interesting that with a comparison between:

public static bool Any1<TSource>(this IEnumerable<TSource> source)
{
    if (source == null) throw new ArgumentNullException("source");
    using (IEnumerator<TSource> e = source.GetEnumerator())
    {
        return e.MoveNext();
    }
}
public static bool Any2<TSource>(this IEnumerable<TSource> source)
{
    if (source == null) throw new ArgumentNullException("source");
    var asCol = source as ICollection<TSource>;
    if (asCol != null) return asCol.Count != 0;
    using (IEnumerator<TSource> e = source.GetEnumerator())
    {
        return e.MoveNext();
    }
}

I find that while the advantage Any1 has with non-collections in skipping the test is slight enough that it doesn't even win every comparison, and while Any2 is more performant with most collections as we might expect, Any1 does considerably better with arrays. Accessing T[] as IList<T> is not as performant as one might like; getting to its Count is slower than getting to its GetEnumerator(), calling MoveNext() and then calling Dispose().

Testing if(source is TSource[]) and skipping the Count check does worse of all in all cases.

Doubling the test to:

        var asArr = source as TSource[];
        if (asArr != null) return asArr.Length != 0;
        var asCol = source as ICollection<TSource>;
        if(asCol != null) return asCol.Count != 0;

Is only slightly less performant with non-array collections, and much more so with arrays as we might expect.

Optimising Count to specifically handle arrays in the same way is probably not worth it (there the main thing is that the change is from an O(n) operation to an O(1) operation), but if we're going to do such checks for ICollection<T> in Any() we should probably test for arrays too as they are far from being obscure case.

At the same time, I think non-generic ICollection checks are definitely work keeping in Count because of the covariant case you mention (again, the change there is from O(n) to O(1)) but not in Any() where we'd only shave off a few nanoseconds (as it's O(1) to a faster O(1) with less constant-costs) and doesn't justify adding on a few nanoseconds to other cases.

JonHanna on 14 Jul 2015

Agreed. With better JIT and better array interface implementation in the CLR we probably could make this work, but not today.

GSPP on 14 Jul 2015

On playing with this, I think this would on balance be a bad idea.

Enumerable.Count uses ICollection and ICollection<T> to perform a fast and allocation-free computation.

More than this. Enumerable.Count uses those attempted casts to perform computation that is generally constant-time instead of one that's linear-time. That's not guaranteed, but very common and certainly the case with the collections provided in the BCL, and certainly it won't be worse than the linear time it would have anyway.

Enumerable.Any should do that as well.

This would mean replacing a O(1) operation with a faster O(1) operation, it's moving around the constant costs.

As is we've got (after the null check that any case would need) three interface operations: GetEnumerator(), MoveNext() & Dispose() that involves 0 or 1 allocations (0-allocation GetEnumerator() is common in the results of linq operations).

Testing gives use the opportunity of reducing that to one interface operation at the cost of the test.

As per above, in the case of arrays it actually takes longer to access IList<T>.Count than to use the approach Any() currently uses (going through JitHelpers.UnsafeCast must have its own costs). It's not impossible that other ICollection<T> implementations are also disappointing in how Count works, though unlikely.

Still, we have to either make Any() worse for arrays, or explicitly cater for them.

And those tests add cost. In the case of Count the potential win, being constant vs linear, far outweighs that cost, but in the case of Any() it's well into double-digit percentage hits on the cases it doesn't help to gain a just-about double-digit percentage gain or less on the cases it does help.

And in the case where the collection is known to be ICollection<T> or T[] or ICollection at coding time, the developer would still do better to call .Count() directly.

Conversely, .Any() is most useful when the object is likely to not be such a type.

So in all this would degrade performance in many cases where it is most useful, to benefit a minority of case, especially if we discount cases where the developer would have been better-off doing something else either way.

(It would be possible to add methods of Count(T[] source) and Count(ICollection<T> source) but these would only benefit the cases where the developer could just call .Count or .Length anyway).

JonHanna on 22 Jul 2015

Made some perfomance tests (Any* - version with suggested optimization).
10 000 runs were made.

Host Process Environment Information:
BenchmarkDotNet=v0.9.8.0
OS=Windows
Processor=?, ProcessorCount=2
Frequency=2435497 ticks, Resolution=410.5938 ns, Timer=TSC
CLR=CORE, Arch=64-bit ? [RyuJIT]
GC=Concurrent Workstation
JitModules=?
dotnet cli version: 1.0.0-preview2-003121

Type=PerfAny  Mode=Throughput  Toolchain=Core  
GarbageCollection=Concurrent Workstation

1. Array

Method |    Median |    StdDev |
------ |---------- |---------- |
   Any | 0.0020 ns | 0.0001 ns |
   Any*| 0.0050 ns | 0.0002 ns |

2. List

Method |    Median |    StdDev |
------ |---------- |---------- |
   Any | 0.0027 ns | 0.0002 ns |
   Any*| 0.0009 ns | 0.0000 ns |

Arrays 250% slower, Lists 300% faster.

DenisIstomin on 13 Aug 2016

What about those that aren't list types at all?

JonHanna on 13 Aug 2016

Would be a useful change, but need to carefully balance the impact of specialization.

Unlike Count, which is by default O(N), Any is typically O(1), and it would be harder to ensure that the improvement is big enough to amortize the cost of specialization.

In particular, consider cases like immutable collections. I am not sure Count is O(1) there, but Any certainly is.

VSadov on 18 Nov 2016

Second answer in http://stackoverflow.com/questions/2989300/interview-question-any-vs-if-length-0-for-testing-if-a-collection-has-e actually actually makes a very good explanation why "Any" could be preferred over "Count > 0" . Basically "Any" is almost certainly O(1), while with "Count" you cannot be sure. Even if sequence implements interfaces that provide "Count" it does not necessarily mean they are cheap.

I.E. checking for System.Array and fetching System.Array.Count seems safe optimization.
As for ICollection - I am not sure. People might call "Any" specifically to avoid expensive "Count" and we would bring it back :-\ .

VSadov on 18 Nov 2016

👍1

As @VSadov says above - it does not look like always beneficial thing to do.

karelz on 28 Nov 2016

Basically "Any" is almost certainly O(1), while with "Count" you cannot be sure. Even if sequence implements interfaces that provide "Count" it does not necessarily mean they are cheap. I.E. checking for System.Array and fetching System.Array.Count seems safe optimization. As for ICollection - I am not sure. People might call "Any" specifically to avoid expensive "Count" and we would bring it back :-\ .

That said, we may still want to add a check for the internal IIListProvider<TSource>. That doesn't suffer from the same concern, as we can ask for the count only if it's deemed cheap to compute, and it also allows for operations like that described in https://github.com/dotnet/corefx/issues/14078#issuecomment-263478710 to be optimized. e.g.
```C#
public static bool Any(this IEnumerable source)
{
if (source == null)
{
throw Error.ArgumentNull(nameof(source));
}

var p = source as IIListProvider<TSource>;
if (p != null)
{
    int count = p.GetCount(onlyIfCheap: true);
    if (count >= 0)
    {
        return count != 0;
    }
}

using (IEnumerator<TSource> e = source.GetEnumerator())
{
    return e.MoveNext();
}

}
```
It does of course add an extra type check and an extra interface call, so it does add expense in the case where the source doesn't implement the interface or provide a cheap implementation of GetCount. But for cases where it does, it avoids the allocation and an interface call, as well as whatever costs may be present in enumerating the source itself.

stephentoub on 29 Nov 2016

An IIListProvider<TSource> could be ultimately wrapping one of the sorts of IList<TSource> that isn't super-cheap as per the above. That "onlyIfCheap" would still be cheap enough often enough to make sense as an allocation optimisation, but not necessarily cheap enough to beat the single iteration of MoveNext that Any currently does.

JonHanna on 29 Nov 2016

An IIListProvider could be ultimately wrapping one of the sorts of IList that isn't super-cheap as per the above

We have IIListProvider<TSource> implementations with GetCount(onlyIfCheap: true) implementations that aren't cheap? Then we should fix those, as such calls are used in cases where they really need to be super cheap, like presizing a list.

stephentoub on 29 Nov 2016

Actually no. The case I was thinking of is how with arrays it was found above that going through IList to get Count was more expensive than trying to enumerate (would still be a gain when it came to allocating), but most (all?) cases where we have an array as the source to an IIListProvider it's already strongly typed to that and will use Length.

So yes, optimising of IIListProvider make sense. All the more so since it could skip multiple chained calls.

JonHanna on 29 Nov 2016

@JonHanna @stephentoub please create a new bug if you both think it is worth pursuing.

karelz on 29 Nov 2016

please create a new bug

Why a new bug rather than reopening this one? This issue was about applying one or more of the optimizations Count includes, and Count has this one:
https://github.com/dotnet/corefx/blob/master/src/System.Linq/src/System/Linq/Count.cs#L25-L29

stephentoub on 29 Nov 2016

New bug saying "Do X (BTW: See background in bug Y if you're interested)" will be easier to comprehend and pick up as "up for grabs" than this longer discussion which folks will try to understand first.
Not a super-strong opinion from my side ...

karelz on 29 Nov 2016

👍1

Has this been addressed? I find it funny that Any is usually slower than count, when I would expect the opposite, or at least equal results.
I'm willing to contribute on this in whatever way I'll be directed to I'm capable of.