1 #ifndef Py_INTERNAL_MEM_H 2 #define Py_INTERNAL_MEM_H 3 #ifdef __cplusplus 4 extern "C" { 5 #endif 6 7 #include "objimpl.h" 8 #include "pymem.h" 9 10 11 /* GC runtime state */ 12 13 /* If we change this, we need to change the default value in the 14 signature of gc.collect. */ 15 #define NUM_GENERATIONS 3 16 17 /* 18 NOTE: about the counting of long-lived objects. 19 20 To limit the cost of garbage collection, there are two strategies; 21 - make each collection faster, e.g. by scanning fewer objects 22 - do less collections 23 This heuristic is about the latter strategy. 24 25 In addition to the various configurable thresholds, we only trigger a 26 full collection if the ratio 27 long_lived_pending / long_lived_total 28 is above a given value (hardwired to 25%). 29 30 The reason is that, while "non-full" collections (i.e., collections of 31 the young and middle generations) will always examine roughly the same 32 number of objects -- determined by the aforementioned thresholds --, 33 the cost of a full collection is proportional to the total number of 34 long-lived objects, which is virtually unbounded. 35 36 Indeed, it has been remarked that doing a full collection every 37 <constant number> of object creations entails a dramatic performance 38 degradation in workloads which consist in creating and storing lots of 39 long-lived objects (e.g. building a large list of GC-tracked objects would 40 show quadratic performance, instead of linear as expected: see issue #4074). 41 42 Using the above ratio, instead, yields amortized linear performance in 43 the total number of objects (the effect of which can be summarized 44 thusly: "each full garbage collection is more and more costly as the 45 number of objects grows, but we do fewer and fewer of them"). 46 47 This heuristic was suggested by Martin von Löwis on python-dev in 48 June 2008. His original analysis and proposal can be found at: 49 http://mail.python.org/pipermail/python-dev/2008-June/080579.html 50 */ 51 52 /* 53 NOTE: about untracking of mutable objects. 54 55 Certain types of container cannot participate in a reference cycle, and 56 so do not need to be tracked by the garbage collector. Untracking these 57 objects reduces the cost of garbage collections. However, determining 58 which objects may be untracked is not free, and the costs must be 59 weighed against the benefits for garbage collection. 60 61 There are two possible strategies for when to untrack a container: 62 63 i) When the container is created. 64 ii) When the container is examined by the garbage collector. 65 66 Tuples containing only immutable objects (integers, strings etc, and 67 recursively, tuples of immutable objects) do not need to be tracked. 68 The interpreter creates a large number of tuples, many of which will 69 not survive until garbage collection. It is therefore not worthwhile 70 to untrack eligible tuples at creation time. 71 72 Instead, all tuples except the empty tuple are tracked when created. 73 During garbage collection it is determined whether any surviving tuples 74 can be untracked. A tuple can be untracked if all of its contents are 75 already not tracked. Tuples are examined for untracking in all garbage 76 collection cycles. It may take more than one cycle to untrack a tuple. 77 78 Dictionaries containing only immutable objects also do not need to be 79 tracked. Dictionaries are untracked when created. If a tracked item is 80 inserted into a dictionary (either as a key or value), the dictionary 81 becomes tracked. During a full garbage collection (all generations), 82 the collector will untrack any dictionaries whose contents are not 83 tracked. 84 85 The module provides the python function is_tracked(obj), which returns 86 the CURRENT tracking status of the object. Subsequent garbage 87 collections may change the tracking status of the object. 88 89 Untracking of certain containers was introduced in issue #4688, and 90 the algorithm was refined in response to issue #14775. 91 */ 92 93 struct gc_generation { 94 PyGC_Head head; 95 int threshold; /* collection threshold */ 96 int count; /* count of allocations or collections of younger 97 generations */ 98 }; 99 100 /* Running stats per generation */ 101 struct gc_generation_stats { 102 /* total number of collections */ 103 Py_ssize_t collections; 104 /* total number of collected objects */ 105 Py_ssize_t collected; 106 /* total number of uncollectable objects (put into gc.garbage) */ 107 Py_ssize_t uncollectable; 108 }; 109 110 struct _gc_runtime_state { 111 /* List of objects that still need to be cleaned up, singly linked 112 * via their gc headers' gc_prev pointers. */ 113 PyObject *trash_delete_later; 114 /* Current call-stack depth of tp_dealloc calls. */ 115 int trash_delete_nesting; 116 117 int enabled; 118 int debug; 119 /* linked lists of container objects */ 120 struct gc_generation generations[NUM_GENERATIONS]; 121 PyGC_Head *generation0; 122 /* a permanent generation which won't be collected */ 123 struct gc_generation permanent_generation; 124 struct gc_generation_stats generation_stats[NUM_GENERATIONS]; 125 /* true if we are currently running the collector */ 126 int collecting; 127 /* list of uncollectable objects */ 128 PyObject *garbage; 129 /* a list of callbacks to be invoked when collection is performed */ 130 PyObject *callbacks; 131 /* This is the number of objects that survived the last full 132 collection. It approximates the number of long lived objects 133 tracked by the GC. 134 135 (by "full collection", we mean a collection of the oldest 136 generation). */ 137 Py_ssize_t long_lived_total; 138 /* This is the number of objects that survived all "non-full" 139 collections, and are awaiting to undergo a full collection for 140 the first time. */ 141 Py_ssize_t long_lived_pending; 142 }; 143 144 PyAPI_FUNC(void) _PyGC_Initialize(struct _gc_runtime_state *); 145 146 #define _PyGC_generation0 _PyRuntime.gc.generation0 147 148 #ifdef __cplusplus 149 } 150 #endif 151 #endif /* !Py_INTERNAL_MEM_H */ 152