ATOM: Automatic Transaction-Oriented Memoization
Hugo Rito, Jorge Beja Rito · 2009
Over the last decades the object-oriented paradigm evolved to the point that, nowadays, it is the preferred approach for software development. In this programming paradigm, objects maintain internal state that influence the objects’ behaviors and, in general, this state changes over time. This differentiating characteristics of object-oriented programs difficult the application of techniques commonly used in other programming paradigms. One such example is memoization, a well-known technique for improving the performance of pure functional programs in a transparent way and without changing their semantics. The difficulty of applying memoization in object-oriented imperative programs results, precisely, from the fact that a method’s behavior may depend on shared state values or produce side-effects. Something that does not what happen in functional contexts. In this dissertation, I propose an extended memoization approach that builds on the support provided by a Software Transactional Memory (STM) to remove many of the limitations of traditional memoization. I argue that my extended automatic memoization system (ATOM) is the first to suit the needs of objectoriented programming. I show how memoization can be implemented almost for free in systems that use an STM, and present the reasons why this synergy can be particularly useful in transactional contexts. I validate the usefulness of memoizing object-oriented programs by applying memoization to the STMBench7 benchmark, a standard benchmark developed for evaluating STM implementations. The memoized version of the benchmark shows up to a 14-fold increase in the throughput for a read-dominated workload. Palavras Chave Keywords