Which .NET collection is faster: enumerating foreach Dictionary<>.Values or List<>?

Question

Are one of these enumerations faster than the other or about the same? (example in C#)

Case 1:

Dictionary<string, object> valuesDict;

// valuesDict loaded with thousands of objects

foreach (object value in valuesDict.Values) { /* process */ }

Case 2:

List<object> valuesList;

// valuesList loaded with thousands of objects

foreach (object value in valuesList) { /* process */ }

UPDATE:

Background:

The dictionary would be beneficial for keyed search elsewhere (as opposed to iterating through a list), but the benefit would be diminished if iterating through the dictionary is much slower than going through the list.

UPDATE: Taking the advice of many, I've done my own testing.

First, these are the results. Following is the program.

Iterate whole collection Dict: 78 Keyd: 131 List: 76

Keyed search collection Dict: 178 Keyd: 194 List: 142800

using System;
using System.Linq;

namespace IterateCollections
{
    public class Data
    {
        public string Id;
        public string Text;
    }

    public class KeyedData : System.Collections.ObjectModel.KeyedCollection<string, Data>
    {
        protected override string GetKeyForItem(Data item)
        {
            return item.Id;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var dict = new System.Collections.Generic.Dictionary<string, Data>();
            var list = new System.Collections.Generic.List<Data>();
            var keyd = new KeyedData();

            for (int i = 0; i < 10000; i++)
            {
                string s = i.ToString();
                var d = new Data { Id = s, Text = s };
                dict.Add(d.Id, d);
                list.Add(d);
                keyd.Add(d);
            }

            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            for (int r = 0; r < 1000; r++)
            {
                foreach (Data d in dict.Values)
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            var dictTime = sw.ElapsedMilliseconds;

            sw.Reset();
            sw.Start();
            for (int r = 0; r < 1000; r++)
            {
                foreach (Data d in keyd)
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            var keydTime = sw.ElapsedMilliseconds;

            sw.Reset();
            sw.Start();
            for (int r = 0; r < 1000; r++)
            {
                foreach (Data d in list)
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            var listTime = sw.ElapsedMilliseconds;

            Console.WriteLine("Iterate whole collection");
            Console.WriteLine("Dict: " + dictTime);
            Console.WriteLine("Keyd: " + keydTime);
            Console.WriteLine("List: " + listTime);

            sw.Reset();
            sw.Start();
            for (int r = 0; r < 1000; r++)
            {
                for (int i = 0; i < 10000; i += 10)
                {
                    string s = i.ToString();
                    Data d = dict[s];
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            dictTime = sw.ElapsedMilliseconds;

            sw.Reset();
            sw.Start();
            for (int r = 0; r < 1000; r++)
            {
                for (int i = 0; i < 10000; i += 10)
                {
                    string s = i.ToString();
                    Data d = keyd[s];
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            keydTime = sw.ElapsedMilliseconds;

            sw.Reset();
            sw.Start();
            for (int r = 0; r < 10; r++)
            {
                for (int i = 0; i < 10000; i += 10)
                {
                    string s = i.ToString();
                    Data d = list.FirstOrDefault(item => item.Id == s);
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            listTime = sw.ElapsedMilliseconds * 100;

            Console.WriteLine("Keyed search collection");
            Console.WriteLine("Dict: " + dictTime);
            Console.WriteLine("Keyd: " + keydTime);
            Console.WriteLine("List: " + listTime);

        }
    }

}

UPDATE:

Comparison of Dictionary with KeyedCollection as suggested by @Blam.

The fastest method is iterating over an Array of KeyedCollection Items.

Note, however, that iterating over the dictionary values is faster than over the KeyedCollection without converting to an array.

Note that iterating over the dictionary values is much, much faster than over the dictionary collection.

 Iterate 1,000 times over collection of 10,000 items
   Dictionary Pair:   519 ms
 Dictionary Values:    95 ms
  Dict Val ToArray:    92 ms
   KeyedCollection:   141 ms
   KeyedC. ToArray:    17 ms

Timings are from a Windows console application (Release build). Here is the source code:

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

namespace IterateCollections
{
    public class GUIDkeyCollection : System.Collections.ObjectModel.KeyedCollection<Guid, GUIDkey>
    {
        // This parameterless constructor calls the base class constructor 
        // that specifies a dictionary threshold of 0, so that the internal 
        // dictionary is created as soon as an item is added to the  
        // collection. 
        // 
        public GUIDkeyCollection() : base() { }

        // This is the only method that absolutely must be overridden, 
        // because without it the KeyedCollection cannot extract the 
        // keys from the items.  
        // 
        protected override Guid GetKeyForItem(GUIDkey item)
        {
            // In this example, the key is the part number. 
            return item.Key;
        }

        public GUIDkey[] ToArray()
        {
            return Items.ToArray();
        }

        //[Obsolete("Iterate using .ToArray()", true)]
        //public new IEnumerator GetEnumerator()
        //{
        //    throw new NotImplementedException("Iterate using .ToArray()");
        //}
    }
    public class GUIDkey : Object
    {
        private Guid key;
        public Guid Key
        {
            get
            {
                return key;
            }
        }
        public override bool Equals(Object obj)
        {
            //Check for null and compare run-time types.
            if (obj == null || !(obj is GUIDkey)) return false;
            GUIDkey item = (GUIDkey)obj;
            return (Key == item.Key);
        }
        public override int GetHashCode() { return Key.GetHashCode(); }
        public GUIDkey(Guid guid)
        {
            key = guid;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            const int itemCount = 10000;
            const int repetitions = 1000;
            const string resultFormat = "{0,18}: {1,5:D} ms";

            Console.WriteLine("Iterate {0:N0} times over collection of {1:N0} items", repetitions, itemCount);

            var dict = new Dictionary<Guid, GUIDkey>();
            var keyd = new GUIDkeyCollection();

            for (int i = 0; i < itemCount; i++)
            {
                var d = new GUIDkey(Guid.NewGuid());
                dict.Add(d.Key, d);
                keyd.Add(d);
            }

            var sw = new System.Diagnostics.Stopwatch();
            long time;

            sw.Reset();
            sw.Start();
            for (int r = 0; r < repetitions; r++)
            {
                foreach (KeyValuePair<Guid, GUIDkey> w in dict)
                {
                    if (null == w.Value) throw new ApplicationException();
                }
            }
            sw.Stop();
            time = sw.ElapsedMilliseconds;
            Console.WriteLine(resultFormat, "Dictionary Pair", time);

            sw.Reset();
            sw.Start();
            for (int r = 0; r < repetitions; r++)
            {
                foreach (GUIDkey d in dict.Values)
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            time = sw.ElapsedMilliseconds;
            Console.WriteLine(resultFormat, "Dictionary Values", time);

            sw.Reset();
            sw.Start();
            for (int r = 0; r < repetitions; r++)
            {
                foreach (GUIDkey d in dict.Values.ToArray())
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            time = sw.ElapsedMilliseconds;
            Console.WriteLine(resultFormat, "Dict Val ToArray", time);

            sw.Reset();
            sw.Start();
            for (int r = 0; r < repetitions; r++)
            {
                foreach (GUIDkey d in keyd)
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            time = sw.ElapsedMilliseconds;
            Console.WriteLine(resultFormat, "KeyedCollection", time);

            sw.Reset();
            sw.Start();
            for (int r = 0; r < repetitions; r++)
            {
                foreach (GUIDkey d in keyd.ToArray())
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            time = sw.ElapsedMilliseconds;
            Console.WriteLine(resultFormat, "KeyedC. ToArray", time);
        }
    }

}

Answer 1

This is relatively easy to check with a stopwatch:

var d = new Dictionary<string, object>();
var s = new List<object>();
for (int i =0 ; i != 10000000 ; i++) {
    d.Add(""+i, i);
    s.Add(i);
}
var sw = new Stopwatch();
sw.Start();
foreach(object o in d.Values) {
    if (o == null) throw new ApplicationException();
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
sw.Reset();
sw.Start();
foreach (object o in s) {
    if (o == null) throw new ApplicationException();
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);

This prints numbers that are reasonably close to each other:

Dict List
---- ----
 136  107
 139  108
 136  108

The List always wins, but the margins are not as large as one would expect, given the relative complexity of the two data structures.

Answer 2

It's about the same time. Surely it won't be noticable once your process includes any code.

But why do you listen to random people from the internet? Test it!

The Stopwatch class might be useful.