Memoization is the technique of saving result of executions so that future executions can be omitted when the inputs repeat. 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.
Principle
We proposed software memoization of pure functions for procedural languages. We rely on the operating system loader, taking advantage of the LD_PRELOAD feature of UNIX systems. By setting this variable to the path of a shared library, we instruct the loader to first look to missing symbols in that library. Our library redefines the functions we wish to intercept. The interception code is very straightforward (see also the algorithm below): it receives the same parameter as the target function and checks in a table (a software cache) if this value is readily available. In the favorable case, the result value is immediately returned. Otherwise, we invoke the original function, and store the result in the cache before returning it.
The table is of limited size and it is implemented as a cache. Older values may be evicted by newer values. The input parameter serves as a tag to guarantee the validity of the accessed data. The table is indexed through a simple yet efficient hash function: we repeatedly XOR the most and least significant bits of the parameter value until we reach the necessary bit-width. For parameters of type double (64 bits) and a 64k-entry table, two XOR operations are enough. For smaller tables, we simply mask the higher bits.
Our technique does not require the availability of source code and thus can be applied even 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. We validated If-memo with x86-64 platform using both GCC and icc compiler tool-chains, and ARM cortex-A9 platform using GCC.
double sin(double x)
{
idx = hash(x);
if (table[idx].tag) != x) {
table[idx].tag = x;
table[idx].val = real_sin(x);
}
return table[idx].val;
}
Interception pseudo-code, example for function sin
Publications
- Suresh, Arjun, et al. “Intercepting functions for memoization: A case study using transcendental functions.” ACM Transactions on Architecture and Code Optimization (TACO) 12.2 (2015): 18.
- Suresh, Arjun, Erven Rohou, and André Seznec. “Compile-time function memoization.” Proceedings of the 26th International Conference on Compiler Construction. ACM, 2017.
Download
If-memo is freely available from the Inria Gitlab: https://gitlab.inria.fr/rohou/if-memo/
Credits and Legal
If-memo is proposed by the PACAP project team at Inria Rennes Bretagne Atlantique. The authors are Arjun Suresh and Erven Rohou.
If-memo is registered at the APP (Agence de Protection des Programmes) under number IDDN.FR.001.250013.000.S.P.2015.000.10800.
