How are you handling enum list.Contains and garbage collection?

Unity Engine
1

Due to comparing enums causing boxing in lists.Contains, there is a lot of memory being allocated causing a lot of garbage collection.

Take this code for example
Click for code

using UnityEngine;
using System.Collections.Generic;

public class TestListGarbageCollection : MonoBehaviour
{
    public enum Test {EnumList, EnumToIntList}
    public Test test;

    enum TestEnum {One, Two, Three}

    List<TestEnum> enumList;
    List<int> enumIntList;
    public int loopAmount = 100;

    void Start()
    {
        enumList = new List<TestEnum>() {TestEnum.One};
        enumIntList = new List<int>() {(int)TestEnum.One};
    }

    void Update()
    {
        for(int i = 0; i < loopAmount; i++)
        {
            if(test == Test.EnumList) if(enumList.Contains(TestEnum.Two)){} //seems to allocate 40B per enum in the list that it checks over (probably due to boxing)
            if(test == Test.EnumToIntList) if(enumIntList.Contains((int)TestEnum.Two)){} //seems to allocate nothing
        }
    }
}

When comparing enums in a list, for every enum in the list there will be a 40B memory allocation for each enum you compare. (doing “if(TestEnum.One == TestEnum.Two){}” causes no memory allocations)
However, if you cast the enums to ints, there seems to be no memory allocated.
The code above is causing garbage memory of about 4KB each frame since it is looping 100 times per frame.
This is only when there is 1 enum in the list. If there were 10 enums, it would be about 40KB per frame, while the int version still shows 0.

I am wondering how people are handling this? Its difficult to make any generic enum method or classes due to there being no enum constraint, so that seems to be out of the question.

Should I just do what I am doing here and always cast an int?

Any info is appreciated!

2

It’s because List.Contains uses the default EqualityComparer:

The default EqualityComparer for enums uses the Enum.Equals method:

Note the Enum.Equals method takes an object, so that’s what is causing the boxing, and thusly the garbage.

Unfortunately List doesn’t allow for you to define the equality comparer to use… otherwise I’d tell you to just pass in a custom EqualityComparer that avoided the Enum.Equals method.

Another option, if you don’t need an ordered indexed collection like List, is to use an unordered collection like a HashSet:

HashSet has a few features that may or may not help you:

  1. it does not allow duplicates (this may be a good or bad thing depending your design, not sure what you need this collection for precisely)
  2. testing if the collection contains anything is theoretically an O(1), as opposed to List which is O(n)
  3. it allows for custom EqualityComparers to be used
2 Likes
3

Yea, when looking this up I saw people making custom equality comparers for dictionaries, but I didnt see anything for lists.
In this particular case, hashsets may work, but I am more so curious as to what people do when it comes to lists.

4

Wow. That is arcane.

How about making it a List? Enums should cast to ints implicitly and that will avoid the call to Enum.Equals.

5

Im not sure as to what you mean. Do you mean what I am alread doing in my example code where I have a list of ints and when adding the enum I cast it to an int, and when checking for an enum I also cast it to an int?

That is how I am handling things at the moment, but enums and lists seems like a basic useful thing many would use, so I am wondering what better way there may be to handling this, or is this just something many dont know about?

6

What are you attempting to do?

Is a List necessary for what you’re attempting to do?

Why I ask is that it’s true this is an unfortunate implementation of how .Net/Mono generalize System.Enum comparisons. Which impacts the List when it is a collection of enums. As eisenpony described it… it’s arcane.

And yeah, most people probably don’t notice it ever. Primarily because in .Net the garbage collector isn’t as sloppy as the one used in the version of Mono that is in unity. And for those who write Mono, the garbage collector in the latest versions of Mono are also pretty darn good. But alas, unity has an outdated one, and garbage collection hits the framerate rather hard (ugh). So really it’s only unity users who would even be looking for this, and only those who are looking for GC optimizations.

Thing is… a List of enums might not be as common as you think.

For example… I can’t think of ANY time I had a collection of enums. I use enums a lot, and I don’t have a single List anywhere in my code.

It might be because whatever you’re attempting to accomplish has another method of accomplishing it… and I just never thought to use a List to do so.

Or maybe you’re attempting to accomplish something I’ve never thought to accomplish before.

So… what are you trying to do? What does this List of enums represent?

1 Like
7

Well as I said in my previous post, hashsets should work fine for my case since I am mainly just caching key presses and…
1 - I do not want duplicates
2 - having a O(1) instead of O(n) is great
3 - custom equality compare for the win

However, what if I cared about duplicate presses and their order? A list of keycodes can be an easy way to not only get how many times a key was pressed, but also in what order.
Could there be another way of doing this? Maybe, but there can be many many ways to do anything, and many say that simplicity and readability is important. Having a list of the keycodes seems simple and readable to me.

8

Sorry, I hadn’t looked at your code. Yes, this is precisely what I meant.

enumIntList = new List<int>() {(int)TestEnum.One};
if(enumIntList.Contains((int)TestEnum.Two)){}

However, I think Enum can cast to int implicitly (I could be wrong), so you can shorten this to

enumIntList = new List<int>() {TestEnum.One};
if(enumIntList.Contains(TestEnum.Two)){}

However, lordofduct is right, as usual. I don’t think List is very common. At least not for me.

1 Like
9

I get errors, so I do not think this is possible.

10

For what you describe, it sounds like it could be represented with a Stack or a Queue (depending access):
https://msdn.microsoft.com/en-us/library/3278tedw(v=vs.110).aspx
https://msdn.microsoft.com/en-us/library/7977ey2c(v=vs.110).aspx

Neither allow defining your own comparer either.

BUT, in the situation you describe I usually use this custom class of mine:
https://github.com/lordofduct/spacepuppy-unity-framework/blob/master/SpacepuppyBase/Collections/CircularQueue.cs

The reason I use this is because usually such history is usually stored for so long and so many presses. I don’t care about a key press 20 presses ago usually. The only situation I could see storing an ever growing number might be to allow an ‘undo’ feature… in which case you’ll want a Stack anyways.

So with this thing, you set how many entries the collection stores at max. And as you add in values, and you reach that number, the oldest entry is dropped off the que. So like say you had ints and set the size to 4 you’d get:

1
1,2
1,2,3
1,2,3,4
2,3,4,5
3,4,5,6

As you added entries.

It also allows for a custom comparer.

And I made the Enumerator on it a struct so that there’s no boxing if you directly access the Enumerator (just like List). Queues aren’t indexed, and foreach causes garbage (the enumerator is boxed). So your way around it is the struct enumerator directly. Like so:

var e = que.GetEnumerator();
while(e.MoveNext())
{
    //do something with e.Current
}

Note that with List you can actually do this to get a custom comparison. You can even wrap it into your own extension method:

public static bool Contains<T>(this List<T> lst, T item, IEqualityComparer<T> comparer)
{
    var e = lst.GetEnumerator();
    while(e.MoveNext())
    {
        if (comparer.Equals(e.Current, item)) return true;
    }
    return false;
}

Note, this only works if you reference List, Queue, CircularQueue, and the sort directly. When you reference them with their interfaces like IList and ICollection, the GetEnumerator method returns the enumerator as the interface IEnumerator, which will box the struct version of the enumerator in those classes.

11

I have not read over all your code since there is a lot of it, but even with the ability to have a custom comparer, does the comparer work with generic enums? Or do I need to make a custom comparer for each enum type that I want to use?

And all this just to avoid casting to an int (I know enums can be other things besides int, but for my uses, int is fine).

If only there is a way to just have a generic class like EnumList that can do the int casting for me, but I cant seem to cast a generic enum. (doing Convert.ToInt32 seems to allocate memory, so that cant be the solution)

12

you don’t have to avoid casting to an int.

You could just use a List like in your original example. It’s not like that cast is all that expensive.

I was just showing you a different type of collection for queues and what not. Note I linked to the .Net versions of stacks and queues. And also enumerators.

Basically a crash course in the various collections and their impacts on garbage collection. For example List in and of itself generates garbage as you add entries to it. Because as you add entries it has to resize the array inside of it, throwing out the old array when doing so.

13

Always casting to an int seems messy and annoying to do, but it is what I am currently doing since its simple. Or I can create a solution for each individual enum type if needed.

You can set a capacity to lists to try and avoid that. You can also do other tricks such as swapping the item you want to remove from the list with the last item in the list and then removing the last list item. (not that you arent aware of this already)

14

Nah, it’s not really that messy at all.

You basically just described my CircularQueue.

The entire point of it is to create a clean interface for such a thing.

15

Just extend List with a contains method that doesn’t do GC allocation. It’s just a simple for loop.

Not sure exactly how extension on generics works, or if it’s possible. You might do better off with a static helper method specifically for List

16

You can extend List, since it’s not sealed or anything, but that path is fraught with peril and pointlessness. Normally I’d just say “implement IList”, but in this case though, you can also just extend a specific type implementation of List- so for instance, this works:

public class EnumList : List<System.Enum>
{
   public new bool Contains(System.Enum item)
   {
      // Write your implementation here and return bool
   }
}

And you could, of course, just write an extension method, but you’d have to make it a new method name or new signature, since extension methods can’t override or hide other methods:

public static class ExtensionMethods
{
   public static bool ContainsEnum(this List<System.Enum> list, System.Enum item)
   {
      // Write your implementation here and return bool
   }
}

I personally prefer the extension method uhh… method, because you don’t need to go around changing all of your lists to the new type, and it’ll only extend the specific type implementation of List and won’t show up pointlessly on every list type.

1 Like
17

Since there is no enum generic constraint, I dont think what you two are offering will work. (Unless if you both mean to do this for every single type of enum I have)

Doing a extension method for List would only work for lists that are literally Enums. Meaning it wont work for “enum TestEnum {…}” or “enum SomeLabel {…}”, the list must contain literal type of Enum. That, as far as I know, is not useful (at least in this case).

As for extending List, how would I go about using that? I think we run into that same problem that since we cant use generics, that new List extended class would just work for literal type of Enum.

Maybe I am wrong here, and if so, please make your example contain an example with an actual enum type and not the literal Enum, that would also work for all enum types.

The solution also must not create any memory allocations similar to just casting the enum to an int.

1 Like
18

It depends on exactly how you want to handle the values. Using reflection, you could very easily get the value passed in via “item”, like:

item.GetType().GetField("value__").GetValue(item);

and not only does the type of enum not matter, but it’s not even one of those ridiculously expensive uses of reflection. shrugs

19

That code seems to allocate 60B of memory, which is more than the 40B from just doing list.Contains.

20

Well that’s a startling revelation that sucks. I didn’t believe you, but MSDN and the compiler both agree that you are right.

I think your make a list of ints and using that instead is the best we’ve got.

3 Likes