Minimizing dependencies within generic classes for faster and smaller programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Minimizing dependencies within generic classes for faster and smaller programs

Full text

Pdf (604 KB)

Source

Conference on Object Oriented Programming Systems Languages and Applications archive
Proceeding of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications table of contents

Orlando, Florida, USA

SESSION: Language implementations table of contents

Pages 425-444

Year of Publication: 2009

ISBN:978-1-60558-766-0

Also published in ...

Authors

Dan Tsafrir	IBM T.J. Watson Research Center, Yorktown Heights, NY, USA
Robert W. Wisniewski	IBM T.J. Watson Research Center, Yorktown Heights, NY, USA
David F. Bacon	IBM T.J. Watson Research Center, Yorktown Heights, NY, USA
Bjarne Stroustrup	Texas A&M University, College Station, TX, USA

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 25, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1640089.1640121 What is a DOI?

ABSTRACT

Generic classes can be used to improve performance by allowing compile-time polymorphism. But the applicability of compile-time polymorphism is narrower than that of runtime polymorphism, and it might bloat the object code. We advocate a programming principle whereby a generic class should be implemented in a way that minimizes the dependencies between its members (nested types, methods) and its generic type parameters. Conforming to this principle (1) reduces the bloat and (2) gives rise to a previously unconceived manner of using the language that expands the applicability of compile-time polymorphism to a wider range of problems. Our contribution is thus a programming technique that generates faster and smaller programs. We apply our ideas to GCC's STL containers and iterators, and we demonstrate notable speedups and reduction in object code size (real application runs 1.2x to 2.1x faster and STL code is 1x to 25x smaller). We conclude that standard generic APIs (like STL) should be amended to reflect the proposed principle in the interest of efficiency and compactness. Such modifications will not break old code, simply increase flexibility. Our findings apply to languages like C++, C#, and D, which realize generic programming through multiple instantiations.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Arnold, S. Fink, D. Grove, M. Hind, and P. F. Sweeney, "Adaptive optimization in the Jalape'no JVM". In 15th ACM Conf. on Object Oriented Prog. Syst. Lang. & App. (OOPSLA), pp. 47--65, 2000.
	2	M. Arnold and D. Grove, "Collecting and exploiting high-accuracy call graph profiles in virtual machines". In IEEE Int'l Symp. Code Generation & Optimization (CGO), pp. 51--62, 2005.
	3	D. F. Bacon and P. F. Sweeney, "Fast static analysis of C++ virtual function calls". In 11th ACM Conf. on Object Oriented Prog. Syst. Lang. & App. (OOPSLA), pp. 324--341, 1996.
	4	L. Bourdev and J. Jarvi, "Efficient run-time dispatching in generic programming with minimal code bloat". In Symp. on Library-Centric Software Design (LCSD), Oct 2006.
	5	W. Bright, "D programming language". http://www.digitalmars.com/d
	6	B. Calder and D. Grunwald, "Reducing indirect function call overhead in C++ programs". In 21st ACM Symp. on Principles of Prog. Lang. (POPL), pp. 397--408, 1994.
	7	B. Calder, D. Grunwald, and B. Zorn, "Quantifying behavioral differences between C and C++ programs". J. Prog. Lang. 2, pp. 313--351, 1994.
	8	M. D. Carroll and M. A. Ellis, Designing and Coding Reusable C++. Addison-Wesley, 1995.
	9	M. M. T. Chakravarty, G. Keller, S. P. Jones, and S. Marlow, "Associated types with class". In 32nd ACM Symp. on Principles of Prog. Lang. (POPL), pp. 1--13, Jan 2005.
	10	S. Chapin et al., "Benchmarks and standards for the evaluation of parallel job schedulers". In 5th Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP), pp. 67--90, Springer-Verlag, Apr 1999. Lect. Notes Comput. Sci. vol. 1659.
	11	D. Citron, G. Haber, and R. Levin, "Reducing program image size by extracting frozen code and data". In ACM Int'l Conf. on Embedded Software (EMSOFT), pp. 297--305, 2004.
	12	T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms. MIT Press, 2nd ed., 2001.
	13	D. Detlefs and O. Agesen, "Inlining of virtual methods". In European Conf. on Object-Oriented Prog. (ECOOP), pp. 258--278, 1999.
	14	A. Diwan, K. S. McKinley, and J. E. B. Moss, "Using types to analyze and optimize object-oriented programs". ACM Trans. on Prog. Lang. & Syst. (TOPLAS) 23(1), pp. 30--72, 2001.
	15	J. J. Dongarra, H. W. Meuer, H. D. Simon, and E. Strohmaier, "Top500 supercomputer sites". http://www.top500.org/
	16	C. L. Dumitrescu and I. Foster, "GangSim: A simulator for grid scheduling studies". In 5th IEEE Int'l Symp. on Cluster Comput. & the Grid (CCGrid), pp. 1151--1158 Vol. 2, 2005.
	17	A. Duret-Lutz, T. Geraud, and A. Demaille, "Design patterns for generic programming in C++". In 6th USENIX Conf. on Object-Oriented Technologies (COOTS), p. 14, 2001.
	18	M. A. Ertl, T. Wien, and D. Gregg, "Optimizing indirect branch prediction accuracy in virtual machine interpreters". In ACM Int'l Conf. Prog. Lang. Design & Impl. (PLDI), pp. 278--288, 2003.
	19	A. Ezust and P. Ezust, An Introduction to Design Patterns in C++ with Qt 4. Prentice Hall, 2006.
	20	D. G. Feitelson, "Experimental analysis of the root causes of performance evaluation results: a backfill case study". IEEE Trans. Parallel Distrib. Syst. (TPDS) 16(2), pp. 175--182, Feb 2005.
	21	D. G. Feitelson, "Metric and workload effects on computer systems evaluation". IEEE Computer 36(9), pp. 18--25, Sep 2003.
	22	J. A. Fisher and S. M. Freudenberger, "Predicting conditional branch directions from previous runs of a program". In 5th Arch. Support for Prog. Lang. & Operating Syst. (ASPLOS), pp. 85--95, 1992.
	23	E. Gamma, R. Helm, R. Johnson, and J. Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995.
	24	R. Garcia, J. J¨arvi, A. Lumsdaine, J. G. Siek, and J. Willcock, "A comparative study of language support for generic programming". In 18th ACM Conf. on Object Oriented Prog. Syst. Lang. & App. (OOPSLA), pp. 115--134, Oct 2003.
	25	R. Garcia, J. Jarvi, A. Lumsdaine, J. G. Siek, and J. Willcock, "An extended comparative study of language support for generic programming". J. Func. Prog. (JFP)) 17(2), pp. 145--205, Mar 2007.
	26	J. Gerlach and J. Kneis, "Generic programming for scientific computing in C++, Java, and C#". In 5th Advanced Parallel Processing Technologies (APPT), pp. 301--310, Sep 2003. Lect. Notes Comput. Sci. vol. 2834.
	27	N. Glew and J. Palsberg, "Type-safe method inlining". J. Sci. Comput. Program. 52(1-3), pp. 281--306, 2004.
	28	S. Gochman et al., "The Intel Pentium M processor: Microarchitecture and performance". Intel Technology Journal 7(2), May 2003.
	29	M. Hansen, "How to reduce code bloat from STL containers". C++ Report 9(1), pp. 34--41, Jan 1997.
	30	H. He, J. Trimble, S. Perianayagam, S. Debray, and G. Andrews, "Code compaction of an operating system kernel". In IEEE Int'l Symp. Code Generation & Optimization (CGO), pp. 283--298, 2007.
	31	A. Iosup, D. H. Epema, T. Tannenbaum, M. Farrellee, and M. Livny, "Inter-operating grids through delegated matchmaking". In ACM/IEEE Supercomputing (SC), pp. 1--12, 2007.
	32	K. Ishizaki, M. Kawahito, T. Yasue, H. Komatsu, and T. Nakatani, "A study of devirtualization techniques for a Java just-in-time compiler". In ACM Conf. on Object Oriented Prog. Syst. Lang. & App. (OOPSLA), pp. 294--310, 2000.
	33	J. A. Joao, O. Mutlu, H. Kim, R. Agarwal, , and Y. N. Patt, "Improving the performance of object-oriented languages with dynamic predication of indirect jumps". In Arch. Support for Prog. Lang. & Operating Syst. (ASPLOS), pp. 80--90, 2008.
	34	M. P. Jones, "Dictionary-free overloading by partial evaluation". Lisp and Symbolic Computation 8(3), pp. 229--248, 1995.
	35	C. E. Kees and C. T. Miller, "C++ implementations of numerical methods for solving differential-algebraic equations: design and optimization considerations". ACM Trans. Math. Softw. 25(4), pp. 377--403, 1999.
	36	A. Kennedy and D. Syme, "Design and implementation of generics for the .NET common language runtime". In ACM Int'l Conf. Prog. Lang. Design & Impl. (PLDI), pp. 1--12, 2001.
	37	H. Kim, J. A. Joao, O.Mutlu, C. J. Lee, Y. N. Patt, and R. Cohn, "VPC prediction: reducing the cost of indirect branches via hardware-based dynamic devirtualization". In 34th Int'l Symp. on Computer Archit. (ISCA), p. 2007, 424--435.
	38	R. Klarer, B. Stroustrup, D. Tsafrir, and M. Wong, "SCARY iterator assignment and initialization". ISO C++ standards committee paper N2913=09-0103, Jul 2009. Frankfurt, Germany. http://www.openstd.org/jtc1/sc22/wg21/docs/papers/2009/n2913.pdf
	39	J. Lau, M. Arnold, M. Hind, and B. Calder, "Online performance auditing: using hot optimizations without getting burned". In ACM Int'l Conf. Prog. Lang. Design & Impl. (PLDI), pp. 239--251, 2006.
	40	A. Legrand, L. Marchal, and H. Casanova, "Scheduling distributed applications: the SimGrid simulation framework". In IEEE Int'l Symp. on Cluster Comput. & the Grid (CCGrid), p. 138, 2003.
	41	A. Mu'alem and D. G. Feitelson, "Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling". IEEE Trans. Parallel Distrib. Syst. (TPDS) 12(6), pp. 529--543, Jun 2001.
	42	"Parallel Workloads Archive". http://www.cs.huji.ac.il/labs/parallel/workload
	43	"Grid Workloads Archive". http://gwa.ewi.tudelft.nl
	44	"Proc(5): process info pseudo-filesystem - Linux man page". http://linux.die.net/man/5/proc (Acceded Mar 2009).
	45	A. Roth, A. Moshovos, and G. S. Sohi, "Improving virtual function call target prediction via dependence-based pre-computation". In 13th ACM Int'l Conf. on Supercomput. (ICS), pp. 356--364, 1999.
	46	E. Shmueli and D. G. Feitelson, "On simulation and design of parallel-systems schedulers: are we doing the right thing?". IEEE Trans. on Parallel Distrib. Syst. (TPDS) 20(7), pp. 983--996, Jul 2009.
	47	J. G. Siek and A. Lumsdaine, "A language for generic programming in the large". J. Science of Comput. Programming, 2009. To appear.
	48	A. Stepanov, "The standard template library: how do you build an algorithm that is both generic and efficient?". Byte 10, Oct 1995.
	49	B. Stroustrup, The C++ Programming Language. Addison-Wesley, 3rd ed., 1997.
	50	D. Tsafrir, Y. Etsion, and D. G. Feitelson, "Backfilling using systemgenerated predictions rather than user runtime estimates". IEEE Trans. Parallel Distrib. Syst. (TPDS) 18(6), pp. 789--803, Jun 2007.
	51	T. L. Veldhuizen and M. E. Jernigan, "Will C++ be faster than Fortran?". In Int'l Sci. Comput. in Object-Oriented Parallel Environments (ISCOPE), 1997.
	52	S. Weeks, "Whole-program compilation in MLton". In Workshop on ML, p. 1, ACM, 2006.
	53	Wikibooks, "C++ programming/code/design patterns". http://en.wikibooks.org/wiki/C++ Programming/Code/Design Patterns.
	54	X. Zhuang, M. J. Serrano, H. W. Cain, and J-D. Choi, "Accurate, efficient, and adaptive calling context profiling". In ACM Int'l Conf. Prog. Lang. Design & Impl. (PLDI), pp. 263--271, 2006.