An on-the-fly reference counting garbage collector for Java

Reference counting is not naturally suitable for running on multiprocessors . The update of pointers and reference counts requires atomic and synchroni zed operations. We present a novel reference counting algorithm suitable fo r a multiprocessor that does not require any synchronized operation in its write barrier (not even a compare-and-swap type of synchronization). The al gorithm is efficient and may compete with any tracing algorithm. We have implemented our algorithm on SUN's Java Virtual Machine 1.2.2 and r an it on a 4-way IBM Netfinity 8500R server with 550MHz Intel Pentium III X eon and 2GB of physical memory. It turns out that our algorithm has an extr emely low latency and throughput that is comparable to the mark and sweep a lgorithm used in the original JVM.