Efficient Multiple and Predicate Dispatching
Craig
Chambers and Weimin Chen
The speed of message dispatching is an important issue in the overall
performance of object-oriented programs. We have developed an
algorithm for constructing efficient dispatch functions that combines
novel algorithms for efficient single dispatching, multiple
dispatching, and predicate dispatching. Our algorithm first reduces
methods written in the general predicate dispatching model (which
generalizes single dispatching, multiple dispatching, predicate
classes and classifiers, and pattern-matching) into ones written using
a simpler multimethod dispatching model. Our algorithm then computes
a strategy for implementing multiple dispatching in terms of sequences
of single dispatches, representing the strategy as a lookup
DAG. Finally, our algorithm computes an implementation strategy
separately for each of the single dispatches, producing for each
dispatch a dispatch tree, which is a binary decision tree
blending class identity tests, class range tests, and table lookups.
Our algorithm exploits any available static information (from type
declarations or class analysis) to prune unreachable paths from the
lookup DAG, and uses any available dynamic profile information to
minimize the expected time to search the dispatch trees. We measure
the effectiveness of our dispatching algorithms on a collection of
large Cecil programs, compiled by the Vortex optimizing compiler,
showing improvements of up to 30% over already heavily optimized
baseline versions.
Published in the proceedings of OOPSLA'99, Denver, CO,
November, 1999.
To get the PostScript file, click
here.
Cecil/Vortex
Project