Array.Contains runs very slow, anyone shed some light?

Question

I have done some benchmark regarding List.Contains, Array.Contains, IEnumerable.Contains, ICollection.Contains and IList.Contains.

The results are:

array pure 00:00:45.0052754 // 45 sec, slow
array as IList 00:00:02.7900305
array as IEnumerable 00:00:46.5871087 // 45 sec, slow
array as ICollection 00:00:02.7449889
list pure 00:00:01.9907563
list as IList 00:00:02.6626009
list as IEnumerable 00:00:02.9541950
list as ICollection 00:00:02.3341203

As I find out that it would be very slow if call Array.Contains directly (which is equivalent to call IEnumerable)

Also I feel it is strange that MSDN array page doesn't have contains method listed in the extension method section.

Sample code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace arrayList
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch watch = new Stopwatch();
            Int64 n = 100000000;
            Int64[] myarray = new Int64[] { 1, 2, 3 };
            List<Int64> mylist = new List<Int64>(myarray);
            watch.Start();
            for (Int64 j = 0; j < n; j++)
            {

                bool i = myarray.Contains(2);

            }
            watch.Stop();
            Console.WriteLine("array pure {0}", watch.Elapsed);

            watch.Restart();
            for (Int64 j = 0; j < n; j++)
            {

                bool i = (myarray as IList<Int64>).Contains(2);

            }
            watch.Stop();
            Console.WriteLine("array as IList {0}",watch.Elapsed);

            watch.Restart();
            for (Int64 j = 0; j < n; j++)
            {

                bool i = (myarray as IEnumerable<Int64>).Contains(2);

            }
            watch.Stop();
            Console.WriteLine("array as IEnumerable {0}",watch.Elapsed);
            watch.Restart();
            for (Int64 j = 0; j < n; j++)
            {

                bool i = (myarray as ICollection<Int64>).Contains(2);

            }
            watch.Stop();
            Console.WriteLine("array as ICollection {0}",watch.Elapsed);

            watch.Restart();
            for (Int64 j = 0; j < n; j++)
            {

                bool i = mylist.Contains(2);

            }
            watch.Stop();
            Console.WriteLine("list pure {0}", watch.Elapsed);

            watch.Restart();
            for (Int64 j = 0; j < n; j++)
            {

                bool i = (mylist as IList<Int64>).Contains(2);

            }
            watch.Stop();
            Console.WriteLine("list as IList {0}", watch.Elapsed);

            watch.Restart();
            for (Int64 j = 0; j < n; j++)
            {

                bool i = (mylist as IEnumerable<Int64>).Contains(2);

            }
            watch.Stop();
            Console.WriteLine("list as IEnumerable {0}", watch.Elapsed);
            watch.Restart();
            for (Int64 j = 0; j < n; j++)
            {

                bool i = (mylist as ICollection<Int64>).Contains(2);

            }
            watch.Stop();
            Console.WriteLine("list as ICollection {0}", watch.Elapsed);
            Console.ReadKey();
        }
    }
}

Answer 1

The way you are timing these are not sufficient. You need significantly larger inputs to get times representative of the algorithms. Yes Contains() will be slower than a simple linear search (something you've omitted) but the different calls are not going to have the times as you've shown. You're likely to not see any variation between the calls to Contains() when cast to the different types as in all likelihood, we're calling the same implementation for all of them.

Try this code for size:

using System;
using System.Collections.Generic;
using System.Linq;

using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            const int iterations = 1000000;
            const long target = 7192;
            var arr = Enumerable.Range(0, 10000).Select(i => (long)i).ToArray();
            var list = arr.ToList();

            bool result;

            var arr0 = Stopwatch.StartNew();
            for (var i = 0; i < iterations; i++)
            {
                result = LinearSearchArr(arr, target);
            }
            arr0.Stop();

            var arr1 = Stopwatch.StartNew();
            for (var i = 0; i < iterations; i++)
            {
                // actually Enumerable.Contains()
                result = arr.Contains(target);
            }
            arr1.Stop();

            var arr2 = Stopwatch.StartNew();
            for (var i = 0; i < iterations; i++)
            {
                result = ((IList<long>)arr).Contains(target);
            }
            arr2.Stop();

            var arr3 = Stopwatch.StartNew();
            for (var i = 0; i < iterations; i++)
            {
                result = ((IEnumerable<long>)arr).Contains(target);
            }
            arr3.Stop();

            var arr4 = Stopwatch.StartNew();
            for (var i = 0; i < iterations; i++)
            {
                result = ((ICollection<long>)arr).Contains(target);
            }
            arr4.Stop();

            var list0 = Stopwatch.StartNew();
            for (var i = 0; i < iterations; i++)
            {
                result = LinearSearchList(list, target);
            }
            list0.Stop();

            var list1 = Stopwatch.StartNew();
            for (var i = 0; i < iterations; i++)
            {
                result = list.Contains(target);
            }
            list1.Stop();

            var list2 = Stopwatch.StartNew();
            for (var i = 0; i < iterations; i++)
            {
                result = ((IList<long>)list).Contains(target);
            }
            list2.Stop();

            var list3 = Stopwatch.StartNew();
            for (var i = 0; i < iterations; i++)
            {
                result = ((IEnumerable<long>)list).Contains(target);
            }
            list3.Stop();

            var list4 = Stopwatch.StartNew();
            for (var i = 0; i < iterations; i++)
            {
                result = ((ICollection<long>)list).Contains(target);
            }
            list4.Stop();

            Console.WriteLine("array linear {0} ({1})", arr0.Elapsed, arr0.ElapsedTicks);
            Console.WriteLine("array pure {0} ({1})", arr1.Elapsed, arr1.ElapsedTicks);
            Console.WriteLine("array as IList {0} ({1})", arr2.Elapsed, arr2.ElapsedTicks);
            Console.WriteLine("array as IEnumerable {0} ({1})", arr3.Elapsed, arr3.ElapsedTicks);
            Console.WriteLine("array as ICollection {0} ({1})", arr4.Elapsed, arr4.ElapsedTicks);
            Console.WriteLine("list linear {0} ({1})", list0.Elapsed, list0.ElapsedTicks);
            Console.WriteLine("list pure {0} ({1})", list1.Elapsed, list1.ElapsedTicks);
            Console.WriteLine("list as IList {0} ({1})", list2.Elapsed, list2.ElapsedTicks);
            Console.WriteLine("list as IEnumerable {0} ({1})", list3.Elapsed, list3.ElapsedTicks);
            Console.WriteLine("list as ICollection {0} ({1})", list4.Elapsed, list4.ElapsedTicks);
        }

        static bool LinearSearchArr(long[] arr, long target)
        {
            for (var i = 0; i < arr.Length; i++)
            {
                if (arr[i] == target)
                {
                    return true;
                }
            }
            return false;
        }

        static bool LinearSearchList(List<long> list, long target)
        {
            for (var i = 0; i < list.Count; i++)
            {
                if (list[i] == target)
                {
                    return true;
                }
            }
            return false;
        }
    }
}

Specs:
Windows 7 Professional 64-bit
Intel Core 2 Quad Q9550 @ 2.83GHz
4x1GiB Corsair Dominator DDR2 1066 (PC2-8500)

Default .NET 4.0 Console App release build targeting x64:

array linear 00:00:07.7268891 (21379939)
array pure 00:00:12.1703848 (33674883)
array as IList 00:00:12.1764948 (33691789)
array as IEnumerable 00:00:12.5377771 (34691440)
array as ICollection 00:00:12.1827855 (33709195)
list linear 00:00:17.9288343 (49608242)
list pure 00:00:25.8427338 (71505630)
list as IList 00:00:25.8678260 (71575059)
list as IEnumerable 00:00:25.8500101 (71525763)
list as ICollection 00:00:25.8423424 (71504547)