GC performance - was Re: [gclist] GC topics

[Darius Blasband]

> 
> >Perhaps you should tell us how you keep track of pointers in YAFL.  We are
> >mixing together many issues here.  Assuming you are generating C code, I think
> >the possibilities are roughly:
> >
> >1) In the single-threaded case, you could explicitly keep a data structure that
> >allows the collector to find all roots.  All evidence I've seen so far suggests
> >that this costs on the order of a factor of 2 for pointer-intensive C/C++ code.
> >Either pointer assignments and/or pointer variable creation become expensive.
> >Much of the cost here is often associated with preventing the C compiler form
> >keeping pointer variables in registers.
> 
[Missed an intermediate message, I am afraid...]
  
Well, I am afraid this is a little long to explain in full length here,
Let's say that we use a rather naive system:

- First, some data dictionary information tells us at which offsets
  we have pointers within objects.
- All allocations refer to their meta class where so that I can mark
  an instance generically, by querying its attached metaclass.
- We keep 2 stacks: the reference stack and the value stack. Whenever
  we enter a method (understand function , procedure), the addresses
  of all locals and formals which might refer to separate allocations
  are pushed on the reference stack, and this stack's state is restored
  when exiting the method. The value stack is only required for
  short-lived objects before they can be referred to by a recognized
  reference (evaluating parameters before actually calling the function,
  for instance).
(I know that given the kind of vigorous talk which has been going on around
here recently, many might find this excessively simple, but the results
are pretty good)
- When the system want to reclaim memory, it marks all references accessible
  from these two stacks, and all references recursively accessible from
  these, and basically frees all the others.
  
Well, this is the basic idea behind YAFL's GC system. However, there
are several other things worth mentioning:

- We have our own allocator for small allocations which are allocated
  in fixed size slots within pages. These pages are allocated using
  malloc, and larger allocations use malloc as well. The rationale
  behind this was simply that since C is a very system-oriented language
  where performance has always been an issue, we can expect its
  allocator to be at least average. Frankly, so far, we accepted this
  as a fact of life, but we have not been investigating the true impact
  of the use of the standard C allocator for our purpose. We are conscious
  of the fact that it does limit our ability to implement some of the
  more sophisticated stuff which is sometimes mentioned in this mailing list.
- Pushing and popping on our two stacks can be done by using register 
  global variables as supported by gcc, typically on RISC machines. Well,
  William Nicora tried this on a SGI machine, and it happened to be much
  slower than the original scheme. I would not take this as an ultimate
  answer, and I think we can get better results if we plunge a bit more
  in the intricaties of GCC.
- YAFL's compiler is optimized in the sense that quite a lot
  of static analysis goes into finding methods which do not require
  that their locals and formals must be pushed on these stacks. The original
  compiler does this locally, and the global optimizer which has been built
  on top of YAFL does that globally. The global version is not in production
  yet, so I have no figures available...
- YAFL is a high-level language, which does not support "inside pointers".  
  Of course, it also makes things much simpler.


> 
> >  If you can do this with only 20%
> >overhead for pointer-intensive optimized C code, I'm impressed.
> 
> Anybody have stats on this?  
>
(If "this" refers to the stack management described above, yes I do).
It does indeed take just 20% of the execution time after careful measures...
Of course, there is nothing in YAFL which can really be compared with
"pointer-intensive" code in the C sense: references are implemented using
plain pointers, but there is no arithmetic with pointers (This is by far
not only a question of GC, it is a far more fundamental language design
issue).
 
Regards...

Darius