Efficient message dispatch in object-oriented systems

ABSTRACT

Single dispatch involves performing at run-time a multi-way switch over the possible classes of the receiver. Most object-oriented systems implement this switch as an array lookup using a table-based technique or as a binary search using a tree-based technique. However, each of these is the best choice only under a particular circumstance; neither outperforms the other under all circumstances. In this paper, we present a time and space efficient implementation of the switch that employs the table-based technique when an array lookup outperforms a binary search and the tree-based technique when a binary search outperforms an array lookup. Further, when neither an array lookup nor a binary search is superior, our scheme blends the two techniques in a manner that gains the benefits of both without suffering the disadvantages of either. We relate our scheme to recent work and discuss extending it to implement multiple dispatch.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Theory

Keywords:
implementation, message dispatch, multiple dispatch, object-oriented programming, single dispatch