Hi,
During the last few weeks I've spent time optimizing code, among other
things. A surprising number of random things I look at in Sage are
too slow by a factor of 10-100,
usually due to programming style. One way to help to remedy that
would be to write a book or article about how to program Cython +
Python *efficiently*, and avoid the numerous traps. Basically, one
false move in Python when implementing mathematics algorithms can
knock you down by a factor of 10-100 in speed. As an example of
this, try multiplying polynomials in ZZ['x'] in Sage right now:
sage: R.<x> = ZZ[]
sage: timeit('x*x',number=10^6)
1000000 loops, best of 3: 1.96 µs per loop
FLINT could do that multiply in a few hundred nanoseconds, so why does
it take 2 microseconds (2000 nanoseconds)? Because the code is
complicated and general, but was written without any thought about
efficiency. By making a few changes (really making the code less
clever), I get:
sage: timeit('x*x', number=10^6)
1000000 loops, best of 3: 687 ns per loop
The categories implementation as it is in Sage must be changed or
removed. There, I got your attention.
A few months ago some code was added to Sage by the combinat folks
called "categories". I recently learned ObjectiveC, and found out
that this idea of "categories" goes back to smalltalk at least, and
was fully implemented in ObjectiveC in the mid 1980s. It has little
to do with category theory in the sense of mathematics, though is
related. Basically, it is a way to attach a bunch of generic methods
to a class without using inheritance. So far so good.
The combinat folks implemented this programming idea in Sage not by
changing the Python languge, but by defining a custom __getattr__
method at sticking it in the base classes for Sage parents and
elements. The problem: this means that every single method lookup on
every single Sage object seem to now have about 1500nanoseconds added
to it in completely unnecessary overhead. Most of what Sage does is
call functions, so this is a huge, huge problem. Try it out for
yourself:
(1) Start up Sage and try this:
flat:~ wstein$ sage-4.4.4
----------------------------------------------------------------------
| Sage Version 4.4.4, Release Date: 2010-06-23 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: QQ.testit = 'foobar'
sage: timeit('QQ.testit',number=10^6)
1000000 loops, best of 3: 2.43 µs per loop
sage: timeit('QQ.testit',number=10^6)
1000000 loops, best of 3: 2.53 µs per loop
This is on my OS X laptop, so your timings may be different.
(2) Now go into SAGE_ROOT/devel/sage/sage/structure/parent.pyx
and change the line
def __getattr__(self, name):
to
def x__getattr__(self, name):
then restart sage with "sage -br"
----------------------------------------------------------------------
| Sage Version 4.4.4, Release Date: 2010-06-23 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: QQ.testit = 'foobar'
sage: timeit('QQ.testit',number=10^6)
1000000 loops, best of 3: 1.53 µs per loop
sage: timeit('QQ.testit',number=10^6)
1000000 loops, best of 3: 1.54 µs per loop
----
This is a major problem. The best solution I can think of at present
is to remove these methods from the top level of Sage, then add
objects like Parent_cat and Element_cat, and put them there. Then
change all the combinat objects to derive from those classes. I'm not
sure this would work though.
Anyway, a slowdown of more than 1 microsecond on everything throughout
sage is absolutely unacceptable.
So, big question -- am I just confused? It seems impossible that
nobody noticed this before, or that people made a conscious decision
to let this code in if it slows down Sage this much. (I.e., my guess
is that nobody even bothered to benchmark the code when refereeing
it.)
Robert B: since you were the one who decided to let this into Sage,
and since I know you know Python insanely well, am I just missing
something here? It seems to me like this one patch is a huge drain on
Sage's performance... So much so that I'm personally tempted to
just remove it for my own work. But maybe I'm just missing something
obvious.
--William
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-de...@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
