class gc

[Godmar Back]

> 
> I imagine the reason Per and others are not swayed by this is that
> they perceive marking an object to be relatively expensive.  Adding
> one more check just doesn't seem like a big deal.
> 
> And when your argument is presented in this way, I agree with them.
> gcj's output isn't really tuned for extremely fast marking.  Right now
> our marking glue function weighs in at about 100 LOC.  It fetches the
> object's class and then uses information there to determine which bits
> to feed to PUSH_CONTENTS.

Maybe we're disagreeing on terminology here.
What you describe in the last paragraph is what I would call "walking"
an object, not "marking" it.  An object is walked, the objects to which 
pointers found in the walked object refer are then marked.
(I may be wrong on terminology here, though, but maybe this explains
some of the misunderstandings.)

> 
> The check for whether the object is on the heap is two comparisons.
> Here is the macro we use:
> 
>     // We must check for plausibility ourselves.
>     #define MAYBE_MARK(Obj, Top, Limit, Source, Exit)  \
> 	  if ((ptr_t) (Obj) >= GC_least_plausible_heap_addr \
> 	      && (ptr_t) (Obj) <= GC_greatest_plausible_heap_addr) \
> 	    PUSH_CONTENTS (Obj, Top, Limit, Source, Exit)
> 
> (I don't remember why we do the check ourselves.  Sigh.)
> 
> As a result I find it hard to believe that removing these two checks
> would have a significant effect on performance.  Of course, without
> measuring it, I can't be certain.

You seem to be making assumptions about how your address space is laid out,
i.e., that your heap and the data segments of shared libraries do not 
interleave.  If this a reasonable assumption, then I have to agree with 
you.  Is it?

Kaffe's gc-managed heap can be grown by whatever sbrk(), malloc(), or
even anonymous mmap() returns.

> 
> But anyway, as a first step, it seems like it would be more worthwhile
> to investigate changing gcj to allow more efficient marking in
> general.
> 
> 
> Anyway, I think the real argument to be made here is that statically
> allocating objects complicates write barriers to an unacceptable
> degree.  I believe (again without measurement -- a bad habit) a write
> barrier is much more performance sensitive than a mark function.  If
> the write barrier must do heap plausibility checks (for instance to
> fetch the referenced object's color), performance will suffer.
> 
> But I don't even really believe this.  The write barrier will be
> intimate with the memory allocator, which means the compiler must be.
> So on the happy day when we have write barriers, we can also change
> the compiler to lay out preinitialized objects with the same sort of
> header the allocator uses and the write barrier expects.
> 

This was actually one of the alternatives I suggested (i.e. faking an
header before the object).

The way this would help with write barriers is such that you could
store the color of the object there (for instance in the lower two or
three bits of a pointer) and make the common case (the write barrier
is not hit) relatively fast.

> Godmar> True.  But minimizing the frequency of this check brings a
> Godmar> huge performance improvement, as I witnessed when I
> Godmar> implemented precise heap walking for Kaffe.
> 
> I find this claim interesting.  I know nothing about Kaffe's GC.  Why
> wasn't this check just noise in the mark function logic?
> 

Originally, when I introduced precise walking, we had an awfully slow
function that would require looking up the pointer in a hashtable.
Clearly, the performance gain was huge then.  Now, marking has become
cheaper since Jason Baker implemented a faster function shown below:

/* Return true if gc_unit is pointer to an allocated object */
static inline int
gc_heap_isobject(gc_block *info, gc_unit *unit)
{
        uintp p = (uintp) UTOMEM(unit) - gc_heap_base;
        int idx; 

        if (!(p & (MEMALIGN - 1)) && p < gc_heap_range && info->inuse) {
                /* Make sure 'unit' refers to the beginning of an
                 * object.  We do this by making sure it is correctly
                 * aligned within the block.
                 */
                idx = GCMEM2IDX(info, unit);
                if (idx < info->nr && GCBLOCK2MEM(info, idx) == unit
                    && (GC_GET_COLOUR(info, idx) & GC_COLOUR_INUSE) ==
                    GC_COLOUR_INUSE) {
                        return 1;
                }
        }
        return 0;
}

However, there's still several memory accesses and arithmetic operations
(MEM2IDX is an integer division) that you would save if you didn't need
to call gc_heap_isobject.

	-- Godmar