Re: Promptness of collection

Eliot Moss wrote:
> How could this be? A mark-sweep collector cannot reclaim an object while
> it is referenced, and (unless you have a lot of smarts in an optimizing
compiler
> or something) the reference persists until the scope is exited.

Exactly as you say, compilers don't necessarily keep references in registers
or on the stack until the "end of scope". They use liveness analysis to
determine when registers and stack space can be reused.

I tested this a while back with OCaml and found that it often reclaims
values before the end of scope of a variable that refers to them.

Here is a simple example using F# on .NET:

let rec loop = function
  | 0 -> ()
  | i ->
      let tmp = List.init n id
      printfn "%d" (System.GC.GetTotalMemory false)
      loop(i-1)
      loop(i-1)

This "loop" function creates a temporary linked list, prints out how much
memory is in use and recurses twice. If references were held until the end
of scope this function would leak. Even if we account for the fact that tail
call optimization should remove the reference to "tmp" during the second
recursive call to "loop", we would still expect the first call to leak.
However, measurements show that there is no evidence of any leak at all.
Thus, the reference must have been removed before even the first recursive
call. Frankly, if .NET didn't do this I'd call it a bug because it would
break most of my production code!

In contrast, reference counted smart pointers retain references to the end
of scope whether they are required or not, leading to floating garbage. I
also compared some programs written in OCaml and C++ and often found that
OCaml was more space efficient which leads me to believe that scope-based
reference counting generates quite a bit of floating garbage. Hence I am
concerned when I see published literature assert the opposite without
justification, especially in the context of deferred reference counting
which presumably exacerbates this problem.

Furthermore, a generational mark-sweep collector wastes no more than a
constant amount of space for the majority of values that do not survive the
nursery. Floating garbage in the nursery just makes nursery collections more
frequent.

> Presumably when reference counting, an explicit assignment of null will
> decrement the reference count immediately.

Yes. Better yet, the compiler could automatically remove references for you
according to liveness analysis instead of scope. That would be competitive
with tracing collectors. However, I don't believe that is being done and it
is not clear what affect it would have on the results. For example, I have
also observed that small perturbations from LIFO allocation/deallocation
order can have a dramatic effect on performance, presumably due to locality.

Also, I'd stress that nulling is not likely to achieve optimal promptness in
the general case. For example, programs often carry references to data that
they end up never using again. Although that is theoretically collectable
data you'd probably have to solve the halting problem to collect it in
practice. Therefore, reference counting and tracing GCs are somewhere in the
middle of a sliding scale in terms of floating garbage. Has any research
tried to quantify where exactly they are on this scale?

Cheers,
Jon.