For the following discussion, we define a generic type definition
language. The language contains a set of scalar types such as integer or real
types, and the following set of type constructors: (1) A *structure*
defines a linear sequence of fields of usually different types. (2) A *
union* defines alternatives between fields of usually different type. (3) An
*array* defines a sequence of fields of the same type.

The generation of optimized presentation conversion routines starts from an
intermediate representation of the interface definition. We define the *
syntax graph* of an interface specification as a tuple *{V, E}* where
*V* is the set of nodes in the syntax graph for which an optimization
decision is required and *E* is a set of arcs representing the sequence in
which the nodes occur in the interface specification.

A syntax graph contains two different classes of nodes: *type definition
nodes* and *field nodes*. Each definition of a constructed type in the
interface specification is mapped to a type definition node in the syntax
graph. A type definition node is labeled by the type constructor of
the type definition.

A field in a constructed type is mapped to a *field node* in the syntax
graph. There are three different kinds of field nodes, which can be
distinguished by a label. A field node can be a constructed type (*
embedded type constructor* label), a reference to a pre-defined scalar type
(*scalar reference* label) or a reference to another type definition (*
type reference* label).

For formalizing the optimization problem, we define the following variables: is the total size of presentation conversion code before optimization, is the total size of presentation conversion code after optimization, is the total execution time of presentation conversion code before optimization for a given workload and is the total execution time of presentation conversion code after optimization for a given workload.

The objective of optimization is then to generate presentation conversion routines in a way that minimizes under the constraint that does not exceed a given maximal code size. We define:

- : Size of code template for type definition node
*i*before optimization. - : Size of code template for type definition node
*i*after optimization. This corresponds to the code duplication caused by the optimization. - : Time for converting values of the type definition mapped
onto node
*i*before optimization. - : Time for converting values of the type definition
mapped onto node
*i*after optimization. This corresponds to the overhead saving achieved by the optimization. - : Execution frequency of presentation conversion code for type definition
mapped onto node
*i*for a given workload. - : if node
*i*is optimized, 0 otherwise.

The size/speed trade-off occurring when generating optimized presentation conversion code
can be expressed as a *0-1 Knapsack problem* (Martello & Toth, 1990). For
this, each type definition node *i* in the syntax graph is assigned a profit and a
weight as follows:

Substituting these equations into the general definition of a Knapsack problem results in the following optimization problem:

maximize:

subject to:

It can be assumed that both the profit and the weight are positive numbers. A negative profit value corresponds to an optimization that increases the execution time, which is impossible by definition. A negative weight corresponds to an optimization that does not increase the code size. This case occurs for example when very small functions are written inline, since the number of instructions required for function linkage is higher than the number of instructions in the function body.The author of a stub compiler should avoid this by using macros definitions rather than function definitions.

For solving the 0-1 Knapsack problem, we use an approximate algorithm. The advantage over exact algorithms is that it is easy to implement. Moreover, investing much effort into making the Knapsack solution found by the algorithm accurate seems inappropriate, given that the values for weights and profits are also only approximations (see below).

First, items are sorted by their profit/weight ratio or profit per unit weight, i.e. so that

Then, items are consecutively inserted into the Knapsack in the order of this
list, until the first item *s* is encountered that does not fit.

We use a heuristic for improving this solution which is to continue going
through the list items following the critical item and including each item
that fits into the residual Knapsack capacity. This algorithm is known as *
Greedy algorithm* for finding a solution to the Knapsack problem (Martello &
Toth, 1990).

For solving the Knapsack problem, the stub compiler must have information on , , , and . All of these values can generally only be estimated. One reason for this is that the stub compiler generates code in an application programming language. Therefore, the , , , depend on the machine code generated by the application language compiler. Moreover, depends on the actual workload. Only estimates of this workload are available at the time the presentation conversion code is generated. The following two sections discuss how these parameters are estimated in our implementation.

Sun Oct 26 21:35:40 MET 1997