[Gcl-devel] compiler speed

[Camm Maguire]

Greetings!  I've been working on this a bit, and have not been able to
find any more errors, which is good!  I'd like to get the 10,000/8
case up to the 50k runs or so you did with clisp, but have discovered
that we have a performance issue in the compiler which scales
quadratically with the number of variables.  I've come up with a fix,
which reduces the GCL portion of the compile time for your forms of
size 10000 to a small fraction of its earlier value.

I'm debating with myself whether its good to commit into the stable
branch before release.  Compile speed is not a major issue in most
cases -- nevertheless I think it useful to be able to report some good
statistics on your random tester which apply to the stable branch.
(BTW, toward this latter end, there are a few minor backports from 2.7
regarding :load-toplevel et.al., and a minor change to your
universe.lsp file omitting (or at least preceding with #+:setf) the
:method statement in your defgeneric dummy function, which are
necessary to get the random tester to work in the stable branch.  I'd
like to get this in if possible -- do you have an objection to
something like

#+(or (not :gcl) :setf)  (:method ((x integer) (y integer) (z
 integer)) (+ x y z))

?)

Thoughts on this most appreciated.

To summarize the change, the compiler maintains internal lists of
referred and changed variables for each level of certain forms.  These
lists are merged at certain points as one pops up a level.  The merge
avoids putting duplicates on the list, so looks something like (dolist
(v from-vars) (unless (member v to-vars) (push v to-vars))).  The
first obvious improvement was to add :test #'eq to the member.  GCL
will compile inline such a loop with no external function calls.  But
one can do better with a sorted array.  One can choose between
m*log(n) for binary searches  and max(m,n) for a linear search.  Just
doing a naive binary search, making sure the binary search routines
are fully optimized, gives results like the following against the
already improved list version using :test #'eq:

list:

real time       :     17.610 secs
run-gbc time    :      7.850 secs
child run time  :      8.590 secs
gbc time        :      1.010 secs

binary search:

real time       :     13.400 secs
run-gbc time    :      2.860 secs
child run time  :      8.610 secs
gbc time        :      1.830 secs


For reference, the original existing code with no improvements gives

real time       :     61.510 secs
run-gbc time    :     25.680 secs
child run time  :     34.790 secs
gbc time        :      0.560 secs

(I've also improved the time macro a bit.  The increased child run
time above is due to using full optimization in GCC in the last run.)

Take care,


"Paul F. Dietz" <address@hidden> writes:

> Camm Maguire wrote:
> 
> > Greetings!  OK, that's our bogey.  We're at about 80k now and counting
> > with no failures on the 1000 size.
> 
> I've been running the same.  149K and counting at size 1000 (with
> 6 lambda parameters.)
> 
>       Paul
> 
> 
> _______________________________________________
> 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