Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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().

like image 394
Pavel Belousov Avatar asked Oct 28 '10 05:10

Pavel Belousov


People also ask

Which is faster IndexOf or contains?

IndexOf(string) has no options and Contains() uses an Ordinal compare (a byte-by-byte comparison rather than trying to perform a smart compare, for example, e with é). So IndexOf will be marginally faster (in theory) as IndexOf goes straight to a string search using FindNLSString from kernel32.

Is for loop faster than contain?

Contains() is about the same speed as, or slightly faster than, the loop. Here's my test code. To test this code, you should compile it as an x86 RELEASE build, and run it from outside the debugger. As you can see, the loop takes around 1/3 the time on my system.

How fast is contain?

Contains() ought to be around 50 nanoseconds. So the overall operation takes 50.05 microseconds. A faster Contains might take half the time, the overall operation takes 50.025 microseconds.

How big can a List be in c#?

List size can be increased up to 2 billion (only when your system works on 64-bit or higher) to store large List<T> objects.


1 Answers

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

like image 161
Andrew Barber Avatar answered Nov 16 '22 12:11

Andrew Barber