# GC Redux

## Soren Renner — 2000-09-07 18:18:52

    More about GC and Joy

    I mentioned that my machine is written in and leaves GC to Oberon. It would be possible to implement memory pools, one for each kind of object. When a new intBox (object containing an integer) is needed one is taken from the intBox pool. Only if the pool is empty is a new intBox allocated  in Oberon.  The problem with the pool approach is that once allocated, memory can be reused only for the same kind of object.  A program that fills memory with discarded integers and then tries to allocate millions of strings  is going to fail even though the same program would have worked perfectly with no collection, since when memory filled up an Oberon collection would have been triggered. But Oberon can't collect objects in a pool, since they are not garbage from Oberon's point of view. It might be interesting to see the garbage left by programs, though. I have written a garbage compactor. It doesn't reuse memory.

    Actually "pop" is the only op rewritten to compact garbage so far.

    Here is "pop" :

    PROCEDURE pop*(VAR stack: Box);

    BEGIN

    	stack := stack.next

    END pop;

    compacting "pop" :

    PROCEDURE pop*(VAR stack: Box);

    VAR

    	a: Box;

    BEGIN

    	a := stack.next;

    	stack.next := garbage;

    	garbage := stack;

    	stack := a

    END pop;

    Demonstration of compaction:

     program:

     [          1 [  dup          1 plus  ]          4 times  ]

     output:

             5         4         3         2         1

     garbage:

     EMPTY BOX

     program:

     [          1 [  dup          1 plus  ]          4 times  [  pop  ]          4 times  ]

     output:

             1

     garbage:

             2         3         4         5 EMPTY BOX

     program:

     [          1 [  dup          1 plus  ]          4 times  [  pop  ]          4 times  ]

     output:

             1

     garbage:

             2         3         4         5         2         3         4         5 EMPTY BOX

    Here is the dictionary object used by the parser printed out:

    	73  "dup" dup

           196  "plus" plus

            78  "mul" mul

            44  "minus" minus

            64  "mod" mod

            67  "div" div

           105  "i" i

           120  "concat" concat

           187  "swap" swap

            62  "map" map

            34  "times" times

           207  "if" if

            79  "pop" pop

            46  "quote" quote

           188  "noop" noop

            16  "infra" infra

           179  "cons" cons

           150  "uncons" uncons

            47  "empty" empty

           192  "zero" zero

           107  "define" define

            24  "equal" equal

            61  "dip" dip

           252  "reverse" reverse

    Here's a definition:

    program:

     [  [  dup  mul  ]  "square"  define  ]

     output:

     [  dup  mul  ]

     garbage:

             2         3         4         5         2         3         4         5 EMPTY BOX

    The dictionary now prints an extra entry: 145  "square" dup  mul

    Notice that the garbage is persistent. The garbage is like an antistack: if it makes you think of a Stirling engine and thermodynamics, you are not the first person this has occurred to. (Probably Henry Baker was.)