Method Cache

Now, searching at run-time is expensive, much more expensive than the two assembly language instructions we identified in the technique used by the virtual method table approach. In order to avoid the high cost of this search, a method cache can be used to hold the most recently invoked methods. This cache is used in the fashion of a large hash table. Prior to beginning the search, the message selector is hashed, and the entry in the table is examined. If it matches the message selector, it is selected, otherwise the previously described run-time search will be performed and the cache will be updated.

Assuming a good hash function is used, cache hits in excess of 90% have been reported. That is, the search is performed for a method only about 10% of the times a message is sent.

[audio] [real] Text to accompany slide12, in Chapter 21 of An Introduction to Object-Oriented Programming