Efficient Polymorphic Calls / Edition 1

by Karel Driesen

Overview

The implementation of object-oriented languages has been an active topic of research since the 1960s when the first Simula compiler was written. The topic received renewed interest in the early 1980s with the growing popularity of object-oriented programming languages such as c++ and Smalltalk, and got another boost with the advent of Java. Polymorphic calls are at the heart of object-oriented languages, and even the first implementation of Simula-67 contained their classic implementation via virtual function tables. In fact, virtual function tables predate even Simula-for example, Ivan Sutherland's Sketchpad drawing editor employed very similar structures in 1960. Similarly, during the 1970s and 1980s the implementers of Smalltalk systems spent considerable efforts on implementing polymorphic calls for this dynamically typed language where virtual function tables could not be used. Given this long history of research into the implementation of polymorphic calls, and the relatively mature standing it achieved over time, why, one might ask, should there be a new book in this field? The answer is simple. Both software and hardware have changed considerably in recent years, to the point where many assumptions underlying the original work in this field are no longer true. In particular, virtual function tables are no longer sufficient to implement polymorphic calls even for statically typed languages; for example, Java's interface calls cannot be implemented this way. Furthermore, today's processors are deeply pipelined and can execute instructions out-of­ order, making it difficult to predict the execution time of even simple code sequences.

Product Details

ISBN-13:	9780792372899
Publisher:	Springer US
Publication date:	02/28/2001
Series:	The Springer International Series in Engineering and Computer Science , #596
Edition description:	2001
Pages:	216
Product dimensions:	6.10(w) x 9.25(h) x 0.36(d)

Table of Contents

1 Introduction.- 1.1 Polymorphism.- 1.2 Inheritance.- 1.3 Problem statement.- 1.4 Overview.- 2 Polymorphic calls.- 2.1 Basic construct.- 2.2 Hand-crafted polymorphism.- 2.3 Object-oriented message dispatch.- 3 Software techniques for efficient polymorphic calls.- 3.1 Basic message dispatch in object-oriented languages.- 3.2 Dynamic techniques.- 3.3 Static techniques.- 3.4 Memory cost.- 3.5 Programming environment aspects.- 3.6 Summary.- 4 Row displacement compression of message dispatch tables.- 4.1 Class-based row displacement.- 4.2 Selector-based row displacement.- 4.3 Compression results.- 4.4 Optimizing table compression speed.- 4.5 interactive programming environments.- 4.6 Summary.- 5 Analysis of dispatch sequences on modern processor architectures.- 5.1 Parameters influencing performance.- 5.2 Dispatch cost calculation.- 5.3 Cost of dynamic typing and multiple inheritance.- 5.4 Influence of processor implementation.- 5.5 Limitations.- 5.6 Summary.- 6 Measurement of virtual function call overhead on modern processors.- 6.1 Virtual function tables and the thunk variant.- 6.2 Superscalar processors.- 6.3 Method.- 6.4 Results.- 6.5 Discussion.- 6.6 Summary.- 7 Hardware techniques.- 7.1 Software vs. hardware prediction.- 7.2 Hardware indirect branch prediction.- 7.3 Indirect branch frequency.- 7.4 Experimental setup.- 7.5 Problem statement.- 8 Basic indirect branch predictors.- 8.1 Branch target buffer.- 8.2 Two-level predictor.- 8.3 History buffers.- 8.4 history tables.- 8.5 Summary.- 9 Hybrid indirect branch predictors.- 9.1 Hybrid prediction.- 9.2 Branch classification.- 9.3 Dual-path hybrid prediction.- 9.4 Cascaded prediction.- 9.5 Summary.- 10 Related work.- 10.1 Software techniques.- 10.2 Polymorphic calls in Java.- 10.3 Hardware techniques.- 11 Conclusions.- 12 Glossary.- 13 References.- Appendix A Polymorphic call sequences in assembly.- Appendix B Indirect branch execution intervals.- Appendix C Basic prediction accuracy per benchmark.

Editorial Reviews

The programming language constructs called polymorphic calls lie at the heart of increasingly popular object-oriented computer languages such as C++, Java, and Smalltalk. The good news is that they allow for flexible construction of code design unlike procedural computer code that permits only one possible target subroutine. The bad news is that such flexibility requires extra instructions. Driesen (McGill U.), an advocate for object-oriented code becoming the norm, surveys the standard implementation approaches and explains hardware and software techniques for minimizing the run-time cost of polymorphic calls. This update of a doctoral dissertation in computer science (U. of Santa Barbara, 1999) includes a glossary of terms, 112 figures and tables, and appended material. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews