Hi There,
Comparison of large vectors in Sage is slow in a surprising way: even if all
the entries of the vectors are different, the cost is proportional to the
length of the vector instead of having constant cost !
sage: l = 1000; m0 = vector(ZZ, [0]*l); m1 = vector(ZZ, [1]*l)
sage: %timeit m0 == m1
625 loops, best of 3: 656 盜 per loop
sage: l = 10000; m0 = vector(ZZ, [0]*l); m1 = vector(ZZ, [1]*l)
sage: %timeit m0 == m1
125 loops, best of 3: 5.66 ms per loop
sage: l = 100000; m0 = vector(ZZ, [0]*l); m1 = vector(ZZ, [1]*l)
sage: %timeit m0 == m1
5 loops, best of 3: 59.1 ms per loop
It happens whatever ring you are using. The reason is the following:
The various vector classes inherits from FreeModuleElement which defines
def __richcmp__(left, right, int op):
[...]
return (<Element>left)._rich_to_bool(op, (
<FreeModuleElement>left)._cmp_same_ambient_c(right))
[...]
ultimately calling the following very inadequate solution:
cdef int _cmp_same_ambient_c(left, FreeModuleElement right) except -2:
return cmp(left.list(copy=False), right.list(copy=False))
On the other hand over ZZ, the vector are instances of Vector_integer_dense
which defines:
cdef int _cmp_c_impl(left, Element right) except -2:
cdef Py_ssize_t i
cdef int c
for i from 0 <= i < left.degree():
c = mpz_cmp(left._entries[i],
(<Vector_integer_dense>right)._entries[i])
if c < 0:
return -1
elif c > 0:
return 1
return 0
But it is never called. I'd like to have confirmation that adding to all
vectors classes (following sage/structure/element.pyx line 881 (5.0.rc0))
def __richcmp__(left, right, int op):
return (<Element>left)._richcmp(right, op)
is the correct solution. Removing the offending __richcmp__ in
FreeModuleElement seems to solve the problem once for all for all rings but
introduce a lot of other problems.
Also it is very likely that the same problem is occuring in different places
(not only the various vector classes) and I'm not completely sure where to
look. I'd rather have an automatic way to find all the places where this fails
and also add the check to TestSuite if possible. Does anyone have a suggestion
for that ? Is it possible to check from Python that any subclass of Element
providing _cmp_c_impl (cdef) does also properly define __richcmp__ or does it
have to be checked on sources with the drawback that if someone introduce the
same mistake it could remain unnoticed for quite a long time ?
Cheers,
Florent, which always have trouble with Cython comparison and which seems not
to be the only one !
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
