Loop implementation of List.Contains() appears faster than the built-in one. Is it? If so, why?

Question

(This question arises from a discussion that started here)

I was comparing the timings for looking for a true value in a List<bool> using List.Contains() with those for a hand-rolled loop.

I am seeing different results from those reported by other people. I have tried it on several systems, and the loop seems faster by between 2 and 3.5 times on all the systems I've tried it on. These systems range from 5-year-old laptops running XP with .Net 4 to recent PCs running Windows 8 and .Net 4.5.

Other people are reporting different results, namely that List.Contains() is about the same speed as, or slightly faster than, the loop.

Here's my test code.

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    internal class Program
    {
        private static void Main()
        {
            int size = 10000000;
            int count = 10;
            List<bool> data = new List<bool>(size);

            for (int i = 0; i < size; ++i)
                data.Add(false);

            var sw = new Stopwatch();

            for (int trial = 0; trial < 5; ++trial)
            {
                sw.Restart();

                for (int i = 0; i < count; ++i)
                    TestViaLoop(data);

                sw.Stop();
                Console.WriteLine(sw.ElapsedMilliseconds + " TestViaLoop()");
                sw.Restart();

                for (int i = 0; i < count; ++i)
                    TestViaListContains(data);

                sw.Stop();
                Console.WriteLine(sw.ElapsedMilliseconds + " TestViaListContains()");
                Console.WriteLine();
            }
        }

        static bool TestViaLoop(List<bool> data)
        {
            for (int i = 0; i < data.Count; ++i)
                if (data[i])
                    return true;

            return false;
        }

        static bool TestViaListContains(List<bool> data)
        {
            return data.Contains(true);
        }
    }
}

To test this code, you should compile it as an x86 RELEASE build, and run it from outside the debugger.

Here are my results from my Windows 8 x64 PC using the .Net 4.5 framework (although I get similar results with .Net 4):

Times are in milliseconds

126 TestViaLoop()
441 TestViaListContains()

122 TestViaLoop()
428 TestViaListContains()

131 TestViaLoop()
431 TestViaListContains()

138 TestViaLoop()
426 TestViaListContains()

122 TestViaLoop()
439 TestViaListContains()

As you can see, the loop takes around 1/3 the time on my system.

Now if we use Resharper to look at the implementation of List.Contains() it looks like this:

bool Contains(T item)
{
    if (item == null)
    {
        for (int j = 0x0; j < this._size; j++)
        {
            if (this._items[j] == null)
            {
                return true;
            }
        }
        return false;
    }
    EqualityComparer<T> comparer = EqualityComparer<T>.Default;
    for (int i = 0x0; i < this._size; i++)
    {
        if (comparer.Equals(this._items[i], item))
        {
            return true;
        }
    }
    return false;
}

Although it is using Comparer.Equals() (which should make it slower than the loop) it is also using the private _items[] array directly, which avoids the index range check which will be being used for my loop implementation.

I have three questions:

1. Can anybody else replicate the results I'm seeing? (Remember to run a release build outside the debugger.)
2. If so, can anybody explain how my loop can be so much faster than List.Contains()?
3. If not, can anyone explain why I'm seeing my loop to be faster?

This is not just of academic interest to me, since I write code that works with large amounts of numeric data and which needs to be as fast as possible, and this is the sort of thing I need to know about. (Note: Yes, I profile things and only try to optimise stuff that needs to be optimised... I know about the problems of premature optimisation.)

[EDIT]

It occurs to me that this could be processor related. All the systems I've tried it on have Intel processors, albeit very different models ranging from Quad Core at 3.8GHz to a Pentium M single core at 1.6 GHz...

For those of you who see the loop running slower, are you running Intel processors?

Tympanites

I get about 185 via loop and 365 via contains, so: yes I can repro - I'm not going to get excited about the difference, though... if I was after the best "contains", I'd be using a HashSet<T> or similar. – Casablanca

+1 nice question. However, I cannot repro! I get approx. 2:1 in favour of the ListContains method. The firt example giving: 890 TestViaLoop() 450 TestViaListConstains()... – Schizophrenia

This tells you that method calls are expensive (comparer.Equals). Move on. – Gerontocracy

How is this telling you that method calls are expensive? There is more at work here... – Schizophrenia

@MarcGravell I take your point, but the scope is greater than just Contains. For example, if I use List.FindIndex(pred) to find the index of the first negative element in a List<int> (which is something we happen to need to do in some of our calculations) then the loop is again around three times faster... I guess that is doing something quite different though. – Tympanites

@Killercam are you running in debug or outside the IDE? I get 310/1220 running the compiled release exe, inside the IDE in debug I get 2195/1220. – Misdemean

@Killercam Interesting - so you have also reproduced the different timings. Most curious - I just can't understand why some systems show different results. There must be some common factor. Processor perhaps? Ours are all Intel processors. – Tympanites

Right. I am with you. Outside of IDE I match the results outlined in the question... Apologies for the miss-direction. – Schizophrenia

Note, my results are almost identical to yours running Core i7, *GB RAM. – Schizophrenia

@Killercam Ah ok, so perhaps people aren't seeing different results after all. – Tympanites

@MatthewWatson: Now that i've compiled it in release-mode and executed it from outside of Visual Studio(logging to a file), i get the same values as you, so i stay corrected (+1 for both, this question and your answer). The execution from outside the IDE makes the difference. Before Contains was twice as fast. – Dioecious

All ok.. the system clock is delaying when using contains. nah I JK :) it's the generic support of course! – Rhonarhonchus

Answer 1

It uses GenericEqualityComparer, if we look at the implementation of the Equals method is looks like this:

public override bool Equals(T x, T y)
{
  if ((object) x != null)
  {
    if ((object) y != null)
      return x.Equals(y);
    else
      return false;
  }
  else
    return (object) y == null;
}

When it checks whether the objects are not equal to null, it makes boxing them and you get two boxing operation. This IL-code shows how it looks:

IL_0002: box !T
IL_0007: ldnull
IL_0008: ceq

---

Edit by 280Z28: The CIL for the same method is slightly different in .NET 4.5.

public override bool Equals(T x, T y)
{
    if (x != null)
        return ((y != null) && x.Equals(y));

    if (y != null)
        return false;

    return true;
}

Here is the IL. For anyone looking at Reflector, note that brfalse.s and brnull.s are the same instruction.

L_0000: ldarg.1 
L_0001: box !T
L_0006: brnull.s L_0021
...

The baseline JIT compiler does not optimize away the box operation, but I have not checked with NGen or the optimizing compiler to see if they do.

Hereof

Aha! That sounds like a convincing explanation as to why the loop is faster. However, it doesn't explain why some people see the loop running slower! (If they are... it's now looking like everyone sees the loop running faster.) – Tympanites

From tests on my system, using the GenericEqualityComparer.Equals() method is a bit over 100% slower than a simple comparison (i.e. a == b) for booleans. That's just for the comparison, not the loop / control structures. – Slap

I think @ws0205 has identified the main root cause. I'll mark this as the answer! – Tympanites

Answer 2

Your loop implementation produces the same output as Contains, but you can't use it in the generic case. I.e. You would have to end up using an Equals comparison for more complex objects. The Contains implementation is performing more work than your implementation, so I don't see why you should expect it to be faster in this case.

If you had a list of custom Person objects say, and overrode the Equals method to compare, say, their Address Name SSNumber and DateOfBirth, the loops would perform at nearly identical performance costs.

I would expect for primitive values, then yes a loop iteration is going to outperform the generic Contains, but this is a premature optimization, you're not going to do (substantially) better than Contains for more complex object comparisons.

Insincerity