Abstract: | A new marking algorithm for garbage collection is presented. Although the method is a variation of the usual simple stacking algorithm, in practice this algorithm has quite improved both in stack space and processing time. One significant modification is to stack a node only when both the sublists are unmarked. The other innovation is a ‘stacked-node-checking’ method invoked after each stack-overflow. With this method, a number of unnecessary nodes are eliminated, the stack is compacted, and the marking process can resume using the generated space in the stack. This algorithm has been used for LISP1.9 garbage collection for years, and succeeded in showing good figures. |