#13400: Use strong caches diligently
-------------------------------+--------------------------------------------
Reporter: nbruin | Owner: robertwb
Type: enhancement | Status: new
Priority: major | Milestone: sage-wishlist
Component: coercion | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
-------------------------------+--------------------------------------------
Comment (by nbruin):
Replying to [comment:16 SimonKing]:
> We could consider to put stuff from
`sage.rings.quotient_rings.QuotientRing_generic.__init__` or
`QuotientRing_nc.__init__` directly into
`sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic.__init__`
and
`sage.rings.finite_rings.finite_field_prime_modn.FiniteField_prime_modn.__init__`.
Yes, if that speeds things up that might benefit quite a bit of sage.
Almost any considerable computation over ZZ (and, by first clearing
denominators, over QQ) benefits enormously from a multimodular approach,
and I expect a lot of computations in sage to already make use of that. It
would be great if these can be computed using the general framework, so
construction of finite fields and conversion between ZZ and GF(p) should
be blindingly fast. Basically anything goes. This case is different from
all other rings *because* it is so close to the metal.
> Hence, I suggest that `IntegerModRing.__init__` puts the ring into a
strong cache, if it would also cache the elements.
With a prudently chosen bound, this would probably not lead to excessive
memory use. I'm wondering whether there's any benefit, though. For
elliptic curve computations and other arithmetic-geometric things there
might be: One often has to look at the reduction modulo *all* primes below
a certain bound, so if one does so repeatedly, the gain can be
substantial. This might explain why the elliptic curves code is relatively
sensitive to these things. Although I think the most heavy duty
applications of this get seconded to GP/Pari wholesale anyway, so would
not involve sage finite fields at all.
It would not help multimodular stuff at all, though, because there one
usually choses primes that are as large as possible while still allowing
for the fastest arithmetic on the processor.
Usually one would randomize the choice of moduli, to amortize the cost of
choosing "wrong" moduli. However, that's only theoretically wise. For an
actual application, when you choose a prime a little below 2^31^ (or
whatever you need to still be able to do a full mult and do a mod
computation afterwards. REALLY worth delving into your CPU's instruction
set to see if a "mult into two 64-bit registers" combined with a
"remainder of 128 mod 64 bit number" exist, because it gives you twice the
number of bits for almost the same price -- hopefully we are already using
libraries that do that for us), it's NEVER going to be a bad one, so using
it all the time's not bad (OK, on a 4GHz machine in a computation that
takes 10^6^ cycles, it would be happening about 1.25 times a month)
What might be a good idea is to have a
{{{
GoodPrimesForMultiModularComputationsIterator()
}}}
which could always start with giving primes from a fixed set (in fixed
order or not) and then continue with generating new ones. If we strongly
cache the fields belonging to those first ones, we'd get most of the
benefit at limited memory cost.
Of course it does mean changing all prime selection loops for multimodular
stuff to using this iterator.
The next bit is tuning the crossover points between
naive/multimodular/padic methods for most of these.
The main thing this does is mitigate the effects if finite field
construction cannot be made lightning fast in general. We still need
conversion between ZZ and GF to be lightning fast, even if that means
special casing this in relevant code paths. It's nice if derived
conversions between matrix algebras and polynomial rings would be
similarly fast.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13400#comment:17>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
