Optimizing Method Search with Lookup Caches and Incremental Coloring

Abstract

An efficient mechanism for method lookup is csscntial in any reasonable implementation of a clussbased object-oriented language.One tcchniquc, static caches, provide constant time lookup, but consumes cxcessive memory.To alleviate the memory consumption problem many systems USC a coloring schcmc that allows cache rows to be shared and thus reduces the ovcrall cache size.This technique is easily implcmcntcd I'OI stongly typed languages such as C++ and Eiffcl, but not for languages such as CLOS or Smalltalk.This papct provides a solution to this latter problem: that of coloring for static caches in dynamically typed objcct-oricnted languages.Our solution is to use an incrcmcntal coloring algorithm to avoid the memory consumption problems of the naive approach.