Comparing reference counting and global mark-and-sweep on parallel computers.pdf

Comparing Reference Counting and Global Mark-and-Sweep on Parallel Computers Hirotaka Yamamoto, Kenjiro Taura, and Akinori Yonezawa Department of Information Science, University of Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo, Japan fymmt,tau,yonezawag@is.s.u-tokyo.ac.jp Abstract. We compare two dynamic memory management schemes for distributed-memory parallel computers, one based on reference counting and the other based on global mark-and-sweep. We present a simple model in which one can analyze performance of the two types of GC schemes, and show experimental results. The two important observations drawn from the analysis are: 1) the performance of reference counting largely depends on shapes of data structures; specically, it is bad when applications use deeply nested data structures such as distributed trees. 2) the cost of reference counting has a portion that is independent of the heap size while that of global mark-and-sweep does not. We conrmed these observations through experiments using three parallel applications. 1 Introduction Most of the proposed algorithms and implementations of garbage collection (GC) on distributed-memory parallel computers can be classied into two groups: Ref- erence Counting and Global Mark-and-Sweep[13]. Reference counting has often been considered superior to global mark-and-sweep because it does not require any synchronization, but previous arguments are often supercial, not conrmed by experiments, and lack a macroscopic viewpoint on the overall eciency of these two collection schemes. This paper reports a performance comparison of these two schemes, with simple analyses on the overall eciency of both reference counting and global mark-and-sweep, and experimental results. Experiments have been done on a parallel computer in which processes communicate solely via message passing, using three parallel applications. Observations drawn from the analyses and experimental results include: { Performance of reference counting is sensit