www.digitalmars.com         C & C++   DMDScript  

D - Garbage Collection

reply Jim Starkey <jas netfrastructure.com> writes:
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.
Mar 21 2002
parent reply "Walter" <walter digitalmars.com> writes:
"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.
Mar 22 2002
parent reply "Jim Starkey" <jas netfrastructure.com> writes:
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

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?
Mar 22 2002
parent "Walter" <walter digitalmars.com> writes:
"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.


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.

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.
Mar 22 2002