article

Research Demonstration of a Hardware Reference-Counting Heap

Authors:

Eric OstAuthors Info & Claims

Lisp and Symbolic Computation, Volume 10, Issue 2

Pages 159 - 181

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

Published: 01 July 1997 Publication History

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.

References

[1]

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

Digital Library

[2]

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.

Digital Library

[3]

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

Digital Library

[4]

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.

[5]

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

Digital Library

[6]

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

[7]

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

Digital Library

[8]

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

Digital Library

[9]

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

Digital Library

[10]

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.

Digital Library

[11]

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.

Digital Library

[12]

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.

Digital Library

[13]

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

Digital Library

[14]

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

[15]

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]

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]

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.

[18]

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.

Digital Library

[19]

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

Digital Library

[20]

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

Digital Library

[21]

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.

Digital Library

[22]

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.

Digital Library

[23]

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.

Digital Library

[24]

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.

Digital Library

[25]

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

Digital Library

[26]

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

Digital Library

[27]

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

Digital Library

[28]

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.

Digital Library

[29]

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.

Digital Library

[30]

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

Digital Library

[31]

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.

Digital Library

[32]

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

Digital Library

[33]

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.

Digital Library

[34]

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.

Digital Library

[35]

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

Digital Library

[36]

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.

[37]

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

Digital Library

[38]

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.

[39]

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.

Digital Library

Cited By

Ismail MSuh G(2018)Hardware-software co-optimization of memory management in dynamic languagesACM SIGPLAN Notices10.1145/3299706.321056653:5(45-58)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3299706.3210566
Ismail MSuh GPayer HSartor J(2018)Hardware-software co-optimization of memory management in dynamic languagesProceedings of the 2018 ACM SIGPLAN International Symposium on Memory Management10.1145/3210563.3210566(45-58)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3210563.3210566
Joao JMutlu OPatt Y(2009)Flexible reference-counting-based hardware acceleration for garbage collectionACM SIGARCH Computer Architecture News10.1145/1555815.155580637:3(418-428)Online publication date: 20-Jun-2009
https://dl.acm.org/doi/10.1145/1555815.1555806
Show More Cited By

Recommendations

Flexible reference-counting-based hardware acceleration for garbage collection
ISCA '09: Proceedings of the 36th annual international symposium on Computer architecture

Languages featuring automatic memory management (garbage collection) are increasingly used to write all kinds of applications because they provide clear software engineering and security advantages. Unfortunately, garbage collection imposes a toll on ...
Flexible reference-counting-based hardware acceleration for garbage collection

Languages featuring automatic memory management (garbage collection) are increasingly used to write all kinds of applications because they provide clear software engineering and security advantages. Unfortunately, garbage collection imposes a toll on ...
Controlling garbage collection and heap growth to reduce the execution time of Java applications

In systems that support garbage collection, a tension exists between collecting garbage too frequently and not collecting it frequently enough. Garbage collection that occurs too frequently may introduce unnecessary overheads at the risk of not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Lisp and Symbolic Computation

Lisp and Symbolic Computation Volume 10, Issue 2

July 1997

81 pages

ISSN:0892-4635

Editors:
Robert R. Kessler
Univ. of Utah, Salt Lake City
,
Carolyn Talcott
Stanford Univ., Stanford, CA

Issue’s Table of Contents

Copyright © Copyright © 1997 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 July 1997

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ismail MSuh G(2018)Hardware-software co-optimization of memory management in dynamic languagesACM SIGPLAN Notices10.1145/3299706.321056653:5(45-58)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3299706.3210566
Ismail MSuh GPayer HSartor J(2018)Hardware-software co-optimization of memory management in dynamic languagesProceedings of the 2018 ACM SIGPLAN International Symposium on Memory Management10.1145/3210563.3210566(45-58)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3210563.3210566
Joao JMutlu OPatt Y(2009)Flexible reference-counting-based hardware acceleration for garbage collectionACM SIGARCH Computer Architecture News10.1145/1555815.155580637:3(418-428)Online publication date: 20-Jun-2009
https://dl.acm.org/doi/10.1145/1555815.1555806
Joao JMutlu OPatt YKeckler SBarroso L(2009)Flexible reference-counting-based hardware acceleration for garbage collectionProceedings of the 36th annual international symposium on Computer architecture10.1145/1555754.1555806(418-428)Online publication date: 20-Jun-2009
https://dl.acm.org/doi/10.1145/1555754.1555806
Boehm H(2004)The space cost of lazy reference countingACM SIGPLAN Notices10.1145/982962.96401939:1(210-219)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1145/982962.964019
Boehm HJones NLeroy X(2004)The space cost of lazy reference countingProceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/964001.964019(210-219)Online publication date: 14-Jan-2004
https://dl.acm.org/doi/10.1145/964001.964019
Meyer M(2004)A Novel Processor Architecture with Exact Tag-Free PointersIEEE Micro10.1109/MM.2004.224:3(46-55)Online publication date: 1-May-2004
https://dl.acm.org/doi/10.1109/MM.2004.2
Srisa-an WDan Lo CChang J(2003)Active Memory ProcessorIEEE Transactions on Mobile Computing10.1109/TMC.2003.12172302:2(89-101)Online publication date: 1-Apr-2003
https://dl.acm.org/doi/10.1109/TMC.2003.1217230
Roth DWise D(1998)One-bit counts between unique and stickyACM SIGPLAN Notices10.1145/301589.28686634:3(49-56)Online publication date: 1-Oct-1998
https://dl.acm.org/doi/10.1145/301589.286866
Roth DWise DJones SJones R(1998)One-bit counts between unique and stickyProceedings of the 1st international symposium on Memory management10.1145/286860.286866(49-56)Online publication date: 1-Oct-1998
https://dl.acm.org/doi/10.1145/286860.286866

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents