Home > Publications > Reports > Informatics (CW)


CW 334

Bart Demoen, Phuong-Lan Nguyen
Respecting the variable order in a copying garbage collector for the WAM

Abstract

One of the main objections against copying collectors for Prolog is that they do not retain the variable ordering as defined by the built-in predicate compare/3. Solutions to this problem exist already for a long time, but seem not widely known. So there is a point in presenting and evaluating them. The first solution reuses an old idea in garbage collection and is a simple add-on to any mark&copy collector. Its cost is O(Vlog(V)) where V is the number of live variables at the moment of the garbage collection. The mutator incurs no cost. The second method is just an old - but never before implemented - method which has a constant overhead on each variable-variable comparison and a O(V) overhead on the garbage collector. It is also very easy to implement. The third method presented is a mixture of the previous two.

report.pdf / mailto: B. Demoen