Unity tutorial: Optimize removes from List

 

Follow @SBC_Games

 If you maintain long List of items in your code and you often need to remove some at arbitrary position within it, then you pay performance penalty as all items with higher index have to be copied one position left.

 This is how code for method List.RemoveAt() looks:

        public void RemoveAt(int index) {
            if ((uint)index >= (uint)_size) {
                ThrowHelper.ThrowArgumentOutOfRangeException();
            }
            Contract.EndContractBlock();
            _size--;
            if (index < _size) {
                Array.Copy(_items, index + 1, _items, index, _size - index);
            }
            _items[_size] = default(T);
            _version++;
        }

 If item you want to remove is not the last one, then Array.Copy() is called. If your list is long and you are removing items at beginning, then performance costs may be high. But, if you do not care about order of items, you can write simple extension method, that will swap item you want to remove with last item in list and then call RemoveAt() on it. As item to remove is now last one, no copying of array is needed. Here is code for FastRemoveAt method:

using System.Collections.Generic;
using UnityEngine;

public static class ListExtensions {

    public static void FastRemoveAt<T>(this IList<T> list, int index) {
        // fast remove swaps item to remove with last item and then removes it
        // it should avoid internal Array.Copy, but changes order of items in List

        int lastIndex = list.Count - 1;

        T tmp = list[index];
        list[index] = list[lastIndex];
        list[lastIndex] = tmp;

        list.RemoveAt(lastIndex);
    }
}

 For test I created list with 100k items. Then, in loop, I remove first item in it and also add new item to the end, so it keeps its length. This is test code:

        // test
        Debug.Log("=========================================");
        var startTime = Time.realtimeSinceStartup;

        var list = new List<int>();
        var val = 0;

        for (; val < 100000; val++) {
            list.Add(val);
        }

        for (int i = 0; i < 1000000; i++) {
            //list.RemoveAt(0);
            list.FastRemoveAt(0);
            list.Add(val++);
        }

        Debug.Log("Time taken = " + (Time.realtimeSinceStartup - startTime));
        Debug.Log("=========================================");

 With both methods RemoveAt() and FastRemoveAt() I got these results for various number of updates:

 As you can see, FastRemoveAt() is much faster then RemoveAt().

Pirates! - the match 3 made it into Apple AppStore

 

 Our game Pirates! - the match 3 is finally finished and its iOS version just made it into Apple AppStore. You can get it here:

 Pirates! is classic match 3 game with many different tasks for players - dig treasures, open chests, fight enemies or fulfil other tasks you are given in each level. It also features lot of gems combinations to produce various gameplay effects. Graphics for game was made by Tomáš Kopecký and music was composed by Juraj Růžička from SoundRoseStudio.

Flat Jewels Match 3 at Yahoo! Japan

 

 On 11th September our game Flat Jewels Match 3 was published at Yahoo! Japan. Game was published by Worker Bee Inc. and you can play it on their site here.