What is the main method for reclaiming the memory in LISP? Does LISP really need garbage collection? Would not reference counts suffice?
I just wanted to know whether reference counts are enough or not for
memory management in LISP, since I am not much familiar with LISP
language and other functional languages either.
Thanks.
6
Reference counting is basically never sufficient for managing memory due to cycles. If a language has mutation we can essentially create a structure like
-------------------
| | |
| Head | Tail |
| | |
-------------------
| | |
| +-------+
|
1 <+
I put way too much effort into this lousy diagram
Now that the head is pointed at the tail the counter for the object will never dip to 0, meaning it’ll lie around forever. This is a persistant issue for Perl and is the reason for the contortions with weak_prt
in C++.
Also frankly a good GC is orders of magnitude faster than reference counting. Bumping those counters constantly (particularly when you need to ensure thread safety) is actually not free. Clever things with generational/parallel garbage collection can give essentially pause free high performance code!
It’s a natural question to wonder why we couldn’t just start with malloc and free in Lisp and see where that takes us. In a language with closures, however, using manual memory management is a constant perilous battle. You are constantly in grave danger of closing over something with a slightly different lifetime and having things slowly pear-shaped. This complexity is noticeable in C++ with the fine grained notions of capturing and moving in and out of closures, even this destroys the time honored series of tricks in Lisp for simulating objects and other useful creatures.
TLDR: Garbage collection is actually pretty fast and reference counting is just too naive.
9
Naive reference counting cannot deal with cyclic data structures, since parts of the data structure will cause other parts to have a reference count higher than zero.
On the trivial end, Lisp (in general and Common Lisp in particular) allows you to create read-time cyclic “lists”: #1#=(red green blue . #1#)
is a never-ending list. They’re even useful, in their right place.
Less obvious, if you have a family tree with each person represented as a node with references to parents and children, you suddenly have a graph that cannot be cleaned up using only reference counting. Is it useful? To some extent, yes. It makes looking up both children and parents from a single node effectively O(1) instead of having one of them being effectively O(1) and the other being effectively O(population) (or, admittedly, you can use weak references).
Even less obvious, updating the reference count must by necessity happen at every time a reference is made or unmade and either requires a Read-Copy-Update or a lock acquisition and release. With a periodic GC policy, this is amortised across the whole interval.
4
Environment fragments in Lisp have an undetermined lifetime, most of the LISP implementations need garbage collection to reclaim free run-time store.