Reducing indirect function call overhead in C++ programs

ABSTRACT

Modern computer architectures increasingly depend on mechanisms that estimate future control flow decisions to increase performance. Mechanisms such as speculative execution and prefetching are becoming standard architectural mechanisms that rely on control flow prediction to prefetch and speculatively execute future instructions. At the same time, computer programmers are increasingly turning to object-oriented languages to increase their productivity. These languages commonly use run time dispatching to implement object polymorphism. Dispatching is usually implemented using an indirect function call, which presents challenges to existing control flow prediction techniques. We have measured the occurrence of indirect function calls in a collection of C++ programs. We show that, although it is more important to predict branches accurately, indirect call prediction is also an important factor in some programs and will grow in importance with the growth of object-oriented programming. We examine the improvement offered by compile-time optimizations and static and dynamic prediction techniques, and demonstrate how compilers can use existing branch prediction mechanisms to improve performance in C++ programs. Using these methods with the programs we examined, the number of instructions between mispredicted breaks in control can be doubled on existing computers.

REFERENCES

• 1: Robert Alverson , David Callahan , Daniel Cummings , Brian Koblenz , Allan Porterfield , Burton Smith, The Tera computer system, Proceedings of the 4th international conference on Supercomputing, p.1-6, June 11-15, 1990, Amsterdam, The Netherlands
• 2: Thomas Ball , James R. Larus, Branch prediction for free, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.300-313, June 21-25, 1993, Albuquerque, New Mexico, United States
• 3: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.59-70, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143180]
• 4: Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990 [doi>10.1145/78969.78963]
• 5: Brad Calder and Dirk Grunwald. Branch alignment. Technical Report (In Preperation), Univ. of Colorado- Boulder, 1993.
• 6: Brad Calder and Dirk Grunwald. Fast & accurate instruction fetch and branch prediction. CU-CS xxx, Univ. of Colorado, October 1993. (in preperation).
• 7: Brad Calder, Dirk Grunwald, and Benjamin Zorn. Exploiting behavioral differences between C and C++ programs. Technical Report (In Preperation), Univ. of Colorado-Boulder, 1993.
• 8: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
• 9: Craig Chambers , David Ungar, Interactive type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.150-164, June 1990, White Plains, New York, United States
• 10: Jack W. Davidson , Anne M. Holler, Subprogram Inlining: A Study of its Effects on Program Execution Time, IEEE Transactions on Software Engineering, v.18 n.2, p.89-102, February 1992 [doi>10.1109/32.121752 ]
• 11: Jack W. Davidson , David B. Whalley, Reducing the cost of branches by using registers, Proceedings of the 17th annual international symposium on Computer Architecture, p.182-191, May 28-31, 1990, Seattle, Washington, United States
• 12: Joseph A. Fisher , Stefan M. Freudenberger, Predicting conditional branch directions from previous runs of a program, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.85-95, October 12-15, 1992, Boston, Massachusetts, United States
• 13: Mary W. Hall , Ken Kennedy, Efficient call graph analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.227-242, Sept. 1992 [doi>10.1145/151640.151643]
• 14: Urs Hölzle , Craig Chambers , David Ungar, Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches, Proceedings of the European Conference on Object-Oriented Programming, p.21-38, July 15-19, 1991
• 15: David R. Kaeli , Philip G. Emma, Branch history table prediction of moving target branches due to subroutine returns, Proceedings of the 18th annual international symposium on Computer architecture, p.34-42, May 27-30, 1991, Toronto, Ontario, Canada
• 16: Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.46-57, May 19-21, 1992, Queensland, Australia
• 17: Johnny K. F. Lee and Alan Jay Smith. Branch prediction strategies and branch target buffer design. IEEE Computer, pages 6-22, January 1984.
• 18: David J. Lilja, Reducing the Branch Penalty in Pipelined Processors, Computer, v.21 n.7, p.47-55, July 1988 [doi>10.1109/2.68 ]
• 19: Michael D. Smith , Mark Horowitz , Monica S. Lam, Efficient superscalar performance through boosting, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.248-259, October 12-15, 1992, Boston, Massachusetts, United States
• 20: S. McFarling , J. Hennesey, Reducing the cost of branches, Proceedings of the 13th annual international symposium on Computer architecture, p.396-403, June 02-05, 1986, Tokyo, Japan
• 21: Shien-Tai Pan , Kimming So , Joseph T. Rahmeh, Improving the accuracy of dynamic branch prediction using branch correlation, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.76-84, October 12-15, 1992, Boston, Massachusetts, United States
• 22: Hemant D. Pande and Barbera G. Ryder. Static type determination for C++. Technical Report LCSR-TR- 197, Rutgers Univ., February 1993.
• 23: C. H. Perleberg , A. J. Smith, Branch Target Buffer Design and Optimization, IEEE Transactions on Computers, v.42 n.4, p.396-412, April 1993 [doi>10.1109/12.214687 ]
• 24: Barbera G. Ryder. Constructing the call graph of a program. IEEE Transactions on Software Engineering, SE-5(3):216-226, May 1979.
• 25: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 26: David W. Wall, Limits of instruction-level parallelism, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.176-188, April 08-11, 1991, Santa Clara, California, United States
• 27: Tse-Yu Yeh , Yale N. Patt, Alternative implementations of two-level adaptive branch prediction, Proceedings of the 19th annual international symposium on Computer architecture, p.124-134, May 19-21, 1992, Queensland, Australia
• 28: Tse-Yu Yeh , Yale N. Patt, A comprehensive instruction fetch mechanism for a processor supporting speculative execution, Proceedings of the 25th annual international symposium on Microarchitecture, p.129-139, December 01-04, 1992, Portland, Oregon, United States
• 29: Tse-Yu Yeh , Yale N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, Proceedings of the 20th annual international symposium on Computer architecture, p.257-266, May 16-19, 1993, San Diego, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Measurement, Performance, Theory

Keywords:
customization, object oriented programming, optimization, profile-based optimization