[issue14775] Dict untracking can result in quadratic dict build-up

[Antoine Pitrou]

Antoine Pitrou <pitrou at free.fr> added the comment:

Okay, found it. The problem is _PyDict_MaybeUntrack() is potentially O(n), so calling it in every GC collection can produce quadratic runtimes when a dict is building up. Attached patch (for 3.3) only calls it in the older collections. Not sure this should be backported to 2.7/3.2.

----------
keywords: +patch
stage:  -> patch review
title: Slow unpickling of certain dictionaries in python 2.7 vs python 2.6 -> Dict untracking can result in quadratic dict build-up
versions: +Python 3.2, Python 3.3
Added file: http://bugs.python.org/file25669/dict_untrack.patch

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue14775>
_______________________________________