FC08 Replace All: Linq.Enumerable.SequenceEqual

In previous two posts, we talked why the simplest Linq.Enumerable method Any is slow and how to fix it by hijacking calls to it with your own much faster extension methods.

Now let’s take a look at a more complex extension method SequenceEqual. Here is its implementation:

So this implementation is purely based on enumeration and comparing elements one by one until either a mismatch is found, or one data stream ends.

When if one data stream contains N elements, another data stream contains the same N elements plus one more? The time spent on enumerating and comparing N items are all wasted.

So we can’t afford to use IEnumerable as input type. At least, we should use ICollection:

With this new extension method, we are using ICollection as input type so that we can access Count property. Before checking counts, we’re adding a quick reference equal short cut. The real enumeration loop is basically the same.

Here is another implementation for IList, no enumerator allocation:

One caveat: do not use this method on ConcurrentDictionary for its Count property implementation could be very expensive (more on this later). Simple enumeration could be faster. But comparing two ConcurrentDictionary as sequences do not make much sense in the first place, because data order is basically random.