Version 2 (modified by jimmy, 5 years ago)

add GC/IncrementalGC/TriColourGC prototype

Rought idea of GC rework

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