(original) (raw)

changeset: 77211:7951900afd00 parent: 77209:7c7bbf4a70b7 parent: 77210:47e6217d0e84 user: Antoine Pitrou solipsis@pitrou.net date: Mon May 28 22:23:42 2012 +0200 files: Misc/ACKS Misc/NEWS Modules/gcmodule.c description: Issue #14775: Fix a potential quadratic dict build-up due to the garbage collector repeatedly trying to untrack dicts. Additional comments by Tim Silk. diff -r 7c7bbf4a70b7 -r 7951900afd00 Misc/ACKS --- a/Misc/ACKS Mon May 28 14:47:53 2012 -0500 +++ b/Misc/ACKS Mon May 28 22:23:42 2012 +0200 @@ -957,6 +957,7 @@ Itamar Shtull-Trauring Eric Siegerman Paul Sijben +Tim Silk Kirill Simonov Nathan Paul Simons Adam Simpkins diff -r 7c7bbf4a70b7 -r 7951900afd00 Misc/NEWS --- a/Misc/NEWS Mon May 28 14:47:53 2012 -0500 +++ b/Misc/NEWS Mon May 28 22:23:42 2012 +0200 @@ -10,6 +10,9 @@ Core and Builtins ----------------- +- Issue #14775: Fix a potential quadratic dict build-up due to the garbage + collector repeatedly trying to untrack dicts. + - Issue #14857: fix regression in references to PEP 3135 implicit __class__ closure variable (Reopens issue #12370) diff -r 7c7bbf4a70b7 -r 7951900afd00 Modules/gcmodule.c --- a/Modules/gcmodule.c Mon May 28 14:47:53 2012 -0500 +++ b/Modules/gcmodule.c Mon May 28 22:23:42 2012 +0200 @@ -116,6 +116,46 @@ http://mail.python.org/pipermail/python-dev/2008-June/080579.html */ +/* + NOTE: about untracking of mutable objects. + + Certain types of container cannot participate in a reference cycle, and + so do not need to be tracked by the garbage collector. Untracking these + objects reduces the cost of garbage collections. However, determining + which objects may be untracked is not free, and the costs must be + weighed against the benefits for garbage collection. + + There are two possible strategies for when to untrack a container: + + i) When the container is created. + ii) When the container is examined by the garbage collector. + + Tuples containing only immutable objects (integers, strings etc, and + recursively, tuples of immutable objects) do not need to be tracked. + The interpreter creates a large number of tuples, many of which will + not survive until garbage collection. It is therefore not worthwhile + to untrack eligible tuples at creation time. + + Instead, all tuples except the empty tuple are tracked when created. + During garbage collection it is determined whether any surviving tuples + can be untracked. A tuple can be untracked if all of its contents are + already not tracked. Tuples are examined for untracking in all garbage + collection cycles. It may take more than one cycle to untrack a tuple. + + Dictionaries containing only immutable objects also do not need to be + tracked. Dictionaries are untracked when created. If a tracked item is + inserted into a dictionary (either as a key or value), the dictionary + becomes tracked. During a full garbage collection (all generations), + the collector will untrack any dictionaries whose contents are not + tracked. + + The module provides the python function is_tracked(obj), which returns + the CURRENT tracking status of the object. Subsequent garbage + collections may change the tracking status of the object. + + Untracking of certain containers was introduced in issue #4688, and + the algorithm was refined in response to issue #14775. +*/ /* set for debugging information */ #define DEBUG_STATS (1<<0) /* print collection statistics */ @@ -437,9 +477,6 @@ if (PyTuple_CheckExact(op)) { _PyTuple_MaybeUntrack(op); } - else if (PyDict_CheckExact(op)) { - _PyDict_MaybeUntrack(op); - } } else { /* This *may* be unreachable. To make progress, @@ -457,6 +494,20 @@ } } +/* Try to untrack all currently tracked dictionaries */ +static void +untrack_dicts(PyGC_Head *head) +{ + PyGC_Head *next, *gc = head->gc.gc_next; + while (gc != head) { + PyObject *op = FROM_GC(gc); + next = gc->gc.gc_next; + if (PyDict_CheckExact(op)) + _PyDict_MaybeUntrack(op); + gc = next; + } +} + /* Return true if object has a finalization method. */ static int has_finalizer(PyObject *op) @@ -856,6 +907,9 @@ gc_list_merge(young, old); } else { + /* We only untrack dicts in full collections, to avoid quadratic + dict build-up. See issue #14775. */ + untrack_dicts(young); long_lived_pending = 0; long_lived_total = gc_list_size(young); } /solipsis@pitrou.net