#5445: [with patch, needs review] coercion is very slow when new coercions are
discovered
----------------------+-----------------------------------------------------
Reporter: cwitty | Owner: robertwb
Type: defect | Status: new
Priority: major | Milestone: sage-3.4
Component: coercion | Keywords:
----------------------+-----------------------------------------------------
Consider the following timings:
{{{
sage: timeit("polygen(QQ, name='x'+str(ZZ.random_element(2^100)))+0")
625 loops, best of 3: 888 µs per loop
sage: timeit("polygen(QQ, name='x'+str(ZZ.random_element(2^100)))+0")
625 loops, best of 3: 1.45 ms per loop
sage: timeit("polygen(QQ, name='x'+str(ZZ.random_element(2^100)))+0",
number=5000)
5000 loops, best of 3: 2.18 ms per loop
sage: timeit("polygen(QQ, name='x'+str(ZZ.random_element(2^100)))+0")
125 loops, best of 3: 5.36 ms per loop
}}}
The operation of adding the Integer 0 to the polynomial keeps getting
slower and slower. This is because each time, it adds to the cache of
known coercions, and there's a performance bug in the cache data
structure.
In particular, in coerce_dict.pyx, this code:
{{{
if self.threshold and len(self) > len(self.buckets) *
self.threshold:
self.resize()
}}}
calls len(self), where len(self) has a slow, O(n) implementation. So
adding n items to a {{{TripleDict}}} takes O(n^2^) time.
The attached patch fixes this by storing the size in the {{{TripleDict}}},
instead of always recomputing it.
After applying the patch, the timings above become:
{{{
sage: timeit("polygen(QQ, name='x'+str(ZZ.random_element(2^100)))+0")
625 loops, best of 3: 690 µs per loop
sage: timeit("polygen(QQ, name='x'+str(ZZ.random_element(2^100)))+0")
625 loops, best of 3: 690 µs per loop
sage: timeit("polygen(QQ, name='x'+str(ZZ.random_element(2^100)))+0",
number=5000)
5000 loops, best of 3: 691 µs per loop
sage: timeit("polygen(QQ, name='x'+str(ZZ.random_element(2^100)))+0")
625 loops, best of 3: 690 µs per loop
}}}
So the operation is essentially constant time.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5445>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
