Changes between Version 6 and Version 7 of GCMassacre

Show
Ignore:
Timestamp:
05/25/10 12:33:33 (5 years ago)
Author:
bacek
Comment:

Split code into chunks to simplify in-page navigation

Legend:

Unmodified
Added
Removed
Modified
  • GCMassacre

    v6 v7  
     1[[PageOutline]] 
     2 
    13= Rought idea of GC rework = 
    24 
     
    1517---- 
    1618 
    17 Pseudo-code for: 
    18  1. Allocator API + PoolAllocator implementation. 
    19  2. M&S/Incremental M&S/TriColour M&S/IncrementalTriColourM&S implementations. 
    20  
    21  
    22 {{{ 
    23 #!perl 
    24  
     19= Implementation pseudo-code = 
     20 
     21== Parrot's objects == 
     22{{{ 
     23#!perl 
    2524# Current PObj. 
    2625class PObj { 
     
    4039}; 
    4140 
     41}}} 
     42 
     43== Allocator API == 
     44 
     45{{{ 
     46#!perl 
    4247# GC don't care how this work. It just have to work _fast_. 
    4348class Allocator { 
     
    5055}; 
    5156 
     57}}} 
     58 
     59== Simple (current) Mark&Sweep == 
     60 
     61{{{ 
     62#!perl 
     63class GC { 
     64    has $allocator; 
     65    has $allocated_since_last_gc; 
     66    has $allocations_between_gc; 
     67 
     68    has @objects; 
     69 
     70    method BUILD() { 
     71        self.allocator = Allocator.new(sizeof(PObj)); 
     72    }; 
     73 
     74    method get_object() { 
     75        if self.need_gc() { 
     76            self.do_gc(); 
     77        }; 
     78 
     79        my $obj := self.allocator.allocate(); 
     80        @objects.push($obj); 
     81 
     82        return $obj; 
     83    } 
     84 
     85    method need_gc() { 
     86        ++self.allocated_since_last_gc >= self.allocations_between_gc; 
     87    } 
     88 
     89    # Current GC schema. 
     90    method do_gc() { 
     91        # Mark phase 
     92        self.mark_alive($_) for self.trace_roots(); 
     93 
     94        self.sweep(); 
     95    } 
     96 
     97    method is_pmc($void) { 
     98        self.allocator.is_owned($void); 
     99    } 
     100 
     101    method trace_roots() { 
     102        my @roots; 
     103        for $system_areas -> $ptr { 
     104            @roots.push($ptr) is self.is_pmc($void); 
     105        } 
     106        @roots; 
     107    } 
     108 
     109    method sweep() { 
     110        # sweep phase 
     111        for @objects -> $obj { 
     112            if $obj.is_alive { 
     113                $obj.is_alive := Bool::False; 
     114            } 
     115            else { 
     116                self.allocator.free($obj); 
     117            } 
     118        } 
     119 
     120        self.allocated_since_last_gc := 0; 
     121    } 
     122 
     123    method mark_alive($obj) { 
     124        return if $obj.is_alive; 
     125 
     126        $obj.is_alive := Bool::True; 
     127        $obj.mark(self); 
     128    } 
     129}; 
     130 
     131}}} 
     132 
     133== Incremental M&S == 
     134 
     135{{{ 
     136#!perl 
     137class IncrementalGC is GC { 
     138    # Grey objects. 
     139    has @working_set; 
     140    has $do_marking; 
     141 
     142    # Override need_gc 
     143    method need_gc() { 
     144        return Bool::False if self.do_marking; 
     145        return self.SUPER.need_gc(); 
     146    } 
     147 
     148    method get_object() { 
     149        self.mark_a_little_bit() if self.do_marking; 
     150        self.SUPER.get_object(); 
     151    } 
     152 
     153    method do_gc() { 
     154        # "Mark" phase 
     155        self.do_marking  := Bool::True; 
     156        self.working_set := self.trace_roots(); 
     157    } 
     158 
     159    method mark_a_little_bit() { 
     160        my $count := 0; 
     161        for self.working_set -> $obj { 
     162            return if $count++ > 10; 
     163            self.real_mark($obj); 
     164        } 
     165 
     166        self.do_marking := Bool::False; 
     167        self.sweep(); 
     168    } 
     169 
     170    # Override GC.mark_alive 
     171    method mark_alive($obj) { 
     172        self.working_set.push($obj); 
     173    } 
     174 
     175    # Just redispatch to GC.mark_alive 
     176    method real_mark($obj) { 
     177        self.SUPER.mark_alive($obj); 
     178    } 
     179} 
     180}}} 
     181 
     182== TriColour M&S == 
     183 
     184{{{ 
     185#!perl 
     186# is non-recursive GC 
     187class TriColourGC is GC { 
     188    # Black (inherited from GC) 
     189    # We need separate @live_list if we want to do it incremental 
     190    # has @objects; 
     191 
     192    # Grey 
     193    has @grey_objects; 
     194    # White during GC 
     195    has @dead_objects; 
     196 
     197    method do_gc() { 
     198        self.dead_objects  = self.objects; 
     199        self.objects       = (); 
     200 
     201        self.grey_objects  = self.trace_roots(); 
     202        # mark_alive will push into self.grey_objects 
     203        self.mark_real($_) for self.grey_objects; 
     204 
     205        # Sweep 
     206        for self.dead_objects -> $dead { 
     207            $dead.destroy(); 
     208            self.allocator.free($dead); 
     209        } 
     210    } 
     211 
     212    method mark_alive($obj) { 
     213        self.grey_objects.push($obj); 
     214        self.dead_objects.remove($obj); 
     215    } 
     216 
     217    method mark_real($obj) { 
     218        self.objects.push($obj); 
     219        self.SUPER.mark_alive($obj); 
     220    } 
     221}; 
     222}}} 
     223 
     224 
     225== Non-recursive, tri-colour, incremental mark and sweep == 
     226{{{ 
     227#!perl 
     228class IncrementalTriColourGC is GC { 
     229    has @live_objects;  # Black 
     230    has @grey_objects;  # Guess? 
     231    has @dead_objects;  # White 
     232 
     233    has $do_marking;    # We are in mark phase. 
     234    has $do_sweeping;   # We are in sweep phase. 
     235 
     236    method need_gc() { 
     237        return Bool::False if self.do_marking || self.do_sweeping; 
     238        return self.SUPER.need_gc(); 
     239    } 
     240 
     241    method get_object() { 
     242        self.mark_a_little_bit() if self.do_marking; 
     243        self.sweep_a_little_bit() if self.do_sweeping; 
     244        self.SUPER.get_object(); 
     245    } 
     246 
     247    method do_gc() { 
     248        # Prepare mark phase 
     249        self.do_marking    = Bool::True; 
     250        self.do_sweeping   = Bool::False; 
     251        self.dead_objects  = self.objects; 
     252        self.objects       = (); 
     253 
     254        self.grey_objects  = self.trace_roots(); 
     255    } 
     256 
     257    method mark_a_little_bit() { 
     258        my $count = 0; 
     259        while(my $obj = self.grey_objects.pop) { 
     260            self.mark_real($obj); 
     261            return if $count++ > 10; 
     262        } 
     263 
     264        # Switch to incremental sweep. 
     265        self.do_marking  = Bool::False; 
     266        self.do_sweeping = Bool::True; 
     267    } 
     268 
     269    method sweep_a_little_bit() { 
     270        my $count = 0; 
     271        while(my $dead = self.dead_objects.pop) { 
     272            $dead.destroy(); 
     273            self.allocator.free($dead); 
     274            return if $count++ > 10; 
     275        } 
     276 
     277        # self.objects can be updated at this point of time. 
     278        # Add live_objects to objects to use on next GC round. 
     279        self.objects.push(self.live_objects); 
     280 
     281        # .grey_objects .dead_objects are empty now. 
     282        # Back to normal life 
     283        self.do_sweeping = Bool::False; 
     284    } 
     285 
     286    method mark_alive($obj) { 
     287        self.dead_objects.remove($obj); 
     288        self.grey_objects.push($obj); 
     289    } 
     290 
     291    method mark_real($obj) { 
     292        self.live_objects.push($obj); 
     293        self.SUPER.mark_alive($obj); 
     294    } 
     295}; 
     296 
     297# vim: ft=perl6 
     298}}} 
     299 
     300== Implementation of PoolAllocator == 
     301{{{ 
     302#!perl 
    52303class PoolAllocator { 
    53304    # 4KB page 
     
    168419 
    169420 
    170 class GC { 
    171     has $allocator; 
    172     has $allocated_since_last_gc; 
    173     has $allocations_between_gc; 
    174  
    175     has @objects; 
    176  
    177     method BUILD() { 
    178         self.allocator = Allocator.new(sizeof(PObj)); 
    179     }; 
    180  
    181     method get_object() { 
    182         if self.need_gc() { 
    183             self.do_gc(); 
    184         }; 
    185  
    186         my $obj := self.allocator.allocate(); 
    187         @objects.push($obj); 
    188  
    189         return $obj; 
    190     } 
    191  
    192     method need_gc() { 
    193         ++self.allocated_since_last_gc >= self.allocations_between_gc; 
    194     } 
    195  
    196     # Current GC schema. 
    197     method do_gc() { 
    198         # Mark phase 
    199         self.mark_alive($_) for self.trace_roots(); 
    200  
    201         self.sweep(); 
    202     } 
    203  
    204     method is_pmc($void) { 
    205         self.allocator.is_owned($void); 
    206     } 
    207  
    208     method trace_roots() { 
    209         my @roots; 
    210         for $system_areas -> $ptr { 
    211             @roots.push($ptr) is self.is_pmc($void); 
    212         } 
    213         @roots; 
    214     } 
    215  
    216     method sweep() { 
    217         # sweep phase 
    218         for @objects -> $obj { 
    219             if $obj.is_alive { 
    220                 $obj.is_alive := Bool::False; 
    221             } 
    222             else { 
    223                 self.allocator.free($obj); 
    224             } 
    225         } 
    226  
    227         self.allocated_since_last_gc := 0; 
    228     } 
    229  
    230     method mark_alive($obj) { 
    231         return if $obj.is_alive; 
    232  
    233         $obj.is_alive := Bool::True; 
    234         $obj.mark(self); 
    235     } 
    236 }; 
    237  
    238  
    239 class IncrementalGC is GC { 
    240     # Grey objects. 
    241     has @working_set; 
    242     has $do_marking; 
    243  
    244     # Override need_gc 
    245     method need_gc() { 
    246         return Bool::False if self.do_marking; 
    247         return self.SUPER.need_gc(); 
    248     } 
    249  
    250     method get_object() { 
    251         self.mark_a_little_bit() if self.do_marking; 
    252         self.SUPER.get_object(); 
    253     } 
    254  
    255     method do_gc() { 
    256         # "Mark" phase 
    257         self.do_marking  := Bool::True; 
    258         self.working_set := self.trace_roots(); 
    259     } 
    260  
    261     method mark_a_little_bit() { 
    262         my $count := 0; 
    263         for self.working_set -> $obj { 
    264             return if $count++ > 10; 
    265             self.real_mark($obj); 
    266         } 
    267  
    268         self.do_marking := Bool::False; 
    269         self.sweep(); 
    270     } 
    271  
    272     # Override GC.mark_alive 
    273     method mark_alive($obj) { 
    274         self.working_set.push($obj); 
    275     } 
    276  
    277     # Just redispatch to GC.mark_alive 
    278     method real_mark($obj) { 
    279         self.SUPER.mark_alive($obj); 
    280     } 
    281 } 
    282  
    283 # is non-recursive GC 
    284 class TriColourGC is GC { 
    285     # Black (inherited from GC) 
    286     # We need separate @live_list if we want to do it incremental 
    287     # has @objects; 
    288  
    289     # Grey 
    290     has @grey_objects; 
    291     # White during GC 
    292     has @dead_objects; 
    293  
    294     method do_gc() { 
    295         self.dead_objects  = self.objects; 
    296         self.objects       = (); 
    297  
    298         self.grey_objects  = self.trace_roots(); 
    299         # mark_alive will push into self.grey_objects 
    300         self.mark_real($_) for self.grey_objects; 
    301  
    302         # Sweep 
    303         for self.dead_objects -> $dead { 
    304             $dead.destroy(); 
    305             self.allocator.free($dead); 
    306         } 
    307     } 
    308  
    309     method mark_alive($obj) { 
    310         self.grey_objects.push($obj); 
    311         self.dead_objects.remove($obj); 
    312     } 
    313  
    314     method mark_real($obj) { 
    315         self.objects.push($obj); 
    316         self.SUPER.mark_alive($obj); 
    317     } 
    318 }; 
    319  
    320 # Non-recursive, tri-colour, incremental mark and sweep. 
    321 class IncrementalTriColourGC is GC { 
    322     has @live_objects;  # Black 
    323     has @grey_objects;  # Guess? 
    324     has @dead_objects;  # White 
    325  
    326     has $do_marking;    # We are in mark phase. 
    327     has $do_sweeping;   # We are in sweep phase. 
    328  
    329     method need_gc() { 
    330         return Bool::False if self.do_marking || self.do_sweeping; 
    331         return self.SUPER.need_gc(); 
    332     } 
    333  
    334     method get_object() { 
    335         self.mark_a_little_bit() if self.do_marking; 
    336         self.sweep_a_little_bit() if self.do_sweeping; 
    337         self.SUPER.get_object(); 
    338     } 
    339  
    340     method do_gc() { 
    341         # Prepare mark phase 
    342         self.do_marking    = Bool::True; 
    343         self.do_sweeping   = Bool::False; 
    344         self.dead_objects  = self.objects; 
    345         self.objects       = (); 
    346  
    347         self.grey_objects  = self.trace_roots(); 
    348     } 
    349  
    350     method mark_a_little_bit() { 
    351         my $count = 0; 
    352         while(my $obj = self.grey_objects.pop) { 
    353             self.mark_real($obj); 
    354             return if $count++ > 10; 
    355         } 
    356  
    357         # Switch to incremental sweep. 
    358         self.do_marking  = Bool::False; 
    359         self.do_sweeping = Bool::True; 
    360     } 
    361  
    362     method sweep_a_little_bit() { 
    363         my $count = 0; 
    364         while(my $dead = self.dead_objects.pop) { 
    365             $dead.destroy(); 
    366             self.allocator.free($dead); 
    367             return if $count++ > 10; 
    368         } 
    369  
    370         # self.objects can be updated at this point of time. 
    371         # Add live_objects to objects to use on next GC round. 
    372         self.objects.push(self.live_objects); 
    373  
    374         # .grey_objects .dead_objects are empty now. 
    375         # Back to normal life 
    376         self.do_sweeping = Bool::False; 
    377     } 
    378  
    379     method mark_alive($obj) { 
    380         self.dead_objects.remove($obj); 
    381         self.grey_objects.push($obj); 
    382     } 
    383  
    384     method mark_real($obj) { 
    385         self.live_objects.push($obj); 
    386         self.SUPER.mark_alive($obj); 
    387     } 
    388 }; 
    389  
    390 # vim: ft=perl6 
    391  
    392 }}} 
     421}}}