CW 303

K. Sagonas and B. Demoen
From (multi-)generational to segment order preserving copying garbare collection for the WAM

Abstract

We develop an algorithm for generational copying garbage collection in the WAM based on three generations. We then generalize this 3-generational algorithm to any number of generations. A new segment order preserving copying garbage collection algorithm then follows in a natural way. In contrast to previous segment preserving algorithms, the new algorithm does not require traversing the stacks in the opposite order, at the cost of a O(log(n)) pointer lookup where n is the number of collected heap segments. A trade-off between precision in the preservation of heap segment order and O(1) pointer lookup is presented. The algorithm gives an overall simple and practical way of implementing multi-generational copying garbarge collection. Issues related to preserving generations on backtracking and cut are also discussed, as well as the impact of generations on early reset.