article

Free access

Improving locality of reference in a garbage-collecting memory management system

Author:

Robert CourtsAuthors Info & Claims

Communications of the ACM, Volume 31, Issue 9

Pages 1128 - 1138

https://doi.org/10.1145/48529.48536

Published: 01 September 1988 Publication History

PDF eReader

Abstract

Modern Lisp systems make heavy use of a garbage-collecting style of memory management. Generally, the locality of reference in garbage-collected systems has been very poor. In virtual memory systems, this poor locality of reference generally causes a large amount of wasted time waiting on page faults or uses excessively large amounts of main memory. An adaptive memory management algorithm, described in this article, allows substantial improvement in locality of reference. Performance measurements indicate that page-wait time typically is reduced by a factor of four with constant memory size and disk technology. Alternately, the size of memory typically can be reduced by a factor of two with constant performance.

References

[1]

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

Digital Library

Google Scholar

[2]

2. Cohen, J. Garbage collection of linked data structures. Comp. Surv., 13, 3 (Sept. 1981), 341-367.

Digital Library

Google Scholar

[3]

3. Lieberman, H., and Hewitt, C. A real-time garbage collector based on the lifetimes of objects. Commun. ACM 26, 6 (June 1983), 419-429.

Digital Library

Google Scholar

[4]

4. Moon, D. A. Garbage collection in a large lisp system. In Proceedings of the 1984 ACM Symposium on Lisp and Functional Programming (August 1984). ACM, New York, 235-246.

Digital Library

Google Scholar

Cited By

View all

Norlinder JYang ABlack-Schaffer DWrigstad TErtl MKirsch C(2024)Mutator-Driven Object Placement using Load BarriersProceedings of the 21st ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3679007.3685060(14-27)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3679007.3685060
Wanninger NMcMichen TCampanoni SDinda PTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Getting a Handle on Unmanaged MemoryProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651326(448-463)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651326
Gast NIoannidis SLoiseau PRoussillon B(2020)Linear Regression from Strategic Data SourcesACM Transactions on Economics and Computation10.1145/33914368:2(1-24)Online publication date: 13-May-2020
https://dl.acm.org/doi/10.1145/3391436
Show More Cited By

Index Terms

Recommendations

Locality and Duplication-Aware Garbage Collection for Flash Memory-Based Virtual Memory Systems
CIT '10: Proceedings of the 2010 10th IEEE International Conference on Computer and Information Technology

As embedded systems adopt monolithic kernels, NAND flash memory is used for swap space of virtual memory systems. While flash memory has the advantages of low-power consumption, shock-resistance and non-volatility, it requires garbage collections due to ...
A locality-improving dynamic memory allocator
MSP '05: Proceedings of the 2005 workshop on Memory system performance

In general-purpose applications, most data is dynamically allocated. The memory manager therefore plays a crucial role in application performance by determining the spatial locality of heap objects. Previous general-purpose allocators have focused on ...
Enabling Hybrid PCM Memory System with Inherent Memory Management
RACS '16: Proceedings of the International Conference on Research in Adaptive and Convergent Systems

Replacing the traditional volatile main memory, e.g., DRAM, with a non-volatile phase change memory (PCM) has become a possible solution to reduce the energy consumption of computing systems. To further reduce the bit cost of PCM, the development trend ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 31, Issue 9

Sept. 1988

109 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/48529

Editor:
Peter,J. Denning
NASA Ames Research Center, Moffett Field, CA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1988

Published in CACM Volume 31, Issue 9

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

95
Total Citations
View Citations
685
Total Downloads

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

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Norlinder JYang ABlack-Schaffer DWrigstad TErtl MKirsch C(2024)Mutator-Driven Object Placement using Load BarriersProceedings of the 21st ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3679007.3685060(14-27)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3679007.3685060
Wanninger NMcMichen TCampanoni SDinda PTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Getting a Handle on Unmanaged MemoryProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651326(448-463)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651326
Gast NIoannidis SLoiseau PRoussillon B(2020)Linear Regression from Strategic Data SourcesACM Transactions on Economics and Computation10.1145/33914368:2(1-24)Online publication date: 13-May-2020
https://dl.acm.org/doi/10.1145/3391436
Gairing MKollias KKotsialou G(2020)Existence and Efficiency of Equilibria for Cost-Sharing in Generalized Weighted Congestion GamesACM Transactions on Economics and Computation10.1145/33914348:2(1-28)Online publication date: 13-May-2020
https://dl.acm.org/doi/10.1145/3391434
Blelloch GHarper R(2015)Cache efficient functional algorithmsCommunications of the ACM10.1145/277682558:7(101-108)Online publication date: 25-Jun-2015
https://dl.acm.org/doi/10.1145/2776825
YOUNG LIYER R(2013)Error latency measurements in symbolic architectures8th Computing in Aerospace Conference10.2514/6.1991-3823Online publication date: 18-Feb-2013
https://doi.org/10.2514/6.1991-3823
Blelloch GHarper R(2013)Cache and I/O efficent functional algorithmsACM SIGPLAN Notices10.1145/2480359.242907748:1(39-50)Online publication date: 23-Jan-2013
https://dl.acm.org/doi/10.1145/2480359.2429077
Blelloch GHarper RGiacobazzi RCousot R(2013)Cache and I/O efficent functional algorithmsProceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/2429069.2429077(39-50)Online publication date: 23-Jan-2013
https://dl.acm.org/doi/10.1145/2429069.2429077
Sauvé JAbath Neto O(2008)Teaching software development with ATDD and easyacceptACM SIGCSE Bulletin10.1145/1352322.135231740:1(542-546)Online publication date: 12-Mar-2008
https://dl.acm.org/doi/10.1145/1352322.1352317
Beck LChizhik A(2008)An experimental study of cooperative learning in cs1ACM SIGCSE Bulletin10.1145/1352322.135220840:1(205-209)Online publication date: 12-Mar-2008
https://dl.acm.org/doi/10.1145/1352322.1352208
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Locality and Duplication-Aware Garbage Collection for Flash Memory-Based Virtual Memory Systems

A locality-improving dynamic memory allocator

Enabling Hybrid PCM Memory System with Inherent Memory Management

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations