Deallocating deeply nested data structure results in stack overflow

[Robert Luce]

Consider this simplistic extension type to model a tree:

cdef class TreeNode():
    # Represents a node in a tree with edges directed from leaves to root

    cdef TreeNode _parent
    cdef object _payload

    def __cinit__(self, TreeNode parent, object payload):
        self._parent = parent
        self._payload = payload

    def __add__(self, other):
        cdef TreeNode newnode
        newnode = TreeNode(self, other)
        return newnode

If I now do on my Linux box with Python 3.9.9/Cython 0.29.28

from example import TreeNode

N = 2**24
path = sum([object() for _ in range(N)], TreeNode(None, 0.0))
print('done.')

I'm getting

done.

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff6aaaed4 in __pyx_tp_dealloc_7example_TreeNode (o=0x7fffad3a9280)
    at example.c:1568
1568      PyObject_GC_UnTrack(o);

The call stack indicates that during deallocation the nested structure of 'path' results in a horribly deep call tree:

#64950 __pyx_tp_dealloc_7example_TreeNode (o=0x7fffad22bc10) at example.c:1569
#64951 0x00007ffff6aaaf25 in _Py_DECREF (op=<optimized out>)
    at /usr/local/include/python3.9/object.h:430
#64952 __pyx_tp_dealloc_7example_TreeNode (o=0x7fffad22bc40) at example.c:1569
#64953 0x00007ffff6aaaf25 in _Py_DECREF (op=<optimized out>)
    at /usr/local/include/python3.9/object.h:430
#64954 __pyx_tp_dealloc_7example_TreeNode (o=0x7fffad22bc70) at example.c:1569
#64955 0x00007ffff6aaaf25 in _Py_DECREF (op=<optimized out>)
    at /usr/local/include/python3.9/object.h:430
#64956 __pyx_tp_dealloc_7example_TreeNode (o=0x7fffad22bca0) at example.c:1569
#64957 0x00007ffff6aaaf25 in _Py_DECREF (op=<optimized out>)
    at /usr/local/include/python3.9/object.h:430
#64958 __pyx_tp_dealloc_7example_TreeNode (o=0x7fffad22bcd0) at example.c:1569
#64959 0x000000000045e04a in _Py_DECREF (op=<optimized out>)

resulting in the stack space being exhausted.  (You may need to play around with the value of N and/or 'ulimit -s' to reproduce.)

Anyone knowing a *simple* way to avoid this?  The current (complicated) solution I have is to (1) maintain an internal reference count for the tree nodes, and (2) add a __dealloc__ method that sets explicitly _parent=None for all reachable, singly-referenced nodes.

Robert

[Stefan Behnel]

Hi,

'Robert Luce' via cython-users schrieb am 10.04.22 um 13:47:

> Consider this simplistic extension type to model a tree:
>
> cdef class TreeNode():
> # Represents a node in a tree with edges directed from leaves to root
>
> cdef TreeNode _parent
> cdef object _payload
>
> def __cinit__(self, TreeNode parent, object payload):
> self._parent = parent
> self._payload = payload
>
> def __add__(self, other):
> cdef TreeNode newnode
> newnode = TreeNode(self, other)
> return newnode
>
> If I now do on my Linux box with Python 3.9.9/Cython 0.29.28
>
> from example import TreeNode
>
> N = 2**24
> path = sum([object() for _ in range(N)], TreeNode(None, 0.0))
> print('done.')
>
> I'm getting
>
> done.
>
> Program received signal SIGSEGV, Segmentation fault.
> 0x00007ffff6aaaed4 in __pyx_tp_dealloc_7example_TreeNode (o=0x7fffad3a9280)
> at example.c:1568
> 1568 PyObject_GC_UnTrack(o);

See

https://cython.readthedocs.io/en/latest/src/userguide/extension_types.html#enabling-the-deallocation-trashcan

Stefan

[Robert Luce]

Thanks for the pointer, that nails it!

Robert