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

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

Spoiler: Click for code

Code (CSharp):

1. using UnityEngine;
2. using System.Collections.Generic;
3.  
4. public class TestListGarbageCollection : MonoBehaviour
5. {
6.     public enum Test {EnumList, EnumToIntList}
7.     public Test test;
8.  
9.     enum TestEnum {One, Two, Three}
10.  
11.     List<TestEnum> enumList;
12.     List<int> enumIntList;
13.     public int loopAmount = 100;
14.  
15.     void Start()
16.     {
17.         enumList = new List<TestEnum>() {TestEnum.One};
18.         enumIntList = new List<int>() {(int)TestEnum.One};
19.     }
20.  
21.     void Update()
22.     {
23.         for(int i = 0; i < loopAmount; i++)
24.         {
25.             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)
26.             if(test == Test.EnumToIntList) if(enumIntList.Contains((int)TestEnum.Two)){} //seems to allocate nothing
27.         }
28.     }
29. }

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!

 

It's because List.Contains uses the default EqualityComparer:
https://msdn.microsoft.com/en-us/library/ms224763(v=vs.110).aspx

The default EqualityComparer for enums uses the Enum.Equals method:
https://msdn.microsoft.com/en-us/library/8bafh2by(v=vs.110).aspx

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:
https://msdn.microsoft.com/en-us/library/bb359438(v=vs.110).aspx

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

 

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.

 

Wow. That is arcane.

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

 

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?

 

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<SomeEnum> 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?

 

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.

 

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

Code (CSharp):

1. enumIntList = new List<int>() {(int)TestEnum.One};
2. 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

Code (CSharp):

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

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

 

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

 

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/space...r/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:

Code (csharp):

1.  
2. var e = que.GetEnumerator();
3. while(e.MoveNext())
4. {
5.     //do something with e.Current
6. }
7.  

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

Code (csharp):

1.  
2. public static bool Contains<T>(this List<T> lst, T item, IEqualityComparer<T> comparer)
3. {
4.     var e = lst.GetEnumerator();
5.     while(e.MoveNext())
6.     {
7.         if (comparer.Equals(e.Current, item)) return true;
8.     }
9.     return false;
10. }
11.  

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

 

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)

 

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

You could just use a List<int> 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.

 

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)

 

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.

 

Just extend List<T> 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<Enum>

 

You can extend List<T>, 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<T>- so for instance, this works:

Code (csharp):

1. public class EnumList : List<System.Enum>
2. {
3.    public new bool Contains(System.Enum item)
4.    {
5.       // Write your implementation here and return bool
6.    }
7. }

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:

Code (csharp):

1. public static class ExtensionMethods
2. {
3.    public static bool ContainsEnum(this List<System.Enum> list, System.Enum item)
4.    {
5.       // Write your implementation here and return bool
6.    }
7. }

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<T> and won't show up pointlessly on every list type.

 

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<Enum> 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<Enum>, how would I go about using that? I think we run into that same problem that since we cant use generics, that new List<Enum> 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.

 

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:

Code (csharp):

1. 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*

 

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

 

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.

 

Yeah, it sort of took me by surprise too, and after my cocky extension method post... I came up with some reflection crap to save face, but if you have to use reflection you've already failed at something.

Meh.

 

As lordofduck has stated, this is probably only an issue for us unity guys due to poor garbage collection. Heck, I cant even use static helper methods that creates a tiny array without having to worry about lots of garbage collection. Makes me start doint sloppy, annoying things such as using refs or not even using my helper methods and doing the code inline.

 

The garbage collector in any non game environment would work fine. Most aps can afford 'loading time' at random points. Its also worth noting that just getting a faster garbage collector would not work. We need one specifically designed for games.

The issue is that in a game even the smallest amount of extra time added to a frame causes a noticeable performance issue. What we need is an asynchronous GC, or a GC that can run over multiple frames, or a GC that gives the developer full control over when its called. These solutions would all make the GC less efficient at doing the job of cleaning up garbage. But perfect for working with games.

 

Damn I thought you guys cracked it too. I was just as surprised.

I thought you were just dealing with KeyCodes. It seems reasonable to do this once for that situation. Like lordofduct said, it's not that common a thing. And if it is for you, maybe we can help you with that design issue.

OR you could just go with one of the other data structures already suggested. lordofduct provides some great source for free, so I think it's worth trying his suggestions.

 

nah, its not common (at least at the moment). I was just dealing with an input manager caching inputs so I have them for fixedupdate (since update can run more than fixedupdate, input could be lost).
I was getting lots of garbage collection and thanks to the profiler I was able to learn about this enum boxing and what not. I also had to get into object pooling of actual script objects.

my OCD side is making want to see all 0's in the garbage collection, but Ill have to try to not pre optimize. It feels so good to see that drop in garbage collection though =), but the ways to accomplishing it can feel so wrong.

 

Sometimes you have to accept some garbage in your life.

Don't kill yourself over it unless you're seeing actual performance loss.

And when you have to write some sloppy weird code, roll it up into a self contained class and display it as a clean interface. Go into my framework, you'll see all sorts of weird things I do to eek some efficiency out... but it's all under the hood so the user of the class doesn't really need to care about that aspect.

 

you could use

Code (CSharp):

1. list.Exists( e => e == MyEnum.Value );