Software and Hardware Techniques for Efficient Polymorphic Calls

Object-oriented code looks different from procedural code. The main differenceis the increased frequency of polymorphic calls. A polymorphic call looks likea procedural call, but where a procedural call has only one possible targetsubroutine, a polymorphic call can result in the execution of one of severaldifferent subroutines. The choice is made at run time, and depends on the typeof the receiving object (the first argument). Polymorphic calls enable theconstruction of clean, modular code design. They allow the programmer toinvoke operations on an object without knowing its exact type in advance.This flexibility incurs an overhead: in general, polymorphic calls must beresolved at run time. The overhead of this run time polymorphic call resolutioncan lead a programmer to sacrifice clarity of design for more efficient code,by replacing instances of polymorphic calls by several single-target proceduralcalls, removing run time polymorphism. This practice typically leads to a morerigid program structure and code duplication, increasing the short term effortrequired to build a functional prototype, and the long term effort ofmaintaining and adapting a program to changing needs.We study techniques to minimize the run-time cost of polymorphic calls. In thesoftware domain, we minimize the memory overhead of table based implementations(message dispatch tables), which are most efficient in terms of number ofinstructions executed. In the hardware domain, we reduce the cycle cost ofthese instructions through indirect branch prediction. For reasonabletransistor budgets, hit rates of more than 95% can be achieved. As a result,only one out of twenty polymorphic calls incurs significant cost at run time.Design of clear, maintainable and reusable code, as enabled by object-orientedtechnology, can thereby become less restrained by efficiency considerations.Only in very time-critical program segments should the programmer avoid the useof polymorphism. In other words, object-oriented code can become the normrather than the exception. From our own experience in building softwarearchitectures, we consider this a Good Thing.