Skip to main content
SpringerLink
Log in

Research Demonstration of a Hardware Reference-Counting Heap

  • Published:
LISP and Symbolic Computation

Abstract

A hardware self-managing heap memory (RCM) for languages like Lisp, Smalltalk, and Java has been designed, built, tested and benchmarked. On every pointer write from the processor, reference-counting transactions are performed in real time within this memory, and garbage cells are reused without processor cycles. A processor allocates new nodes simply by reading from a distinguished location in its address space. The memory hardware also incorporates support for off-line, multiprocessing, mark-sweep garbage collection.

Performance statistics are presented from a partial implementation of Scheme over five different memory models and two garbage collection strategies, from main memory (no access to RCM) to a fully operational RCM installed on an external bus. The performance of the RCM memory is more than competitive with main memory.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Appel, A.W. Garbage collection can be faster than stack allocation. Inf. Proc. Lett., 25(4):275–279, June 1987.

    Google Scholar 

  2. Appel, A.W., Ellis, J.R., and Li, K. Real-time concurrent collection on stock multiprocessors. Proc. SIGPLAN '88 Conf. Programming Language Design and Implementation, ACM SIGPLAN Notices, 23(7):11–20, July 1988.

    Google Scholar 

  3. Baker, H.G., Jr. List processing in real time on a serial computer. Comm. ACM, 21(4):280–294, April 1978.

    Google Scholar 

  4. Baker, H.G., Jr. Preface to Baker, H.G., Jr. (Ed.) Memory Management. Lecture Notes in Computer Science. Springer, Berlin, vol. 986, pp. v–viii, Springer, 1995.

    Google Scholar 

  5. Bobrow, D.G. Managing reentrant structures using reference counts. ACM Trans. Prog. Lang. Sys., 2(3):269–273, July 1980.

    Google Scholar 

  6. Clark D.W. and Green, C.C. A note on shared structure in LISP. Inform. Proc. Ltrs., 7(6):312–314, Oct. 1978.

    Google Scholar 

  7. Cohen, J. Garbage collection of linked data structures. Comput. Surveys, 13(3):341–367, Sept. 1981.

    Google Scholar 

  8. Collins, G.E. A method for overlapping and erasure of lists. Comm. ACM, 3(12):655–657, Dec. 1960.

    Google Scholar 

  9. Deutsch, L.P. and Bobrow, D.G. An efficient, incremental, real-time garbage collector. Comm. ACM, 19(9):522–526, Sept. 1976.

    Google Scholar 

  10. Deutsch, L.P. and Schiffman, A.M. Efficient implementation of the SMALLTALK-80 system. Conf. Rec. 11th ACM Symp. on Principles of Programming Languages, pp. 297–302, 1984.

  11. Diwan, A., Tarditi, D., and Moss, E. Memory-system performance of programs with intensive heap allocation. ACM Trans. Comput. Sys., 13(3):244–273, Aug. 1995.

    Google Scholar 

  12. Duff, I.S., Grimes, R.G., and Lewis, J.G. Sparse matrix test problems. ACM Trans. Math. Software, 15(1):1–14, March 1989.

    Google Scholar 

  13. Dybvig, R.K. Three Implementation Models for SCHEME, Ph.D. dissertation. Univ. of North Carolina at Chapel Hill, April 1987.

  14. Feldman, S.I. Technological Maturity Scale. Personal communication, 1991.

  15. Feldman, S.I. Technological maturity and the history of UNIX. Keynote address, USENIX Summer 1992 Technical Conference, San Antonio, TX, June 10, 1992.

  16. Frens, J. and Wise, D.S. Matrix inversion Using quadtrees implemented in GOFER. Technical Rept. 433, Computer Science Dept., Indiana Univ., May 1995.

  17. Friedman, D.P. and Wise, D.S. Reference counting can manage the circular environments of mutual recursion. Inform. Proc. Ltrs., 8(1):41–44, Jan. 1979.

    Google Scholar 

  18. Gottlieb, A., Girshman, R., Kruskal, C.P., McAuliffe, K.P., Rudolph, L., and Snir, M. The NYU ultracomputer—Designing an MIMD shared memory parallel computer. IEEE Trans. Computers, C-32(2): 175–189, Feb. 1983.

    Google Scholar 

  19. Gries, D. An exercise in proving programs correct. Comm. ACM, 20(12):921–930, Dec. 1977.

    Google Scholar 

  20. Halstead, R.H., Jr. MULTILISP: A language for concurrent symbolic computation. ACM Trans. Prog. Lang. Sys., 7(4):501–538, Oct. 1985.

    Google Scholar 

  21. Heck, B., and Wise, D.S. Implementation of an applicative file system. In Memory Management. Y. Bekkers, and J. Cohen (Eds.), Lecture Notes in Computer Science, Springer, Berlin, vol. 637, pp. 248–263, 1992.

    Google Scholar 

  22. Hudak, P. and Keller, R.M. Garbage collection and task deletion in distributed applicative processing systems. Conf. Rec. 1982 ACM Symp. on Lisp and Functional Programming, pp. 168–178, 1982.

  23. Ingalls, D.H.H. The SMALLTALK-76 programming system: Design and implementation. Conf. Rec. 5th ACM Symp. on Principles of Programming Languages, pp. 9–15, 1978.

  24. Johnson, S.D., Bose, B., and Johnson, S.D. DDD-FM9001: Derivation of a verified microprocessor; an exercise in integrating verification with formal derivation. In Proc. IFIP Conf. on Correct Hardware Design and Verification Methods. G. Milne, and L. Pierre (Eds.). Lecture Notes in Computer Science, Springer, Berlin, vol. 683, pp. 191–202, 1993.

    Google Scholar 

  25. Jones, R. and Lins, R. Garbage Collection, Algorithms for Automatic Dynamic Memory Management, John Wiley and Sons, New York, 1996.

    Google Scholar 

  26. Knuth, D.E. The Art of Computer Programming I, Fundamental Algorithms, 2nd edition, Reading, MA, Addison-Wesley, 1973.

    Google Scholar 

  27. Knuth, D.E. The Art of Computer Programming III, Sorting and Searching, Addison-Wesley, Reading, MA, 1973.

    Google Scholar 

  28. Lang, B., Queinnec, and C., Piquer, J. Garbage collecting the world. Conf. Rec. 19th ACM Symp. on Principles of Programming Languages, pp. 39–50, 1992.

  29. Lieberman, H. and Hewitt, C. A real-time garbage collector based on the lifetime of objects. Comm. ACM, 26(6):419–429, June 1983.

    Google Scholar 

  30. Moon, D. Garbage collection in a large LISP system. Conf. Rec. 1984 ACM Symp. on Lisp and Functional Programming, pp. 235–246.

  31. Nilsen, K. Progress in hardware-assisted real-time garbage collection. In Memory Management. H.G. Baker (Ed.). Lecture Notes in Computer Science, Springer, Berlin, vol. 986, pp. 355–379, 1995.

    Google Scholar 

  32. Rees, J. and Clinger, W. (Eds.). Revised3 report on the algorithmic language SCHEME. ACM SIGPLAN Notices 21(12):37–79, Dec. 1986.

  33. Schmidt, W. and Nilsen, K. Performance of a hardware-assisted real-time garbage collector. ASPLOS-VI Proc.: 6th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, ACM SIGPLAN Notices, 29(11):76–85, Nov. 1994.

    Google Scholar 

  34. Schorr, H. and Waite, W.M. An efficient machine-independent procedure for garbage collection in various list structures, Comm. ACM, 10(8):501–506, Aug. 1967.

    Google Scholar 

  35. Weizenbaum, J. Symmetric list processor. Comm. ACM, 6(9):524–544, Dec. 1963.

    Google Scholar 

  36. Wise, D.S. Design for a multiprocessing heap with on-board reference counting. In Functional Programming Languages and Computer Architecture, J.-P. Jouannaud (Ed.). Lecture Notes in Computer Science, Springer, Berlin, vol. 201, pp. 289–304, 1985.

    Google Scholar 

  37. Wise, D.S. Undulant block elimination and integer-preserving matrix inversion. Sci. Comput. Programming, (to appear).

  38. Wise, D.S. and Franco, J. Costs of quadtree representation of non-dense matrices. J. Parallel Distrib. Comput., 9(3):282–296, July 1990.

    Google Scholar 

  39. Wise, D.S. and Walgenbach, J. Static and dynamic partitioning of pointers as links and threads. Proc. 1996 Intl. Conf. on Functional Programming, ACM SIGPLAN Notices, vol. 31, no. 6, pp. 42–49, June 1996.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Indiana University, Bloomington, Indiana, 47405-4101, USA

    David S. Wise, Brian Heck, Caleb Hess & Willie Hunt

  2. Computer Science Department and Center for Innovative Computer Applications, Indiana University, Bloomington, Indiana, 47405, USA

    Eric Ost

Authors
  1. David S. Wise
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Brian Heck
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Caleb Hess
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Willie Hunt
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Eric Ost
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wise, D.S., Heck, B., Hess, C. et al. Research Demonstration of a Hardware Reference-Counting Heap. Higher-Order and Symbolic Computation 10, 159–181 (1997). https://doi.org/10.1023/A:1007715101339

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1007715101339

Search

Navigation