Improved replication-based incremental garbage collection for embedded systems

Abstract

We have developed an incremental compacting garbage collector for embedded Java systems. The collector divides the heap into equal sized pages and uses the segregated free lists for fast allocation. Collectors that have such a heap layout have a problem of fragmentation in allocating objects larger than the page size. We solve this problem by using the replication-based incremental compaction. The compactor evacuates all objects in one area, the evacuation area, of the heap, thereby creating a large chunk of free space. We developed an algorithm for choosing the evacuation area that effectively cures fragmentation. The compactor does not use any read-barriers. Instead, it uses a technique similar to the replication-based incremental copying collection. This needs forwarding pointers for all evacuated objects. Rather than introducing an extra field for each object, we use a hash table to store forwarding pointers.