Fastest Collection to Use for Optimization in Unity3D?

Question

I was reading about how collections such as Built-in Arrays and Lists differ from each other, and noticed that built-in arrays are a lot faster than Lists (up to 7 times as faster in certain situations).

So my question is, If I use built in arrays that I do not fill completely but instead have a max value, and use a counter int to keep track of the size, will it be significantly faster than using Lists?

The reason it matters is I have a multiplayer game that I built the server for myself in Node.js from the ground up, and am using websockets-sharp as the library for the client, and am seeing some lag due to the collections I have to modify and check in my update functions (using Lists, Stacks, Dictionary, and Queues) and am wondering byte[] array would increase performance.

P.S. Here are is where I got the information from about built in array performance vs System.Collections:

http://answers.unity3d.com/questions/38479/is-listt-as-fast-to-access-as-a-standard-array.html

Performance differences... so dramatic?

http://wiki.unity3d.com/index.php/Choosing_the_right_collection_type

Answer 1

If I use built in arrays that I do not fill completely but instead have a max value, and use a counter int to keep track of the size, will it be significantly faster than using Lists?

Yes.

I've done experiment with Unity in the past and doing this is totally fine for large amount of items that needs to be looped over every frame such as image processing.

I once made an app that stream HQ Image over the network. It was easy to make with a List but after I switched to Array, the number of frames I received per second increased. It also got ride of memory allocation.

The only down side to using Array is that you have to allocate large amount of memory to make sure that it is enough to hold your items. You also have to check if the current item you want to put in the array can fit. If not, you have to create new array with bigger size, then copy old data to the new one.

Unity's blog also has a post that shows the performance different between using Array and List to improve the Update() function. It is really a big performance increase and the Array is about 5x faster than List in that experiment.

These are the rules I set for myself when working Unity and it still remians to be true even today:

1.If you need to store large items(200k and above) that requires you loop through them every frame, use array and a simple int value that you can use to determine the length of the array.

2.If this is just items about the size of 5,000 and runs only once in a while then use List.

I modified this code to run in Unity and below is the result.

Array/for: 6726ms (-1295415896)

List/for: 15803ms (-1295415896)

Array/foreach: 8511ms (-1295415896)

List/foreach: 42689ms (-1295415896)

The difference is very important in Unity unlike a normal C# Application.

void Start()
{
    List<int> list = new List<int>(6000000);
    for (int i = 0; i < 6000000; i++)
    {
        list.Add(UnityEngine.Random.Range(1, 10));
    }
    int[] arr = list.ToArray();

    int chk = 0;
    Stopwatch watch = Stopwatch.StartNew();
    for (int rpt = 0; rpt < 100; rpt++)
    {
        int len = list.Count;
        for (int i = 0; i < len; i++)
        {
            chk += list[i];
        }
    }
    watch.Stop();
    UnityEngine.Debug.Log(String.Format("List/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk));

    chk = 0;
    watch = Stopwatch.StartNew();
    for (int rpt = 0; rpt < 100; rpt++)
    {
        int len = arr.Length;
        for (int i = 0; i < len; i++)
        {
            chk += arr[i];
        }
    }
    watch.Stop();
    UnityEngine.Debug.Log(String.Format("Array/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk));

    chk = 0;
    watch = Stopwatch.StartNew();
    for (int rpt = 0; rpt < 100; rpt++)
    {
        foreach (int i in list)
        {
            chk += i;
        }
    }
    watch.Stop();
    UnityEngine.Debug.Log(String.Format("List/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk));

    chk = 0;
    watch = Stopwatch.StartNew();
    for (int rpt = 0; rpt < 100; rpt++)
    {
        foreach (int i in arr)
        {
            chk += i;
        }
    }
    watch.Stop();
    UnityEngine.Debug.Log(String.Format("Array/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk));
}

Answer 2

In the overlap of functionality between arrays and lists the fact that lists implemented by wrapping an array means that we would almost always expect arrays to be faster, and that's before considering that directly accessing the array can allow some compiler and jitter optimisations, too.

That said, there's now more that you have to do, if you are going to do something list provided and arrays don't. If your doing that isn't as efficient as the code in list, you're just going to make things slower. Even if done perfectly you might e.g. not be able to have code that lets the jitter skip the bounds check (because you are leaving some space at the end of the array for example) which means that the real performance won't be as good as a benchmark where the jitter could do that).

All the more so when it comes to dictionary, which you also mention as arrays do not provide the same hash-based O(1) lookup.

Really, to switch to arrays from lists in the interest of performance you want to study the code of List (the source is available) understand where the costs are, and then consider how those costs affect your given usages. That'll be a guide to where switching will gain, lose, break, or just be a waste of time.