Premium
A new fast and safe marking algorithm
Author(s) -
Kurokawa Toshiaki
Publication year - 1981
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380110703
Subject(s) - stack (abstract data type) , algorithm , computer science , garbage collection , node (physics) , garbage , call stack , stacking , process (computing) , real time computing , engineering , operating system , programming language , physics , structural engineering , nuclear magnetic resonance
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.