Eliminating Cycles in Weak Tables

Alexandra Barros (Pontifical Catholic University of Rio de Janeiro, Brazil)

Roberto Ierusalimschy (Pontifical Catholic University of Rio de Janeiro, Brazil)

Abstract: Weak References constitute an elegant mechanism for an application to interact with its garbage collector. In most of its typical uses, weak references are used through weak tables (e.g., Java's WeakHashMap). However, most implementations of weak tables have a severe limitation: Cyclic references between keys and values in weak tables prevent the elements inside a cycle from being collected, even if they are no longer reachable from outside. This ends up bringing difficulties to the use of weak tables in some kinds of applications.

In this work, we present our approach for overcoming this problem in the context of the Lua programming language. Our approach consists of an adaptation of the ephemerons mechanism to tables. We modified the garbage collector of the Lua virtual machine in order to offer support to this mechanism. With this adapted garbage collector we could verify the efficiency and effectiveness of the implementation in solving the problem of cycles on weak tables in Lua.

Keywords: Garbage collection, weak references, weak tables

Categories: D.3.3