Re: [Gcl-devel] efficiency of package symbol tables

[Camm Maguire]

Greetings, and thanks again for the discussion.

Bruno Haible <address@hidden> writes:

> Camm Maguire wrote:
> > we get the much improved
> 
> Yes, that's what I meant.
> 
> > There is of course the issue of what the
> > ratios of free pages to total used pages should be per type.
> 
> Is there a criterion which would let you decide that, say, it's more
> welcome to allocate new STRING pages than new CONS pages before doing
> a GC?
> 

I can't think of anything better (right now) than assigning a mark
cost proportional to the number of pointers in the object, and a sweep
cost proportional to its size.  The difficulty comes with
contiguous/relocatable blocks, i.e. in arrays, which could either be
completely mark benign if the element type is fixnum, or quite costly
if the element type is t.  Not to mention that the array size is not
known when the array body is allocated.

> Up to now, I can see two leading criteria:
> 
>   1) The Lisp process wants to not waste time doing GC, and therefore
>      allows itself to wait longer for doing GC when the GC is expected
>      to be costly.
> 
>   2) The other processes on the system expect the Lisp process to be
>      economic with memory, i.e. to not waste more than a given percentage
>      of what it actually needs.
> 
> For criterion 2, the type of a page makes no difference (because it is
> not perceived outside the Lisp process), i.e. all page types should be
> handled equally.
> 
> For criterion 1, a STRING page costs less than a CONS page, therefore it
> should be allowed to consume some more STRING pages than CONS pages before
> triggering a GC.
> 
> Therefore what I would do is to measure the relative GC cost of each type
> of page, compute percentages according to criterion 1, and then finally
> move these percentages closer together to account for criterion 2.
> 

It would seem that a proper algorithm might also want to take into
account the relative percentages of pages the user is actually
allocating, or perhaps merely retaining.  One could automatically
'rebalance' the allocation percentages at some interval.

I'm also a little unclear as to what you mean by moving the
percentages closer together.  Can't 2) be addressed by the global
PERCENT_FREE macro (in the afore-posted example), i.e. given the
proper natural size for this type, how full to we want it to be before
actually resetting?

Take care,


> Bruno
> 
> 
> 
> _______________________________________________
> Gcl-devel mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/gcl-devel
> 
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah