Paul R. Wilson
Abstract
We describe a scheme for supporting huge address spaces without the need for long addresses implemented in hardware. Pointers are translated ("swizzled") from a long format to a shorter format (directly supported by normal hardware) at page fault time. No extra hardware is required beyond that normally used by virtual memory systems, and no continual software cost is incurred by presence checks or indirection of pointers.This scheme could be used to fault pages into a normal memory from a persistent store, or simply to avoid extra hardware requirements when supporting large address spaces. It exploits temporal and spatial locality in much the same way as a normal virtual memory, so its performance should be quite good.
- ApEL88 Appel, Andrew W., John R. Ellis, and Kai Li "Realtime concurrent garbage collection on stock multiprocessors," Proc. SIGPLAN PLDI '88, pp. 11- 20. Google Scholar
Digital Library
- ABCC83 Atkinson, M.P., P.J. Bailey, K.J. Chisholm, P. W. Cockshott, and R. Morrison, "An approach to persistent programming," The Computer Journal, vol. 26, no. 4, December 1983, pp. 360-365.Google ScholarCross Ref
- Bart88 Bartlett, Joel F. "Compacting garbage collection with ambiguous roots," Technical Report 88/2, Digital Equipment Corp., Western Research Laboratory, February 88.Google Scholar
- BaSa76 Baer, J.-L., and Sager, G.R. "Dynamic improvement of Locality in virtual memory systems," IEEE TSWE, vol. SE-2, no. 1 (March 1976).Google Scholar
- BoWe88 Boehm, Hans-Juergen, and Mark Weiser. "Garbage collection in an uncooperative environment," Software: Practice and Experience, 1988, pp. 495-508. Google ScholarDigital Library
- CACB84 Cockshott, W., M. Atkinson, K. Chisholm, P. Bailey, and R. Morrison, "Persistent Object Management System," Software Practice and Experience, vol. 14, 1984, pp. 49-71.Google ScholarCross Ref
- DWHB90 Demers, Alan, Mark Weiser, Barry Hayes Hans Boehm, Daniel Bobrow, and Scott Shenker, "Combining generational and conservative garbage collection: framework and implementations," ACM Symposium on Principles of Programming Languages, January 1990, pp. 261-269. Google ScholarDigital Library
- DeBr76 Deutsch, L. Peter, and Daniel G. Bobrow, "An efficient incremental automatic garbage collector," Communications of the ACM 19(9), September 1976, pp. 522-526. Google ScholarDigital Library
- LiHe83 Lieberman, Henry, and Carl Hewitt, "A real-time garbage collector based on the lifetimes of objects," CACM 26, 6 (June 1983), pp. 419-429. Google ScholarDigital Library
- HeK185 Heering, J., and P. Klint, "Towards monolingual programming environments," ACM Trans Prog. Lang. Syst., 7, 2 (April 1985), pp. 183- 213. Google ScholarDigital Library
- Kaeh81 Kaehler, T. "Virtual memory for an object-oriented language," Byte 6, 8 (August 1981), pp. 378-387.Google Scholar
- Moss89 Moss, J. Eliot B. "Addressing large distributed collections of persistent objects: the Mneme project's approach," in Second International Workshop on Database Programming Languages, pp. 269-285. Also available as University of Massachusetts Dept. of Computer and Information Science Technical Report 89-68. Google ScholarDigital Library
- Moon84 Moon, David "Garbage collection in a large lisp system," ACM Symp. on Lisp and Functional Programming 1984, pp. 235-246. Google ScholarDigital Library
- Moss90 Moss, Eliot "Working with objects: to swizzle or not to swizzle?," Unpublished technical report, University of Massachusetts 1990.Google Scholar
- Stam82 Stamos, James William, "A large object-oriented virtual memory: grouping strategies, measurements, and performance," Xerox Palo Alto Research Centers Technical Report SCG-82-2, May 1982.Google Scholar
- Unga84 Ungar, David M., "Generation Scavenging: a non-disruptive high-performance storage reclamation algorithm," ACM SIGPLAN Notices, 19,5 (May 1984), pp. 157-167. Google ScholarDigital Library
- Wils89 Wilson, Paul R. "Heap management and hierarchical memories," Unpublished working paper, May 1989.Google Scholar
- Wils90 Wilson, Paul R. "Issues and strategies in heap management and hierarchical memories." Position paper, OOPSLA/ECOOP '90 Workshop on Garbage Collection in Object-Oriented Systems. Also forthcoming in SIGPLAN Notices. Google ScholarDigital Library
- WiLM90 Wilson, Paul R., Michael S. Lain, and Thomas G. Moher, "Effective static-graph reorganization to improve locality in garbage-collected Systems," Proc. SIGPLAN '91, to appear. Google ScholarDigital Library
- WiMo89 Wilson, Paul R. and Thomas G. Moher, "Design of the Opportunistic Garbage Collector," Proc. OOPSLA '89. Google ScholarDigital Library
- WiWH87 Williams, Ifor, Mario Wolkzko, and Trevor Hopkins, "Dynamic grouping in an object-oriented virtual memory hierarchy," In European Conference on Object-Oriented Programming, pages 87-96, 1987. Google ScholarDigital Library
- WiWH90 Williams, Ifor, Mario Wolkzko, and Trevor Hopkins, "Realization of a dynamically grouped object-oriented memory hierarchy," technical report, University of Manchester Dept. of Computer Science, 1990.Google Scholar
Index Terms
- Pointer swizzling at page fault time: efficiently supporting huge address spaces on standard hardware
Recommendations
Interprocedural pointer alias analysis
We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Adaptable pointer swizzling strategies in object bases: design, realization, and quantitative analysis
Persistent object systemsIn this article, different techniques for "pointer swizzling" are classified and evaluated for optimizing the access to main-memory resident persistent objects. To speed up the access along inter-object references, the persistent pointers in the form of ...
Comments