ABSTRACT
The possibility of incredibly cheap, fantastically large media for storage gives rise to a realistic LISP memory management scheme under which GC may be postponed for days, or even indefinitely; the idea is encapsulated in the acronym “DDI”—“GC? Don't Do It!”. Tertiary memory is used to archive pages of the LISP environment which are perhaps reclaimable, but which have not been proven so; whereas the standard technique of “paging” is used to swap active data from the main memory to a secondary store such as magnetic disk. Some scenarios are presented considering a variety of currently-available technologies, and of one speculative possibility—videodisc—by which a requisite compactifying GC would be done “overnight”, or over the weekend. With enough tertiary available, one design could last for over 12 years without a GC. “Write-once” memories, probably unusable for most applications, would not be at a disadvantage here.
- 1.Baker, H.G., Jr.; "List Processing in Real Time on a Serial Computer"; Comm. ACM 21, 4 (April 1978), Pp. 280-294. Google ScholarDigital Library
- 2.Bishop, P. B.; Garbage Collection in a Very Large Address Space: Technical Report TR-178, MIT Laboratory for Computer Science.Google Scholar
- 3.Bobrow, D.G., and Clark, D.W.; "Compact Encodings of List Structure"; ACM Trans. on Prog. Lang. and Systems 1, 2 (Oct 1979), Pp. 266-286. Google ScholarDigital Library
- 4.Clark, D.W., and Green, C.C.; "An Empirical Study of List Structure In LISP"; Comm. ACM 20, 2 (Feb 1977), Pp. 78-87. Google ScholarDigital Library
- 5.Deutsch, L.P.; "Experience With a Microprogrammed Interlisp System"; Proc. 11th Annual Microprogramming Workshop, Asilomar, Pacific Grove, CA. (Nov 1978) Google ScholarDigital Library
- 6.Doyle, J.; "A Truth Maintenance System"; Artificial Intelligence 12, 3 (Nov 1979), Pp. 231-272.Google ScholarCross Ref
- 7.Edwards, Daniel J.; "Secondary Storage in LISP"; A.I. Memo 63, M.I.T. Artificial Intelligence Lab, Cambridge MA (Dec 1963). Google ScholarDigital Library
- 8.Fenichel, R.R., and Yochelson, J.C.; "A LISP Garbage-Collector for Virtual-Memory Computer Systems"; Comm. ACM 12, 11 (Nov. 1969), Pp. 611-612. Google ScholarDigital Library
- 9.Greenblatt, R.; "The LISP Machine"; Working Paper No. 79, M.I.T. Artificial Intelligence Lab, Cambridge MA (Nov 1974).Google Scholar
- 10.Greenblatt, R., et. al.; "LISP Machine Progress Report"; A.I. Memo 444, M.I.T. Artificial Intelligence Lab, Cambridge MA (Aug 1977).Google Scholar
- 11.Ingalls, D. H. "The SMALLTALK Programming System Design and Implementation"; Fifth Annual Symposium on Principles of Programming Languages, 1978. Google ScholarDigital Library
- 12.Lieberman, Henry, and Hewitt, Carl; "A Real Time Garbage Collector That Can Recover Temporary Storage Quickly"; A.I. Memo 569, M.I.T. Artificial Intelligence Lab, Cambridge MA (Apr 1980); (also submitted for publication)Google Scholar
- 13.Marti, J., Hearn, A., Griss, M., and Griss, C.; Standard LISP Report; UCP-60, University of Utah (Jan 1978).Google Scholar
- 14.McWilliams, T.M., Widdoes, L.C., Jr., and Wood, L.L.; The S-1 Project; Lawrence Livermore Laboratory, Livermore CA (Sep 1977)Google Scholar
- 15.Minsky, Marvin L.; "A LISP Garbage Collector Using Serial Secondary Storage"; A.I. Memo 58, M.I.T. Artificial Intelligence Lab, Cambridge MA (Dec 1963) (out of print). Google ScholarDigital Library
- 16.Nadan, J.S. "Optical Information Storage and Retrieval Systems"; in Archival Memory Technology, Proc. of a Workshop Held at Carnegie-Mellon Univ. (Sep 28, 1978), Pp. 28-30.Google Scholar
- 17.Steele, G.L. Jr.; "Data Representations in PDP-10 Maclisp", A.I. Memo 420, M.I.T. Artificial Intelligence Lab, Cambridge MA (Sep 1977).Google Scholar
- 18.White, JonL; "NIL—A Perspective"; in Proc. of 1979 MACSYMA Users Conference (June 1979), Pp. 190-199.Google Scholar
- 19.White, JonL; "LISP/370: A Short Technical Description of the Implementation"; SIGSAM Bull. 12, 4 (Nov 1978), Pp. 23-27. Google ScholarDigital Library
Index Terms
- Address/memory management for a gigantic LISP environment or, GC considered harmful
Recommendations
Address/memory management for a gigantic LISP environment or, GC considered harmful
The possibility of incredibly cheap, fantastically large media for storage gives rise to a realistic LISP memory management scheme under which GC may be postponed for days, or even indefinitely; the idea is encapsulated in the acronym "DDI" --- "GC? Don'...
Regularities considered harmful: forcing randomness to memory accesses to reduce row buffer conflicts for multi-core, multi-bank systems
ASPLOS '13We propose a novel kernel-level memory allocator, called M3 (M-cube, Multi-core Multi-bank Memory allocator), that has the following two features. First, it introduces and makes use of a notion of a memory container, which is defined as a unit of memory ...
GC assertions: using the garbage collector to check heap properties
PLDI '09: Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and ImplementationThis paper introduces GC assertions, a system interface that programmers can use to check for errors, such as data structure invariant violations, and to diagnose performance problems, such as memory leaks. GC assertions are checked by the garbage ...
Comments