Efficient Polymorphic Calls Book

	Foreword	xi
	Preface	xv
	Acknowledgments	xvii
1	Introduction	1
1.1	Polymorphism	2
1.2	Inheritance	4
1.3	Problem statement	5
1.4	Overview	6
2	Polymorphic calls	7
2.1	Basic construct	7
2.2	Hand-crafted polymorphism	8
2.3	Object-oriented message dispatch	9
3	Software techniques for efficient polymorphic calls	15
3.1	Basic message dispatch in object-oriented languages	15
3.2	Dynamic techniques	18
3.3	Static techniques	21
3.4	Memory cost	27
3.5	Programming environment aspects	31
3.6	Summary	32
4	Row displacement compression of message dispatch tables	33
4.1	Class-based row displacement	34
4.2	Selector-based row displacement	35
4.3	Compression results	43
4.4	Optimizing table compression speed	47
4.5	Interactive programming environments	52
4.6	Summary	53
5	Analysis of dispatch sequences on modern processor architectures	55
5.1	Parameters influencing performance	55
5.2	Dispatch cost calculation	57
5.3	Cost of dynamic typing and multiple inheritance	62
5.4	Influence of processor implementation	62
5.5	Limitations	66
5.6	Summary	67
6	Measurement of virtual function call overhead on modern processors	69
6.1	Virtual function tables and the thunk variant	69
6.2	Superscalar processors	71
6.3	Method	75
6.4	Results	80
6.5	Discussion	94
6.6	Summary	95
7	Hardware techniques	97
7.1	Software vs. hardware prediction	97
7.2	Hardware indirect branch prediction	99
7.3	Indirect branch frequency	99
7.4	Experimental setup	104
7.5	Problem statement	105
8	Basic indirect branch predictors	107
8.1	Branch target buffer	107
8.2	Two-level predictor	108
8.3	History buffers	114
8.4	History tables	116
8.5	Summary	122
9	Hybrid indirect branch predictors	125
9.1	Hybrid prediction	125
9.2	Branch classification	127
9.3	Dual-path hybrid prediction	135
9.4	Cascaded prediction	141
9.5	Summary	163
10	Related work	165
10.1	Software techniques	165
10.2	Polymorphic calls in Java	171
10.3	Hardware techniques	171
11	Conclusions	177
12	Glossary	179
13	References	183
Appendix A	Polymorphic call sequences in assembly	193
Appendix B	Indirect branch execution intervals	201
Appendix C	Basic prediction accuracy per benchmark	207
	Index	211