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.