Reducing Indirect Function CallOverhead In C++ ProgramsBrad Calder and Dirk Grunwald(Email:{calder, grunwald}(?cs. colorado. edu)Department of Computer Science,Campus Box 430, University of Colorado,Boulder, CO 80309-0430AbstractModern computer architectures increasingly depend onmechanisms that estimate fhture control flow decisionsto increase performance. Mechanisms such asspeculativeexecutionand prefetching are becoming standard architec-tural mechanisms that rely oncontrol flow prediction toprefetch and speculatively execute future instructions. Atthe same time, computer programmers are increasinglyturning to object-oriented languages to increase their pro-ductivity. These languages commonly userun time dis-patching toimplement object polymorphism. Dispatch-ing is usually implemented using an indirect finction call,which presents challenges to existing control flow predic-tion techniques.We have measured the occurrence of indirect functioncalls in a collection of C++ programs. We show that, al-though it is more important to predict branches accurately,indirect call prediction is also an important factor in someprograms and will grow in importance with the growth ofobject-oriented programming. We examine the improve-ment offered by compile-time optimization and static anddynamic prediction techniques, and demonstrate how com-pilers can use existing branch prediction mechanisms toimprove performance in C++ programs. Using these meth-ods with the programs we examined, the number of in-structions between mispredicted breaks in control can bedoubled on existing computers.Keywords: Object oriented programming, optimization,profile-based optimization, customization1IntroductionThe design of computer architectures and languages aretightly entwined. For example, the advent of register dis-placement addressing enabled efficient implementation ofPerrnksion to copy without fee ell or part of this material isgranted provided that the copies sro not made or distributed fordirect commercial advsntage, the ACM copyright notice and thetitle of the publication end its date appaar, and notice is giventhet copying is by permission of the Association for ComputingMachinery. To copy otherwise, or to republish, requiras a feaand/or specific permission.POPL 94- 1/94, Portland Oregon, USA~ 1994 ACM o-89791 -636-9/04~1 ..$3.s0Algol and the increased use of COBOL emphasized the useof BCD arithmetic. Likewise, the C and FORTRAN lan-guages have become ubiquitous, strongly influenced RISCprocessor design. Object-oriented programming has re-cently gained popularity, illustrated by the wide-spreadpopularity of C++. Object-oriented languages exercise dif-ferent aspects of computer architectures to support theobject-oriented programming style. In this paper, we ex-amine how indirect fi.mction calls, used to support objectpolymorphism, influence the pefiormance of an efficientobject oriented language. Modern architectures using deepinstruction pipelines and speculative execution rely on pre-dictable control flow changes, and indirect function callscause unpredictable changes in program control flow. Forexample, the DEC Alpha AXP 21064 processor, one of thefirst widely-available deeply pipelined superscalar micro-processors, stalls for 10 instructions if the processor mis-predicts the flow of control. This increases if the mispre-dicted target is not in the instruction cache and must befetched. As systems increasingly rely on speculative exe-cution [19, 16], the importance of control flow predictionwill increase.In most programs, conditional branches introduce themain uncertainty in program flow, and architectures use avariety ofbranch prediction techniques to reduce instruc-tion cache misses and to insure instructions are availablefor the processor pipeline. Most fimction calls specifi ex-plicit call targets, and thus most fimction calls can be triv-ially predicted. Control flow prediction is just as importantin object-oriented programs, but these languages tend touse indirect finction calls, where the address of the calltarget is loaded horn memory. Fisher et al [12] said indi-rection fimction calls ”... are unavoidable breaks in controland there are few compiler or hardware tricks that couldallow instruction-level parallelism to advance past them”.By accurately predicting the calling address, the processorcan reduce instruction stalls and prefetch instructions.Our results show that accurately predicting the be-havior of indirect function calls can largely eliminate thecontrol-flow rnisprediction penalty for using static-typedobject-oriented languages such as C++. Figure 1 showsthenormalized execution time for a variety of C++ pro-grams. We measured the number of instructions executed397by each program, and collected information concerning theconditional branches and indirect fimction calls executedby each program. Although we measured the programson a DECstation-5000, we simulated the branch mispre-diction characteristics of a deeply pipelined superscalararchitecture, similar to the DEC Alpha AXP 21064.For each program, each bar indicates the number ofmachine cycles spent executing instructions and sufferingfrom the delay imposed by mispredicting control flow un-der different assumptions. A value of ’1’ indicates the pro-gram spends no additional time due to delays, while avalue of ’2’ indicates the program would execute twice asslowly. The left-most bar indicates the delay that wouldbe incurred if every control flow change was incorrectlypredicted or there was no prediction. The next bar indi-cates the increase in execution if onlyconditional branchesare predicted, using static profile based prediction. Thenext three bars indicate the decrease in execution timeif branches andindirect function calls are correctly pre-dicted, using three different techniques described in thispaper. For the programs we measured, we found we couldimprove performance 270-24% using these simple tech-niques; the final improvement depends on the numberof indirect function calls, how program libraries are usedand the underlying architecture. Architectures that havedeeper pipelines or that issue more instructions per cyclewould evince greater improvement.We are interested in reducing the cost of indirect func-tion calls (I-calls) for modern architectures. If a compilercan determine a unique or likely call target, indirect func-tion calls can be converted to direct calls for unique calltargets. Likewise, compilers may