research-article

Open access

Reference counting with frame limited reuse

Authors:

Anton Lorenzen,

Daan LeijenAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 6, Issue ICFP

Article No.: 103, Pages 357 - 380

https://doi.org/10.1145/3547634

Published: 31 August 2022 Publication History

Abstract

The recently introduced _Perceus_ algorithm can automatically insert reference count instructions such that the resulting (cycle-free) program is _garbage free_: objects are freed at the very moment they can no longer be referenced. An important extension is reuse analysis. This optimization pairs objects of known size with fresh allocations of the same size and tries to reuse the object in-place at runtime if it happens to be unique. Unfortunately, current implementations of reuse analysis are fragile with respect to small program transformations, or can cause an arbitrary increase in the peak heap usage. We present a novel _drop-guided_ reuse algorithm that is simpler and more robust than previous approaches. Moreover, we generalize the linear resource calculus to precisely characterize garbage-free and frame-limited evaluations. On each function call, a frame-limited evaluation may hold on to memory longer if the size is bounded by a constant factor. Using this framework we show that our drop-guided reuse _is_ frame-limited and find that an implementation of our new reuse approach in Koka can provide significant speedups.

References

[1]

Andrew W. Appel. 1991. Compiling with Continuations. Cambridge University Press. https://doi.org/10.1017/CBO9780511609619

[2]

Erik Barendsen and Sjaak Smetsers. 1996. Uniqueness typing for functional languages with graph rewriting semantics. Mathematical Structures in Computer Science, 6, 6 (1996), 579–612. https://doi.org/10.1017/S0960129500070109

[3]

Jeffrey M. Barth. 1975. Shifting Garbage Collection Overhead to Compile Time. EECS Department, University of California, Berkeley. https://doi.org/10.1145/359636.359713

Digital Library

[4]

Jean-Philippe Bernardy, Mathieu Boespflug, Ryan R. Newton, Simon Peyton Jones, and Arnaud Spiwack. 2017. Linear Haskell: Practical Linearity in a Higher-Order Polymorphic Language. Proc. ACM Program. Lang., 2, POPL (2017), Article 5, Dec., 29 pages. https://doi.org/10.1145/3158093

Digital Library

[5]

Hans Boehm. 2000. GC bench. https://hboehm.info/gc/gc_bench

[6]

Edwin Brady. 2021. Idris 2: Quantitative Type Theory in Practice. In 35th European Conference on Object-Oriented Programming (ECOOP 2021), Anders Møller and Manu Sridharan (Eds.) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 194). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany. 9:1–9:26. isbn:978-3-95977-190-0 issn:1868-8969 https://doi.org/10.4230/LIPIcs.ECOOP.2021.9

[7]

Jawahar Chirimar, Carl A. Gunter, and Jon G. Riecke. 1996. Reference Counting as a Computational Interpretation of Linear Logic. Journal of Functional Programming, 6 (1996), 6–2. https://doi.org/10.1017/S0956796800001660

[8]

Jiho Choi, Thomas Shull, and Josep Torrellas. 2018. Biased Reference Counting: Minimizing Atomic Operations in Garbage Collection. In Proceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques (PACT ’18). Article 35, 12 pages. https://doi.org/10.1145/3243176.3243195

Digital Library

[9]

George E Collins. 1960. A method for overlapping and erasure of lists. Commun. ACM, 3, 12 (1960), 655–657. https://doi.org/10.1145/367487.367501

Digital Library

[10]

Karl Crary and Stephnie Weirich. 2000. Resource Bound Certification. In Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’00). 184–198. https://doi.org/10.1145/325694.325716

Digital Library

[11]

Edsko de Vries, Rinus Plasmeijer, and David M. Abrahamson. 2008. Uniqueness Typing Simplified. In Implementation and Application of Functional Languages (IFL’08), Olaf Chitil, Zoltán Horváth, and Viktória Zsók (Eds.). Springer, 201–218. isbn:978-3-540-85373-2 https://doi.org/10.1007/978-3-540-85373-2_12

Digital Library

[12]

Damien Doligez and Xavier Leroy. 1993. A Concurrent, Generational Garbage Collector for a Multithreaded Implementation of ML. In Proceedings of the 20th ACM Symposium on Principles of Programming Languages (POPL). ACM press, 113–123. https://doi.org/10.1145/158511.158611

Digital Library

[13]

Gaspard Férey and Natarajan Shankar. 2016. Code Generation Using a Formal Model of Reference Counting. In NASA Formal Methods, Sanjai Rayadurgam and Oksana Tkachuk (Eds.). Springer International Publishing, 150–165. isbn:978-3-319-40648-0 https://doi.org/10.1007/978-3-319-40648-0_12

Digital Library

[14]

Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen. 1993. The Essence of Compiling with Continuations. In Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation (PLDI ’93). 237–247. https://doi.org/10.1145/155090.155113

Digital Library

[15]

Free Software Foundation, Silicon Graphics, and Hewlett–Packard Company. 1994. Internal red-black tree implemention for ßtl::map". https://github.com/gcc-mirror/gcc/tree/master/libstdc++-v3/src/c++98/tree.cc

[16]

Matt Gallagher. 2016. Reference Counted Releases in Swift. Dec., https://www.cocoawithlove.com/blog/resources-releases-reentrancy.html Blog post.

[17]

The Computer Language Benchmark Game. 2021. binarytrees. Nov., https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/binarytrees.html

[18]

Clemens Grelck and Kai Trojahner. 2004. Implicit Memory Management for SAC. In 6th International Workshop on Implementation and Application of Functional Languages (IFL’04).

[19]

Leo J Guibas and Robert Sedgewick. 1978. A dichromatic framework for balanced trees. In 19th Annual Symposium on Foundations of Computer Science (sfcs 1978). 8–21. https://doi.org/10.1109/SFCS.1978.3

Digital Library

[20]

Paul Hudak and Adrienne Bloss. 1985. The Aggregate Update Problem in Functional Programming Systems. In Proceedings of the 12th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL ’85). ACM, 300–314. isbn:0897911474 https://doi.org/10.1145/318593.318660

Digital Library

[21]

Gérard P. Huet. 1997. The Zipper. Journal of Functional Programming, 7, 5 (1997), 549–554. https://doi.org/10.1017/S0956796897002864

Digital Library

[22]

Daan Leijen. 2014. Koka: Programming with Row Polymorphic Effect Types. In MSFP’14, 5th workshop on Mathematically Structured Functional Programming. https://doi.org/10.4204/EPTCS.153.8

[23]

Daan Leijen. 2017. Type Directed Compilation of Row-typed Algebraic Effects. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL’17). 486–499. isbn:978-1-4503-4660-3 https://doi.org/10.1145/3009837.3009872

Digital Library

[24]

Daan Leijen. 2021. The Koka Language. https://koka-lang.github.io

[25]

Daan Leijen, Zorn Ben, and Leo de Moura. 2019. Mimalloc: Free List Sharding in Action. Programming Languages and Systems, 11893 (2019), https://doi.org/10.1007/978-3-030-34175-6_13 APLAS’19.

[26]

Anton Lorenzen and Daan Leijen. 2021. Reference Counting with Frame Limited Reuse (extended version). Microsoft Research.

[27]

Anton Lorenzen and Daan Leijen. 2022. Implementation and Benchmarks for "Reference Counting with Frame-Limited Reuse". https://doi.org/10.5281/zenodo.6946310 Also available at <https://hub.docker.com/r/daanx/icfp22-reuse>.

Digital Library

[28]

Conor McBride. 2001. The Derivative of a Regular Type is its Type of One-Hole Contexts. http://strictlypositive.org/diff.pdf (Extended Abstract).

[29]

J. McGraw, S. Skedzielewski, S. Allan, D. Grit, R. Oldehoeft, J. Glauert, I. Dobes, and P. Hohensee. 1983. SISAL: streams and iteration in a single-assignment language. Language reference manual, Version 1. 1. Lawrence Livermore National Lab., CA, USA.

[30]

Yasuhiko Minamide. 1999. Space-Profiling Semantics of the Call-by-Value Lambda Calculus and the CPS Transformation. Electronic Notes in Theoretical Computer Science, 26 (1999), 105–120. issn:1571-0661 https://doi.org/10.1016/S1571-0661(05)80286-5 HOOTS ’99, Higher Order Operational Techniques in Semantics.

[31]

Yaron Minsky, Anil Madhavapeddy, and Jason Hickey. 2012. Real World OCaml: Functional programming for the masses. isbn:978-1449323912 https://dev.realworldocaml.org

[32]

Leonardo de Moura and Sebastian Ullrich. 2021. The Lean 4 Theorem Prover and Programming Language. In Automated Deduction – CADE 28, André Platzer and Geoff Sutcliffe (Eds.). 625–635. https://doi.org/10.1007/978-3-030-79876-5_37

Digital Library

[33]

Chris Okasaki. 1999. Purely Functional Data Structures. Colombia University. isbn:9780521663502

Digital Library

[34]

Chris Okasaki. 1999. Red-black trees in a functional setting. Journal of Functional Programming, 9, 4 (1999), 471–477. https://doi.org/10.1017/S0956796899003494

Digital Library

[35]

Zoe Paraskevopoulou and Andrew W Appel. 2019. Closure conversion is safe for space. Proceedings of the ACM on Programming Languages, 3, ICFP (2019), 1–29. https://doi.org/10.1145/3341687

Digital Library

[36]

Gordon D. Plotkin and John Power. 2003. Algebraic Operations and Generic Effects. Applied Categorical Structures, 11, 1 (2003), 69–94. https://doi.org/10.1023/A:1023064908962

[37]

Gordon D. Plotkin and Matija Pretnar. 2009. Handlers of Algebraic Effects. In 18th European Symposium on Programming Languages and Systems (ESOP’09). 80–94. https://doi.org/10.1007/978-3-642-00590-9_7

Digital Library

[38]

Reinking ḩar 44 Xie, de Moura, and Leijen. 2021. Perceus: Garbage Free Reference Counting with Reuse. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2021). ACK, New York, NY, USA. 96–111. https://doi.org/10.1145/3453483.3454032

Digital Library

[39]

Sven-Bodo Scholz. 2003. Single Assignment C: Efficient Support for High-Level Array Operations in a Functional Setting. Journal of Functional Programming, 13, 6 (2003), Nov., 1005–1059. https://doi.org/10.1017/S0956796802004458

Digital Library

[40]

H. Schorr and W. M. Waite. 1967. An Efficient Machine-Independent Procedure for Garbage Collection in Various List Structures. Comm. ACM, 10, 8 (1967), Aug., 501–506. issn:0001-0782 https://doi.org/10.1145/363534.363554

Digital Library

[41]

KC Sivaramakrishnan, Stephen Dolan, Leo White, Sadiq Jaffer, Tom Kelly, Anmol Sahoo, Sudha Parimala, Atul Dhiman, and Anil Madhavapeddy. 2020. Retrofitting Parallelism onto OCaml. Proc. ACM Program. Lang., 4, ICFP (2020), Article 113, Aug., 30 pages. https://doi.org/10.1145/3408995

Digital Library

[42]

David N. Turner and Phillip Wadler. 1999. Operational interpretations of linear logic. 231–248. https://doi.org/10.1016/S0304-3975(99)00054-7

Digital Library

[43]

Sebastian Ullrich and Leonardo de Moura. 2019. Counting Immutable Beans – Reference counting optimized for purely functional programming. In Proceedings of the 31st symposium on Implementation and Application of Functional Languages (IFL’19). https://doi.org/10.1145/3412932.3412935

Digital Library

[44]

David Ungar, David Grove, and Hubertus Franke. 2017. Dynamic Atomicity: Optimizing Swift Memory Management. In Proceedings of the 13th ACM SIGPLAN International Symposium on on Dynamic Languages (DLS 2017). 15–26. https://doi.org/10.1145/3133841.3133843

Digital Library

[45]

Phillip Wadler. 1990. Linear Types can Change the World!. In Programming Concepts and Methods.

[46]

Andrew K. Wright and Matthias Felleisen. 1994. A syntactic approach to type soundness. Inf. Comput., 115, 1 (1994), Nov., 38–94. https://doi.org/10.1006/inco.1994.1093

Digital Library

[47]

Ningning Xie and Daan Leijen. 2021. Generized Evidence Passing for Effect Handlers – Efficient Compilation of Effect Handlers to C. In Proceedings of the 26th ACM SIGPLAN International Conference on Functional Programming (ICFP’2021) (ICFP ’21). https://doi.org/10.1145/3473576

Digital Library

[48]

Danil Yarantsev. 2020. ORC - Nim’s cycle collector. Oct., https://nim-lang.org/blog/2020/10/15/introduction-to-arc-orc-in-nim.html

Cited By

Lorenzen ALeijen DSwierstra WLindley S(2024)The Functional Essence of Imperative Binary Search TreesProceedings of the ACM on Programming Languages10.1145/36563988:PLDI(518-542)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656398
Lorenzen ALeijen DSwierstra W(2023)FP²: Fully in-Place Functional ProgrammingProceedings of the ACM on Programming Languages10.1145/36078407:ICFP(275-304)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607840
Leijen DLorenzen A(2023)Tail Recursion Modulo Context: An Equational ApproachProceedings of the ACM on Programming Languages10.1145/35712337:POPL(1152-1181)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571233

Index Terms

Reference counting with frame limited reuse
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Control structures
        Polymorphism
2. Theory of computation
  1. Logic
    1. Type theory

Recommendations

Perceus: garbage free reference counting with reuse
PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

We introduce Perceus, an algorithm for precise reference counting with reuse and specialization. Starting from a functional core language with explicit control-flow, Perceus emits precise reference counting instructions such that (cycle-free) programs ...
Unanticipated reuse of large-scale software features
ICSE '06: Proceedings of the 28th international conference on Software engineering

Software reuse has been endorsed as a way to reduce development times and costs while increasing software quality and reliability. Techniques designed to encourage software reuse have concentrated on creating reusable software in the form of frameworks, ...
Towards specifying pragmatic software reuse
ECSAW '15: Proceedings of the 2015 European Conference on Software Architecture Workshops

Software reuse has numerous benefits, including reduced development time, defect density, and increased developer productivity. Numerous approaches to software reuse have been developed and we can divide them into two categories: preplanned approaches, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 6, Issue ICFP

August 2022

959 pages

EISSN:2475-1421

DOI:10.1145/3554306

Editor:
Philip Wadler
University of Edinburgh, UK

Issue’s Table of Contents

Copyright © 2022 Owner/Author.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 August 2022

Published in PACMPL Volume 6, Issue ICFP

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
696
Total Downloads

Downloads (Last 12 months)240
Downloads (Last 6 weeks)35

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lorenzen ALeijen DSwierstra WLindley S(2024)The Functional Essence of Imperative Binary Search TreesProceedings of the ACM on Programming Languages10.1145/36563988:PLDI(518-542)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656398
Lorenzen ALeijen DSwierstra W(2023)FP²: Fully in-Place Functional ProgrammingProceedings of the ACM on Programming Languages10.1145/36078407:ICFP(275-304)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607840
Leijen DLorenzen A(2023)Tail Recursion Modulo Context: An Equational ApproachProceedings of the ACM on Programming Languages10.1145/35712337:POPL(1152-1181)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571233

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents