Mostly-copying reachability-based orthogonal persistence

ABSTRACT

We describe how reachability-based orthogonal persistence can be supported even in uncooperative implementations of languages such as C++ and Modula-3, and without modification to the compiler. Our scheme extends Bartlett's mostly-copying garbage collector to manage both transient objects and resident persistent objects, and to compute the reachability closure necessary for stabilization of the persistent heap. It has been implemented in our prototype of reachability-based persistence for Modula-3, yielding performance competitive with that of comparable, but non-orthogonal, persistent variants of C++. Experimental results, using the 007 object database benchmarks, reveal that the mostly-copying approach offers a straightforward path to efficient orthogonal persistence in these uncooperative environments. The results also characterize the performance of persistence implementations based on virtual memory protection primitives.

REFERENCES

• 1: R. Agrawal , N. H. Gehani, ODE (Object Database and Environment): the language and the data model, ACM SIGMOD Record, v.18 n.2, p.36-45, June 1989
• 2: R. Agrawal , N. H. Gehani, Rationale for the design of persistence and query processing facilities in the database programming language O++, Proceedings of the second international workshop on Database programming languages, p.25-40, December 1989, Salishan Lodge, Gleneden Beach, Oregon, United States
• 3: Suad Alagic, The ODMG object model: does it make sense?, ACM SIGPLAN Notices, v.32 n.10, p.253-270, Oct. 1997
• 4: Andrew W. Appel , Kai Li, Virtual memory primitives for user programs, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.96-107, April 08-11, 1991, Santa Clara, California, United States
• 5: Malcolm Atkinson , Ken Chisholm , Paul Cockshott, PS-algol: an algol with a persistent heap, ACM SIGPLAN Notices, v.17 n.7, July 1982 [doi>10.1145/988376.988378]
• 6: ATKINSON, M. P., BAILEY, P. J., CHISHOLM, K. J., COCKSHOTT, P. W., AND MORRISON, R. An approach to persistent programming. The Computer Journal 26, 4 (Nov. 1983), 360-365.
• 7: Malcolm P. Atkinson , O. Peter Buneman, Types and persistence in database programming languages, ACM Computing Surveys (CSUR), v.19 n.2, p.105-170, June 1987 [doi>10.1145/62070.45066]
• 8: ATKINSON, M. e., CHISHOLM, K. J., COCKSHOTT, W. P., AND MARSHALL, R. M. Algorithms for a persistent heap. Software: Practice and Experience 13, 7 (Mar. 1983), 259-271.
• 9: M. P. Atkinson , L. Daynès , M. J. Jordan , T. Printezis , S. Spence, An orthogonally persistent Java, ACM SIGMOD Record, v.25 n.4, p.68-75, Dec. 1996 [doi>10.1145/245882.245905]
• 10: ATKINSON, M. P., JORDAN, M. J., DAYNES, L., AND SPENCE, S. Design issues for persistent Java: A type-safe object-oriented, orthogonally persistent system. In Connor and Nettles {27}, pp. 33-47.
• 11: Malcolm Atkinson , Ronald Morrison, Orthogonally persistent object systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.3, July 1995
• 12: BARTLETT, J. F. Compacting garbage collection with ambiguous roots. Research Report 8812, Western Research Laboratory, Digital Equipment Corporation, Feb. 1988.
• 13: BARTLETT, J. F. Mostly-copying garbage collection picks up generations and C++. Technical Note TN-12, Western Research Laboratory, Digital Equipment Corporation, Oct. 1989.
• 14: BAUMANN, R. Client/server distribution in a structure-oriented database management system. Tech. Rep. AIB 97-14, RWTH Aachen, Germany, 1997.
• 15: Hans-Juergen Boehm, Space efficient conservative garbage collection, ACM SIGPLAN Notices, v.28 n.6, p.197-206, June 1993
• 16: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 17: Kumar Brahnmath , Nathaniel Nystrom , Antony L. Hosking , Quintin I. Cutts, Swizzle Barrier Optimizations for Orthogonal Persistence in Java, Proceedings of the 8th International Workshop on Persistent Object Systems (POS8) and Proceedings of the 3rd International Workshop on Persistence and Java (PJW3): Advances in Persistent Object Systems, p.268-278, January 1999
• 18: BRAHNMATH, K. J. Optimizing orthogonal persistence for Java. Master's thesis, Purdue University, May 199g.
• 19: CARDELLI, L., DONAI-tUE, J., GLASSMAN, L., JORDAN, M., KALSOW, B., AND NELSON, G. Modula-3 language definition, in Systems Programming with Modula-3, G. Nelson, Ed. Prentice Hall, 1991, ch. 2, pp. 11-66.
• 20: Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States
• 21: Michael J. Carey , David J. DeWitt , Jeffrey F. Naughton, The 007 Benchmark, ACM SIGMOD Record, v.22 n.2, p.12-21, June 1, 1993
• 22: Michael J. Carey , Michael J. Franklin , Markos Zaharioudakis, Fine-grained sharing in a page server OODBMS, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.359-370, May 24-27, 1994, Minneapolis, Minnesota, United States
• 23: R. G. G. Cattell , Douglas K. Barry , Dirk Bartels , Mark Berler , Jeff Eastman , Sophie Gamerman , David Jordan , Adam Springer , Henry Strickland , Drew Wade, The object database standard: ODMG 2.0, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 24: Jeffrey S. Chase , Henry M. Levy , Michael J. Feeley , Edward D. Lazowska, Sharing and protection in a single-address-space operating system, ACM Transactions on Computer Systems (TOCS), v.12 n.4, p.271-307, Nov. 1994 [doi>10.1145/195792.195795]
• 25: Jeffrey S. Chase , Henry M. Levy , Edward D. Lazowska , Miche Baker-Harvey, Lightweight shared objects in a 64-bit operating system, ACM SIGPLAN Notices, v.27 n.10, p.397-413, Oct. 1992
• 26: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 27: CONNOR, R., AND NETTLES, S., Eds. Proceedings of the Seventh International Workshop on Persistent Object Systems (Cape May, New Jersey, May 1996). Persistent Object Systems: Principles and Practice, Morgan Kaufmann, 1997.
• 28: Alan Dearle , Richard Connor , Fred Brown , Ron Morrison, Napier88—a database programming language?, Proceedings of the second international workshop on Database programming languages, p.179-195, December 1989, Salishan Lodge, Gleneden Beach, Oregon, United States
• 29: Alan Dearle , Rex di Bona , James Farrow , Frans Henskens , Anders Lindström , John Rosenberg , Francis Vaughan, Grasshopper: an orthogonally persistent operating system, Computing Systems, v.7 n.3, p.289-312, Summer 1994
• 30: DEARLE, A., SHAW, G. M., AND ZDONIK, S. B., Eds. Proceedings of the Fourth International Workshop on Persistent Object Systems (Martha's Vineyard, Massachusetts, Sept. 1990). Implementing Persistent Object Bases: Principles and Practice, Morgan Kaufmann, 1991.
• 31: David L. Detlefs , Maurice P. Herlihy , Jeannette M. Wing, Inheritance of Synchronization and Recovery Properties in Avalon/C++, Computer, v.21 n.12, p.57-69, December 1988 [doi>10.1109/2.16189]
• 32: DETREVILLE, J. Experience with concurrent garbage collectors for Modula-2+. Tech. Rep. 64, Systems Research Center, Digital Equipment Corporation, Palo Alto, CA, Aug. 1990.
• 33: Amer Diwan , Eliot Moss , Richard Hudson, Compiler support for garbage collection in a statically typed language, ACM SIGPLAN Notices, v.27 n.7, p.273-282, July 1992
• 34: ELPHINSTONE, K., RUSSELL, S., HEISER, G., AND LIEDTKE, J. Supporting persistent object systems in a single address space. In Connor and Nettles {27}, pp. 111-119.
• 35: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• 36: Nicholas Haines , Darrell Kindred , J. Gregory Morrisett , Scott M. Nettles , Jeannette M. Wing, Composing first-class transactions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1719-1736, Nov. 1994 [doi>10.1145/197320.197346]
• 37: Germont Heiser , Kevin Elphinstone , Jerry Vochteloo , Stephen Russell , Jochen Liedtke, The Mungi single-address-space operating system, Software—Practice & Experience, v.28 n.9, p.901-928, July 25, 1998 [doi>10.1002/(SICI)1097-024X(19980725)28:9<901::AID-SPE181>3.0.CO;2-7]
• 38: Antony Lloyd Hosking, Lightweight support for fine-grained persistence of stock hardware, University of Massachusetts, Amherst, MA, 1995
• 39: HOSKING, A. L. Residency check elimination for object-oriented persistent languages. In Connor and Nettles {27}, pp. 174-183.
• 40: Antony L. Hosking , Eric W. Brown , J. Eliot B. Moss, Update Logging for Persistent Programming Languages: A Comparative Performance Evaluation, Proceedings of the 19th International Conference on Very Large Data Bases, p.429-440, August 24-27, 1993
• 41: Antony L. Hosking , Jiawan Chen, PM3: An Orthogonal Persistent Systems Programming Language - Design, Implementation, Performance, Proceedings of the 25th International Conference on Very Large Data Bases, p.587-598, September 07-10, 1999
• 42: Antony L. Hosking , J. E Moss, Compiler Support for Persistent Programming, University of Massachusetts, Amherst, MA, 1991
• 43: HOSKING, A. L,, AND MOSS, J. E. B. Towards compile-time optimisations for persistence. In Dearie et al. {30}, pp. 17-27.
• 44: Antony L. Hosking , J. Eliot B. Moss, Object fault handling for persistent programming languages: a performance evaluation, ACM SIGPLAN Notices, v.28 n.10, p.288-303, Oct. 1, 1993
• 45: Antony L. Hosking , J. Eliot B. Moss, Protection traps and alternatives for memory management of an object-oriented language, ACM SIGOPS Operating Systems Review, v.27 n.5, p.106-119, Dec. 1993
• 46: HOSKING, A. L., AND MOSS, J. E. B. Lightweight write detection and checkpointing for fine-grained persistence. Tech. Rep. 95-084, Department of Computer Sciences, Purdue University, Dec. 1995.
• 47: HOSKING, A. L., AND NOVIANTO, A. P. Reachability-based orthogonal persistence for C, C++ and other intransigents. In Proceedings of the OOPSLA Workshop on Memory Management and Garbage Collection (Atlanta, Georgia, Oct.). 1997. http://www.dcs.gla.ac.uk/'huw/oopsla97/gc/papers.html.
• 48: Antony L. Hosking , Nathaniel Nystrom , Quintin I. Cutts , Kumar Brahnmath, Optimizing the Read and Write Barriers for Orthogonal Persistence, Proceedings of the 8th International Workshop on Persistent Object Systems (POS8) and Proceedings of the 3rd International Workshop on Persistence and Java (PJW3): Advances in Persistent Object Systems, p.149-159, January 1999
• 49: Proceedings of the second international workshop on Database programming languages, December 1989
• 50: Proceedings of the ACM International Symposium on Memory Management (Vancouver, Canada, Oct., 1998). ACM SIGPLAN Notices 34, 3 (Mar. 1999).
• 51: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 52: JORDAN, M. Early experiences with persistent Java. In Proceedings of the First International Workshop on Persistence and Java (Drymen, Scotland, Sept.), M. P. Atkinson and M. J. Jordan, Eds. Sun Microsystems Laboratories Technical Report 96-58, Nov. 1996.
• 53: Mick J. Jordan , Malcolm P. Atkinson, Orthogonal Persistence for Java? - A Mid-term Report, Proceedings of the 8th International Workshop on Persistent Object Systems (POS8) and Proceedings of the 3rd International Workshop on Persistence and Java (PJW3): Advances in Persistent Object Systems, p.335-352, January 1999
• 54: Ted Kaehler, Virtual memory on a narrow machine for an object-oriented language, Conference proceedings on Object-oriented programming systems, languages and applications, p.87-106, September 29-October 02, 1986, Portland, Oregon, United States
• 55: KAEHL}~R, T., AND KRASNER, G. LOOM-large object-oriented memory for Smalltalk-80 systems. In SmaUtalk-80: Bits of History, Words ofAdvice, G. Krasner, Ed. Addison-Wesley, 1983, ch. 14, pp. 251--270.
• 56: Sheetal V. Kakkad , Mark S. Johnstone , Paul R. Wilson, Portable run-time type description for conventional compilers, Proceedings of the 1st international symposium on Memory management, p.146-153, October 17-19, 1998, Vancouver, British Columbia, Canada
• 57: Norbert Kiesel , Andy Schuerr , Bernhard Westfechtel, GRAS, a graph oriented (software) engineering database system, Information Systems, v.20 n.1, p.21-51, March 1995 [doi>10.1016/0306-4379(95)00002-L]
• 58: Charles Lamb , Gordon Landis , Jack Orenstein , Dan Weinreb, The ObjectStore database system, Communications of the ACM, v.34 n.10, p.50-63, Oct. 1991 [doi>10.1145/125223.125244]
• 59: Tian F. Lim , Przemysław Pardyak , Brian N. Bershad, A memory-efficient real-time non-copying garbage collector, Proceedings of the 1st international symposium on Memory management, p.118-129, October 17-19, 1998, Vancouver, British Columbia, Canada
• 60: Florian Matthes , Joachim W. Schmidt, Persistent Threads, Proceedings of the 20th International Conference on Very Large Data Bases, p.403-414, September 12-15, 1994
• 61: Ronald Morrison , Alfred L. Brown , Raymund Carrick , Richard C. H. Connor , Alan Dearle , Malcolm P. Atkinson, The Napier Type System, Proceedings of the Third International Workshop on Persistent Object Systems, p.3-18, January 10-13, 1989
• 62: MORRISON, R., JORDAN, M., AND ATKINSON, M., Eds. Proceedings of the Third International Workshop on Persistence and Java (Tiburon, California, August 1998). Advances in Persistent Object Systems, Morgan Kaufmann, 1999.
• 63: J. Eliot B. Moss, Working with Persistent Objects: To Swizzle or Not to Swizzle, IEEE Transactions on Software Engineering, v.18 n.8, p.657-673, August 1992 [doi>10.1109/32.153378]
• 64: J. Eliot B. Moss , Antony L. Hosking, Expressing Object Residency Optimizations Using Pointer Type Annotations, Proceedings of the Sixth International Workshop on Persistent Object Systems, p.3-15, September 05-09, 1994
• 65: NYSTROM, N., HOSKING, A. L., WHITLOCK, D., CUTTS, Q., AND DIWAN, A. Partial redundancy elimination for access path expressions. Tech. Rep. 98-044, Department of Computer Sciences, Purdue University, Oct. 1998. Submitted for publication.
• 66: NYSTROM, N. J. Bytecode level analysis and optimization of Java classes. Master's thesis, Purdue University, Aug. 1998.
• 67: RICHARDSON, J. E. Compiled item faulting: A new technique for managing I/O in a persistent language. In Dearie et al. {30}, pp. 3-16.
• 68: Joel E. Richardson , Michael J. Carey, Programming constructs for database system implementation in EXODUS, ACM SIGMOD Record, v.16 n.3, p.208-219, Dec. 1987
• 69: Joel E. Richardson , Michael J. Carey, Persistence in the E Language: Issues and implementation, Software—Practice & Experience, v.19 n.12, p.1115-1150, Dec. 1989
• 70: Joel E. Richardson , Michael J. Carey , Daniel T. Schuh, The design of the E programming language, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.3, p.494-534, July 1993 [doi>10.1145/169683.174157]
• 71: John Rosenberg , Alan Dearle , David Hulse , Anders Lindström , Stephen Norris, Operating system support for persistent and recoverable computations, Communications of the ACM, v.39 n.9, p.62-69, Sept. 1996 [doi>10.1145/234215.234472]
• 72: A clustering algorithm for hierarchical structures, ACM Transactions on Database Systems (TODS), v.2 n.1, p.27-44, March 1977 [doi>10.1145/320521.320531]
• 73: SCHUH, D., CAREY, M., AND Dt~WITT, D. Persistence in E revisited - implementation experiences. In Dearie et al. {30}, pp. 345-359.
• 74: Proceedings of the ACM International Conference on Management of Data (Minneapolis, Minnesota, May). ACM SIGMOD Record 23, 2 (June 1994).
• 75: SINGHAL, V., KAKKAD, S. V., AND WILSON, P. R. Texas, an efficient, portable persistent store, in Proceedings of the Fifth International Workshop on Persistent Object Systems (San Miniato, Italy, Sept.), A. Albano and R. Morrison, Eds. Workshops in Computing. Springer-Verlag, 1992, pp. 11-33.
• 76: James W. Stamos, Static grouping of small objects to enhance performance of a paged virtual memory, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.155-180, May 1984 [doi>10.1145/190.194]
• 77: A. Straw , F. Mellender , S. Riegel, Object management in a persistent smalltalk system, Software—Practice & Experience, v.19 n.8, p.719-737, August 1989 [doi>10.1002/spe.4380190803]
• 78: E. P. Wentworth, Pitfalls of conservation garbage collection, Software—Practice & Experience, v.20 n.7, p.719-727, July 1990 [doi>10.1002/spe.4380200707]
• 79: Seth J. White , David J. DeWitt, QuickStore: a high performance mapped object store, ACM SIGMOD Record, v.23 n.2, p.395-406, June 1994
• 80: WILSON, P. R. Uniprocessor garbage collection techniques. ACM Comput. Surv.. To appear.
• 81: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 82: WILSON, P. R., AND KAKKAD, S. V. Pointer swizzling at page fault time: Efficiently and compatibly supporting huge address spaces on standard hardware. In Proceedings of the 1992 international Workshop on Object Orientation in Operating Systems (Paris, France, Sept.). IEEE Computer Society, 1992, pp. 364-377.

INDEX TERMS

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

          Nouns: C++

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

          Nouns: Modula-3
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

General Terms:
Design, Experimentation, Languages, Measurement, Performance, Reliability, Theory