I often see people assert that reference counting techniques such as shared_ptr
in C++ provide prompt collection (e.g. here and here) but I am not sure what exactly is meant by this. Some people tell me that they mean "collects at the earliest possible point" but I think that is not true of scope-based reference counting because it defers collection to the end of scope even if a variable is dead. Therefore, I'm wondering if other people have a different interpretation that may be correct.
Do computer scientists use the term "prompt" in this context and, if so, what do they mean by it?
More concretely, I once studied the behaviour of various OCaml and F# programs and found that they often collect values before they fall out of scope and, therefore, more "promptly" than scope-based reference counting. For example, the following function runs in bounded memory:
let rec loop tmp i =
if i<=0 then tmp else
loop (Array.copy (loop (Array.copy tmp) (i-1))) (i-100)
Even though the argument tmp
is in scope for the entire body of the function it is collected before even the first recursive call to loop
.
EDIT Here is a simpler F# example with a single recursive call and some post-processing to ensure that the call is not in tail position so it cannot be eliminated:
let rec loop tmp i =
if i<=0 then tmp else
let tmp = loop (Array.copy tmp) (i-1)
tmp.[0] <- tmp.[0] + 1
tmp
Between the copying of the array and the call to loop
the argument tmp
dies and, indeed, I find that it is garbage collected so this program requires only O(1) space.
Here is the equivalent reference counted C++:
shared_ptr<vector<double> > loop(shared_ptr<vector<double> > tmp, int i) {
if (i<=0) {
return tmp;
} else {
shared_ptr<vector<double> > tmp1(new vector<double>(*tmp));
shared_ptr<vector<double> > tmp2 = loop(tmp1, i-1);
++(*tmp2)[0];
return tmp2;
}
}
Although tmp
dies between the creation of tmp1
and the call to loop
, scope-based reference counting keeps it allocated until the end of scope. So n
recursive calls require O(n) space.