ATOM: Automatic Transaction-Oriented Memoization, October 2009

Abstract. Memoization is a well-known technique for improving the performance of a program, but it has been confined mostly to functional programming, because it applies only to pure functions. In this paper, we propose an extended memoization approach that takes advantage of the support provided by a Software Transactional Memory (STM) to remove many of the limitations of traditional memoization. We argue that our extended memoization system is the first to suit the needs of object-oriented programming, and show that it may be implemented almost for free in systems that use an STM. We describe the major design and implementation decisions of our system and present results for a benchmark that show a 3-fold increase in the throughput of the system when using our memoization system. Key words: Memoization, function caching, object-oriented program-ming, software transactional memor