3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So you agree that reference counting with shared_ptr in C++ defers collection until the end of scope? $\endgroup$ – Jon Harrop Oct 13 '13 at 23:21
  • $\begingroup$ @JonHarrop C++ stack objects don't know about "collection", only of scope. So yes, reference counting with shared_ptr in C++ defers collection until it goes out of "scope" or is explicitly cleared, but it doesn't just defer collection to the end of scope, it also guarantees collection at the end of scope, and guarantees a call to the destructor at the end of scope. $\endgroup$ – Realz Slaw Oct 14 '13 at 1:25
  • $\begingroup$ For single threaded programs, yes. Consider a multithreaded program with thread-safe shared_ptrs to a single object. When the object falls out of scope in each thread that thread atomically decrements the object's counter. But they are racing to decrement to zero and the thread that wins is burdened with cleanup. So it is non-deterministic in general. $\endgroup$ – Jon Harrop Oct 14 '13 at 13:24
  • $\begingroup$ @JonHarrop C++ never took threading into account much, though there are things in the runtime libs that now do take threading into account, including shared_ptr, it never guaranteed "determinism" of this sort, so it is true that this is non-deterministic. But this isn't really a "problem", and I'll continue in another comment explaining why. $\endgroup$ – Realz Slaw Oct 14 '13 at 13:46
  • 1
    $\begingroup$ @JonHarrop continuing ... In practice, if this is a problem, you can have a cleanup thread that shares the pointer, and cleans it up when there is only 1 reference left: the one from the cleanup thread (I've done this for a game thread loop, where cleanup is expensive, and I don't want it to stall). Or, you can use an extra layer of destruction which is lightweight, (like a nested shared_ptr) which only triggers an addition to the actual cleanup queue. Thus, C++ leaves this type of stuff entirely in your explicit control. $\endgroup$ – Realz Slaw Oct 14 '13 at 13:48
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I've clarified the first example and added a second to drive home the point that this is not due to tail call elimination. $\endgroup$ – Jon Harrop Oct 13 '13 at 23:19
  • $\begingroup$ "No longer than the lifetime of the last pointer to the object would be accurate". Is my code a counter example? The last pointer is clearly dead (after all, it gets garbage collected) yet reference counting keeps it alive for longer. $\endgroup$ – Jon Harrop Oct 14 '13 at 0:00
  • $\begingroup$ The reference counting is irrelevant. Replace the shared_ptr with unique_ptr (or just an automatically allocated vector) and you'll have the same problem. You're just upset that the C++ spec doesn't require the compiler to do whole-procedure analysis and optimization. C++ gives a well defined lifetime for automatic objects that has to do with their scope. Everything in C++ is designed to make it possible to write an efficient program even with a dumb compiler. If you don't like when the destructor is called, then dynamically allocate the pointer and explicitly free it. $\endgroup$ – Wandering Logic Oct 14 '13 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.