Higher-Order and Symbolic Computation, 14(4)357-386
Tree Rerooting in Distributed Garbage Collection: Implementation and Performance EvaluationLuc Moreau, Department of Electronics and Computer Science, University of Southampton, Southampton SO17 1BJ, UK
|
Abstract: We have recently defined a new algorithm for
distributed garbage collection based on reference-counting (Luc
Moreau, in Proceedings of the Third International Conference of
Functional Programming (ICFP'98), Sept. 1998, pp. 204?215; Luc
Moreau and J. Duprat, Technical Report RR1999-18, Ecole Normale
Supérieure, Lyon, March 1999). At the heart of the algorithm, we find
tree rerooting, a mechanism able to reduce third-party dependencies by
reorganising diffusion trees. In reality, the algorithm describes a
spectrum of algorithms according to the policy used to manage
messages. In this paper, we present the implementation of the
algorithm and evaluate its performance. We have implemented two
policies, which are extremes of the spectrum, respectively using and
not using tree rerooting. In addition, two different strategies for
managing action queues have been implemented. The conclusions of our
experimentations are the following. Tree rerooting offers more
parallelism during distributed GC activity; we explain this phenomenon
by the length reduction of causality chains in the distributed
GC. Grouping messages per destination dramatically reduces the number
of messages, but requires a more complex implementation as messages
have to be sorted per destination. Speed up of 100% has been observed
on some benchmarks.
Keywords: distributed garbage collection, distributed reference counting, performance evaluation, benchmark |
This article can be downloaded [here].