Deng-Jyi Chen, Shih-Kun Huang, Wu-Chi Chen
and Pao-Hsu Shih*
Computer Science and Information Engineering Department
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.
*Technology Research Division
Institute for Information Industry
In object-oriented systems, heavy message sending with a large number of method lookups has slowed down program execution. Most current solutions to this problem are based on the table of message selector in a class-hierarchy for developing more efficient lookup algorithms. In this paper, we propose a new run-time dispatch technique, Bitmap Check Dispatching(BCD), organized as chains of message selectors. It is based on the message protocols which are concentrated in the message interfaces rather than in a conventional class-hierarchy. Judging from our observations and performance analysis, the BCD approach is more cost-effective, in terms of speed and space, than any other existing run time dispatch mechanism. Furthermore, the BCD approach can be improved by the graph coloring algorithm in reducing the size of the bitmap. Several case studies are presented, and the performance of the BCD approach is compared with that of existing run time dispatchers.
Keywords: object oriented programming, message sending, message interface dynamic binding, inheritance, class hierarchy
Received April 20, 1993; revised July 19, 1995.
Communicated by Y. S. Kuo.
*An earlier version of this paper was presented at the internation conference on computer software and application CompSac 92, Chicago, Sep., 1992.
This works was supported in part by the National Science Council of thte R.O.C.