TU Darmstadt / ULB / TUbiblio

Performance problems you can fix: a dynamic analysis of memoization opportunities

Della Toffola, Luca and Pradel, Michael and Gross, Thomas R.
Andy, Gill (ed.) (2015):
Performance problems you can fix: a dynamic analysis of memoization opportunities.
In: Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, ACM, Pittsburgh, PA, USA, In: OOPSLA 2015, ISBN 978-1-4503-3689-5,
DOI: 10.1145/2814270.2814290, [Conference or Workshop Item]

Abstract

Performance bugs are a prevalent problem and recent research proposes various techniques to identify such bugs. This paper addresses a kind of performance problem that often is easy to address but difficult to identify: redundant computations that may be avoided by reusing already computed results for particular inputs, a technique called memoization. To help developers find and use memoization opportunities, we present MemoizeIt, a dynamic analysis that identifies methods that repeatedly perform the same computation. The key idea is to compare inputs and outputs of method calls in a scalable yet precise way. To avoid the overhead of comparing objects at all method invocations in detail, MemoizeIt first compares objects without following any references and iteratively increases the depth of exploration while shrinking the set of considered methods. After each iteration, the approach ignores methods that cannot benefit from memoization, allowing it to analyze calls to the remaining methods in more detail. For every memoization opportunity that MemoizeIt detects, it provides hints on how to implement memoization, making it easy for the developer to fix the performance issue. Applying MemoizeIt to eleven real-world Java programs reveals nine profitable memoization opportunities, most of which are missed by traditional CPU time profilers, conservative compiler optimizations, and other existing approaches for finding performance bugs. Adding memoization as proposed by MemoizeIt leads to statistically significant speedups by factors between 1.04x and 12.93x.

Item Type: Conference or Workshop Item
Erschienen: 2015
Editors: Andy, Gill
Creators: Della Toffola, Luca and Pradel, Michael and Gross, Thomas R.
Title: Performance problems you can fix: a dynamic analysis of memoization opportunities
Language: German
Abstract:

Performance bugs are a prevalent problem and recent research proposes various techniques to identify such bugs. This paper addresses a kind of performance problem that often is easy to address but difficult to identify: redundant computations that may be avoided by reusing already computed results for particular inputs, a technique called memoization. To help developers find and use memoization opportunities, we present MemoizeIt, a dynamic analysis that identifies methods that repeatedly perform the same computation. The key idea is to compare inputs and outputs of method calls in a scalable yet precise way. To avoid the overhead of comparing objects at all method invocations in detail, MemoizeIt first compares objects without following any references and iteratively increases the depth of exploration while shrinking the set of considered methods. After each iteration, the approach ignores methods that cannot benefit from memoization, allowing it to analyze calls to the remaining methods in more detail. For every memoization opportunity that MemoizeIt detects, it provides hints on how to implement memoization, making it easy for the developer to fix the performance issue. Applying MemoizeIt to eleven real-world Java programs reveals nine profitable memoization opportunities, most of which are missed by traditional CPU time profilers, conservative compiler optimizations, and other existing approaches for finding performance bugs. Adding memoization as proposed by MemoizeIt leads to statistically significant speedups by factors between 1.04x and 12.93x.

Title of Book: Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications
Series Name: OOPSLA 2015
Volume: 50
Number: 10
Publisher: ACM
ISBN: 978-1-4503-3689-5
Uncontrolled Keywords: Memoization, caching, performance bugs, profiling
Divisions: Profile Areas
Profile Areas > Cybersecurity (CYSEC)
Event Location: Pittsburgh, PA, USA
Date Deposited: 17 Aug 2017 14:42
DOI: 10.1145/2814270.2814290
Identification Number: TUD-CS-2015-12088
Export:

Optionen (nur für Redakteure)

View Item View Item