#15036: Speed up matrix repr for matrices larger than 20
-------------------------------+-----------------------------
Reporter: nbruin | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-5.12
Component: linear algebra | Keywords:
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Dependencies: | Stopgaps:
-------------------------------+-----------------------------
See this [https://groups.google.com/d/msg/sage-devel/Gnw389Bd-
0k/bqprN5AxtK8J sage-devel discussion].
Sage has a very nice feature where it tries to not print all entries of a
large matrix:
{{{
sage: A=matrix(20,20,[2]*400)
sage: A
20 x 20 dense matrix over Integer Ring (type 'print A.str()' to see all of
the entries)
}}}
But, as you see, Sage has to do some magic to know that `A` refers to the
matrix in question. Indeed, in other situations it won't find a useful
name:
{{{
sage: B=A
sage: A
20 x 20 dense matrix over Integer Ring (type 'print obj.str()' to see all
of the entries)
}}}
The process of finding a name consists of trawling through all "globals"
dictionaries on the call stack. This is an incredibly expensive operation
which also breaks python's programming model: reverse lookups of bindings
are not part of the language specification.
The main concern here is that string representations may not actually make
it to an output stream: they may be part of a (perhaps poorly constructed)
exception message that gets caught. Fixing the exception message may not
be an option, since some of these happen internally in python. TO
illustrate the dramatic effect, consider:
{{{
sage: def t(depth,N,n):
....: if depth:
....: return t(depth-1,N,n)
....: else:
....: G = matrix([[2 for u in range(N)] for v in
range(N)])
....: for i in range(n):
....: _=repr(G)
}}}
Trying it with a flat call stack is already showing that the repr of a
20x20 matrix is much more expensive to produce than for a 19x19 matrix (a
factor 80):
{{{
sage: timeit('t(0,19,10)')
125 loops, best of 3: 2.14 ms per loop
sage: timeit('t(0,20,10)')
5 loops, best of 3: 172 ms per loop
}}}
With a deep call stack this gets even more pronounced:
{{{
sage: sage: timeit('t(100,19,10)')
125 loops, best of 3: 2.22 ms per loop
sage: timeit('t(100,20,10)')
5 loops, best of 3: 5.45 s per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/15036>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
