How to optimize heavily used hashmap where instances are both keys and values?

Unity Engine
1

Hello folks! I have decided to implement the Game of Life in Unity for one of my projects and I found that the HashLife algorithm is one of the most efficient. I found following implementation based on Java. The algorithm almost entirely translates into C#. However, there is one problem I have encountered and that is the amount of garbage this accumulates when the pattern grows too chaotic. GC.Collect takes its tall to collect massive amount of garbage and produces a noticeable lag.

Shortly, to calculate the next generation, the nodes are created and are either safely retrieved from the hashmap (thus discarding new constructed instance) or saved as completely unique without being discarded. Each time the algorithm creates instances just to use them as keys. Here is an example of how a node is created using a factory method:

public override TreeNode Create(TreeNode nw, TreeNode ne, TreeNode sw, TreeNode se)
{
   return new CanonicalTreeNode(nw, ne, sw, se).Intern();
}

With Intern() implementation being the code in question:

public TreeNode Intern()
{
   if (hashMap.TryGetValue(this, out TreeNode canon))
   {
      return canon;
   }

   hashMap[this] = this;
   return this;
}

As you can see, the algorithm always requires the instance to be created to at least serve as the key for the hash table. On a massive scale with > 10000 instances being created, this becomes unbearable.
It would be nice if the Create() method was the following instead:

public override TreeNode Create(TreeNode nw, TreeNode ne, TreeNode sw, TreeNode se)
{
   return Intern(nw, ne, sw, se);
}

With Intern() method (pseudocode):

public TreeNode Intern(TreeNode nw, TreeNode ne, TreeNode sw, TreeNode se)
{
   var key = GenerateKey(nw, ne, sw, se); //Some kind of key
   if (hashMap.TryGetValue(key, out TreeNode canon))
   {
      return canon;
   }

   //Only then it would use the constructor!
   canon = new CanonicalTreeNode(nw, ne, sw, se);
   hashMap[key] = canon;
   return canon;
}

My question is the following: is there any way I could still access the hash table without generating the new instance? The class has methods like Equals() and GetHashCode() overridden for collision management and that’s why I couldn’t simply replace the key with some kind of int.

Any help appreciated! And let me know if you need other info!

2

Choosing a good hash key and even using a hashing function at all are dependent on the problem.

I have not studied this HashLife module so I’m not sure what all they’re doing to make what is already an extremely simple simulation more efficient.

I have implemented Conways Game Of Life many times, even on hardware as simple as an 8-bit 6502 CPU, and I used no hashes or pointers or links, just did it brute-force, and it was plenty fast enough. I have never bothered to think further about it, but maybe this HashLife guy did.

What you need to do is identify why and what he is hashing and connecting with this tree system, and see if there is a simpler way to generate the keys, or perhaps store the keys too.

In other news, this fellow here did it on a GPU:

https://nullprogram.com/blog/2014/06/10/

1 Like
3

Thanks for the reply. The GPU implementation also seems interesting enough! However, in my project, I am creating the Life that interacts with the Life and regular Unity objects alike, with user also given ability to inject patterns of choice at location. If it was just a shader code, then I assume it would be quite problematic to handle interactions with other than Life. Also, the simulation I needed spans large spaces for an unknown amount of generations, which brute force approach unfortunately can’t handle. The larger the space, the heavier it becomes for the CPU. That is why the devised HashLife approach seemed to be the good choice (and it most certainly is!) because it can tackle massive evolving patterns at the expense of memory.

The only issue standing in this implementation is the problem of generating new instance each time to access hash table. Here is what the current hash function looks like:

public override int GetHashCode()
{
   if (level == 0)
   {
      return (int)population;
   }

   return RuntimeHelpers.GetHashCode(nw) +
      11 * RuntimeHelpers.GetHashCode(ne) +
      101 * RuntimeHelpers.GetHashCode(sw) +
      1007 * RuntimeHelpers.GetHashCode(se);
}

As you can see, each node’s uniqueness is defined by 4 sub nodes it features. Say, there is a separate function that generates the int key, same as the function presented. But in this case, there is also a separate Equals() method override for the cases when there is collision in hash map. In case we had just int as the key, it would be impossible to handle the collision. Or am I wrong? Is there a way to define a very unique and specific int key for such situation? Or is there a totally different approach instead with using instances without generating garbage?