koobas.hobune.stream
Vector3.Equals without memory allocation?
In my A* pathfinding project I use a hashset for my closed-list (a list of nodes that have been checked already). When running the profiler I noticed something funny, running 20 instances created 3KB GC allocation (per frame) from the Hashset.Contains() function. After googleing I found out that Vector3.Equals() uses a copy of the vector3 and thus create garbage. I tried using a Hashset(float[]) instead, didn't work. Found out that arrays dont create a hashcode that reflects the elements inside of it.
Anyone have an idea how I can create a hashset (I would like to have Contains() with O(1)) for a vector3 without memory allocation? I also read that there is a GetHashCode-function for vector3, but the default comparer is Equals(). How do I change this (the default comparer) for the hashset? Will it solve my problem?
I'm curious as to where you found that info about Vector3.Equals. I would expect it to use copies, but surely they're local and hence on the stack and not subject to garbage collection? Or did you mean something else by "garbage" here?
As for your last question, you can set a different comparer by using a alternative constructor when you declare the HashSet. See $$anonymous$$SDN https://msdn.microsoft.com/en-us/library/bb359438(v=vs.110).aspx
V3.equals takes an 'object'? Does that mean it has to use boxing?
Ah yes, it does. Good point, that'll be the garbage.
And that makes me think that @Salmjak is probably right to think in terms of a bespoke equality comparer.
I first read about it in the comments here "3. Unity Vector3 equals allocates!"
I also used a deep-profiling and all the GC Allocation from Hashset.Contains() was tracked to Vector3.Equals() --> Single.Equals(). So it might not have to do with the vector3-class itself, but rather the comparer-method. I can't find the thread saying it uses a copy, maybe I just misunderstood something.
No, you're right. As Owen and wibble say, Vector3.Equals uses boxing to pass the Vector as an object. That's why the heap comes into play.
Thanks for the link.
I haven't checked, but I am guessing Vector3.Equals is being passed an object, or casts to an object internally for some reason. If so, then it would allocate memory, as the input parameter has to be 'boxed' to be passed as an object.
The hash set generic can take a generic equality comparer. Inside your comparer you can write any comparison you like - such as directly comparing the 3 floating point components, thus avoiding the problem:
https://msdn.microsoft.com/en-us/library/bb359100(v=vs.110).aspx
That said, if you're doing an A* search algorithm, might be better off working on an integer grid anyway? Then you can encode an x/y(/z?) position into a single ulong, which makes it super quick to look up and, far less memory intensive.
-Chris
