Changes between Version 1 and Version 2 of GCMassacre

Show
Ignore:
Timestamp:
05/25/10 10:25:37 (4 years ago)
Author:
jimmy
Comment:

add GC/IncrementalGC/TriColourGC prototype

Legend:

Unmodified
Added
Removed
Modified
  • GCMassacre

    v1 v2  
    1212 6. "Optional" rename VTABLE_mark to VTABLE_gc_visit 'cause I want to reuse it in Compacting phase. 
    1313   a. Or try to reuse VTABLE_visit 
     14 
     15---- 
     16 
     17GC/IncrementalGC/TriColourGC prototype 
     18 
     19 
     20{{{ 
     21# GC don't care how this work. Pools/Arenas/Blocks/whatever. 
     22class Allocator { 
     23    has $object_size; 
     24 
     25    method allocate() { ... }; 
     26    method free(pointer $obj) { ... }; 
     27}; 
     28 
     29# Current PObj. 
     30class PObj { 
     31    has $flags; 
     32}; 
     33 
     34 
     35class PMC is PObj { 
     36    method mark($gc) { ... } 
     37}; 
     38 
     39class RPA is PMC { 
     40    has @pmcs; 
     41 
     42    method mark($gc) { 
     43        $gc.mark_alive($_) for self.pmcs; 
     44    } 
     45}; 
     46 
     47 
     48class GC { 
     49    has $allocator; 
     50    has $allocated_since_last_gc; 
     51    has $allocations_between_gc; 
     52 
     53    has @objects; 
     54 
     55    method BUILD() { 
     56        self.allocator = Allocator.new(sizeof(PObj)); 
     57    }; 
     58 
     59    method get_object() { 
     60        if self.need_gc() { 
     61            self.do_gc(); 
     62        }; 
     63 
     64        my $obj := self.allocator.allocate(); 
     65        @objects.push($obj); 
     66 
     67        return $obj; 
     68    } 
     69 
     70    method need_gc() { 
     71        ++self.allocated_since_last_gc >= self.allocations_between_gc; 
     72    } 
     73 
     74    # Current GC schema. 
     75    method do_gc() { 
     76        # Mark phase 
     77        self.mark_alive($_) for self.trace_roots(); 
     78 
     79        self.sweep(); 
     80    } 
     81 
     82    method trace_roots() { ... } 
     83 
     84    method sweep() { 
     85        # sweep phase 
     86        for @objects -> $obj { 
     87            if $obj.is_alive { 
     88                $obj.is_alive := Bool::False; 
     89            } 
     90            else { 
     91                self.allocator.free($obj); 
     92            } 
     93        } 
     94        self.allocated_since_last_gc := 0; 
     95    } 
     96 
     97    method mark_alive($obj) { 
     98        return if $obj.is_alive; 
     99 
     100        $obj.is_alive := Bool::True; 
     101        $obj.mark(self); 
     102    } 
     103}; 
     104 
     105class IncrementalGC is GC { 
     106    has @working_set; 
     107    has $do_marking; 
     108 
     109    # Override need_gc 
     110    method need_gc() { 
     111        return Bool::False if self.do_marking; 
     112        return self.SUPER.need_gc(); 
     113    } 
     114 
     115    method get_object() { 
     116        self.mark_a_little_bit() if self.do_marking; 
     117        self.SUPER.get_object(); 
     118    } 
     119 
     120    method do_gc() { 
     121        # "Mark" phase 
     122        self.do_marking := Bool::True; 
     123        self.working_set := self.trace_roots(); 
     124    } 
     125 
     126    method mark_a_little_bit() { 
     127        my $count := 0; 
     128        for self.working_set -> $obj { 
     129            return if $count++ > 10; 
     130            self.real_mark($obj); 
     131        } 
     132 
     133        self.do_marking := Bool::False; 
     134        self.sweep(); 
     135    } 
     136 
     137    # Override GC.mark_alive 
     138    method mark_alive($obj) { 
     139        self.working_set.push($obj); 
     140    } 
     141 
     142    # Just redispatch to GC.mark_alive 
     143    method real_mark($obj) { 
     144        self.SUPER.mark_alive($obj); 
     145    } 
     146} 
     147 
     148# is non-recursive GC 
     149class TriColourGC is GC { 
     150    # Black (inherited from GC) 
     151    # We need separate @live_list if we want to do it incremental 
     152    # has @objects; 
     153 
     154    # Grey 
     155    has @grey_objects; 
     156    # White during GC 
     157    has @dead_objects; 
     158 
     159    method do_gc() { 
     160        self.dead_objects = self.objects; 
     161        self.objects = (); 
     162 
     163        self.grey_objects = self.trace_roots(); 
     164        # mark_alive will push into self.grey_objects 
     165        self.mark_real($_) for self.grey_objects; 
     166 
     167        # Sweep 
     168        for self.dead_objects -> $dead { 
     169            $dead.destroy(); 
     170            self.allocator.free($dead); 
     171        } 
     172    } 
     173 
     174    method mark_alive($obj) { 
     175        self.grey_objects.push($obj); 
     176        self.dead_objects.remove($obj); 
     177    } 
     178 
     179    method mark_real($obj) { 
     180        self.objects.push($obj); 
     181        self.SUPER.mark_alive($obj); 
     182    } 
     183}; 
     184 
     185 
     186 
     187# vim: ft=perl6 
     188 
     189 
     190}}}