Caching Function Results: Faster Arithmetic by Avoiding Unnecessary Computation

Abstract

This paper discusses trivial computation, where simple operands trivialize potentially complex operations. An example of a trivial operation is integer division, where the divisor is two; the division becomes a simple shift operation. The paper also discusses the concept of redundant computation, where some operation repeatedly does the same function because it repeatedly sees the same operands. Experiments on two separate benchmark suites, the SPEC benchmarks and the Perfect Club, find a surprisingly large amount of trivial and redundant operation. Various architectural means of exploiting this knowledge to improve computational efficiency include detection of trivial operands and the result cache. Further experimen-tation shows significant speedup from these techniques, as measured on three different styles of machine architecture.