Introduction

Presentation conversion is often been identified as "the performance problem of the 90's" in text books on high-speed networking (e.g.( Partridge, 1993), (Peterson & Davie, 1996)). The performance of automatically generated presentation conversion code often prevents applications to take advantage of the performance of high-speed networks. For example, we found that due to presentation conversion code, the throughput of a 155 Mbit/s ATM network can be reduced to 3.1 Mbit/s on the application level, corresponding to a loss in performance by a factor of fifty.

The performance of presentation conversion code can be considerably improved by increasing the size of the code, using techniques such as compilation and inlining. While stub compilers today implement these optimization techniques, their use often leads to code sizes that are unacceptable for many applications in practice.

Further analysis reveals that the code size could be largely reduced if these optimizations where only applied to the parts of the presentation conversion code that are used most often. In other words, rather than applying the same optimization technique (compilation or inlining) to all or the presentation conversion code, it should only be applied to the code parts where it is most beneficial.

This paper shows how a stub compiler can automatically decide which parts of the code are worth optimizing. It is based on three main contributions:

• It is shown that the size/speed trade-off problem in the generation of presentation conversion code can be mapped onto a Knapsack problem.
• Heuristic branch prediction rules are developed that allow determining the execution frequency of different parts of the presentation conversion code.
• Experiments show that adding an optimization stage to stub compilers is worthwhile.

The rest of this paper is structured as follows: Section 2 explains basic concepts of the implementation of presentation conversion routines. Section 3 discusses related work. Section 4 describes the design of the optimizer, including the Knapsack model and the heuristic branch prediction rules. Section 5 gives experimental results for the optimization stage. Section 6 gives our conclusions.