Our great sponsors
-
pen
The parallel, concurrent, and functional programming language for scalable software development (by pen-lang)
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
-
InfluxDB
Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
In this post, I describe my experience and some caveats about implementing and gaining benefits from the Perceus RC. I've been developing a programming language called Pen and implemented a large part of the Perceus RC there. I hope this post helps someone who is implementing the algorithm or even deciding if it's worth implementing it in their own languages.
By implementing all of those optimizations in the Koka programming language, they achieved GC overhead much less and execution time faster than the other languages including OCaml, Haskell, and even C++ in several algorithms and data structures that frequently keep common sub-structures of them, such as red-black trees. For more information, see the latest version of the paper.
Reference counting (RC) has rather been a minor party to the other garbage collection (GC) algorithms in functional programming in the last decades as, for example, OCaml and Haskell use non-RC GC. However, several recent papers, such as Counting Immutable Beans: Reference Counting Optimized for Purely Functional Programming and Perceus: Garbage Free Reference Counting with Reuse, showed the efficiency of highly optimized RC GC in functional languages with sacrifice or restriction of some language features like circular references. The latter paper introduced an efficient RC GC algorithm called Perceus which is basically all-in-one RC.
Finally, thanks for reading! I would appreciate your feedback on this post and the Pen programming language. The language's new release has been blocked by LLVM 14 adoption in Homebrew but the ticket had some progress in the last few weeks. So I can probably release v0.4 of it soon...
When your language has record types and syntax for record field access, things might be a little complex. Let's think about the following pseudo code where we want to update a recursive data structure of type A in place (The code is written in Elm but assume that we implemented it with Perceus.):