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





13 comments:

  1. -----------------------------------------------

    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
  2. 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
  3. Very significant Information for us, I have think the representation of this Information is actually superb one. This is my first visit to your site. Mobile App developer

    ReplyDelete
  4. This blog is very helpful for us.Thanks for sharing these valuable information with us.Game Development

    ReplyDelete
  5. There is definately a great deal to know about this subject. I like all of the points you've made. Visit: Poker Game App Development Company

    ReplyDelete
  6. Thanks for sharing this amazing content. I learn new information from your article, you are doing a great job. Keep it up.

    Cryptocurrency Wallet Development Company

    ReplyDelete
  7. It's really nice and meaningful. it's really cool blog. Linking is very useful thing. you have really helped lots of people who visit blog and provide them useful information. Visit: Dhamaal Games

    ReplyDelete
  8. Hello! Checking your dissertation with our online student tool will save you time and help you edit your text accurately. We have developed this assistant so that each student can be one hundred percent sure of his dissertation and receive only high scores for his work! >> college paper checker

    ReplyDelete
  9. Good afternoon everyone, do you know about the paraphrase generator free? It's a very handy and useful tool for writers, editors and even ordinary users. This tool will be able to edit your text quickly and for free, paraphrasing the right words or sentences. A nice bonus is that here you can also check your text for all kinds of errors and plagiarism. Try it and enjoy the results!

    ReplyDelete
  10. Sentence correction online is a new and easy-to-use tool that I strongly recommend you use when writing various text works. This tool will replace copywriting agencies that will charge you a lot of money and will do it for more than one day. The tool will do the same, only many times faster. All you have to do is add your text to it and wait a bit!

    ReplyDelete
  11. Best mobile game companies is one of the best mobile game companies out there. They have an amazing portfolio of games for both iOS and Android platforms, and their customer service is top-notch. Highly recommended for anyone looking for a reliable and high-quality mobile game development experience!"

    ReplyDelete