Re: C Garbage collector

[Hong Zhang]

Almost every GC algorithm has its advantages and disadvantages.
Real-time gc normally carry high cost, both in memory and in
cpu time.

I believe that options is very important. We should make Perl
6 runtime compaible with multiple gc schemes, possibly including
reference counting. However, it will be very hard to do so.
We have to design for it at the very beginning.

Hong

> Do you folks know anything about the garbage collector in rScheme
>  http://www.rscheme.org/>?  They say it's got a "real time
>  generational" garbage collector.  It must be worth looking over.
> 
> -- 
> mailto: (Karl M. Hegbloom) [EMAIL PROTECTED]
> http://www.microsharp.com
> phone://USA/WA/360-260-2066

Re: C Garbage collector

[Karl M. Hegbloom]

 Do you folks know anything about the garbage collector in rScheme
 http://www.rscheme.org/>?  They say it's got a "real time
 generational" garbage collector.  It must be worth looking over.

-- 
mailto: (Karl M. Hegbloom) [EMAIL PROTECTED]
http://www.microsharp.com
phone://USA/WA/360-260-2066

RE: C Garbage collector

[wiz]

Dear Hong,
   This was actually a reply to a posted link for a C/C++ replacement GC
(http://www.hpl.hp.com/personal/Hans_Boehm/gc/), not the default GC from any
particular C package.
Grant M.

Re: C Garbage collector

[Hong Zhang]

I don't quite understand what is the intention here. Most of
C garbage collector is mark sweep based. It has all common
problems of gc, for example non-deterministic finalization
(destruction), or conservativeness. If we decide to use
GC for Perl, it will be trivial to implement a simple
mark sweep collector or semi space copy collector. There
is no advantage to use C garbage collector.

Hong

- Original Message -
From: "NeonEdge" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Wednesday, February 21, 2001 3:32 AM
Subject: RE: C Garbage collector


> I agree with Damien that the Sun description sounds less portable, which
we all
> know in the Perl world is crucial (>80 ports)(although Sun mentions 16-bit
> DOS/Win). Any GC implementation needs to try to 'not break' the existing
stuff.
> Other questions are somewhat dependent upon what language is used to
implement
> (both GC descriptions are C or C++ dependent which is ok by me, but I'm a
> masochist). I've been off the list since RFCs closed, so does anyone know
if
> there's been any further thoughts on the implementation language?
> Grant M.
>

RE: C Garbage collector

[NeonEdge]

I agree with Damien that the Sun description sounds less portable, which we all
know in the Perl world is crucial (>80 ports)(although Sun mentions 16-bit
DOS/Win). Any GC implementation needs to try to 'not break' the existing stuff.
Other questions are somewhat dependent upon what language is used to implement
(both GC descriptions are C or C++ dependent which is ok by me, but I'm a
masochist). I've been off the list since RFCs closed, so does anyone know if
there's been any further thoughts on the implementation language?
Grant M.

Re: C Garbage collector

[Ask Bjoern Hansen]

On Wed, 21 Feb 2001, Alan Burlison wrote:

> Alan Burlison wrote:
> 
> > I've attached the HTML
> 
> Well it was there when I sent it... does this list strip attachments or
> something?

yes, it does. It is usually just misconfigured mailers or spam.

-- 
ask bjoern hansen - 

Re: C Garbage collector

[Damien Neil]

On Wed, Feb 21, 2001 at 12:25:10AM +, Alan Burlison wrote:
> Shame it only works with the Sun compilers.

See also Boehm's garbage collector, which is rather more portable:
  http://www.hpl.hp.com/personal/Hans_Boehm/gc/

  "The collector uses a mark-sweep algorithm.  It provides incremental
  and generational collection under operating systems which provide
  the right kind of virtual memory support.  (Currently this includes
  SunOS[45], IRIX, OSF/1, Linux, Windows NT, and Windows 95, with
  varying restrictions.) It allows finalization code to be invoked
  when an object is collected.  It can take advantage of type
  information to locate pointers if such information is provided,
  but it is usually used without such information."

   - Damien

C Garbage collector

[Alan Burlison]

Documentation excerpt:

With Sun WorkShop Memory Monitor, you can program without calling free()
or delete. Determining when to call free() or delete is difficult. 
Studies indicate that 30% to 40% of programmer time is spent on memory
management in C or C++ programs. Failing to release memory causes memory
leaks, which refers to the accumulation of unused memory in the program,
ultimately causing the program to monopolize or even run out of memory.
Releasing memory too early leaves loose pointers, which are pointers
that do not point to valid memory. Using loose pointers invariably
causes data corruption, segmentation faults, or general protection
violations. Sun WorkShop Memory Monitor automatically eliminates the
problems of freeing memory at the wrong time.

In the field, Sun WorkShop Memory Monitor automatically protects your
program against memory leaks and premature frees, even those in
third-party libraries. Simply linking with Sun WorkShop Memory Monitor
automatically eliminates any leaks. In deployment mode, Sun WorkShop
Memory Monitor's high-performance memory allocator makes your programs
run faster and consume less memory. 

Sounds like nirvana ;-)

Shame it only works with the Sun compilers.

However, there is an explanation of how it works that might be useful
when considering how to do this for perl6.  I've attached the HTML -
sorry about the broken links, but I don't think this is on any
externally-visible webpage.

Alan Burlison

Re: C Garbage collector

[Alan Burlison]

Alan Burlison wrote:

> I've attached the HTML

Well it was there when I sent it... does this list strip attachments or
something?
 
Here is is as badly-formatted text - sorry!

Alan Burlison


Appendix A: How Sun WorkShop Memory Monitor Works 

Memory management in C/C++ is both time consuming and
error prone. Typically, about one-third of development time
is spent on memory management, and most commercially
available programs ship with memory leaks or premature
frees. Even worse, no matter how well written your own
code is, third-party libraries and DLLs used by your
program may leak, leaving you with no way to deliver
leak-free applications.

Imagine what would happen if memory just freed itself when
it was no longer in use. Programs that freed memory in the
wrong place would automatically be fixed, and new code
wouldn't need to free memory at all. Such automatic
garbage collection is the standard in Java and Smalltalk.
I'll lift the hood on the Sun WorkShop Memory Monitor
garbage collector, focusing on the details that make it
practical, transparent, and scalable.

Why Garbage Collection? 

The basic idea behind garbage collection is refreshingly logical. As a
program runs, the garbage collector
periodically scans the program's data marking everything that is in use.
It begins by scanning the
program's stack, registers, and the static segment. Every time it
encounters a pointer, it marks the object
that it points to. Then it scans the object for pointers to other heap
objects. Once it has marked all
reachable heap objects, it frees all the objects that haven't been
marked (see Figure 1).

The hard part of adapting garbage collection to C/C++ is identifying
pointers. Since object libraries and
DLLs often lack source, you can't examine the source for type
information, and you can't recompile.
Typically, you don't even have debugging information. The only remaining
option is to relink. This isn't as
bad as it sounds, since relinking lets you redefine whatever functions
you like.

What functions should you redefine? The natural candidates are
memory-management functions --
malloc(), free(), new, and delete. Redefining free() and delete to Null
operations protects the
programmer from premature frees. This leaves only the malloc() and new
allocators.

But how does this help you identify pointers? A solution to this problem
was first observed by Hans Boehm
and Mark Weiser. (For more information, see their article, "Garbage
Collection In an Uncooperative
Environment," Software Practice and Experience, September 1988, as well
as Boehm's "Advantages and
Disadvantages of Conservative Garbage Collection," at
ftp://parcftp.xerox.com/pub/gc/issues.html.)
Allocators keep track of what memory has been allocated. You can test
whether a data word points inside
an allocated object. If so, it's probably a pointer. Is this test always
right? No, but it's a start.

Sun WorkShop Memory Monitor implements a refined version of this
pointer-finding strategy through a
custom allocator that can efficiently report on the status of any
address. Once you can identify pointers,
you can garbage collect a program.

We Interrupt this Program... 

Proper scheduling may be the most important factor in garbage collector
performance. The earliest
collectors only performed garbage collection when the computer ran out
of memory. When a collection
finally occurred, it analyzed the computer's entire address memory,
interrupting operation for long periods
of time. No wonder early garbage collectors were invariably associated
with annoying interruptions of
program operation.

Many current garbage collectors, especially Java collectors, rely
primarily on a low-priority background
thread to schedule garbage collection. This approach sounds good, but
leads to poor performance. The
low-priority background thread provides lots of garbage collection to
inactive programs that don't need it.
By the same token, computation-intensive programs require large amounts
of garbage collection, but don't
receive any because the background collection thread doesn't have a
chance to run since such a program
always demands CPU cycles. As a result, background collection threads
should, at best, supplement some
other primary collection strategy.

Sun WorkShop Memory Monitor decides when to collect garbage by watching
how much memory has been
allocated since the last collection. This way, programs that use lots of
dynamic memory allocation receive
the collection they need, while programs that don't allocated much
memory don't waste a lot of time doing
unnecessary garbage collection.

To further limit program interruptions, you can do only a small part of
the garbage collection each time. At
first glance, this seems impossible. The heap is constantly changing, so
how can you know that the
analysis from earlier partial collections is still correct?
Memory-management hardware in the CPU provides
some help. After analyzing a page of memory, simply "write-protect" that
page