Efficient Polymorphic Calls

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.