Dear Gaby, Waldek, Ralf,
Waldek Hebisch <hebi...@math.uni.wroc.pl> writes:
> 1) Yes. Currently operations from IntegerMod can not be inlined, so
> every operation from IntegerMod pays cost of function call. The
> reason is that p is parameter of the type so to perform operations
> you need the type. Spad compiler refuses to inline any operation
> which need to access its type -- the reason is that in case of
> recompilation system could break in strange ways. So, operations
> in IntegerMod do not need further function calls, but you need
> to call them.
I guess that this would be a major general speed improvement - Aldor style
"inline" statements...
Gaby, did you work on this yet? Also, could you report on the other
optimizations you build in some time ago? That would be great! (I
don't even know what they do roughly...)
> 2) After you eliminate cost of function call (say by creation version
> of IntegerMod which has p as parameter to every operation) there
> is still a substantial cost. Namely, the most expensive part of
> modular computation is computing remainders. Generic code
> specialized to modular arithmetic will compute remainders after
> any operations and this can not be fast. Given that our basic
> step is multiplication and addition we would get two remainder
> operations per step which will probably take around 40-50 clocks
> -- slower than dmp2.spad (and I do not count overhead for control
> etc.). When multiplying modular polynomials one can avoid most of
> remainder operations by allowing integers to became slightly
> bigger and performing modular reduction only at the end.
So, in essence: there are cheaper algorithms for dense polynomials
operations when we know that the coefficient domain is Z_p. I guess it
*might* be desirable at some point to do the specialisation within
DensePolynomial, ie.
DensePolynomial(R): with
...
== add
-- the following line is currently impossible maybe, we could have an
-- appropriate category and set p:=size()$R instead.
if R is IntegerMod p then
...
else
...
but it is certainly more important to do what's possible *now*, and not
wait until by magic the compiler and the language improves.
Furthermore, I'm not even sure whether this really is desirable.
Actually, I think that the representation (in particular dense
vs. sparse) should be given as an option to the domain constructor.
(Sage allows this, you can not only choose sparse or dense, but also
the implementation, i.e., NTL or FLINT)
A dream: be competitive with the best available implementations. (I'd
be happy with having one lisp implementation to optimize for, i.e., ecl
or sbcl, of course, still supporting all the others.)
Martin
------------------------------------------------------------------------------
This SF.net email is sponsored by:
SourcForge Community
SourceForge wants to tell your story.
http://p.sf.net/sfu/sf-spreadtheword
_______________________________________________
open-axiom-devel mailing list
open-axiom-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/open-axiom-devel
