Re: What is GCL about? was Re: [Gcl-devel] numerical quirks

[Paul F. Dietz]

Camm Maguire wrote:

> By the way, although detailed performance analysis is still a ways
> off, my first impression is that memory layout is the bottleneck on
> modern systems.  Is anyone aware of algorithms to group conses onto
> pages to minimize the number of links across page boundaries?

Minimizing the number of links is hard, but typically you get
good locality by having a copying compacting garbage collector.  Lists
tend to get copied together into nearby memory locations.  You can
even exploit this to do prefetches under the assumption that
successive cons cells of a list are laid out consecutively.

You might try moving stuff you know is not going to be referenced
much (for example, documentation strings) off into a separate area
of memory.

> Sounds
> like an NP complete traveling salesman problem.  In any case, this is
> where image size still matters, IMHO, not in the lack of available
> system memory.  I've committed a few patches to the maxima tree to
> enable building with our ansi image, and it is significantly slower in
> running 'make check'.  Likewise, Clisp, which produces an apparently
> much smaller maxima image (rss size), performs about as fast as GCL on
> 'make check' even though it has no native code capability.  I hope we
> can find time to look into these issues soon.

One source of slowness may be some of the algorithms.  I notice many
of the sequence functions run in O(n^2) time on lists.  We'd also
benefit from having compiler macros to implement special cases (for
example: (ASSOC ... ... :TEST #'EQ), (MAPCAR #'(LAMBDA (X) ...) ...),
(MEMBER ... ... :TEST #'EQ), etc.)

Do you have any more detailed profile of where the time and space
are going?

        Paul