Version 3 (modified by bacek, 12 years ago)

Add "Non-recursive, tri-colour, incremental mark and sweep." proto

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);
    }
};


# 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