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





3 comments:

  1. Really Amazing Blog. In Case You Wish You Read Some Similar Blogs Or Find A Great Choice Of Everything Online, Use The Coupons Codes And Discounts Codes From Our Site.
    Coupons Codes

    ReplyDelete
  2. -----------------------------------------------

    Chicken Invaders 5 You will be happy with the spoils you receive from the enemies that come towards you and the eggs that fall towards you. Let's get more advanced weapons by playing this game and collecting the spoils. Have fun.

    -----------------------------------------------

    One Piece Adventure Yeah, you're up against a whole new fighting game. Will you be able to save your character from creatures approaching you ? What you should do. You have to try to get the highest score once you get the highest score, you can strengthen your character for the next episode. We wish you a good time with One Piece Adventure Good luck

    -----------------------------------------------

    One Piece Vs Naruto 4.0 Indispensable of the fighting game! With the new version, the developers added quite a lot of characters in this version. One Piece Vs Naruto 3.0. We claim that you will love the version. Let's start the game and look at the changes. Have fun

    -----------------------------------------------

    Bad Ice Cream 4 Fun is waiting for you with new version. With the new update, Bad Ice Cream 4 has become one of the most popular games of the year. If you want to have fun you can start playing now.

    -----------------------------------------------

    Krunker.io we believe you'll enjoy it. Because it's an Online game, the opponents will be real people, so you have to be careful. Krunker.io we wish you good luck in advance. Enjoy yourselves

    -----------------------------------------------

    ReplyDelete
  3. I am very curious to know about the Unity coding. Your blog is very beneficial for me. Thanks a lot for sharing your views and thoughts on this topic and make it valuable. Keep blogging!
    iGaming Software Development Solutions

    ReplyDelete