Preamble
Code optimization is very important for developers; especially video game developers. In a world where reflexes and timing are so important you have to keep optimization always in mind. There are good practices and bad practices for optimizing your code.
In providing some support on another thread I received some information regarding a more optimized approach to shifting the contents of an array. Another community member, @steego , brought several variations of this sort of data manipulation to my attention.
With my curiosity piqued, I set about writing a few classes to test his suggestions and get a clear illustration of which approach is actually the most efficient, but I digress. Who cares how this all came about? You just want to optimize your code and get back to business, right? Let’s continue!
Question
What is the most efficient way to generate and shift a collection of integers? What is the best way to store these integers? Moreover, what is the best way to test the efficiency of a block of code and compare it against other solutions that produce the same result?
Methodology
I used two custom classes to test this. I set these classes up in such a way that you could simply place a method before and after your block of code and those methods work in tandem to return the time elapsed between them to the debug console. Simple enough, right?
The first class I’m going to outline is the static class that I used to call these methods. It just contains a Dictionary and two methods.
using System.Collections.Generic;
using hamsterbyte.MethodTimer;
public static class MethodTimer {
public static Dictionary<string, MethodTimerObject> methodDictionary;
public static void Start(string name) {
if(methodDictionary == null)
methodDictionary = new Dictionary<string, MethodTimerObject>();
methodDictionary.Add(name, new MethodTimerObject(name));
methodDictionary[name].Start();
}
public static void End(string name) {
if(methodDictionary != null) {
if(methodDictionary.ContainsKey(name)){
methodDictionary[name].End();
methodDictionary.Remove(name);
}
}
}
}
The second class is the MethodTimerObject itself. This class serves as a container for individual timers and their data/methods.
using System.Diagnostics;
namespace hamsterbyte.MethodTimer
{
public class MethodTimerObject
{
private Stopwatch _stopWatch;
private string _name;
private float _startTime;
public string Name { get { return _name; } set { _name = value; } }
public MethodTimerObject (string name)
{
_name = name;
}
public void Start ()
{
_stopWatch = new Stopwatch();
_stopWatch.Start();
}
public void End ()
{
UnityEngine.Debug.Log ("\"" + _name + "\"" + " completed in " + _stopWatch.ElapsedMilliseconds + "ms");
_stopWatch.Stop();
}
}
}
Lastly, I used a basic Monobehaviour to test and interact with these classes and the data in question. I used a few different data containers: LinkedList, Queue, and of course an int[ ] array.
The first thing I did was write methods to populate each of these containers with 5 million random integers. Then I shifted the data in each of these containers once to the left using several different methods.
using UnityEngine;
using System;
using System.Collections.Generic;
public class Example : MonoBehaviour {
Queue<int> _theQueue = new Queue<int>();
LinkedList<int> _theList = new LinkedList<int>();
int[] _theArray = new int[5000000];
// Use this for initialization
void Start () {
MethodTimer.Start("Populate List");
PopulateList();
MethodTimer.End("Populate List");
MethodTimer.Start("Populate Queue");
PopulateQueue();
MethodTimer.End("Populate Queue");
MethodTimer.Start("Populate Array");
PopulateArray();
MethodTimer.End("Populate Array");
MethodTimer.Start("Shift Loop Array");
_theArray = Shift(_theArray);
MethodTimer.End("Shift Loop Array");
MethodTimer.Start("Shift Copy Array");
_theArray = ShiftCopy(_theArray);
MethodTimer.End("Shift Copy Array");
MethodTimer.Start("Shift List");
ShiftList();
MethodTimer.End("Shift List");
MethodTimer.Start("Shift Queue");
ShiftQueue();
MethodTimer.End("Shift Queue");
}
public void PopulateArray() {
System.Random r = new System.Random();
for(int i = 0; i < _theArray.Length; i++){
_theArray[i] = r.Next(0, 100);
}
}
public void PopulateQueue(){
System.Random r = new System.Random();
for(int i = 0; i < 5000000; i ++)
_theQueue.Enqueue(r.Next(0, 100));
}
public void PopulateList() {
System.Random r = new System.Random();
for(int i = 0; i < 5000000; i++)
_theList.AddLast(r.Next(0, 100));
}
public int[] Shift(int[] myArray){
int[] tArray = new int[myArray.Length];
for(int i = 0; i < myArray.Length; i++){
if(i < myArray.Length - 1)
tArray[i] = myArray[i + 1];
else
tArray[i] = myArray[0];
}
return tArray;
}
public int[] ShiftCopy(int[] myArray)
{
int[] tArray = new int[myArray.Length];
int v = myArray[0];
Array.Copy(myArray, 1, tArray, 0, myArray.Length - 1);
tArray[tArray.Length - 1] = v;
return tArray;
}
public void ShiftQueue () {
int v = _theQueue.Dequeue();
_theQueue.Enqueue(v);
}
public void ShiftList () {
int v = _theList.First.Value;
_theList.RemoveFirst();
_theList.AddLast(v);
}
}
Using these two classes to return the time elapsed during the execution of a code block returned some very interesting results. Keep in mind that I am not claiming this is the best way to test something like this; apparently the built in profiler has similar methods to the ones I’ve written. You can enclose any code you want between the two methods as illustrated above and it will return a debug statement telling you how long it took to execute that code. Let’s move on.
Results
The results of my testing with this methodology were quite interesting and they lead me to believe this same type of procedure could be applied to any code; this methodology, though unrefined, is universal.
Here’s a graphic displaying a block of results in the debugger:
I took the liberty of sorting these in the script by order of their efficiency. As you can see the speed with which I was able to populate the data in various containers differed quite a bit; LinkedList took the longest to populate and Queue was a close second behind the array.
Shifting this data was a whole different story. I used two methods for shifting the data in the array: A basic for loop and a copy and replace style method (more details can be gleaned from the Monobehaviour above). I found that the for loop was on average 10x slower than the copy and replace method.
When shifting the LinkedList and Queue things got really interesting Both of these methods returned an average of less than 1ms; in fact, most of the time they returned 0ms.
Your results will vary every time you check the elapsed time of your code, this is not an error, it is the expected behaviour. The best thing to do is compile a large amount of results and calculate the average; you will have outliers in your data set.
Summary
In closing, I think all developers should be aware of good optimization techniques. This is especially important if you intend to develop applications for mobile platforms. Mobile devices have come a long way in the last few years, but they still pale in comparison to a console and especially to a high end gaming PC.
The best thing to do is always be aware of optimization. Make yourself knowledgeable about good optimization practices and apply that in your work. Feel free to use the scripts in this thread to test the efficiency of your code. Completely open-source. I may refine the concept even more and set up a public repository for the project on git. If anyone has any suggestions for refining my methodology I would love to hear them as I intend to use this to optimize blocks of my code from this point forward. Thanks for taking the time to read this thread and best of luck to each and every one of you in your future endeavours!
