Orchid XP v8 wrote:
> Trouble with mark/sweep is that you have to stop the program executing 
> while you do your sweep, 

The other "problem" is that the process is recursive just as you've run 
out of memory.  You have to be clever about walking through the data 
structures in a way that uses the pointers you're following as stack 
space.  Which, of course, means it's difficult to run the GC in parallel 
with the main processing. :-)

On the other hand, calling malloc() or free() from two separate threads 
in the same heap is likely problematic too, unless you're clever about it.

The way the original Smalltalk-80 worked was to have a 5-bit reference 
count in each object. Things got collected when the reference count went 
to zero. If the reference count went >30, it never got collected until 
you did a mark-sweep, which indeed stopped the whole program.

Note too that reference counting can lock up a program just as bad as 
mark-sweep does, if done foolishly. Ever have a program where exiting it 
made the disk thrash wildly?  Probably using a library that freed 
everything you allocated before exiting.  Think how long you'll thrash 
cleaning up (say) a level of a game with reference counting when you 
dispose the last pointer to a few hundred meg of AI, textures, geometry, 
etc.

> Obviously, stopping your entire program (all parallel threads!) so you 
> can run the GC isn't a fantastic idea.

Erlang has one heap per process, where a program not uncommonly has tens 
of thousands of "processes", not unlike a thread but much lower 
overhead.  (Managed co-routines, perhaps?)

> most designs of GC, the entire chain of objects will be reclaimed in a 
> single pass of the GC. (Although it might be the next "major" rather 
> than "minor" pass or something, depending on the exact design details.)

Yep.

A lot of the newer languages designed to run on massively-parallel 
machines (distributed or not) basically have no aliased values, so GC 
becomes a lot easier when you can only have one pointer. At that point, 
reference counting (or destroying when it goes out of scope) becomes a 
lot easier to design in.

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