Saturday, September 30, 2017

Unity tutorial: Optimize removes from List

 





 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().





6 comments:


  1. Really appericiated post. Thanks for sharing this article. I usually go through your blogs. Contact to the Poker Card game development Company for

    best results.

    PokerDevelopment
    PokerAppDevelopment
    CardGameAppDevelopment
    CardDevelopment
    CardAppDevelopment

    ReplyDelete
  2. In my view, your website is well organized .I am a gaming blog writer to check out my blog to learn more and download War Thunder.
    click here

    ReplyDelete
  3. Great information...I am happy to find this post Very Helpful for me, as it contains lot of information. We are the Best Mobile App Development Company in India.

    ReplyDelete
  4. Good Information
    We are the best piping design course in Hyderabad, India. Sanjary academy Offers Piping Design Course and Best Piping Design Training Institute in Hyderabad. Piping Design Institute in India Piping Design Engineering.
    Piping Design Course
    Piping Design Course in india
    Piping Design Course in hyderabad

    ReplyDelete
  5. Thanks for sharing information
    Sanjary kids is the best playschool, preschool in Hyderabad, India. Start your play school,preschool in Hyderabad with sanjary kids. Sanjary kids provides programs like Play group,Nursery,Junior KG,Serior KG,and Teacher Training Program.
    play school in hyderabad
    Preschool in hyderabad
    Preschool teacher training course in hyderabad
    pre and primary teacher training course in hyderabad

    ReplyDelete