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

[Camm Maguire]

Greetings!  What about an algorithm like the following:

npp_i = number of elements of type i per page
s_i   = sizeof type i
p_i   = 1 + number of pointers in element of type i

c_i = gc cost for page of type i = npp_i * (s_i + p_i)

      (sweep and mark cost equally weighted)


m_i = maxpages of type i
q_i = free pages of type i before GC
f_i = free pages of type i after GC
np_i = number of pages of type i in use after GC

R = approximate GC rate due to semi-permanent heap growth
  = sum_i (np_i - previous np_i)/m_i

r = approximate GC rate due to generation of temporary garbage
  = max_i (f_i - q_i)/m_i

C = approximate cost of GC
  = sum_i c_i m_i

Then when triggering a GC in allocating a page of type i, increase
maxpages when either

1) The number of free pages of this type is less than PERCENT_FREE of
   maxpages, as at present.  This allows tuning of GC due to
   semi-permanent heap growth.

2) If type i is the type governing GC due to temporary garbage
   generation, as in the definition of 'r' above, increase m_i to
   minimize 

        (R+r)*C

   or 

        -f_i + \sqrt (f_i^2 + (r/R)*(C-c_i*f_i))

This is obviously still quite rough, and leaves case 1) in its
conventional heuristic algorithm, but might accomplish the bulk of the
goal for now.  I'm also writing this quickly, so the above could still
contain mistakes.  Thoughts nevertheless appreciated.

Take care,


Bruno Haible <address@hidden> writes:

> Camm Maguire wrote:
> > 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.
> 
> True, but I consider this as fine-tuning. If the fine-tuning is not
> perfect, the GC performances may not be optimal. But if you assume the
> worst case (i.e. that arrays contain pointers everywhere), they are still
> within a fixed percentage of the optimum.
> 
> > 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.
> 
> Yes, there are many ways to do fine-tuning. Some people base it on
> the current state only, some also on the input/output statistics of
> previous GCs. The former approach is more robust against unexpected
> change in behaviour of the application; the latter approach may be
> more economic on the average...
> 
> > I'm also a little unclear as to what you mean by moving the
> > percentages closer together.
> 
> It's meant as a counter-goal that weighs against the goal of
> optimizing GC time. It can be different in details. I thought that
> when you measure that, say, GCing a STRING page costs 0.5 ms and
> GCing a CONS page costs 1 ms, then it would be logical to allow
> a fixed amount of "allocation units" until the next GC, and a STRING
> page consists of 0.5 allocation units and a CONS page of 1 allocation
> units. In other words, a GC would be triggered when
> 
>   0.5 * number of new STRING pages + 1 * number of new CONS pages > N.
> 
> But this point of view neglects the point of view of the other programs,
> which compete about the memory pages in RAM, L2-cache, L1-cache. To take
> this into account I would change the trigger criteria to
> 
>   0.75 * number of new STRING pages + 1 * number of new CONS pages > N.
> 
> It's quite arbitrary, sure.
> 
> Bruno
> 
> 
> 
> 

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