changeset: 77212:6554ebbeb2f3 branch: 2.7 parent: 77207:8a65eceea56c user: Antoine Pitrou date: Mon May 28 22:22:34 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 8a65eceea56c -r 6554ebbeb2f3 Misc/ACKS --- a/Misc/ACKS Mon May 28 13:52:59 2012 -0500 +++ b/Misc/ACKS Mon May 28 22:22:34 2012 +0200 @@ -791,6 +791,7 @@ Itamar Shtull-Trauring Eric Siegerman Paul Sijben +Tim Silk Kirill Simonov Nathan Paul Simons Janne Sinkkonen diff -r 8a65eceea56c -r 6554ebbeb2f3 Misc/NEWS --- a/Misc/NEWS Mon May 28 13:52:59 2012 -0500 +++ b/Misc/NEWS Mon May 28 22:22:34 2012 +0200 @@ -9,6 +9,9 @@ Core and Builtins ----------------- +- Issue #14775: Fix a potential quadratic dict build-up due to the garbage + collector repeatedly trying to untrack dicts. + - Issue #14494: Fix __future__.py and its documentation to note that absolute imports are the default behavior in 3.0 instead of 2.7. Patch by Sven Marnach. diff -r 8a65eceea56c -r 6554ebbeb2f3 Modules/gcmodule.c --- a/Modules/gcmodule.c Mon May 28 13:52:59 2012 -0500 +++ b/Modules/gcmodule.c Mon May 28 22:22:34 2012 +0200 @@ -111,6 +111,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 */ @@ -436,9 +476,6 @@ if (PyTuple_CheckExact(op)) { _PyTuple_MaybeUntrack(op); } - else if (PyDict_CheckExact(op)) { - _PyDict_MaybeUntrack(op); - } } else { /* This *may* be unreachable. To make progress, @@ -478,6 +515,20 @@ return 0; } +/* 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; + } +} + /* Move the objects in unreachable with __del__ methods into `finalizers`. * Objects moved into `finalizers` have gc_refs set to GC_REACHABLE; the * objects remaining in unreachable are left at GC_TENTATIVELY_UNREACHABLE. @@ -890,6 +941,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); }

AltStyle によって変換されたページ (->オリジナル) /