>>   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

Warp wrote:
> 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?

Correct.  Once the weak_to_strong creates the strong reference, it can 
no longer be GCed, since there's still a strong reference around.

>   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?

Sure. If nothing else, you need the overhead of calling 
weak_to_strong(). You don't want to use weak references if you don't 
need them.

But generally, if your GC is letting your code run while the GC is 
running, you're going to have various kinds of locking overhead. Often, 
instead, you'll have the program stopped briefly while a little bit of 
objects is marked either "free" or "in use", then more application code, 
then a little bit of scanning, etc, until you've finished a full scan. 
Then you throw things away, a little at a time, also.

But generally, if you have threads, you GC one thread at a time, so the 
thread you're GCing isn't mutating memory as you're collecting it. 
Remember, too, that you're looking for live objects, not dead ones, so 
if an object goes from live to dead while you're scanning, you're OK - 
you'll get it the next time around. The complexity comes from objects 
going from dead to live while you're scanning.

It's not just the weak-to-strong that needs locks. If you compact memory 
to make larger free spaces, you obviously need to make sure nobody is in 
the middle of referencing what you're moving and so on either. Even 
reference counting stuff has to have locks, except now you need locks 
for every time you assign a pointer, instead of just during garbage 
collection.

It's actually pretty darn complicated to get right. And it has been an 
ongoing field of research for 30 years already, and there's still no 
solution that makes everybody happy, so...

-- 
   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

Warp wrote:
>   Also, I assume that the weak_to_strong() function must be locking

http://www.cs.purdue.edu/homes/jv/pubs/lctes07.pdf

If you want some ugly nitty-gritties. :-)

-- 
   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

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

Actually, thinking about this, it's really not possible the way you mean 
it. How would you say which object's reference count went to zero? As 
soon as you say "Remember that open file? Its reference count went to 
zero," the reference count isn't zero any more. Which is why finalizers 
always have problems with being "resurrected" during finalization.

So, I guess it's impossible to implement weak references yourself in the 
same language as you access the references (i.e., as a library). If you 
can return the strong reference from your library, the weak reference 
can't be collected. Cool.

-- 
   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