Intercepting Functions for Memoization: A Case Study Using Transcendental Functions

International audienceMemoization is the technique of saving result of executions so that future executions can be omitted when the input set repeats. Memoization has been proposed in previous literature at the instruction level, basic block level and function level using hardware as well as pure software level approaches including changes to programming language.In this paper, we focus on software memoization for procedural languages like C and Fortran, at the granularity of a function. We propose a simple linker based technique for enabling software memoization of any dynamically linked pure function by function interception and we illustrate our framework using a set of computationally expensive pure functions – the transcendental functions. The transcendental functions are those which cannot be expressed in terms of a finite sequence of algebraic operations (like trigonometric functions, exponential function etc.) and hence are computationally expensive.Our technique does not need the availability of source code and thus can even be applied to commercial applications as well as applications with legacy codes. As far as users are concerned, enabling memoization is as simple as setting an environment variable. Our framework does not make any specific assumptions about the underlying architecture or compiler tool-chains, and can work with a variety of current architectures. We present experimental results for x86-64 platform using both gcc and icc compiler tool-chains, and for ARM cortex-A9 platform using gcc. Our experiments include a mix of real world programs and standard benchmark suites: SPEC and Splash2x. On standard benchmark applications that extensively call the transcendental functions we report memoization benefits of upto 50% on Intel Ivy bridge and upto 10% on ARM Cortex-A9.Memoization was also able to regain a performance loss of 76% in bwaves due to a known performance bug in the GNU implementation of pow function. The same benchmark on ARM Cortex-A9 benefited by more than 200%