The importance of improving the performance of the marshalling function has been widely recognized:

• Dave Clark, MIT: "Presentation will be the problem layer of the 90's" (Tutorial "Protocol Performance", Sigcomm '94)
• Craig Partidge, BBN: "The problem of efficient (external data) format conversion is far from solved" ("Gigabit Networking", p. 343).
• July '94 ARPA/NSF Workshop on Research in Gigabit Networking: "Better mechanisms for fast data conversion are needed"

For my Ph.D. thesis, I investigated compiler optimization algorithms for the marshalling or presentation conversion code in communication software. Marshalling or data representation conversion is a key component in many distributed applications (e.g. applications using RPC-based systems such as Sun's ONC, CORBA , OSF/DCE or Microsoft's Distributed OLE).

The marshalling code in today's distributed applications is usually generated automatically by a stub compiler. These compilers often generate inefficient code which leads to performance problems. Marshalling may require executing several thousands of CPU instructions per message transfer. In contrast, recent optimized transport protocol implementations execute only a few hundered CPU instructions per message. For example, Van Jacobson showed that TCP receive packet processing requires only about 33 Sparc CPU instructions. (Jacobson explains this also in an Mbone talk (on the Media on Demand server )).

Analysis of the code generated by stub compilers reveals that the code is often overly general. Consequently, the overhead of marshalling can often be reduced by a factor of 10 when specialized "fast path" marshalling code is added by hand. I investigated algorithms that can replace this manual optimisation of marshalling routines by an automatic optimisation stage in the stub generator.

Automatic generation of fast path marshalling code by a stub compiler requires solving two problems:

• Finding the fast path. This requires determining the execution frequency of the individual paths through the marshalling code. Depending on the exact problem, this is best done by using user annotation, control flow analysis or profile information.
• Deciding when to stop generating fast path code. The optimisation of marshalling code is based on increasing the object code size in order to reduce execution time. This can lead to an explosive growth in the object code size, if we do not control the generation of the fast path code. Control can be achieved by using a mathematical optimization model and algorithm.

Practical experiments and implementation are undertaken using the ASN.1 compiler MAVROS developed at INRIA-Rodeo by Christian Huitema . According to performance measurements for Mavros , the generated marshalling code is much faster than code generated by many other ASN.1 compilers. Mavros is available free of charge to research institutions.

USC is a tool for a restricted subset of C which was developed at the University of Arizona under the direction of Sean O'Malley . USC is available via ftp .

Work on implementing efficient decoders for the ASN.1's Basic Encoding Rules is also ongoing at Harvard University. They developed a prototype which uses run time code generation and optmization.

Compact and Efficient Presentation Conversion Code

Published in "IEEE/ACM Transactions on Networking"
[Postscript]
[PDF]

Automating Performance Optimisation by Heuristic Analysis of a Formal Specification (uncompressed postscript)

Describes design and implementation of an optimizer for an ASN.1 stub compiler.

In: Reinhard Gotzhein, Jan Bredereke "Formal Description Techniques IX", Kaiserslautern, Germany. London: Chapman & Hall, 1996, 77-92.

Thesis talk slides (uncompressed postscript, PDF format)

A Compiler-Based Approach to Protocol Optimization (html version)

Shows how to automate fast path prediction to optimize TCP. The slides contain more details.

Proceedings "Third IEEE Workshop on the Architecture and Implementation of High Performance Communication Subsystems", Mystic, Conneticut, Aug. 23-25 1995, (with Claude Castelluccia )
Postscript Version

Automatic Generation of Optimized Code for Marshalling Routines

Shows how to arrive at fast marshalling code without an excessive code size overhead by combining compiled and interpreted code

In: Manuel Medina, Nathaniel Borenstein (Ed.), IFIP TC6/WG6.5 International Working Conference on Upper Layer Protocols, Architectures and Applications, Barcelona. Amsterdam: North-Holland, 1994, 131-146, (with Christian Huitema )
Abstract+Bibtex
Slides

Control Flow Graph Analysis for Automatic Fast Path Implementation

Presents an approach for optimizing communication software inspired by a compiler optimization technique called program based branch prediction.

Proceedings "Second IEEE Workshop on the Architecture and Implementation of High Performance Communication Subsystems", Williamsburg, Virginia, Sep. 1-3 1993, (with Christian Huitema ).
Abstract+Bibtex
Slides

Using Control Flow Analysis for Space and Time Efficient Stub Generation

Extended version of HPCS paper, containing first version of analysis algorithm and measurement results.

Internal report, September 1993.
Abstract+Bibtex

Towards Tailoring Protocols to Application Specific Requirements

Shows how to write application-specific protocol configurations using ASN.1 subtyping.

Infocom 93 Proceedings, Volume 2. Los Alamitos: IEEE Computer Society Press, 1993, 647-653.
Abstract+Bibtex
Slides

A Programming Environment for Distributed Applications Based on OSI Application Services (html version)

Presents idea to use an expert system for configuring an application specific protocol from a set of building blocks, and for optimising the configuration. Some of these ideas have made it into the HIPPARCH project.

Thesis proposal, Sophia Antipolis, 1992.
Postscript

Use of ASN.1 for remote procedure call interfaces

A few slides on how ASN.1 is used in RPC applications, the network data representations used with ASN.1, and performance.

Interop Europe, Paris, October 1993.

Copyright © 1994, 1995, 1996 Philipp Hoschka