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.