What does “prompt collection” mean in the context of memory management?

Question

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.

Answer 1

Do computer scientists use the term "prompt" in this context and, if so, what do they mean by it?

What is meant by prompt, is that it is guaranteed to be deleted and more importantly, destructed, when it goes out of scope. The main point of this, is to take advantage of the mainly-C++-ish paradigm of Resource Acquisition Is Initialization.

Look at the following program in pythonish:

def procedure():
  f = open('path')

  ... #use f

def main():
  procedure()
  #f *might* still be alive here, which means it is hogging a file resource

So, languages like python therefore must supply some manual cleanup methods. One is supposed to call f.close() before leaving procedure(). However, this can be error prone, because of early-return (you must remember to close at every return, and remember this when changing code later; it is very cumbersome) and exception safety (what if somewhere before returning, something throws an exception?, then your f.close();return isn't called at all).

The C++ solution to this is very elegant; when things go out of scope, they are guaranteed to call a destructor. The destructor of a resource object will/should clean up the resource. So you have the following code in C++:

void procedure(){
  std::ofstream f("path");
  ... //do stuff with f
  // we *can* call f.close(), but we don't have to, because f::~() (the destructor) will clean it up, and it is guaranteed to be called when going out of scope.
}

The python solution to this is to use the finally exception block like so:

def procedure():
  f = open('path')
  try:
    ... #use f
  finally:
    f.close()
def main():
  procedure()

Alternatively, there is some syntax sugar for some special resource classes (you can add this to any custom class as well) that accomplishes the same thing:

def procedure():
  with open('path') as f:
    ... #use f
  #f.close() is called once out of "scope" of the with; it is essentially the same as the finally block.
def main():
  procedure()

So it is simply two different paradigms; C++'s concept of the "on-the-stack" objects allows self-cleanup, python and most other languages require manual cleanup, but enjoy garbage collection.

Now, the issue is, pointers don't have destructors; they are essentially POD (plain old data). Therefore, if you want to keep an object around longer, you would allocate it on the heap, and save a pointer to it, but you must manually call the destructor (via delete ptr;), but only when you "know" you are done with it. In many situations, it is hard to know when you are done with a pointer, for example, if it is used in many places ("shared ownership"); therefore a reference counter such as shared_ptr can be used, and the underlying objected that is pointed to will be destructed (the destructor will be called) "promptly" when it goes out of scope, ie. when the last user gets rid of the pointer.

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.

This is probably not guaranteed though. A garbage collector can decide to clean things up whenever it wants to, they usually don't take resources other than memory into consideration, and AFAIK, never provide any such guarantees. C++, and the finally blocks provide guarantees of resource cleanup.

Answer 2

I have never heard the term "prompt" used in a technical sense with regard to memory management or reference counting. "No longer than the lifetime of the last pointer to the object" would be accurate (and that is not true of OCaml or F#).

I don't really understand your example, (why is tmp getting garbage collected before the second call to array.copy tmp?) but I think you may be confusing C++'s "automatic (stack allocated) variables have a destructor that is called when the variable goes out of scope," with "reference counted." In C++ you mainly use reference counted pointers when you don't know the scope of the dynamically allocated object (and so, in cases where there may be another pointer to the memory, which means that it is not dead yet.)

Your example is not demonstrating a problem with reference counting so much as it is demonstrating that C++ doesn't have tail recursion elimination in the language definition (or in most compilers), so you can't use recursion to do looping. The similarly double nested loop in C++ would, I think, look something like this:

void
loop(vector<foo> tmp, int i)
{
top_label:
   if (i > 0) {
     do {
       auto mem = System.GC.GetTotalMemory(false) // whatever this means
       if (mem > maxMem) maxMem = mem;            // and what is maxMem?
       tmp = tmp;     // call the assignment operator (which does nothing in this case.)
       i--;           // mem goes out of scope on every loop iteration
     } while (i > 0);
     tmp = tmp;  
     i = 0;
     goto top_label;
  }
}

There's no reference counting, but there are automatic stack-allocated variables. Whereas in OCaml you really do make a copy, and then delete the original (because the compiler is doing tail recursion elimination) in C++ you call the assignment operator, which by convention is required to test for equality of the source and destination and do nothing.