CODEWITHSUNDEEP
.netlistcontainsindexof
Pavel Belousov
Pavel Belousov

Reputation: 1858

Why is List<T>.IndexOf() a lot faster than List<T>.Contains()?

I have List which has 150K elements. Average time of work IndexOf() is 4 times lower than Contains(). I tried to use List of int. For List of strings IndexOf is a bit faster.

I found only one main difference, it's attribute TargetedPatchingOptOut. MSDN tells:

Indicates that the .NET Framework class library method to which this attribute is applied is unlikely to be affected by servicing releases, and therefore is eligible to be inlined across Native Image Generator (NGen) images.

Could this attribute be a reason of such behavior? And why doesn't method Contains() have such attribute?

Thanks in advance.

EDIT:

I have code something like this:

List<int> list = CommonHelper.GetRandomList(size);

long min = long.MaxValue;
long max = 0;
long sum = 0;

foreach (var i in list)
{
    m_stopwatch.Reset();
    m_stopwatch.Start();
    list.Contains(i); // list.IndexOf(i);
    m_stopwatch.Stop();

    long ticks = m_stopwatch.ElapsedTicks;

    if (ticks < min)
        min = ticks;

    if (ticks > max)
        max = ticks;

    sum += ticks;
}

long averageSum = sum / size;

EDIT 2:

I have written same code as in IndexOf() and it work slower than Contains().

Upvotes: 16

Views: 3613

Answers (1)

Andrew Barber
Andrew Barber

Reputation: 40139

They each arrive at the method to determine equality slightly differently, according to their MSDN entries. Look under the 'remarks' of each of these entries:

List<T>.IndexOf uses EqualityComparer<T>.Default http://msdn.microsoft.com/en-us/library/e4w08k17.aspx

List<T>.Contains uses IEquatable<T>.Equals http://msdn.microsoft.com/en-us/library/bhkz42b3.aspx

Even if they end up calling the same method to determine equality in the very end (as is certainly the case here), they are taking different routes to get there, so that probably 'splains it.

Given that the "4x difference" seems not to be the actual case, some off-handed boxing might account for some difference, particularly with a 150k sized set of data

Upvotes: 4

Related Questions