Re: [Axiom-developer] Re: Bug#407109: axiom: loops forever while )read'ing expression

[Waldek Hebisch]

Camm Maguire wrote:
> Greetings!
> 
> Waldek Hebisch <address@hidden> writes:
> > Now, one problem is that Axiom naively computes the sum.
> > Another problem is that gcd computations take quite a lot of
> > time (it seems that other systems can compute gcd 10-100
> > times faster).
> > 
> 
> Does axiom use GCL's gcd?  Are the gcd arguments most frequently
> fixnums or smaller?  2.7.0 has about a 2x improvement here, another
> 10% is easily in reach.  This seems even with cmucl and considerably
> faster than clisp.  I'm obviously interested in any factor of 10 or
> 100 that might be available -- any details here?
> 

I mean here polynomial gcd.  Yes, Axiom polynomial gcd uses integer
gcd from GCL (or more generally form the underlying Lisp).  However,
in best algorithms (IIRC Axiom has 6 different gcd algorithms) integer
gcd typically takes only small fraction of the time.  Best algoritms
use modular methods -- most of the time is spent in modular arithmetic
operating on rather small numbers.  I write "rather small" because
for problems like above the minimal size that works well is probably
of order 40 bits -- if fixnums are limited to 32 bit some program
use doubles instead.

Concerning Axiom slowness -- main reason is on Axiom side: every
modular arithmetic operation is done via (indirect!) function call.
This incures cost of function calls and (probably more important)
give no chance to Lisp optimizer.  And all opertaion are done in
generic arithmetic.

Of course, good Lisp can make Axiom code to run faster.  One obvious
thing is to have fast function calls.  Another is to have directly
representable fixnums (IIUC GCL 2.7.0 has them).  Also gc times may be
quite significant.  FYI, I have found that on polynomial manipulation
(in particular gcd) SBCL worked significantly faster (1.5 to 3 times
faster).  While I was unable to profile GCL, SBCL profile indicated
that significant percentage of time went into fixnum arithmetic,
so representable fixnums can help a lot.

While improvements in Lisp implementation can give us some speed
increase (say 2-3 times), I belive that in short term correct way
to speed up Axiom is to move some core computations down to Lisp or
C level.  In longer term improved Spad compiler could in principle
generate efficient Lisp code...

-- 
                              Waldek Hebisch
address@hidden