Partial Evaluation for Software Engineering
by Renaud Marlet, Scott Thibault and Charles Consel
Software architectures promote flexibility at the expense of performance
overhead. The COMPOSE project at IRISA/INRIA Rennes has developed automatic
program transformation techniques and tools to systematically improve efficiency
while retaining genericity, safety, and adaptability.
Software architectures express how systems should be built from various
interacting components. As the size and complexity of software systems
increase, the choice of software architectures becomes a major issue, impacting
on time-to-market as well as development cost, validation, and maintenance.
Software architectures are designed to be flexible, including aspects
such as genericity, extensibility, adaptability. But flexibility impairs
efficiency because it is usually not only present at the design level but
also in the implementation. Whereas efficiency requires tight integration
of components, flexibility calls for greater separation.
Commonly used manual optimizations are ad hoc, tedious, error prone,
and unpredictable; they do not scale up and defeat the purposes of software
engineering. Other approaches, aiming generating and efficiently composing
building blocks, are specific to architectures and component domains, and
do not fully exploit all integration opportunities.
We propose a systematic method to improve the efficiency of software
architectures: program specialization. This is a general program transformation
that exploits information available prior to execution (such as known input
values) yielding a specialized program where all computations depending
on known information are being performed early. The specialized program
is thus faster (due to less computation) while semantically equivalent
to the original program. In particular, program specialization can exploit
the gluing information and the parameterization of software components
in order to better integrate them. It is not specific to a particular software
architecture style.
Partial evaluation is the technique that automates program specialization.
Therefore it does not conflict with software engineering purposes. We have
shown that partial evaluation can improve the performance of a wide range
of software architectures and mechanisms:
- In the selective broadcast (a.k.a. implicit invocation) architecture,
components are independent agents that interact with each other by subscribing
to certain types of events and sending broadcast messages. Specializing
with respect to a subscription converts broadcasting into mere explicit
calls to registered agents. Also, the selection and decoding of message
arguments may rely on a pattern matching mechanism. Specializing the pattern
matcher and the decoder with respect to the selection pattern generates
efficient automata-like routines.
- Software layers provide services to the layers above and act as a client
to the layer below. An example is Sun's implementation of the Remote Procedure
Call (RPC) protocol. Specializing the process of encoding data to a network-independent
representation results in bare memory transfers, with speedups up to 3.7.
- Scripting languages glue together powerful components (building blocks)
written in traditional programming languages. For flexibility and simplicity,
they are often interpreted. Specializing an interpreter with respect to
the script yields a fast compiled-like version of the script. Typical speedups
range from 10 to 100. We have a framework to apply this to Domain-Specific
Languages; it has been successfully put into practice for the automatic
generation of safe and efficient video card drivers.
- Tests for options in generic libraries can be evaluated by partial
evaluation when these options are known early. Furthermore, such libraries
often include validity tests (including bound checking) of complex data
structures. Specializing with respect to the shape of the structure (as
opposed to the actual content) eliminates verifications: the safety interface
layer is compiled away.
Partial evaluation can also be performed at run time, thus allowing
dynamic software reconfiguration. Furthermore, the program analysis embedded
in the partial evaluation process ensures predictability as the user can
assess the degree of specialization.
All of the above experiments have been performed using Tempo, a partial
evaluator for C developed in our group. Tempo has been applied in various
other domains such as operating systems, networking, graphics, and scientific
computation. Besides C, Tempo is used as a back-end for specializing Java
programs using Harissa, a bytecode-to-C compiler that we have also developed.
Similarly, Fortran and C++ programs have been specialized using translators
to C.
Our goal is to relieve the programmer of efficiency concerns, letting
him concentrate on the functionalities to implement in generic and high-level
way. To this end, partial evaluation provides a systematic and automatic
means to improve performance while retaining flexibility. Other uses of
partial evaluation in software engineering include program understanding.
For more information, see: http://www.irisa.fr/compose
Please contact:
Renaud Marlet - INRIA/IRISA
Tel: +33 2 99 84 75 01
E-mail: marlet@irisa.fr
