28 March 2017

Xojo: How to improve performance when using WeakRefs

If you're building tree structures with leaves (children) that shall keep a reference to their branch (ancestor, parent) they're attached to, the simplest (but not smart) solution is to store a direct references to the parent object in the child object.

Imagine this node class:

class Person
  property name as String
  property parent as Person
  property children() as Person
end class

And then you'd have a Constructor like this:

sub Constructor (parentIn as Person, nameIn as String)
  self.parent = parentIn
  self.name = nameIn
end sub

and create new children like this:

sub AddAChildNamed (name as String)
  dim newChild as new Person (self, name)
  self.children.Append newChild
end sub

This is not optimal because you'd get circular references (parent references children who in turn reference back their parent). And since Xojo uses ref-counting for keeping its objects alive, and does not have a separate garbage collection task, removing all references from your main code to the top parent won't free all those Person objects, because they still keep referencing each others, thereby keeping themselves alive.

One solution would be to add a "FreeAllChildren" method that you'd have to call right before are ready to release the entire tree, but that's not very elegant (it's the fatest solution, though, if you get this right).

A more natural and fool-proof way is to use weak references for the child-to-parent connections, like this:

class Person
  property name as String
  property parent as WeakRef // **changed**
  property children() as Person
end class

sub Constructor (parentIn as Person, nameIn as String)
  self.parent = new WeakRef (parentIn)
  self.name = nameIn
end sub

To access the actual parent, you'd use code like this to temporarily re-create a hard reference to the parent object:

  dim myParent as Parent = Parent (self.parent.Value)

With the above changes, you won't have circular references any more.

However, it's not very efficient. If you have many 1000s of parent objects, you'll get as many WeakRef objects. And the downside of WeakRef is that it involves a search operation to locate the actual parent object when you use the WeakRef.Value function. And the more WeakRef objects you have, the more time it takes to look up these values.

Now consider this: Usually, with these parent-child relationships, there are more children to a parent than vice versa. In the above code, every child creates a WeakRef, often for the same Parent. And that's what we can optimize for:

Instead of having the child create its own WeakRef, let us have the parent provide it, as it'll remain constant.

Change the constructor to accept a WeakRef:

sub Constructor (parentRefIn as WeakRef, nameIn as String)
  self.parent = parentRefIn
  self.name = nameIn
end sub

add a new property to the class:

class Person
  property selfRef as WeakRef
  ...

and update the way a child gets added accordingly:

sub AddAChildNamed (name as String)
  if selfRef = nil then selfRef = new WeakRef (self)
  dim newChild as new Person (selfRef, name)
  self.children.Append newChild
end sub

And that's all.

TL;DR

If you use WeakRefs, and if you create many WeakRef for the same object, consider creating the WeakRef only once and cache it, to gain runtime performance.