(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:
- Can anybody else replicate the results I'm seeing? (Remember to run a release build outside the debugger.)
- If so, can anybody explain how my loop can be so much faster than
List.Contains()
? - 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?