What is the status of Weak References?

[David Bruant]

Le 03/02/2013 06:21, Brandon Benvie a écrit :
> Some people would say that garbage collection is the most important 
> advancement in computer science in the last 20 
> years....http://www.codinghorror.com/blog/2009/01/die-you-gravy-sucking-pig-dog.html
Don't get me wrong, I didn't say nor didn't mean to say that garbage 
collectors as a tool aren't awesome. I'm very happy that most of the 
time, I don't need to worry about releasing memory and that in most of 
the remaining cases, null-ing out a single reference makes an entire 
subgraph collectable.

However, like any tool, I think it's crucially important to understand 
the limitations of it. From the article you posted:
> Use your objects, and just walk away when you're done. The garbage 
> collector will cruise by periodically, and when he sees stuff you're 
> not using any more, he'll clean up behind you and deal with all that 
> nasty pointer and memory allocation stuff on your behalf. It's totally 
> automatic. 
"It's totally automatic". Here is someone who is not aware of the 
limitations of a garbage collector apparently.

Also from the article:
> *I view explicit disposal as more of an optimization than anything else*
Nonsense. I'm sorry, but this is fueling the fantasy. Manual disposal is 
necessary in cases where the GC cannot make the decision. And the GC 
cannot make a decision because it is an algorithm, bound by decidability.

I feel there is a lot of misconception about what a GC can and cannot 
do. Here is an article I wrote about memory management [1]. Here is 
probably the most important part of it:
> ## Release when the memory is not needed anymore
>
> Most of memory management issues come at this phase. The hardest task 
> here is to find when "the allocated memory is not needed any longer". 
> It often requires for the developer to determine where in the program 
> such piece of memory is not needed anymore and free it.
>
> High-level languages interpreter embed a piece of software called 
> "garbage collector" whose job is to track memory allocation and use in 
> order to find when a piece of allocated memory is not needed any 
> longer in which case, it will automatically free it. This process is 
> an approximation since the general problem of knowing whether some 
> piece of memory is needed is undecidable (can't be solved by an 
> algorithm).
The most important part of this section is "approximation". Every GC 
algorithm in existence has to approximate conservatively an answer to 
the question "will this piece of memory be used again?". As an aside, I 
prefer that the GC is conservative and doesn't abusively free memory I 
would actually still need. In other words, memory leaks are the price to 
pay for the memory to be reliable.

> ## Reference-counting garbage collection
>
> This is the most naive garbage collection algorithm. This algorithm 
> reduces the definition of "an object is not needed anymore" to "an 
> object has no other object referencing to it". An object is considered 
> garbage-collectable if there is zero reference pointing at this object.
> ## Mark-and-sweep algorithm
>
> This algorithm reduces the definition of "an object is not needed 
> anymore" to "an object is unreachable". [then definition of reachable 
> by explaining the root and the traversal]
And in both cases, I explain the limitations. I couldn't find a simple 
enough example to put in the documentation for the limitations of 
mark-and-sweep.
Let's try to make up a simple example:

     function Storage(){
         var storage = []
         return {
             push(e){storage.push(e)},
             last(){return storage[storage.length-1]};
         }
     }

     var s = new Storage();
     s.push({});
     s.push({});
     s.last();

In this example, we know, as human beings understanding the semantics of 
JavaScript, that all but last elements of storage could be collected. 
Because of its limited definition of "unreachable", the mark-and-sweep 
algorithm thinks these elements should be kept in memory.
Some serious static analysis might figure out (as we do, human beings 
understanding the semantics of JavaScript) that all but the last element 
of storage aren't needed anymore... This analysis needs to prove at some 
point that Array.prototype.push is a frozen property.
As a side note, as far as I know, all GC algorithms are runtime 
algorithms and deal with runtime "objects" and "references" and don't 
exploit static analysis/language-specific information.

Let's see how the example would be with weakrefs:

     function Storage(){
         var storage = []
         return {
             push(e){storage.push(makeWeakRef(e))},
             last(){
                 var last = storage[storage.length-1]
                 return last.get(); // oops!
             };
         }
     }

     var s = new Storage();
     s.push({});
     s.push({});
     s.last();

Interestingly, holding weakly the references in storage couldn't be of 
help here, it may be possible that the last element in the array has 
been GC'ed and that the call to .last doesn't return the element that 
was last pushed.

This example is dummy and unrealistic, but I hope shows the limitations 
of GCs. As I said, all GC algorithms are limited because the question 
"is this object still needed?" is undecidable. That's why there will 
always be cases where manually disposing is mandatory (and not an 
optimization like @codinghorror seems to think).


In any case, GC are awesome, the mark-and-sweep approximation goes a 
very very long way in helping developers not having to worry about 
memory, but like any GC algorithms existing and upcoming, its definition 
of "is this object no longer needed?" is limited and it's crucially 
important to understand this limitation. Since the GC is limited, there 
will *always* be cases where human beings need to manually do some work 
to tell the GC "hey, this is collectable"

I don't want to go too far in the self-promotion, but since I'm writing 
about GC, it seems on topic... For anyone who'd be interested, I'll be 
talking about that at Fluent in San Fransisco in May
http://fluentconf.com/fluent2013/public/schedule/detail/27841

David

[1] https://developer.mozilla.org/en-US/docs/JavaScript/Memory_Management
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20130203/8a96148f/attachment.html>