Re: My arguments

El mié, 13 de 08 de 2003 a las 11:22, Fergus Henderson escribió:
> On 13-Aug-2003, Fernando Diaz <[email protected]> wrote:
> > 
> > At the last version of Mono (0.25), lihgc is working with the metadata
> > of the objects as the libgc works with GJC (GNU Java Compiler). This is
> > and advantage because makes the collector less conservative and more
> > accuracy. In spite of the fact, libgc isn't a good collector for Mono,
> > because it can take advantage of the complete metadata that Mono
> > provides, it only uses a piece of metadata.
> 
> I think you meant to say it _can't_ take advantage. 
> That's right, the C stack is still scanned conservatively.

Yes, i wanted to say that it can't thake advantage.

> > In theory, a copying one needs more space (the double than Mark-Compact)
> > and less time (only needs to travel through the heap once, instead of
> > Mark-Compact that needs to travel through at least twice) than a
> > Mark-Compact collector. But in practice, I have read that they are very
> > similar (http://www.hpl.hp.com/personal/Hans_Boehm/gc/complexity.html,
> > this site talks about a Mark-Sweep collector, but the complexity of
> > Mark-Compact it will be very similar to a Mark-Compact one).
> 
> Huh?  Did you mean to say that the complexity of Mark-Sweep will be
> similar to the complexity of Mark-Compact?

No!!! :). I know that a Mark-Compact algorithm complexity is bigger than
a Mark-Sweep one. Because Mark-Sweep doesn't need to move the data and
rebuild the references. My argument was wrong...

What i want to say is that both alternatives (Copying and Mark-Compact)
have a similar complexity. Mark-Compact needs to travel through the heap
at least twice (depending on the technique we use, in the two-finger
algorithm we need to travel it twice, the Lisp 2 algorithm need to
travel through the heap for three times, table-based and threaded
algorithms needs to travel through it twice too), while Copying need to
travel through the heap only once. On the other side, a Mark-Compact
collector need the half of the size of the heap that a Copying collector
needs. 

If we look into the amortized cost of a collection with both techniques
when the amount of live objects in the heap are almost all (in my
opinion it is the common situation), the amortized cost (calculated
dividing the time spent collecting by the amount of garbage reclaimed)
is very similar (using an alternative inside the Mark-Compact algorithm
that needs two passes over the heap).

Don't you think so?

Respecting the locality of data for computers with virtual or cache
memory (nowadays almost all), Mark-Compact have a better behaviour than
Copying. All of this it depends on the alternative inside each algorithm
that choose, but in general the locality of Copying techniques is less
than the locality of Mark-Compact techniques. The alternatives inside
the Mark-Compact algorithms that keep the locality of data (LISP2, Table
Based and Threaded), are more expensive than others that don't take this
advantage (Two-Finger). Inside the Copying techniques, the Cheney
algorithm (Copying with an width search algorithm) doesn't take
advantage of the locality, a Copying algorithm with a depth search is
very expensive because of it is a bad alternative. A hybrid search
(mixing depth and width techniques) takes a little advantage of the
locality and it's amortized cost is similar to a table-based or threaded
Mark-Compact collector.

In my opinion, both alternatives are very similar.

> > Personally, i think that a Mark-Compact will be better because we can
> > made Mono more compatible with .NET (.NET uses a Mark-Compact collector)
> > in this subject.
> 
> It will only be "more compatible" in the sense that the performance
> characteristics might be a bit more similar.  I think that is a very
> low-priority goal.

You are right. It isn't a goal for the collector, but on equality of
conditions, this things help us to decide among the techniques.

The copying collection is simplier to implement than a Mark-Compact
collector, but, in your opinion, What is the best?. I know that they are
a lot of different implementations for this algorithms, but in general,
What is the best for Mono from your point of view?.

I think that i am going to start the first prototype with a Copying
algorithm. After, modify it to make a Mark-Compact collector i think
that won't be very complex.

Thanks again!.

Regards.
-- 
Fernando Diaz <[email protected]>
_______________________________________________
Mono-gc-list maillist  -  [email protected]
http://lists.ximian.com/mailman/listinfo/mono-gc-list