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

[Camm Maguire]

Greetings, and thanks again for your feedback.

Bruno Haible <address@hidden> writes:

> Camm Maguire wrote:
> > I think the
> > GC time should increase, as the heap is getting larger.  Each call
> > consumes cons and symbol pages at least.  Here is a bit more detail.
> 
> I agree that the time for 1 GC should increase, as the heap is getting
> larger. However, what you see here is that the proportion of real time
> spent on GC for a given task (fill-symtab 10000) increases from ca. 50%
> in the first two runs to ca. 90% in the last two runs. This means that
> if the heap gets bigger and bigger, the system gets slower and slower.
> 

Agreed.

> Probably it is not due to swapping of virtual memory, assuming your machine
> has more than 32 MB of RAM?
> 

No swapping here.

> Then the only reason for it that I can see is that the GC is triggered too
> often. I.e. when the number of pages that the GC will have to scan is big,
> the intervals between GCs - measured in allocation requests - should become
> larger. A possibly way to implement this is to make the amount of "reserve"
> pages grow proportionally with the number of already used pages.
> 

This is exactly the case.  Traditionally, GCL has been designed to be
exceedingly sparing with memory.  There is even a branch in the code,
never used anymore in practice, which will simply refuse to allocate
more pages of a given type than the set maximum.  With Vadim's help,
we recently improved the maximum page growth algorithm defaults
somewhat.  The way it works now, the maximum number of pages for each
type will be increased when the free area is less than 30% of the
total available after GC.  This is user settable via the function
si::allocate-growth.  The info page has a good description.  Also
settable with this function are the minimum and maximum pages in the
increment, and the percentage by which the space should be expanded
when the minimum and maximum are not hit.  

No doubt we are still likely a bit too conservative here.  I cannot at
present think of an optimal solution to this problem which is not
quite ad-hoc.  Perhaps you have a suggestion?  

In any case, you can see that the cons and symbol page types have
increased their allocation, and hence are GC'ed quite seldom.  The
problem is that our current implementation of (intern (write-to-string
...)) generates 3 temporary strings and churns the GC unnecessarily.

We have

(defun write-to-string (object &rest rest
                        &key escape radix base
                             circle pretty level length
                             case gensym array
                        &aux (stream (make-string-output-stream)))
  (declare (ignore escape radix base
                   circle pretty level length
                   case gensym array))
  (apply #'write object :stream stream rest)
  (get-output-stream-string stream))

There is one string allocated to make the stream, another temporary
one in writing the bignum to the stream, and another when copying the
result in get-output....  The middle allocation is completely
unnecessary -- in fact I just plugged a similar superfluous allocation
in gensym.  The other two could be either eliminated via a rewrite of
write-to-string, or, perhaps preferably, to capitalize on GCL's
current ability to make use of :dynamic-extent declarations in the
compiler to produce C code using alloca for such temporary storage.
Currently, only lists and conses have such support, but it would be
straightforward to add other structures.  In fact, in 2.7 I'd like to
take a shot at having automatic :dynamic-extent declarations inserted
where the compiler can figure out they are permissible, as in this
case for 'stream.  We can get the most mileage out of these and
'fixnum automatically determined declarations.

All such considerations seem a little foreign to the 'lisp philosophy'
of not worrying about memory management, a philosophy to which GCL has
apparently adhered throughout the course of its development thus far.

Take care,

> Bruno
> 
> 
> 

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