Efficient message dispatch in object-oriented systems

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.