Fastest way for .Contains() inside a List of Collider

[Darkkingdom]

Hey folks

I got a List and I need to use .Contains() on the List very, very often.
Since I saw that I can improve the performance with an SortedSet List I build this hash comparison:

public class Collider2DWrapperComparer : IComparer<Collider2DWrapper>
{
   public int Compare(Collider2DWrapper x, Collider2DWrapper y)
   {
       if (x.GetHashCode() == y.GetHashCode())
           return 0;

       return 1;
   }
}
[System.Serializable]
public struct Collider2DWrapper
{
   public Collider2DWrapper(Collider2D coll)
   {
       collider = coll;
   }

   public Collider2D collider;

   public override int GetHashCode()
   {
       unchecked
       {
           int hash = 14;
           hash = hash * 25 + collider.GetHashCode();
           return hash;
       }
   }
}

//SomewhereElseInMyCode: 
public SortedSet<Collider2DWrapper> collisions = new SortedSet<Collider2DWrapper>(new Collider2DWrapperComparer()); 
void OnTriggerEnter2D(Collider2D coll)
{
    //This line is stupid:
   Collider2DWrapper colliderWrapper = new Collider2DWrapper(coll);
   if (collisions.Contains(colliderWrapper))
   {
       //yay
   }     
}

I works, but well… the wrapper is a pretty stupid idea, since the instantiation of the struct kills my garbage collection as well as the performance xD

Has anyone an idea how to do this right?

EDIT: Why am i doing the wrapper in the first place?

[PraetorBlue]

Just use a HashSet. You don’t need any of this extra stuff. HashSets don’t allow duplicates (adding a duplicate is a no-op), and they are optimized for fast Add, Remove and Contains operations.

HashSet<Collider2D> colliders = new HashSet<Collider2D>();

void OnTriggerEnter2D(Collider2D coll)
{
  colliders.Add(coll);
}

void OnTriggerExit2D(Collider2D coll) {
  colliders.Remove(coll);
}

bool IsCollidingWith(Collider2D coll) {
  return colliders.Contains(coll);
}

[Darkkingdom]

@PraetorBlue : Hey thanks for the answer!
The hashset seems pretty neat thanks a lot

[MelvMay]

I’d also be curious why you’re doing this too. There’s plenty of queries available to determine what is in contact with a collider etc if that’s what you’re doing.

[Darkkingdom]

@MelvMay : It’s to “pretest” a collision in my MoveObject Script.
Instead of using boxcasting for everything, I got one pretest collider2D which rotates in the moving direction.
The pretest collider stores all it’s collision inside the list for easy access.
After much tinkering the system work pretty well, even for my pretty fast moving game objects.

Well since it’s not every day that you can ask a Senior developer for 2D physics:
That’s probably a stupid idea as well right?^^"

[lordofduct]

1. as was stated, use a HashSet

2. structs don’t kill garbage collection unless you box them in some manner, which your code is not doing.

3. what is creating garbage is your ‘Add’ method, if you run the profiler you’ll see that is where the garbage is coming from:
   

   

And if you look at the source you’ll see that indeed SortedSet has an internal class called “Node” for each element of the collection:
https://referencesource.microsoft.com/#system/compmod/system/collections/generic/sortedset.cs,2130

Affirming you should use HashSet since you’re not really needing the ‘sorting’ aspect of SortedSet. You just need the ‘Contains’ aspect to be O(1), which HashSet offers.

4. Also, why do you even need this struct in the first place? You can create a IComparer for type Collider2D directly:

public class Collider2DComparer : IComparer<Collider2D>
{
    public int Compare(Collider2D x, Collider2D y)
    {
        return x.GetHashCode() == y.GetHashCode() ? 0 : 1;
    }
}

5. You shouldn’t rely on hashcode inequality for comparison of objects since GetHashCode isn’t necessarily guaranteed to be unique. Incidentally it will work for UnityEngine.Objects since the hash code is its instance id which happens to be unique. Of course you may be already aware of this… just mentioning it for sake of clarity in case anyone else comes and reads this thread. Usually when I go and write some exploited aspect of the api that happens to be incidental I put a comment in saying as such:

public class Collider2DComparer : IComparer<Collider2D>
{
    public int Compare(Collider2D x, Collider2D y)
    {
        //incidentally the hashcode is the instanceid and happens to be unique for all UnityEngine.Objects including Collider2D
        return x.GetHashCode() == y.GetHashCode() ? 0 : 1;
    }
}

This way if someone else has to maintain the code in the future, including yourself, or attempts to repurpose the code elsewhere. They don’t just blindly use the code.

Honestly this last one isn’t the most important… hence why I put it at the end of the list. It’s just one of those things I’m vigilant about since I’ve maintained a lot of code written by others in my life, as well as led teams doing conversions of code… and undocumented exploits are the bane of a conversion/maintainers life.

(nevermind that you do some arithmetic on the hashcode reducing its range… only by a little, but I really find that one weird… why was that even done? And also why put 14 in a variable if you’re just going to multiply it by a constant? Why not just do 350 + GetHashCode? Why not just forego the 350 all together?)

[_geo1]

@lordofduct

nevermind that you do some arithmetic on the hashcode reducing its range… only by a little

Sorry for sidetracking the thread but this got me thinking. How is this reducing the hash range? Isn’t this only transposing the hash? It’s in an unchecked context. Wouldn’t it just wrap around to negative if above max value. Just like turning a wheel wouldn’t actually reduce the circumference (sorry for the probably ham-handed analogy). I’d be interested

[lordofduct]

@_geo1

Sorry for sidetracking the thread but this got me thinking. How is this reducing the hash range? Isn’t this only transposing the hash? It’s in an unchecked context. Wouldn’t it just wrap around to negative if above max value. Just like turning a wheel wouldn’t actually reduce the circumference (sorry for the probably ham-handed analogy). I’d be interested

Good point, didn’t actually logic the whole thing out in my head.

I likely had the idea of bitshifting in my head because I usually do bit manipulation in my hashcode algorithms.

Kind of reasserts my point about exploitative code. Weird hackery relies on the person reading it to not only be able to understand the hackery on a fundamental level, but also be of sound mind when doing so.