Home My Page Projects Function Memoization
Summary Activity SCM

Project Members
Project Information

This project has not yet categorized itself in the Trove Software Map Registered: 2016-04-26 07:56
Public Tools
SCM Repository (Subversion: 0 updates, 113 adds)
Project description

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. If-memo proposes software memoization of pure functions for procedural languages. It relies 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 for symbols in that library.

Our library redefines the functions we wish to intercept. The interception code is very straightforward: 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.