Coloring, a Versatile Technique for Implementing Object-Oriented Languages

Roland Ducournau 1
1 MAREL - Models And Reuse Engineering, Languages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Late binding and subtyping create run-time overhead for object-oriented languages. Dynamic typing and multiple inheritance create even more overhead. Static typing and single inheritance lead to two major invariants, of reference and position, that make the implementation as efficient as possible. Coloring is a technique that preserves these invariants for dynamic typing or multiple inheritance at minimal spatial cost. Coloring has been independently proposed for method invocation under the name of /selector coloring/, for subtype tests under the name of /pack encoding/, and for attribute access and object layout. This paper reviews a number of uses of coloring for optimizing object-oriented programming, generalizes them, and specifies several variations, such as bidirectional and /n/-directional coloring. Coloring is NP-hard, hence compilers that use it depend on heuristics. The paper describes two families of heuristics and presents some experimental results which indicate that coloring is both efficient and tractable and that bidirectional coloring gives the best results.
Type de document :
Article dans une revue
Software: Practice and Experience, Wiley, 2011, 41 (6), pp.627-659
Liste complète des métadonnées
Contributeur : Martine Peridier <>
Soumis le : lundi 30 mai 2011 - 11:28:32
Dernière modification le : jeudi 24 mai 2018 - 15:59:22


  • HAL Id : lirmm-00596802, version 1



Roland Ducournau. Coloring, a Versatile Technique for Implementing Object-Oriented Languages. Software: Practice and Experience, Wiley, 2011, 41 (6), pp.627-659. 〈lirmm-00596802〉



Consultations de la notice