Data specialization
Todd B. Knoblock, Erik Ruf · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 1996
Given a repeated computation, part of whose input context remains invariant across all repetitions, program staging improves performance by separating the computation into two phases. An early phase executes only once, performing computations depending only on invariant inputs, while a late phase repeatedly performs the remainder of the work given the varying inputs and the results of the early computations.Common staging techniques based on dynamic compilation statically construct an early phase that dynamically generates object code customized for a particular input context. In effect, the results of the invariant computations are encoded as the compiled code for the late phase.This paper describes an alternative approach in which the results of early computations are encoded as a data structure, allowing both the early and late phases to be generated statically. By avoiding dynamic code manipulation, we give up some optimization opportunities in exchange for significantly lower dynamic space/time overhead and reduced implementation complexity.
Cited by 54 works. doi:10.1145/231379.231428 Open-access PDF
Authors
References
- Compilers: Principles, Techniques, and Tools
- Efficiently computing static single assignment form and the control dependence graph
- Efficient implementation of the smalltalk-80 system
- Partial evaluation and automatic program generation
- The RenderMan companion
- Threads and input/output in the synthesis kernal
- A general approach for run-time specialization and its application to C
- C: a language for high-level, efficient, and machine-independent dynamic code generation
- Fast, effective dynamic compilation
- Incremental computation via function caching