Once again, I just ran across D.  Please pardon me if I walk on toes
already trodden
upon.

A couple of ideas on garbage collection.  First, many of the ideas of
"modern" garbage
collectors were formed when physical memory was much smaller than
virtual memory.
At the moment, however, max memory on a x86 < $1000.  While a compacting
garbage
collector may save page faults on the 486 in your basement, it doesn't
make much sense
on a 2 GB machine.  Slopping crud around wastes processor cycles that
can be used
elsewhere.  Probably.

Second, it isn't necessary to stop program execution to do garbage
collection.  I have
a very JVM garbage collector (OK, it's a retro-grade mark-and-sweep [see
above])
that asks each thread to mark itself when convenient (it will mark
threads known to
be stalled), then waits for all threads to report completion.  In the
meantime, objects
are created marked, and assignments into objects are marked.  The net
result is
that no thread stalls waiting on garbage collection.  Furthermore, on a
multi-processor,
marking of thread can take place in parallel on a multi-processor.  All
in all, the
scheme takes a great deal of the pain out of garbage collection.

I'm not going to insist that this technique is appropriate for D.  I
just want to remind
folks that most thinking about garbage collection was done for Lisp
umpteen
generations ago.  Before anything gets cast in concrete, fresh thinking
would be
a very good thing.

"Jim Starkey" <jas@netfrastructure.com> wrote in message news:3C9A46D6.5B211715@netfrastructure.com...
> Second, it isn't necessary to stop program execution to do garbage
> collection.  I have
> a very JVM garbage collector (OK, it's a retro-grade mark-and-sweep [see
> above])
> that asks each thread to mark itself when convenient (it will mark
> threads known to
> be stalled), then waits for all threads to report completion.  In the
> meantime, objects
> are created marked, and assignments into objects are marked.  The net
> result is
> that no thread stalls waiting on garbage collection.  Furthermore, on a
> multi-processor,
> marking of thread can take place in parallel on a multi-processor.  All
> in all, the
> scheme takes a great deal of the pain out of garbage collection.

Write barriers as you describe can have a major performance hit. That scheme also requires cooperation from each thread - which is fine where the VM controls the thread, but D has no VM, and threads are controlled by the operating system, which cares nothing about an application garbage collection.

> I'm not going to insist that this technique is appropriate for D.  I
> just want to remind
> folks that most thinking about garbage collection was done for Lisp
> umpteen
> generations ago.  Before anything gets cast in concrete, fresh thinking
> would be
> a very good thing.

D is the first systems programming language to be designed from the ground up for garbage collection. I think GC has progressed far enough to make this possible.

Walter wrote in message ...
>
>> Second, it isn't necessary to stop program execution to do garbage collection.
>
>Write barriers as you describe can have a major performance hit. That
scheme
>also requires cooperation from each thread - which is fine where the VM controls the thread, but D has no VM, and threads are controlled by the operating system, which cares nothing about an application garbage collection.
>

Could you explain what you mean by write barriers and the nature of the performance hit?  I also don't understand your point about thread cooperation.  Isn't thread cooperation required to implement any GC scheme?

"Jim Starkey" <jas@netfrastructure.com> wrote in message news:a7fm46$2228$1@digitaldaemon.com...
> Walter wrote in message ...
> >> Second, it isn't necessary to stop program execution to do garbage collection.
> >Write barriers as you describe can have a major performance hit. That
> scheme
> >also requires cooperation from each thread - which is fine where the VM controls the thread, but D has no VM, and threads are controlled by the operating system, which cares nothing about an application garbage collection.
> Could you explain what you mean by write barriers and the nature of the performance hit?

Write barriers are where the writes to memory are trapped and logged by the gc as potential changes to the root set. They can be implemented with checking code emitted for each assignment (I've seen this done with java vm's), or by write protecting each page and putting in an exception handler that catches each write. Both offer substantial performance penalties, and the former produces a lot of code bloat.

>  I also don't understand your point about thread
> cooperation.  Isn't thread cooperation required to implement any GC
> scheme?

Threads have to cooperate by deciding when it is convenient to do a gc mark with your proposal. With D's gc implementation, this is not necessary - each thread gets forcibly suspended and scanned by the gc.