On 1/30/12 2:36 AM, Martin Albrecht wrote:
Dear Martin,
Hi Benjamin, (CC [sage-devel] where I think this discussion belongs),
Of course, an implementation that uses the library routines directly
will be the fastest. However, this is still pretty sad for the standard
code. I looked into it:
Interestingly, just the call to M.new_matrix is horribly slow, over
twice as slow as the entire My_matrix_from_columns. This only happens
the first time, though; after that the matrix space is cached and the
call is fast:
sage: M = Matrix(GF(2),5000,5000); M.randomize()
sage: L = range(5000); shuffle(L); L = L[:2500]
sage: time M.new_matrix(len(L))
2500 x 5000 dense matrix over Finite Field of size 2
Time: CPU 0.70 s, Wall: 0.81 s
sage: time M.new_matrix(len(L))
2500 x 5000 dense matrix over Finite Field of size 2
Time: CPU 0.02 s, Wall: 0.02 s
for comparison:
sage: time N=My_matrix_from_columns(M,L)
Time: CPU 0.25 s, Wall: 0.31 s
I did notice some missing cdefs and some inefficient python comparisons
in the matrix_from_columns method, but even taking care of those didn't
help the timings all that much. Possibly the real problem here is
unboxing of each element in set_unsafe in matrix_mod2_dense.pyx? It
seems that every element is converted to an integer, which seems fairly
slow:
sage: a=GF(2)(0)
sage: timeit('int(a)')
625 loops, best of 3: 385 ns per loop
Anyways, that's a start into diagnosing the underlying problem.
Thanks,
Jason
Patch for matrix1.pyx which adds some of the cdefs in:
diff --git a/sage/matrix/matrix1.pyx b/sage/matrix/matrix1.pyx
--- a/sage/matrix/matrix1.pyx
+++ b/sage/matrix/matrix1.pyx
@@ -1452,7 +1452,7 @@
return Z
- def matrix_from_columns(self, columns):
+ def matrix_from_columns(self, list columns):
"""
Return the matrix constructed from self using columns with indices
in the columns list.
@@ -1472,16 +1472,17 @@
if not (PY_TYPE_CHECK(columns, list) or PY_TYPE_CHECK(columns,
tuple)):
raise TypeError, "columns (=%s) must be a list of
integers"%columns
cdef Matrix A
- cdef Py_ssize_t ncols,k,r
-
- ncols = PyList_GET_SIZE(columns)
+ cdef Py_ssize_t ncols,k,r,i,index,selfncols
+ selfncols=self._ncols
+ ncols = len(columns)
A = self.new_matrix(ncols = ncols)
k = 0
for i from 0 <= i < ncols:
- if columns[i] < 0 or columns[i] >= self._ncols:
+ index=columns[i]
+ if index < 0 or index >= selfncols:
raise IndexError, "column %s out of range"%columns[i]
for r from 0 <= r < self._nrows:
- A.set_unsafe(r,k, self.get_unsafe(r,columns[i]))
+ A.set_unsafe(r,k, self.get_unsafe(r,index))
k = k + 1
return A
--
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
