Optimizing hash lookup & memory performance in Go
- by Moishe
As an exercise, I'm implementing HashLife in Go.
In brief, HashLife works by memoizing nodes in a quadtree so that once a given node's value in the future has been calculated, it can just be looked up instead of being re-calculated. So eg. if you have a node at the 8x8 level, you remember it by its four children (each at the 2x2 level). So next time you see an 8x8 node, when you calculate the next generation, you first check if you've already seen a node with those same four children. This is extended up through all levels of the quadtree, which gives you some pretty amazing optimizations if eg. you're 10 levels above the leaves.
Unsurprisingly, it looks like the perfmance crux of this is the lookup of nodes by child-node values. Currently I have a hashmap of
{&upper_left_node,&upper_right_node,&lower_left_node,&lower_right_node} -> node
So my lookup function is this:
func FindNode(ul, ur, ll, lr *Node) *Node {
var node *Node
var ok bool
nc := NodeChildren{ul, ur, ll, lr}
node, ok = NodeMap[nc]
if ok {
return node
}
node = &Node{ul, ur, ll, lr, 0, ul.Level + 1, nil}
NodeMap[nc] = node
return node
}
What I'm trying to figure out is if the "nc := NodeChildren..." line causes a memory allocation each time the function is called. If it does, can I/should I move the declaration to the global scope and just modify the values each time this function is called? Or is there a more efficient way to do this?
Any advice/feedback would be welcome. (even coding style nits; this is literally the first thing I've written in Go so I'd love any feedback)
