Assume we have some kind of class, let's call it Engine, with one unique
instance. We also have an abstract interface, let's call it EventListener,
which contains callback functions.

  Classes can implement the EventListener interface and register themselves
to the Engine object. The latter will call the callback functions of the
registered objects when certain events happen.

  In C++ we could do, for example, so that we create a class, let's call
it ListeningClass, which implements EventListener, and the constructor
of this class registers itself to the Engine object (by giving itself as
a raw pointer to it). The destructor of ListeningClass tells the Engine
object to remove this object from the list of callback objects.

  This is a safe thing to do: Whenever such object is destroyed, it
automatically tells the Engine object to remove that raw pointer from
its internal list of listener objects. Thus the Engine object will never
call a destroyed listener.

  Suppose that we have to instantiate ListeningClass dynamically for
whatever reasons (for example because it has to be shared). We can use
reference counting to handle this: No matter how much the object is
shared and moved around, when the last reference to it is destroyed,
the ListeningClass instance is also destroyed, which then causes it to be
removed from the Engine object. This works because the Engine object only
has a raw pointer to the callback object, not a reference-counted one.
(And, as noted previously, this is completely safe.)

  However, what happens in a GC'd language where you basically *can't*
implement a reference-counted system like this (which is the case eg.
with Java)?

  There's just *no way* for the ListeningClass to automatically tell the
Engine object to remove the reference to it because the former cannot
automatically know when it's not used anymore.

  This will cause the Engine object to hold onto the references to all
listener objects even if all the other references to those objects die.
Thus the object will never by garbage-collected.

  The only solution for this would be for the program to explicitly remove
listening objects from the Engine object when they are not used anymore.
However, this is error-prone, as we all know: Whenever you have to free
some resource manually there's a big chance that in some situations it
will never happen.
  If this is so, then what we have is a memory leak. In a GC'd system.

  Any ideas about how this sould be done instead?

-- 
                                                          - Warp

Post a reply to this message

It depends on the garbage collected language, but I think in Java this 
should do it:

http://java.sun.com/javase/6/docs/api/java/lang/ref/package-summary.html

in particular it looks like the WeakReference class would do what you want:

http://java.sun.com/javase/6/docs/api/java/lang/ref/package-summary.html

And also:

http://java.sun.com/javase/6/docs/api/java/util/WeakHashMap.html

I believe Python (and probably many other garbage collected languages as 
well) support similar functionality.

Post a reply to this message

Warp wrote:
>   However, what happens in a GC'd language where you basically *can't*
> implement a reference-counted system like this (which is the case eg.
> with Java)?

You can, of course. You're just reference counting whether the Listener 
is "alive" rather than whether the memory is still allocated.

Do all the same stuff, but maintain the reference counter yourself. 
(This can, of course, be difficult, if your language doesn't support 
automatically doing something when a pointer to an object leaves its scope.)

>   This will cause the Engine object to hold onto the references to all
> listener objects even if all the other references to those objects die.
> Thus the object will never by garbage-collected.

It's also the case the Engine will continue to send messages to the 
Listener, so you'll see it still behaving after you thought it was gone. 
Not a cure, but not hard to figure out what's going on, either.

>   The only solution for this would be for the program to explicitly remove
> listening objects from the Engine object when they are not used anymore.

As pointed out, this is part of what "weak references" were created for. 
If a GC runs and the only pointers to an object are "weak", then all the 
"weak" pointers get set to null, and your Engine can notice that and not 
try to use that pointer any more.

>   If this is so, then what we have is a memory leak. In a GC'd system.

It's definitely a problem. Some would argue that it's not technically a 
memory leak, but rather a failure to disconnect the Listener from the 
Engine. It's easier to diagnose (if it's deterministic, at least), 
because you see the Engine's list growing indefinitely. You don't lose 
memory and not know what's in it.

But yes, if you don't have weak references, you could have this 
situation. You can also have the situation where you think you're done 
with the object, you tell it to "close" itself (for whatever that 
means), and you fail to take it off the Engine's list, which means it 
still gets messages after it's no longer wanting to handle them.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

>>   If this is so, then what we have is a memory leak. In a GC'd system.
> 
> It's definitely a problem. Some would argue that it's not technically a 
> memory leak, but rather a failure to disconnect the Listener from the 
> Engine. It's easier to diagnose (if it's deterministic, at least), 
> because you see the Engine's list growing indefinitely. You don't lose 
> memory and not know what's in it.

It would be a leak if the Engine kept *strong* references to the 
Listeners. Then the Listeners would never get GC'd.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> You can, of course. You're just reference counting whether the Listener 
> is "alive" rather than whether the memory is still allocated.

> Do all the same stuff, but maintain the reference counter yourself. 
> (This can, of course, be difficult, if your language doesn't support 
> automatically doing something when a pointer to an object leaves its scope.)

  Can you mention some popular GC's languages where it's possible to
implement reference-counting of objects? AFAIK in Java it's not possible
(because there's no way for the object to detect if a reference to it
is copied or destroyed).

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   Can you mention some popular GC's languages where it's possible to
> implement reference-counting of objects? 

Hmmm. Well, of course you can implement the reference counting 
everywhere you assign or overwrite or dispose of a pointer of that type, 
but that's not what you mean. I can't think of any languages offhand 
that specify reference counting is built in but also allow you to do 
actions when pointers enter and leave scope, like you can in C++.

Maybe Objective-C? That's the only "popular" one I know of but don't 
know well enough to answer the question.

Of course, if you make a mistake anywhere in the reference counting 
doing this, you're going to have a memory leak just like any other 
manual memory management.

Weak references are the solution to this sort of thing, which also 
brings the benefit of being able to add the listener to more than one 
engine, for example. I don't think it's possible to reasonably implement 
weak references with a library without compiler support, at least in 
most GCed languages (which don't give you access to the internal data 
they use to do the GC).

Now, COP (concurrency-oriented programming) is a bit different. In 
languages where your objects tend to be "active", i.e., not only have 
code but have a stack and a program counter, the connections between 
objects are often tracable - you can tell when another process has 
connected to you, and when it has disconnected, and how many are 
connected. Some languages can, some can't, depending on whether they 
implement the connections as connections between processes or 
connections between ports/mailboxes.

But no, C++ is definitely more powerful in this respect. It would be 
nice to see a language that would invoke a finalize method any time it 
can statically deduce that some object is going to disappear at some 
particular point, or to let you mark some particular class as 
reference-counted, so as long as you don't get into circular references, 
it can get collected deterministically (and trigger finalizers).

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Darren New wrote:
> that specify reference counting is built in but also allow you to do 

Correction:
... that specify GC is built in ...

Regardless of GC mechanism, I don't know any langauge that automates the 
GC and also lets you track individual objects, in an OO language. Come 
of the concurrent languages do, but that's more for "has the person I'm 
talking to crashed out or lost their ISP connection" more than for this 
sort of task.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> As pointed out, this is part of what "weak references" were created for. 
> If a GC runs and the only pointers to an object are "weak", then all the 
> "weak" pointers get set to null, and your Engine can notice that and not 
> try to use that pointer any more.

  If the GC runs in parallel in its own thread, wouldn't there be a mutual
exclusion problem (even in 1-core processors)?

  Let's assume the Engine object does this:

if(listeners[i] != null)
  listeners[i].doSomething();

  If the GC happens to make a sweep after the conditional but before
the call, and it sets the weak reference at listeners[i] to null, we'll
get a null pointer exception (which may seem crazy because we just
checked that it's not null).

  Or are GC engines run only at places where there can't be mutual
exclusion problems? (How does the VM/compiler/interpreter know that?)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   If the GC happens to make a sweep after the conditional but before
> the call, and it sets the weak reference at listeners[i] to null, we'll
> get a null pointer exception (which may seem crazy because we just
> checked that it's not null).

Yes, except that's always possible in a multi-threaded system, if 
another thread sets the listeners[i] to null. :-)

Generally speaking, you can't invoke a weak reference like that. Most 
systems get around the problem by having a function (which has to be 
built-in, you can't implement it yourself) that takes a weak reference 
and returns either null or a strong reference; *that* really is the 
point where the weak reference gets cleaned up after the object is gone. 
  I.e., weak references are simply pointers into some system-maintained 
table, not actual pointers to the objects themselves.

So the code would be

thisListener = weak_to_strong(listeners[i]);
if (thisListener != null) listeners[i].doSomething();
else listeners[i] = null;

You'd still have the weak reference. If the call to doSomething() 
cleared out the last intentional reference to that listener (the "this" 
in the call), then when you returned from the doSomething and 
"thisListener" went out of scope, then you'd wind up getting it 
collected. But you'd have to return from doSomething before that 
newly-created strong reference disappeared.

>   Or are GC engines run only at places where there can't be mutual
> exclusion problems? (How does the VM/compiler/interpreter know that?)

When the GC actually doesn't stop all threads, it uses funky tricks like 
making memory pages non-writable or non-readable and catching hardware 
exceptions to avoid having problems with interactions like that. Like, 
if the GC scans an object X for outgoing pointers, it marks it as 
read-only until it's done. Then you store a new pointer in that object 
from another thread, the GC catches the write, sees what new object Y 
you might be pointing to, and makes sure that if that 
newly-pointed-to-object had already been marked free (because you had 
not been pointing to it before but now X points to it), Y is now marked 
"in use" again.

But weak references generally have to be turned into strong references 
to use them. At least everywhere I've seen such implemented.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> So the code would be

> thisListener = weak_to_strong(listeners[i]);
> if (thisListener != null) listeners[i].doSomething();
> else listeners[i] = null;

  In theory it could happen that each time the GC takes a sweep,
that second line is being executed. (Yes, extremely unlikely for
that to happen each time, but theoretically possible.) Since that
second line is using a strong reference, the object is not destroyed?

  Also, I assume that the weak_to_strong() function must be locking
(ie. have mutual exclusion). Doesn't that make it slower than just
using a strong reference?

-- 
                                                          - Warp

Post a reply to this message