Memory leaks in classes of linked nodes

Question

I'm trying to reimplement (once more... i know...) a simple network in python made of node classes that reference other node classes (their children), and I was wondering what would happen if I create a recursive network (node1 -> node2 -> node3 -> node1) and accidentally lose all references to any of the nodes.

Imagine I have the following code

class node():
    def __init__(self):
        self.children = []

    def append(self, child):
        self.children.append(child)

node1 = node()
node2 = node()

node1.append(node2)
node2.append(node1) # now the network is recursive

node1 = 0
# node1 is still referenced in node2.children so will not be deleted
node2 = 0

# now both node1 and node2 are not directly referenced by any variable
# but they are referenced by the two children instances

after the last line of code, all references to node1 and node2 are lost, but the memory originally allocated to the nodes sill contain a reference to themselves.

Would node1 and node2 still be destroyed?

Martijn Pieters Martijn Pieters · Accepted Answer · 2015-01-16T15:51:52

Yes, the objects will be garbage collected. The garbage collector will detect the circular reference and break it so that normal reference counting cleanup can take place. See the gc module.

You would have a problem if your node class implemented a __del__ method and you are using a Python version < 3.4. In 3.4 now can break circular references involving instances with __del__ methods in most cases.

From the object.__del__ documentation:

Note: del x doesn’t directly call x.__del__() — the former decrements the reference count for x by one, and the latter is only called when x‘s reference count reaches zero. Some common situations that may prevent the reference count of an object from going to zero include: circular references between objects (e.g., a doubly-linked list or a tree data structure with parent and child pointers); a reference to the object on the stack frame of a function that caught an exception (the traceback stored in sys.exc_traceback keeps the stack frame alive); or a reference to the object on the stack frame that raised an unhandled exception in interactive mode (the traceback stored in sys.last_traceback keeps the stack frame alive). The first situation can only be remedied by explicitly breaking the cycles; the latter two situations can be resolved by storing None in sys.exc_traceback or sys.last_traceback. Circular references which are garbage are detected when the option cycle detector is enabled (it’s on by default), but can only be cleaned up if there are no Python-level __del__() methods involved. Refer to the documentation for the gc module for more information about how __del__() methods are handled by the cycle detector, particularly the description of the garbage value.

Memory leaks in classes of linked nodes

1 Answers