A Complexity Study of Garbage Collection for Small Devices

Garbage collection techniques have been the focus of numerous research works. In particular, their efficiencies and properties have been measured and discussed for years, concerning their use on computers. Today, virtual machines are increasingly considered for constraints devices such as smart cards, sensors, or personal digital assistants (pdas). These small devices have a specific hardware configuration. In particular, the memories used can be very different of the RAM (e.g. EEPROM, Flash memory, different types of RAM, etc.). Although garbage collection has been widely studied in the past decades, existing works do not take into account the specifics of such memories. This article presents a fine complexity study which takes into account the properties of the memories, especially their read and write access speeds.