Message Dispatch on Modern Computer Architectures

Object-oriented systems must implement message dispatch efficiently in ordernot to penalize the object-oriented programming style. We characterize theperformance of most previously published dispatch techniques for bothstatically- and dynamically-typed languages with both single and multipleinheritance. Hardware organization (in particular, branch latency andsuperscalar instruction issue) significantly impacts dispatch performance. Forexample, inline caching may outperform c++-style \"vtables\" on deeply pipelinedprocessors even though it executes more instructions per dispatch.We also show that adding support for dynamic typing or multiple inheritancedoes not significantly impact dispatch speed for most techniques, especially onsuperscalar machines. Also, instruction space overhead (calling sequences) canexceed the space cost of data structures (dispatch tables), so that minimaltable size may not imply minimal run-time space usage.