Version 3 (modified by bacek, 12 years ago) |
---|
Rought idea of GC rework
- Decouple GC from Memory Allocation (Remove all this Pool/Arena/Whatever)
- Made GC track GCable.
(Without going through Pools to find if we need more memory/iterating headers/etc)
- Implement sweep-free GC. (And it will be much easy because GC track GCable already)
- Break API to make Parrot_gc_mark_PMC_alive to accept PMC**. (And probably rename it into gc_visit_pmc)
- Implement Compacting GC.
- Implement Generational GC on top of Compacting.
- "Optional" rename VTABLE_mark to VTABLE_gc_visit 'cause I want to reuse it in Compacting phase.
- 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); } }; # 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