Objective

The Main Objective of this blog is to Make your games run 10 Times faster by understanding Arrays, Lists and Dictionaries in detail

 

This blog post is part of our ongoing Latest Optimization Initiative for Unity Games.

If you would like to learn how to optimize your games, you can check out this blog post:

Should I use Array? Or should I use List? Oh wait! Dictionary?

Why are my loops taking so much time??

I don’t see anything wrong with my code, then why is the execution of my code so slow?

Why is it taking so much time searching my required object?

I can’t see any Garbage Collection Issue, then why is my game lagging?

"These are some of the common questions we often come across while developing a game."
 

But yes these slow loops affect the game developers the most!

A few millisecond delays can make the player go mad!

At the end, we always end up blaming someone! “It’s Unity’s Fault, My Code is Perfect!” ;)

Well, that’s not always the case, it’s just sometimes we use wrong Data Structure collection and end up wondering, “Collections are so slow!”

In any applications we manage group of related objects by either of the two following ways:

  1. By creating arrays of objects
  2. By creating collections of objects

Each collection was developed keeping in mind its specific usage. Each collection has its own pros and cons, and it’s up to us which one suits our case.

In this blog post, I will get in depth of collections and help improve your understanding. I will cover all the common collections that are frequently used in unity.

WHAT ARE COLLECTIONS?

Collections are specialized classes used for data storage and retrieval. Collection classes generally cover purposes like allocating memory dynamically to elements and accessing a list of items on the basis of an index etc.

These classes create collections of objects of the Object class, which is the base class for all data types in C#. Unlike Arrays, Collections can grow and shrink dynamically as per the needs of the application, and this is its main advantage over arrays.

Collections make the process of memory management and data management quite easy.

SO WHICH ARE THE COMMON COLLECTIONS USED IN UNITY?

Dictionary and List are the most commonly used collections in Unity. Let me give a basic idea of Dictionary and List for beginners, others can skip to next section of the Blog.

  1. List
    • The C# List < T > class represents a strongly typed list of objects that can be accessed by index and it supports storing values of a specific type without casting to or from object.
    • Like any other collection it allows data processing functionality of addition, inserting, removing, searching etc.
    • Lists are indexed just like arrays, and the main advantage it gives is dynamism of its size.
    • E.g. we can make the list of GameObjects as:
      List<GameObject> myListOfGameObjects = new List<GameObject>();
  2. Dictionary
    • Dictionary is actually an updated collection of type hash table.
    • Dictionary represents a collection of keys and values.
    • For example, if 5 represents Red and 10 represent Green, we can link it up in Dictionary by stating 5 as the key for the value Red.
    • Thus, we can always find the Color Red by remembering the key as 5
    • This is how dictionary makes it easier searching through its data
    • E.g. We can make Dictionary object like:
      Dictionary<int, String>: //in this example ‘int’ is key and ‘String’ is value.
      Dictionary<int, String> myDictionary = new Dictionary<int, String>();

"Now as the main objective of this blog is of optimizing the usage of Collections, we will skip collections learning part here."

But if you want to learn it in detail, you can check out following links, which will help you learn the concepts of collections in detail:

  1. https://msdn.microsoft.com/en-us/library/ybcx56wz.aspx
  2. http://www.dotnetperls.com/
  3. http://www.tutorialspoint.com/csharp/csharp_collections.htm

HOW DO COLLECTIONS AFFECT THE GAME?

Let's take an example and understand how collections affect our game.

  1. Set up Scene in Unity as follows:
    • Take an empty Game Object and name it as per your wish (I have named it Test)
  2. Create a Script and name it as per your wish
    • I have named it as GenericCollectionsTest.cs
    • I use C# as my coding language, you can use javascript if you wish.
      public class GenericCollectionsTest : MonoBehaviour
      {
      
          #region PUBLIC_DECLARATIONS
      
          public int numberOfIterations = 10000000;
      
          #endregion
      
          #region PRIVATE_DECLARATIONS
      
          private Stopwatch stopWatch;
        
          private List<int> intList;
          private Dictionary<int,int> intDictionary;
          private int[] intArray;
      
          #endregion
      
          #region UNITY_CALLBACKS
      
          void Start()
          {
              stopWatch = new Stopwatch();
              intArray = new int[numberOfIterations];
              intList = new List<int>();
              intDictionary = new Dictionary<int, int>();
      
              AddFakeValuesInArray(numberOfIterations);
              AddFakeValuesInList(numberOfIterations);
              AddFakeValuesInDictionay(numberOfIterations);
          }
      
          void Update()
          {
              if (Input.GetKeyDown(KeyCode.Space))
              {
                  PerformTest();
              }
      
              if (Input.GetKeyDown(KeyCode.S))
              {
                  SearchInList(111);
                  SearchInDictionary(numberOfIterations - 1);
                  UnityEngine.Debug.Log("SearchComplete");
              }
          }
      
          #endregion
      
          #region PRIVATE_METHODS
      
          private void AddFakeValuesInArray(int iterations)
          {
              for (int i = 0; i < iterations; i++)
              {
                  intArray[i] = Random.Range(0, 100);
              }
          }
      
          private void AddFakeValuesInList(int iterations)
          {
              for (int i = 0; i < iterations; i++)
              {
                  intList.Add(Random.Range(0, 100));
              }
              intList[iterations - 1] = 111;
          }
      
      
          private void AddFakeValuesInDictionay(int iterations)
          {
              for (int i = 0; i < iterations; i++)
              {
                  intDictionary.Add(i, Random.Range(0, 100));
              }
              intDictionary[iterations - 1] = 111;
          }
      
          private void SearchInList(int value)
          {
              #region FIND_IN_LIST
              stopWatch.Start();
              int index = intList.FindIndex(item => item == value);
      
              stopWatch.Stop();
              UnityEngine.Debug.Log("Index " + index);
              UnityEngine.Debug.Log(“Time Taken to Find in List  ”+stopWatch.ElapsedMilliseconds+” ms”);
              stopWatch.Reset();
              #endregion
      
              #region CHECK_IF_CONTAINS_VALUE_IN_LIST
              stopWatch.Start();
              bool containsValue = intList.Contains(value);
      
              stopWatch.Stop();
              UnityEngine.Debug.Log(containsValue);
              UnityEngine.Debug.Log(“Time Taken To Check in List ”+stopWatch.ElapsedMilliseconds+” ms”);
              stopWatch.Reset();
              #endregion
          }
      
          private void SearchInDictionary(int key)
          {
              #region FIND_IN_DICTIONARY_USING_REQUIRED_KEY
              stopWatch.Start();
              int value = intDictionary[key];
              stopWatch.Stop();
              UnityEngine.Debug.Log((“Time Taken to Find in Dictionary   ”+stopWatch.ElapsedMilliseconds+” ms”);
              stopWatch.Reset();
              #endregion
      
              #region CHECK_IF_DICTIONARY_CONTAINS_VALUE
              stopWatch.Start();
              bool containsKey = intDictionary.ContainsKey(key);
      
              stopWatch.Stop();
              UnityEngine.Debug.Log(containsKey);
              UnityEngine.Debug.Log("Time taken to check if it contains key in Dictionary" + stopWatch.ElapsedMilliseconds+ “ ms”);
              stopWatch.Reset();
              #endregion
          }
      
          private void PerformTest()
          {
              
              #region ARRAY_ITERATION
              stopWatch.Start();
      
              for (int i = 0; i < intArray.Length; i++)
              {
      
              }
      
              stopWatch.Stop();
              UnityEngine.Debug.Log(“Time Taken By Array ”+stopWatch.ElapsedMilliseconds+ ”ms”);
              stopWatch.Reset();
      
              #endregion
      
              #region LIST_ITERATION
              stopWatch.Start();
              for (int i = 0; i < intList.Count; i++)
              {
      
              }
              stopWatch.Stop();
              UnityEngine.Debug.Log(“Time Taken By List ”+stopWatch.ElapsedMilliseconds+ ”ms”);
              stopWatch.Reset();
              #endregion
      
              #region LIST_ITERATION_BY_FOREACH_LOOP
              stopWatch.Start();
              foreach (var item in intList)
              {
                  
              }
              stopWatch.Stop();
              UnityEngine.Debug.Log(“Time Taken By List Using foreach  ”+stopWatch.ElapsedMilliseconds+ ”ms”);
              stopWatch.Reset();
              #endregion
      
              #region DICTIONARY_ITERATIOn_LOOP
              stopWatch.Start();
      
              foreach (var key in intDictionary.Keys)
              {
      
              }
              stopWatch.Stop();
              UnityEngine.Debug.Log(“Time Taken By Dictionary ”+stopWatch.ElapsedMilliseconds+ ”ms”);
              stopWatch.Reset();
              #endregion
          }
      
          #endregion
      }
  3. Breaking and understanding the code
    • Let us break down the code and understand it one by one
    • Here to show you the difference, I have taken
      intArray An integer Array
      intList An integer List
      intDictionary A Dictionary with both key and values as integer.
    • Now lets check the Start() Method
      void Start()
          {
           
              intArray = new int[numberOfIterations];
              intList = new List<int>();
              intDictionary = new Dictionary<int, int>();
      
              AddFakeValuesInArray(numberOfIterations);
              AddFakeValuesInList(numberOfIterations);
              AddFakeValuesInDictionay(numberOfIterations);
      
        stopWatch = new Stopwatch();
      
          }
    • Here I have initialized array, list and dictionary. I have also added some random values to them.
    • As you can see in the code, I created private methods for adding fake values in these collections.
    • I have also used a Stopwatch Object for the time and performance test purposes, and is also initialized here
    • If you do not know how Stopwatch works, first check out its working before moving ahead as it will be useful for understanding.
    • Refer the following link for the same:
    • Now lets check the method PerformTest()
    • I divided this method into 4 regions for better understanding:
      ARRAY_ITERATION Here we just iterate over the array
      LIST_ITERATION Here we just iterate over the List using simple for loop
      LIST_ITERATION_BY_FOREACH_LOOP Here we iterate over the List by using foreach Loop
      DICTIONARY_ITERATION_LOOP Here we iterate over the Dictionary
    • As you can see in the Update(), we call PerformTest() on pressing key ‘Space’.
    • So we will do the same by executing the program now.

      Note

      To get the exact idea of its performance we have used total iterations of 10 million for each data collection.

    • Your output should be something like the image below:
      collections-part-1
    • So does this mean Arrays are the best? Should we stop usage of others?
      No not at all, as I had mentioned at the start, all collections were designed keeping in mind its usage.
    • It’s just we have to be wise enough to know the right one for our requirements.
    • Let’s understand what kind of data structure we should use by considering few cases:

      Case 1) Number of objects remains the same throughout the game

      • Now here it’s not worth using List or a Dictionary, as obviously the number of objects doesn’t change. Than why give extra burden to memory and processor by using a collection?
      • Here Array's performance is twice as fast compared to List!

      Case 2) Number of objects keeps changing during gameplay

      • Since we know that arrays are not dynamic, the obvious choice is List. As objects keeps changing and it is faster to manage as compared to Dictionary.
      • In case of object pooling, Lists are commonly used to manage the pool.
      • Lists are almost 8-10 times faster compared to Dictionary
      • If you iterate through a List using foreach loop it will almost take 3 times the time than the normal for loop, as seen in the above example thus adding one more disadvantage of using foreach loop.
      • If you want to see other disadvantages of foreach loop check out my following blog
        http://www.theappguruz.com/blog/foreach-loop-optimization

SO DOES IT MEAN I SHOULD STOP USAGE OF DICTIONARY COMPLETELY?

Nope, not at all. Let us move ahead with the next part of this example to understand it. There are two methods SearchInList() and SearchInDictionary()

They are again separated in two parts:

SearchInList() Method’s first part is to find a value that is passed to it in the List, and the second part will check if it actually contains the value, and return Boolean accordingly.
SeatchInDictionary() Method’s first part is to get the value according to the key passed to it, and the second part will check if the method has a specific key or not, by using ContainsKey()

Again these methods are called on pressing Key ‘S’. So let’s again execute the program and check the log.

Output would be something like this:

collections-part-2

So the obvious conclusion from above picture is that search time is almost nil when it comes to dictionary.

So whenever there is going to be case of continuously finding some object throughout the game, wiser choice would be to choose dictionary

ACCEPT IT! YOU CAN'T CREATE A GAME WITHOUT COLLECTIONS

Yes, it’s true, and it’s not bad either. Just proper knowledge of its implementation is required for quality Data structure management

Conclusion is simple, with three basic guidelines:

  1. Do not use Lists when a number of objects remains same and also there is no requirement of intensive searching.
  2. If objects are dynamic and searching is not a priority, List is the way to Go!
  3. Fast access and the less changes in objects, then Dictionary would be the wise choice

You can also go through following links to get more in-depth study of the same:

Feel free to ask me questions in the comment section, will be happy to help. And keep checking our blog, we will be adding lot of blog posts.

I hope you find this post usefule while developing game. If you still don’t get it, you can always ask me questions in the comment section. I will surely get back to you for the same.

"So that’s it for this post! Keep checking our BLOG section. We will keep updating new tips and tricks of optimization. And help you simplify the hard phase of optimization."

This blog post is part of our ongoing Latest Optimization Initiative for Unity Games.

If you would like to learn how to optimize your games, you can check out this blog post:

Got an Idea of Game Development? What are you still waiting for? Contact us now and see the Idea live soon. Our company has been named as one of the best Unity 3D Game Development Company in India.

Talented Game Developer as well as a player with a mania for video games and the game industry. Always Ready to take up challenging Projects. Proud to be making with the TheAppGuruz Team