[Openmcl-devel] Bignum speed

[Gary Byers]

Sorry for not responding sooner.

"Plans" in the sense of "in N weeks, someone plans to do X, Y, and Z
and therefore speed things up by M percent" ?  I don't know of any
such plans, no.

"Plans" in the sense of many people thinking "someday, someone should
take the time to do X, Y, and Z, and therefore speed things up ..." ?
Sure.

Designing and implementing really good bignum code takes significant
time.  Taking bignum code that's often pretty bad (worse than it seems
that it should be ...) and making it "not so bad" or "not bad at all"
or "maybe kind of good" takes far less time.  In some cases, one would
hit a wall where there's no more low-hanging fruit left and further
improvements involve better algorithms (or better support for doing
unboxed arithmetic, or ...), but I don't think that we're particularly
close to that wall, or that anyone's put any effort/time into getting
there.

I don't know exactly how to quantify what it would mean to go from
where things are now to where we could get with a moderate amount of
effort; I've poked at some of the code in the last few days and seem
to have gotten some improvement (maybe 2X-3X in some cases, though
it's hard to know if those cases are representative and - since memory
allocation/GC costs factor into this - should note that those results
weren't obtained in a controlled environnent.  (The kinds of stuff
that I did just involved the obvious first steps one might take in
trying to improve code: removing function call overhead, declaring the
types of things that're heavily used and non-obvious, removing
unnecesary typechecking, etc.  Again, there's a limit to how far this
approach can take you; again, it's not surprising that doing obvious
and simple things to improve performance ...  improves performance, at
least some.)

Two things that someone interested in helping CCL's bignum performance
could provide that'd help are:

1) A fistful of cash.  (Hey, I had to mention it.)  We -do- do work
on CCL that isn't directly funded, but a significant amount of work
(multiple person-months) is much more likely to happen if it's funded
than if it isn't.

2) Concrete examples of things where performance is bad.  (It may
be the case that things are just bad across the board; I don't know.)
The simpler it is to reproduce a performance problem (or an outright
bug, for that matter), the more time someone can put into trying to
improve/fix the problem.




On Tue, 14 Oct 2008, Waldek Hebisch wrote:

> Are there any plans to speed up large integer arithmetic?
> Currently it looks that large integer multiplication in
> Closure CL is much slower that in some other Lisp implementations.
> I understand that in typical applications speed of large
> integer operations is irrelevant.  However, for computer
> algebra systems like FriCAS large integer integer arithmetic
> is very important.  Closure CL is quite fast on some operations
> and on average on FriCAS testsuite is second one (after sbcl),
> however on some realistic computation Closure CL is the slowest
> (when compared to sbcl, clisp, ecl and gcl) -- the reson
> seem to be very poor large integer performance.
>
> --
>                              Waldek Hebisch
> hebisch at math.uni.wroc.pl
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel
>
>