Iterating speed and data type

Question

Does the iteration speed through an array (or list,linkedList,Dictionary ect) depend on the data type?

Example: An array of 10 bools v/s an array of 10 integers?

Answer 1

Yes, the datatype matters. It has nothing to do with the iteration; it has everything to do with the datatypes.

Value types

An int is 4 bytes in length. A decimal is 16 bytes in length. So a decimal is 4 times bigger than an int. Every time you retrieve a value from the array the that value is copied. In case of a decimal al 16 bytes are copied. (In case of a reference type the reference is copied, normally 4 or 8 bytes). Copying more bytes will simply slow down the iteration.

Boxing

If you iterate trough a collection, there is also the possibility that you have change type. For example:

foreach(object o in new int[] { 1,2,3 })
     ....

This will box every int to an object. This takes time. That has nothing to do with the iteration, it has everything to do with the fact that you are boxing.

Casting

Last example: There are also arrays in where you have to cast:

foreach(Person p in new object[] { ... })
     ....

Casting also takes extra time.

EDIT

Some time measurements to backup my claim:

Answer 2

Run the code below if you want , but here's a quick comparison. All that it does is iterate over the array/list, and set a temp variable to the value in that index.

Do note that somehow the Int performance took a hit when running now ... no idea why ... but it happens on repeated runs as well ...

    namespace Iterating_types
    {
    using System;
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.Linq;
    using System.Text;
class Program
    {
        static void Main(string[] args)
        {
            Thread.CurrentThread.Priority = ThreadPriority.Highest;
            Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.RealTime;

            Stopwatch watch = new Stopwatch();
            int UPPER = 1000000;
            int[] int_arr = Enumerable.Range(1, UPPER).ToArray();
            List<int> int_list = Enumerable.Range(1, UPPER).ToList();

            Int32[] int32_arr = Enumerable.Range(1, UPPER).ToArray();

            Int64[] int64_arr = new Int64[UPPER]; 

            IntObject[] intobject_arr = new IntObject[UPPER];
            List<IntObject> intobject_list = new List<IntObject>();

            string[] string_arr = new string[UPPER];
            List<string> string_list = new List<string>();

            bool[] bool_arr = new bool[UPPER];
            Boolean[] boolean_arr = new Boolean[UPPER];
            List<bool> bool_list = new List<bool>();
            List<Boolean> boolean_list = new List<Boolean>();
            // Initializing some of the above
            for (int i = 0; i < UPPER; i++)
            {
                int64_arr[i] = (Int64) i;
                string_arr[i] = i.ToString();
                string_list.Add(i.ToString());
                intobject_arr[i] = new IntObject(i);
                intobject_list.Add(new IntObject(i));
                bool_arr[i] = (i%2 ==0);
                boolean_arr[i] = (i%2 ==0);
                bool_arr[i] = (i%2 ==0);
                bool_list.Add(i%2 ==0);

                boolean_list.Add(i%2 == 0);
            }

            Console.WriteLine("Iterations: {0}{1}", UPPER, Environment.NewLine);
            Console.WriteLine("Thread priority: {0}", Thread.CurrentThread.Priority);
            Console.WriteLine("Process priority: {0}", Process.GetCurrentProcess().PriorityClass);

            Console.WriteLine("\n\rArrays:\t----------------------------------------------");

            bool b;
            b = bool_arr[1];
            watch.Start();
            for (int i = 0; i < UPPER; i++)
            {
                b = bool_arr[i];
            }
            watch.Stop();
            Console.WriteLine("Type: bool\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds);

            watch.Start();
            for (int i = 0; i < UPPER; i++)
            {
                b = boolean_arr[i];
            }
            watch.Stop();
            Console.WriteLine("Type: Boolean\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds);

            int temp_int;
            temp_int = int_arr[1];
            watch.Start();
            for (int i = 0; i < UPPER; i++)
            {
                temp_int = int_arr[i];
            }
            watch.Stop();
            Console.WriteLine("Type: Int\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds);

            Int32 temp_int32 ;
            temp_int32 = int32_arr[1];
            watch.Reset();
            watch.Start();
            for (int i = 0; i < UPPER; i++)
            {
                temp_int32 = int32_arr[i];
            }
            watch.Stop();
            Console.WriteLine("Type: Int32\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds);

            Int64 temp_int64 ;
            temp_int64 = int64_arr[1];
            watch.Reset();
            watch.Start();
            for (int i = 0; i < UPPER; i++)
            {
                temp_int64 = int64_arr[i];
            }
            watch.Stop();
            Console.WriteLine("Type: Int64\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds);

            string s ;
            s = string_arr[1];
            watch.Reset();
            watch.Start();
            for (int i = 0; i < UPPER; i++)
            {
                s = string_arr[i];
            }
            watch.Stop();
            Console.WriteLine("Type: string\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds);

            temp_int = intobject_arr[1].IntValue;
            watch.Reset();
            watch.Start();
            for (int i = 0; i < UPPER; i++)
            {
                temp_int = intobject_arr[i].IntValue;
            }
            watch.Stop();
            Console.WriteLine("Type: IntObject\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds);

            Console.WriteLine("\n\rLists:\t----------------------------------------------");

            watch.Reset();
            watch.Start();
            foreach (var val in bool_list)
            {
                b = val;
            }
            watch.Stop();
            Console.WriteLine("Type: bool\tStructure: List\t\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds);

            watch.Reset();
            watch.Start();
            foreach (var val in boolean_list)
            {
                b = val;
            }
            watch.Stop();
            Console.WriteLine("Type: Boolean\tStructure: List\t\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds);

            temp_int = int_list.First();
            watch.Reset();
            watch.Start();
            foreach (var val in int_list)
            {
                temp_int = val;
            }
            watch.Stop();
            Console.WriteLine("Type: Int\tStructure: List\t\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds);

            s = string_list.First();
            watch.Reset();
            watch.Start();
            foreach (var val in string_list)
            {
                s = val;
            }
            watch.Stop();
            Console.WriteLine("Type: string\tStructure: List\t\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds);

            temp_int = intobject_list.First().IntValue;
            watch.Reset();
            watch.Start();
            foreach (var val in intobject_list)
            {
                temp_int = val.IntValue;
            }
            watch.Stop();
            Console.WriteLine("Type: IntObject\tStructure: List\t\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds);

            Console.WriteLine();
            Console.WriteLine("Hit any key to exit.");
            Console.ReadKey();


        }
    }

    class IntObject
    {
        public int IntValue { get; set; }

        public IntObject ()
        {
            IntValue = 0;
        }

        public IntObject(int i)
        {
            IntValue = i;
        }
    }
}

Answer 3

The simple answer is YES for reference types, and NO for value types.

This is because, implementation of .NET generics are done in such a way that it is boxing/unboxing is avoided when using Value Types though not in ArrayLists. For instance a List<int> would store the array integers directly as integers on the heap rather than as objects. In the case of reference types e.g. List<string>, List<person> however, there will be a little time loss in conversion/casting from object to data type.

See comparison between HashSet and List using strings and objects.

Deciding which one to use between List, LinkedList, Dictionary, HashSet, etc. when you are doing a large number of iterations is mainly a matter of understanding how they are stored, and their runtime complexities. Below is a list of the implementation and asymptotic indexing/iteration time complexities of some of the .NET Generics:

Internal Implementation / Asymptotic Time Complexities for .NET Generics

---

+------------------+---------------------------------------+-------------------------+-------------+
|                  |                                       |         Item[i]         |             |
| Name             | Internal Implementation               |------------+------------| Iteration   |
|                  |                                       | Avg. Case  | Worst Case |             |
+------------------+---------------------------------------+------------+------------+-------------+
| List             | Array                                 | O(1)       | O(1)       | O(n)        |
| LinkedList       | Doubly Linked List                    | O(n)       | O(n)       | O(n)        |
| Dictionary       | Hashtable with links to another array | O(1)       | O(n)       | O(n)        |
| HashSet          | Hashtable with links to another array | O(1)       | O(n)       | O(n)        |
| SortedDictionary | Red-black tree                        | O(log n)   | O(log n)   | O(n)        |
| SortedList       | Array                                 | O(1)       | O(n)       | O(n)        |
| SortedSet        | Red-black tree                        | O(n)       | O(n)       | O(n)        |
+------------------+---------------------------------------+------------+------------+-------------+

To summarize, one can determine the most likely speed of iterating through these data types based on their time complexities. As far as it concerns fast finding of items, List, SortedList, Dictionary, and HashSet will always out-perform others, however List and SortedList are not advisable to use if you are going to be handling a large number of items which then puts Dictionary and HashSet on the advantage for large lists (where performance matters most).

References:

1. Runtime Complexity of .NET Generic Collection
2. Comparative Analysis of List, HashSet and SortedSet
3. Time complexity overview: Dictionary classes
4. Generic Collections in C# - Time complexity overview
5. Algorithms: Big-Oh Notation
6. Sorted Dictionary(Tkey, Tvalue) - MSDN
7. List(T) - MSDN

Glossary:

1. Red-black tree
2. Boxing and Unboxing