Reference cycles (zombis objects) in SortedDict

[pivosan97]

SortedDict creates reference cycles (zombie objects) which are not destroyed by reference counting algorithm but only by garbage collector iteration, what can cause performance and latency issues. It can be tracked using gc module.

[grantjenks]

It’s possible to create reference cycles with any container object. I can’t think of anything specific about the design of sortedcontainers that would create reference cycles. Please include code to demonstrate.

[pivosan97]

I think that a reference cycle appears somewhere inside a SortedDict object.
Test

from sortedcontainers import SortedDict
import gc

def check(f):
    a = f()
    t = type(a)

    print(1)
    for obj in gc.get_objects():
        if type(obj) == t:
            print(obj)

    del a

    print(2)
    for obj in gc.get_objects():
        if type(obj) == t:
            print(obj)

    gc.collect()

    print(3)
    for obj in gc.get_objects():
        if type(obj) == t:
            print(obj)

check(lambda: SortedDict({'a': 1, 'b': 2}))


class MyDict(dict):
    pass

check(lambda: MyDict({'a': 1, 'b': 2}))

Output

1
SortedDict({'a': 1, 'b': 2})
2
SortedDict({'a': 1, 'b': 2})
3
1
{'a': 1, 'b': 2}
2
3

As you can see a regular dict is deallocated right after del operator (it is done by reference counting algorithm) while SortedDict object is collected only by GC what means there is a reference cycle.

[grantjenks]

Thank you for the code sample. I did a bit of debugging and traced the issue to this code in __init__:

        # Calls to super() are expensive so cache references to dict methods on
        # sorted dict instances.

        _dict = super(SortedDict, self)
        self._dict_clear = _dict.clear
        self._dict_delitem = _dict.__delitem__
        self._dict_iter = _dict.__iter__
        self._dict_pop = _dict.pop
        self._dict_setitem = _dict.__setitem__
        self._dict_update = _dict.update

SortedDict references dict through its base class reference and here the super call forces the dict methods to reference self which I think creates the cycle.

One fix would be to stop using super() and access the dictionary methods as dict.__delitem__ directly. The code where the functions are used would need to change so that self was passed as the first argument.

I'm not sure if this is worth fixing. Typically I only use a few SortedDict objects in a program. What's your use case like?

[grantjenks]

Fix pushed at 2b03703. Will deploy new version once Travis/AppVeyor are green.

@pivosan97 Would you please test on master?

Also, I would appreciate if you did not leave comments like this https://pythontips.com/2016/04/24/python-sorted-collections/comment-page-1/#comment-75266 for an open and on-going issue. My last comment (above) ended with "What's your use case like?" for which I didn't hear back.

[pivosan97]

Hi, Thank you for fixing it. I think the comment is valid as it reflects my experience with the lib. I do not know how to delete it, so I’ll replay to it saying that the issue is resolved. Best regards, Aliaksandr Pivavarchyk

…

On Jun 4, 2020, at 06:42, Grant Jenks ***@***.***> wrote: Fix pushed at 2b03703 <2b03703>. Will deploy new version once Travis/AppVeyor are green. @pivosan97 <https://github.com/pivosan97> Would you please test on master? Also, I would appreciate if you did not leave comments like this https://pythontips.com/2016/04/24/python-sorted-collections/comment-page-1/#comment-75266 <https://pythontips.com/2016/04/24/python-sorted-collections/comment-page-1/#comment-75266> for an open and on-going issue. My last comment (above) ended with "What's your use case like?" for which I didn't hear back. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#147 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACXX2EH4KLE3FQMNT5ECTELRU4X4FANCNFSM4M6VPVRQ>.

[grantjenks]

Fix deployed in version 2.2.0 on PyPI: https://pypi.org/project/sortedcontainers/2.2.0/