An optimization-based approach to lookup table program transformations

Chris Wilcox, Michelle Mills Strout, James M. Bieman

Research output: Contribution to journalArticlepeer-review


Scientific programmers can improve the performance of function evaluation by precomputing and storing results in a lookup table (LUT), thereby replacing costly evaluation code with an inexpensive memory access. A code transformation that replaces computation with LUT code can improve performance; however, accuracy is reduced because of error inherent in reconstructing values from LUT data. LUTs are commonly used to approximate expensive elementary functions. The current practice is for software developers to: (i) manually identify expressions that can benefit from an LUT; (ii) modify the code by hand to implement the LUT transformation; and (iii) run experiments to determine if the resulting error is within application requirements. This approach reduces productivity, obfuscates code, and limits programmer control over accuracy and performance. We propose source code analysis and program transformation to substantially automate LUT transformations. Our approach uses a novel optimization algorithm that selects Pareto optimal sets of expressions that benefit most from an LUT, on the basis of the error and performance estimates. We demonstrate our methodology with the Mesa tool, which achieves speedups of 1.4-6.8× on scientific codes with an acceptable loss of accuracy. Our tool makes the programmer more productive and facilitates finding effective LUT transformations.

Original languageEnglish (US)
Pages (from-to)533-551
Number of pages19
JournalJournal of software: Evolution and Process
Issue number6
StatePublished - Jun 2014
Externally publishedYes


  • code generation
  • error analysis
  • lookup table
  • memoization
  • performance optimization
  • scientific computing

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'An optimization-based approach to lookup table program transformations'. Together they form a unique fingerprint.

Cite this