At 1:18 AM +0900 8/24/02, William Djaja Tjokroaminata wrote:

>I think one of the problems with reference counting is the circular
>reference, which cannot be handled by the gc.

That's one problem. Reference counting is also more expensive over 
the long run than more automatic methods. Also more error-prone.

>  However, now the problems
>with mark-and-sweep gc for my specific applications are:
>
>1) It is linear (O(N)) in the number of Ruby objects, and therefore it
>seems that it will not scale well.  Yes, probably for the majority of Ruby
>applications, the cost of gc invocation is small as compared to all the
>other functions in the Ruby code, i.e.,
>
>     cost = eps * N
>
>where eps is a small number.  However, no matter how small eps is, as N
>grows large, eventually the gc cost cannot be neglected.

While mark&sweep (and other forms of tracing GC) are O(N) on the 
number of objects that exist when a sweep is done, reference counting 
is O(N) on the number of objects that exist *ever* in the program. 
M&S only looks at live objects.

Reference counting also tends to make poorer use of the cache. L1 and 
L2 cache effects are subtle and often a tad counter-intuitive. 
Basically with refcounting you use more L1 cache in mainline program 
execution than with other mechanisms. While tracing GCs do need 
storage to work, just as refcount schemes to, that storage is only 
used when a sweep is being done, so it doesn't dirty the cache during 
normal execution and can be densely packed for good cache locality 
during a sweep.

>2) When the Ruby objects are static, gc invocation is a waste.
>

That's why you don't normally trace your constant pools. :)

>I never had a formal training on the subject of gc, and therefore I don't
>know whether my question above is simply impossible because of the
>fundamental natures of mark-and-sweep gc.

I'd recommend getting the book _Garbage Collection_ by Jones and 
Lins. It goes into detail on a lot of this stuff. A run through 
CiteSeer might also be in order.
-- 
                                         Dan

--------------------------------------"it's like this"-------------------
Dan Sugalski                          even samurai
dan / sidhe.org                         have teddy bears and even
                                       teddy bears get drunk