Changes between Version 6 and Version 7 of GCMassacre

Timestamp:

05/25/10 12:33:33 (12 years ago)

Author:

bacek

Comment:

Split code into chunks to simplify in-page navigation

GCMassacre

@@ +1 @@
+[[PageOutline]]
+
 = Rought idea of GC rework =
 
@@ -15 +17 @@
 ----
 
-Pseudo-code for:
- 1. Allocator API + PoolAllocator implementation.
- 2. M&S/Incremental M&S/TriColour M&S/IncrementalTriColourM&S implementations.
-
-
-{{{
-#!perl
-
+= Implementation pseudo-code =
+
+== Parrot's objects ==
+{{{
+#!perl
 # Current PObj.
 class PObj {
@@ -40 +39 @@
 };
 
+}}}
+
+== Allocator API ==
+
+{{{
+#!perl
 # GC don't care how this work. It just have to work _fast_.
 class Allocator {
@@ -50 +55 @@
 };
 
+}}}
+
+== Simple (current) Mark&Sweep ==
+
+{{{
+#!perl
+class GC {
+    has $allocator;
+    has $allocated_since_last_gc;
+    has $allocations_between_gc;
+
+    has @objects;
+
+    method BUILD() {
+        self.allocator = Allocator.new(sizeof(PObj));
+    };
+
+    method get_object() {
+        if self.need_gc() {
+            self.do_gc();
+        };
+
+        my $obj := self.allocator.allocate();
+        @objects.push($obj);
+
+        return $obj;
+    }
+
+    method need_gc() {
+        ++self.allocated_since_last_gc >= self.allocations_between_gc;
+    }
+
+    # Current GC schema.
+    method do_gc() {
+        # Mark phase
+        self.mark_alive($_) for self.trace_roots();
+
+        self.sweep();
+    }
+
+    method is_pmc($void) {
+        self.allocator.is_owned($void);
+    }
+
+    method trace_roots() {
+        my @roots;
+        for $system_areas -> $ptr {
+            @roots.push($ptr) is self.is_pmc($void);
+        }
+        @roots;
+    }
+
+    method sweep() {
+        # sweep phase
+        for @objects -> $obj {
+            if $obj.is_alive {
+                $obj.is_alive := Bool::False;
+            }
+            else {
+                self.allocator.free($obj);
+            }
+        }
+
+        self.allocated_since_last_gc := 0;
+    }
+
+    method mark_alive($obj) {
+        return if $obj.is_alive;
+
+        $obj.is_alive := Bool::True;
+        $obj.mark(self);
+    }
+};
+
+}}}
+
+== Incremental M&S ==
+
+{{{
+#!perl
+class IncrementalGC is GC {
+    # Grey objects.
+    has @working_set;
+    has $do_marking;
+
+    # Override need_gc
+    method need_gc() {
+        return Bool::False if self.do_marking;
+        return self.SUPER.need_gc();
+    }
+
+    method get_object() {
+        self.mark_a_little_bit() if self.do_marking;
+        self.SUPER.get_object();
+    }
+
+    method do_gc() {
+        # "Mark" phase
+        self.do_marking  := Bool::True;
+        self.working_set := self.trace_roots();
+    }
+
+    method mark_a_little_bit() {
+        my $count := 0;
+        for self.working_set -> $obj {
+            return if $count++ > 10;
+            self.real_mark($obj);
+        }
+
+        self.do_marking := Bool::False;
+        self.sweep();
+    }
+
+    # Override GC.mark_alive
+    method mark_alive($obj) {
+        self.working_set.push($obj);
+    }
+
+    # Just redispatch to GC.mark_alive
+    method real_mark($obj) {
+        self.SUPER.mark_alive($obj);
+    }
+}
+}}}
+
+== TriColour M&S ==
+
+{{{
+#!perl
+# is non-recursive GC
+class TriColourGC is GC {
+    # Black (inherited from GC)
+    # We need separate @live_list if we want to do it incremental
+    # has @objects;
+
+    # Grey
+    has @grey_objects;
+    # White during GC
+    has @dead_objects;
+
+    method do_gc() {
+        self.dead_objects  = self.objects;
+        self.objects       = ();
+
+        self.grey_objects  = self.trace_roots();
+        # mark_alive will push into self.grey_objects
+        self.mark_real($_) for self.grey_objects;
+
+        # Sweep
+        for self.dead_objects -> $dead {
+            $dead.destroy();
+            self.allocator.free($dead);
+        }
+    }
+
+    method mark_alive($obj) {
+        self.grey_objects.push($obj);
+        self.dead_objects.remove($obj);
+    }
+
+    method mark_real($obj) {
+        self.objects.push($obj);
+        self.SUPER.mark_alive($obj);
+    }
+};
+}}}
+
+
+== Non-recursive, tri-colour, incremental mark and sweep ==
+{{{
+#!perl
+class IncrementalTriColourGC is GC {
+    has @live_objects;  # Black
+    has @grey_objects;  # Guess?
+    has @dead_objects;  # White
+
+    has $do_marking;    # We are in mark phase.
+    has $do_sweeping;   # We are in sweep phase.
+
+    method need_gc() {
+        return Bool::False if self.do_marking || self.do_sweeping;
+        return self.SUPER.need_gc();
+    }
+
+    method get_object() {
+        self.mark_a_little_bit() if self.do_marking;
+        self.sweep_a_little_bit() if self.do_sweeping;
+        self.SUPER.get_object();
+    }
+
+    method do_gc() {
+        # Prepare mark phase
+        self.do_marking    = Bool::True;
+        self.do_sweeping   = Bool::False;
+        self.dead_objects  = self.objects;
+        self.objects       = ();
+
+        self.grey_objects  = self.trace_roots();
+    }
+
+    method mark_a_little_bit() {
+        my $count = 0;
+        while(my $obj = self.grey_objects.pop) {
+            self.mark_real($obj);
+            return if $count++ > 10;
+        }
+
+        # Switch to incremental sweep.
+        self.do_marking  = Bool::False;
+        self.do_sweeping = Bool::True;
+    }
+
+    method sweep_a_little_bit() {
+        my $count = 0;
+        while(my $dead = self.dead_objects.pop) {
+            $dead.destroy();
+            self.allocator.free($dead);
+            return if $count++ > 10;
+        }
+
+        # self.objects can be updated at this point of time.
+        # Add live_objects to objects to use on next GC round.
+        self.objects.push(self.live_objects);
+
+        # .grey_objects .dead_objects are empty now.
+        # Back to normal life
+        self.do_sweeping = Bool::False;
+    }
+
+    method mark_alive($obj) {
+        self.dead_objects.remove($obj);
+        self.grey_objects.push($obj);
+    }
+
+    method mark_real($obj) {
+        self.live_objects.push($obj);
+        self.SUPER.mark_alive($obj);
+    }
+};
+
+# vim: ft=perl6
+}}}
+
+== Implementation of PoolAllocator ==
+{{{
+#!perl
 class PoolAllocator {
     # 4KB page
@@ -168 +419 @@
 
 
-class GC {
-    has $allocator;
-    has $allocated_since_last_gc;
-    has $allocations_between_gc;
-
-    has @objects;
-
-    method BUILD() {
-        self.allocator = Allocator.new(sizeof(PObj));
-    };
-
-    method get_object() {
-        if self.need_gc() {
-            self.do_gc();
-        };
-
-        my $obj := self.allocator.allocate();
-        @objects.push($obj);
-
-        return $obj;
-    }
-
-    method need_gc() {
-        ++self.allocated_since_last_gc >= self.allocations_between_gc;
-    }
-
-    # Current GC schema.
-    method do_gc() {
-        # Mark phase
-        self.mark_alive($_) for self.trace_roots();
-
-        self.sweep();
-    }
-
-    method is_pmc($void) {
-        self.allocator.is_owned($void);
-    }
-
-    method trace_roots() {
-        my @roots;
-        for $system_areas -> $ptr {
-            @roots.push($ptr) is self.is_pmc($void);
-        }
-        @roots;
-    }
-
-    method sweep() {
-        # sweep phase
-        for @objects -> $obj {
-            if $obj.is_alive {
-                $obj.is_alive := Bool::False;
-            }
-            else {
-                self.allocator.free($obj);
-            }
-        }
-
-        self.allocated_since_last_gc := 0;
-    }
-
-    method mark_alive($obj) {
-        return if $obj.is_alive;
-
-        $obj.is_alive := Bool::True;
-        $obj.mark(self);
-    }
-};
-
-
-class IncrementalGC is GC {
-    # Grey objects.
-    has @working_set;
-    has $do_marking;
-
-    # Override need_gc
-    method need_gc() {
-        return Bool::False if self.do_marking;
-        return self.SUPER.need_gc();
-    }
-
-    method get_object() {
-        self.mark_a_little_bit() if self.do_marking;
-        self.SUPER.get_object();
-    }
-
-    method do_gc() {
-        # "Mark" phase
-        self.do_marking  := Bool::True;
-        self.working_set := self.trace_roots();
-    }
-
-    method mark_a_little_bit() {
-        my $count := 0;
-        for self.working_set -> $obj {
-            return if $count++ > 10;
-            self.real_mark($obj);
-        }
-
-        self.do_marking := Bool::False;
-        self.sweep();
-    }
-
-    # Override GC.mark_alive
-    method mark_alive($obj) {
-        self.working_set.push($obj);
-    }
-
-    # Just redispatch to GC.mark_alive
-    method real_mark($obj) {
-        self.SUPER.mark_alive($obj);
-    }
-}
-
-# is non-recursive GC
-class TriColourGC is GC {
-    # Black (inherited from GC)
-    # We need separate @live_list if we want to do it incremental
-    # has @objects;
-
-    # Grey
-    has @grey_objects;
-    # White during GC
-    has @dead_objects;
-
-    method do_gc() {
-        self.dead_objects  = self.objects;
-        self.objects       = ();
-
-        self.grey_objects  = self.trace_roots();
-        # mark_alive will push into self.grey_objects
-        self.mark_real($_) for self.grey_objects;
-
-        # Sweep
-        for self.dead_objects -> $dead {
-            $dead.destroy();
-            self.allocator.free($dead);
-        }
-    }
-
-    method mark_alive($obj) {
-        self.grey_objects.push($obj);
-        self.dead_objects.remove($obj);
-    }
-
-    method mark_real($obj) {
-        self.objects.push($obj);
-        self.SUPER.mark_alive($obj);
-    }
-};
-
-# Non-recursive, tri-colour, incremental mark and sweep.
-class IncrementalTriColourGC is GC {
-    has @live_objects;  # Black
-    has @grey_objects;  # Guess?
-    has @dead_objects;  # White
-
-    has $do_marking;    # We are in mark phase.
-    has $do_sweeping;   # We are in sweep phase.
-
-    method need_gc() {
-        return Bool::False if self.do_marking || self.do_sweeping;
-        return self.SUPER.need_gc();
-    }
-
-    method get_object() {
-        self.mark_a_little_bit() if self.do_marking;
-        self.sweep_a_little_bit() if self.do_sweeping;
-        self.SUPER.get_object();
-    }
-
-    method do_gc() {
-        # Prepare mark phase
-        self.do_marking    = Bool::True;
-        self.do_sweeping   = Bool::False;
-        self.dead_objects  = self.objects;
-        self.objects       = ();
-
-        self.grey_objects  = self.trace_roots();
-    }
-
-    method mark_a_little_bit() {
-        my $count = 0;
-        while(my $obj = self.grey_objects.pop) {
-            self.mark_real($obj);
-            return if $count++ > 10;
-        }
-
-        # Switch to incremental sweep.
-        self.do_marking  = Bool::False;
-        self.do_sweeping = Bool::True;
-    }
-
-    method sweep_a_little_bit() {
-        my $count = 0;
-        while(my $dead = self.dead_objects.pop) {
-            $dead.destroy();
-            self.allocator.free($dead);
-            return if $count++ > 10;
-        }
-
-        # self.objects can be updated at this point of time.
-        # Add live_objects to objects to use on next GC round.
-        self.objects.push(self.live_objects);
-
-        # .grey_objects .dead_objects are empty now.
-        # Back to normal life
-        self.do_sweeping = Bool::False;
-    }
-
-    method mark_alive($obj) {
-        self.dead_objects.remove($obj);
-        self.grey_objects.push($obj);
-    }
-
-    method mark_real($obj) {
-        self.live_objects.push($obj);
-        self.SUPER.mark_alive($obj);
-    }
-};
-
-# vim: ft=perl6
-
-}}}
+}}}