Update docs

python · markshannon · Nov 18, 2024 · Nov 4, 2024 · Nov 4, 2024 · Nov 4, 2024
commit b9467ec138ca1eeac2b40165bcd4151ad7a227eb
diff --git a/InternalDocs/garbage_collector.md b/InternalDocs/garbage_collector.md
@@ -352,29 +352,6 @@ follows these steps in order:
   objects.


-Optimization: marking
-=====================
-
-An object cannot be garbage if it can be reached.
-
-To avoid performing the complex algorithm above on the whole heap, we first
-mark all objects that can be reached from any frame stack or from global
-objects like the modules or builtin classes.
-
-This marking step does much less work per object, so reduces the time spent
-performing garbage collection by at least half.
-
-This mark phase marks all object that are transitively reachable from the
-roots as follows:
-* All objects directly referred by any builtin class, the `sys` module, the `builtins`
-module or any frame stack are added to a working set of reachable objects.
-* Until this working set is empty:
-   * Pop an object from the set and move it to the reachable set
-   * For each object directly reachable from that object:
-      * If it is not already reachable and it is a GC object, then move it to
-        the working set
-
-
 Optimization: incremental collection
 ====================================

@@ -508,6 +485,43 @@ specifically in a generation by calling `gc.collect(generation=NUM)`.
 ```


+Optimization: visiting reachable objects
+========================================
+
+An object cannot be garbage if it can be reached.
+
+To avoid having to identify reference cycles across the whole heap, we can
+reduce the amount of work done considerably by first moving most reachable objects
+to the `visited` space. Empirically, most reachable objects can be reached from a
+small set of global objects and local variables.
+This step does much less work per object, so reduces the time spent
+performing garbage collection by at least half.
+
+> [!NOTE]
+> Objects that are not determined to be reachable by this pass are not necessarily
+> unreachable. We still need to perform the main algorithm to determine which objects
+> are actually unreachable.
+
+We use the same technique of forming a transitive closure as the incremental
+collector does to find reachable objects, seeding the list with some global
+objects and the current frame of each stack.
-objects and the current frame of each stack.
+objects and the currently executing frames.
-objects and the current frame of each stack.
+objects and the currently executing frames.
+
+This mark phase moves all objects `visited` space, as follows:
+
+1. All objects directly referred by any builtin class, the `sys` module, the `builtins`
+module and all objects directly referred to from stack frames are added to a working
+set of reachable objects.
+2. Until this working set is empty:
+   1. Pop an object from the set and move it to the `visited` space
+   2. For each object directly reachable from that object:
+      * If it is not already in `visited` space and it is a GC object,
+        then move it to the working set
+
+Before each increment of collection is performed, any stack frames that have been created
+since the last increment are added to the working set and above algorithm is repeated,
+starting from step 2.
+
+
 Optimization: reusing fields to save memory
 ===========================================