- Home /
List.RemoveAt() Causing Huge Memory Allocation
So one of my scripts is causing a very large Garbage Collection Allocation in the Unity Profiler. I have narrowed the cause down to one of my Generic Lists. Every frame the List.Add() function is called along with List.RemoveAt(0). When I comment out the List.RemoveAt(0) the memory allocation remains at 100 bytes, but when I un-comment it again the allocation jumps to 211 kilobytes! What is happening!? If anyone has any idea, any help would be greatly appreciated! Thanks.
Just so it gets said, this is 2015 and two tenths of a megabyte isn't exactly a huge allocation.
List operations are somewhat expensive; someone correct me if I'm way off, but internally, add/remove represent the creation of a new collection with copied elements. Ergo the time cost scales with the size of the list, and the memory cost with the complexity of list elements.
This may or may not be the only issue causing the noticeable spike; I have found the profiler is great for putting you in the general area of an issue, but doesn't always point directly to the only issue.
Thanks again sir. Yes, .2$$anonymous$$B is not very much but that being allocated every frame seems a bit costly to me. Would there be an easy way to remove the first element of a built-in array?
Tell us more details about your list:
How many items are in the list? (Since you always add one and remove one it should be a more or less fix amount after the initial seeding).
What does the list contain? A reference type (class, string) or a value type (struct, primitive datatype)?
If it's a reference type, is it a type derived from UnityEngine.Object or a "normal" C# class?
If it's a reference type, do you actually create new instances each frame or do you just move existing references around between lists?
There is nothing like a "Garbage Collection Allocation". Either you mean memory that has been collected by the Garbage Collector (in which case the memory is deallocated) or you mean an actual memory allocation in which case the GC is out of the question for the moment.
It would probably help to see the offending code snippet (with the add and remove statement) and if it's a custom class, what elements it constains.
There are between 0 and 4 items in the list since I am waiting until the list is empty before adding 4 and then removing them one by one.
The list contains a struct which contains 3 int values.
$$anonymous$$y bad. I mean that the memory has been collected by the Garbage Collector. Sorry about that.
Answer by supernat · Apr 04, 2015 at 03:53 PM
If you plan to remove the first element every frame, a standard list may not be the best approach. You should use a form of Linked List instead, so that removing the first element is a simple O(1) operation (I think that's right...been a while since I've thought about O(n) type stuff).
However, the problem you have is that you are commenting out the removal of the first element, so if you are also adding new elements every frame, the memory will grow continually. That's expected.
Huge question-asking failure on my part. I meant to write that the other way around: when I comment out the RemoveAt(0) the mem alloc is at 100b, but when I un-comment it the mem alloc goes to 211kb. I have edited the question.
I tried converting to a LinkedList and the same issue still occurs.
Ahh, I thought it was an odd question, haha. Well, I'm surprised that LinkedList doesn't help the GC size at least a bit, but maybe try using a Queue ins$$anonymous$$d, assu$$anonymous$$g you always only pop off the first item in the queue. Queue is First In First Out (FIFO), so the first item pushed in will be the first item popped off (i.e. oldest items popped off in order they arrived). The reason I suggested a LinkedList is because it's a doubly linked list, meaning that C# should be able to just remove the first item by disconnecting the front node, but if you're running with a pretty old version of .NET (2.X), maybe it used to be singly linked (don't really know). The Queue should definitely be able to provide some sort of memory enhancements. The other possibility is that the List type has very good memory management and works just as well as a LinkedList in this particular condition (my assumption for a List would be that it had to move the entire list after item 0 backward by reallocation, but it could be smart enough to realize that since you are removing element 0, it has some internal offset index and leaves the memory intact as-is.).
Well said @supernat. When your program$$anonymous$$g education starts and ends with C#, memory management gets overlooked til the final hour. Also I've been spoiled by developing exclusively on desktops; I wouldn't bat an eye at these allocations.
Interesting-if-true regarding "smart" lists that don't reallocate when removing the zeroth element. I do often wind up using lists even when I want FIFO/FILO behavior; it'd be cool to know for sure whether these operations are cheaper than they appear.
Answer by kingcoyote · Apr 05, 2015 at 12:14 AM
A List datastype is actually a resizing array, as shown recently when the C# code was open sourced.
What this means is that the list is initialized as an array with a set capacity, 4 by default. If you try to add a 5th element, a new array of size 8 is created, the first 4 are copied, and the 5th is added. If you try to add a 9th element, a new array of size 16 is created, the first 8 are copied and the 9th is added.
This amortizes the cost of adding an element to a list pretty nicely, since the size doubles each time and the copy operation only happens when you reach max.
On the flip side, this means that removing an element from the array is really, really, really fucking costly. A lot. Unless you remove it from the end!
If you have a list with 1000 items and you remove at 0, you have to copy 999 items to the new array, each offset by 1. If you remove at 999, you do nothing but mark the length of the list as being a little smaller and say that element 999 doesn't exist anymore.
So if you can find a way to reverse the order of your list and remove at the end rather than the start, you'll shave off nearly 100% of the overhead.
And I disagree with @AlwaysSunny. 0.2mb is a lot, relative to the size of this operation. But maybe that's just my perspective coming from the embedded systems world where 200kb of program memory is a lot, let alone 200kb of RAM.
First of all the implementation of the List can easily be viewed with any .NET reflector like ILSpy and is nothing new. Second the implementation of mono's List is slightly different from the original .NET implementation.
Removing an item from the list never creates a new array. It just has to move / copy all elements one index down. So index0 receives index1, index1 receives index2, ... This doesn't allocate any new memory. The capacity only grows if it runs out of free "slots".
As i said in my comment above we can't say anything about his actual problem with that little information.
The article you linked seems to be more like a rant on the List class than any real summary. If you really plan to add 2$$anonymous$$ items to a list you set the capacity manually beforehead. The acticle doesn't even mention that possibility.
The OP most likely can't reverse the order since he add and remove an element each frame. So he use it like a queue where the oldest element should be removed. If the max-size known a simple circular buffer would be the most efficient solution. But again we don't know how he uses the List exactly, with how many items, .... so we can't say much about what's going on.
The first summary point in the article actually mentions that you can specify the size on creation.
And the reason I posted this is because the Linked List data type operates very differently than the Resizing Array datatype. I may have had some nuances wrong, but the gist is the same - a Linked List is very fast on add/remove, very slow on lookup, a resizing array is the opposite.
Resizing arrays are especially bad at removing from the start, since you have to touch every element to do it, which is not obvious to those who expect List to operate like a Linked List.