Loop implementation of List.Contains() appears fas

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?

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.

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.