Borrow, copy or steal?: loans and larceny in the orthodox canonical form

ABSTRACT

Dynamic memory management in C++ is complex, especially across the boundaries of library abstract data types. C++ libraries designed in the orthodox canonical form (OCF) alleviate some of the problems by ensuring that classes which manage any kind of heap structures faithfully copy and delete these. However, in certain common circumstances, OCF heap structures are wastefully copied multiple times. General reference counting is not an option in OCF, since a shared body violates the intended value semantics; although a copy-on-write policy can be made to work with borrowed heap structures. A simpler ownership policy, based on larceny, allows low-level memory manager objects to steal heap structures from temporary variables, in properly isolated circumstances. Various strategies for regulating theft are presented, ranging from pilfer-constructors to locks on heap data. Larceny has similarities with other transfer of ownership patterns, but is more a core implementation technique designed to improve the efficiency and effectiveness of OCF-conformant libraries.

REFERENCES

• Alme97: P S Almeida, "Balloon types: controlling sharing of state in data types", Proc. l lth European Conf. Object-Oriented Prog. (1997), Springer Verlag, 32-59.
• Booc94: Grady Booch, Object-oriented analysis and design with applications (2nd ed.), Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1993
• BrLo97: Marshall Brain , Lance Lovette, Developing Professional Applications; For Windows 95 and NT Using MFC, with CD-ROM, Simon & Schuster, 1996
• CABD94: Derek Coleman , Patrick Arnold , Stephanie Bodoff , Chris Dollin , Helena Gilchrist , Fiona Hayes , Paul Jeremaes, Object-oriented development: the fusion method, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• Carg96: Tom Cargill, Localized ownership: managing dynamic objects in C++, Pattern languages of program design 2, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• Colv98: G Colvin, "Why is auto_ptr defined the way it is?", The comp.std.c++ FAQ, question C2, http.'//real ity. s g i. com/auste rn_mti/std-c + + /faq.html, 13 May (1998).
• Cope92: James O. Coplien, Advanced C++ programming styles and idioms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• GHJV95: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• GOP90: Keith E. Gorlen , Sanford M. Orlow , Perry S. Plexico, Data abstraction and object-oriented programming in C++, John Wiley & Sons, Inc., New York, NY, 1990
• HLHW92: John Hogg , Doug Lea , Alan Wills , Dennis deChampeaux , Richard Holt, The Geneva convention on the treatment of object aliasing, ACM SIGPLAN OOPS Messenger, v.3 n.2, p.11-16, April 1992 [doi>10.1145/130943.130947]
• Hogg91: John Hogg, Islands: aliasing protection in object-oriented languages, ACM SIGPLAN Notices, v.26 n.11, p.271-285, Nov. 1991
• Hors95: Cay S. Horstmann, Mastering object-oriented design in C++, John Wiley & Sons, Inc., New York, NY, 1995
• Lea 93: D Lea, "The GNU C++ Library", C++ Report, June (1993); reprinted in {Lipp96}; revised as: http://gee.cs.oswego.edu/dl/libg+ +paper/ libg++/libg++.html, (1995).
• Lea96: Douglas Lea , Doug Lea, Concurrent Programming in Java: Design Principles and Patterns, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• Lipp96: Stanley B. Lippman, C++ gems, SIGS Publications, Inc., New York, NY, 1996
• Meye92: Scott Meyers, Effective C++: 50 specific ways to improve your programs and designs, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• Mins96: Naftaly H. Minsky, Towards Alias-Free Pointers, Proceedings of the 10th European Conference on Object-Oriented Programming, p.189-209, July 08-12, 1996
• Rati93: Rational, C++ Booch Components Class Catalog, version 2.3 (1993), Rational.
• Rogu95: Rogue Wave, Tools.h++ Foundation Class Library for C++ Programming, version 6 (1995), Rogue Wave Software, Inc.
• SaCa96: Aamod Sane , Roy Campbell, Resource exchanger: a behavioral pattern for low-overhead concurrent resource management, Pattern languages of program design 2, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• SBGL91: Robert E. Strom , David F. Bacon , Arthur P. Goldberg , Andy Lowry , Daniel M. Yellin , Shaula Alexander Yemini, Hermes: a language for distributed computing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• Stee86: G L Steele, The Common Lisp Reference Manual (1986), Digital Press.
• StLe94: A Stepanov and M Lee, "The standard template library", Technical Report, Hewlett- Packard Laboratories, May (1994).
• Stro91: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• VCK96: John M. Vlissides , James O. Coplien , Norman L. Kerth, Pattern languages of program design 2, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• Wild96: F Wild, "Instantiating code patterns", Dr Dobb's Journal, June (1996), 72.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C++

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries
  D.4 OPERATING SYSTEMS

General Terms:
Design, Languages, Performance, Theory

Keywords:
C++, borrowing, copy-on-write, implementation strategies, larceny, memory management, stealing, transfer of ownership