Changes between Version 1 and Version 2 of GCMassacre

Timestamp:

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

Author:

jimmy

Comment:

add GC/IncrementalGC/TriColourGC prototype

GCMassacre

@@ -12 +12 @@
  6. "Optional" rename VTABLE_mark to VTABLE_gc_visit 'cause I want to reuse it in Compacting phase.
    a. Or try to reuse VTABLE_visit
+
+----
+
+GC/IncrementalGC/TriColourGC prototype
+
+
+{{{
+# GC don't care how this work. Pools/Arenas/Blocks/whatever.
+class Allocator {
+    has $object_size;
+
+    method allocate() { ... };
+    method free(pointer $obj) { ... };
+};
+
+# Current PObj.
+class PObj {
+    has $flags;
+};
+
+
+class PMC is PObj {
+    method mark($gc) { ... }
+};
+
+class RPA is PMC {
+    has @pmcs;
+
+    method mark($gc) {
+        $gc.mark_alive($_) for self.pmcs;
+    }
+};
+
+
+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 trace_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 {
+    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);
+    }
+};
+
+
+
+# vim: ft=perl6
+
+
+}}}