weird difference in performance
Pablo Angulo
A colleague was working in code for a certain projecteuler problem,
and found that using "len" of a list has a severe penalty on the sage
notebook, which doesn't happen on either the sage or the python console.
The two versions of the code below differ only in a call to the function
len. In console, the penalty in performance is around 10%, but in the
Sage notebook, it takes 3 times longer: the call to "len" costs doble
time as the rest of the loop. Anyway, we've been getting weird results
from time and its family lately (like CPU time longer than Wall time: is
that ok?). This is tested on versions 4.6 and 4.4, on different
architectures.
Regards
Version 1
tri=pen=hex=dt=dp=dh=1
results=[]
cota = 3
while len(results)<cota:
if tri==pen==hex:
results.append(tri)
if tri<=pen and tri<=hex:
dt+=1
tri+=dt
elif pen<=hex:
dp+=3;
pen+=dp
else:
dh+=4;
hex+=dh
print results
Version 2
cota = 3
tri=pen=hex=dt=dp=dh=1
results=[]
n=0
while n<cota:
if tri==pen==hex:
results.append(tri)
n+=1
if tri<=pen and tri<=hex:
dt+=1
tri+=dt
elif pen<=hex:
dp+=3;
pen+=dp
else:
dh+=4;
hex+=dh
print results
Tom Boothby
to an Integer required in comparing len(results)<cota.
The following code is faster than either of your versions. Note that
'3r' is an int, whereas '3' is an Integer.
tri=pen=hex=dt=dp=dh=1r
results=[]
cota = 3r
while len(results)<cota:
if tri==pen==hex:
results.append(tri)
if tri<=pen and tri<=hex:
dt+=1r
tri+=dt
elif pen<=hex:
dp+=3r
pen+=dp
else:
dh+=4r
hex+=dh
print results
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
John Cremona
len(results), but in the comparison between that value (a Python int)
and the Sage Integer cota, which involves creating a temporary Sage
integer and then doing the comparison between two of those.
In Pablo's second version there is no conversion, but still two Sage
integers are being compared.
In Tom's version the variable cota is a python int so (since taking
len() really is negligible!) the speedup comes from the speed of
comparing two (very small) python ints.
There is a lesson to be learned here, which is in fact very similar to
one which William explained very well recently: beware the Sage
preprocessor which converts every integer it sees to an Integer, which
can have serious performance consequences and is often not necessary!
John
William Stein
> So: in Pablo's first version the problem was not in computing
> len(results), but in the comparison between that value (a Python int)
> and the Sage Integer cota, which involves creating a temporary Sage
> integer and then doing the comparison between two of those.
Yep. Since this is such a common case, I wonder if we should modify
the Sage integer __richcmp__ method to be more sophisticated, and
allow direct comparisons with builtin Python types, without first
requiring them to be converted to Sage integers? The main problem
with:
"while len(results)<cota:"
is that in every iteration, len(results) is converted to a Sage
integer, and that conversion is expensive.
GMP has a function:
mpz_cmp_si
and we could rewrite Sage integers so if comparing with a Python int,
one grabs the long out of it (very quick) and calls mpz_cmp_si.
Does anybody want to do this? See the function
def __richcmp__(left, right, int op):
in devel/sage/rings/integer.pyx to get going.
> In Pablo's second version there is no conversion, but still two Sage
> integers are being compared.
>
> In Tom's version the variable cota is a python int so (since taking
> len() really is negligible!) the speedup comes from the speed of
> comparing two (very small) python ints.
>
> There is a lesson to be learned here, which is in fact very similar to
> one which William explained very well recently: beware the Sage
> preprocessor which converts every integer it sees to an Integer, which
> can have serious performance consequences and is often not necessary!
But also a good way to point out ideas for optimizations to Sage.
William
--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org
Dan Christensen
> There is a lesson to be learned here, which is in fact very similar to
> one which William explained very well recently: beware the Sage
> preprocessor which converts every integer it sees to an Integer, which
> can have serious performance consequences and is often not necessary!
I've often been quite frustrated by this aspect of the preparser. Not
only does it frequently have speed issues, even for trivial things like
comparing an Integer to the length of a sequence, it also can cause
problems when calling functions from other libraries which expect a
python int and can't handle getting an Integer. Moreover, it is so
transparent most of the time that it is a surprise to beginners and
sometimes even to people who aren't so new.
What would be the consequence of having sage use python int's by
default? Could sage do the conversion to Integer just when needed?
And when is it needed? Is it just for speeding up arithmetic with
large integers, or is it also to help with the coercion framework?
Or is the main reason so that 1/2 works?
I know this has been discussed before, but I think it's worth thinking
again about whether defaulting to python int's might be better.
Dan
pang
I see there is a second issue then: when I used
%run script.sage
from the ipython console, there is no preprocessing. That's why there
was "no penalty in the sage console". Of course, there is a penalty
when running the script as in:
sage script.sage
BTW: how do you guys run scripts from the sage console, in a way
similar to %run? This is not documented in the tutorial.
David Roe
Yep. Since this is such a common case, I wonder if we should modify
the Sage integer __richcmp__ method to be more sophisticated, and
allow direct comparisons with builtin Python types, without first
requiring them to be converted to Sage integers?
That's such a good idea that I did it. http://trac.sagemath.org/sage_trac/ticket/10314, ready for review.
BEFORE:
sage: b = 4r
sage: timeit("a < b")
625 loops, best of 3: 1.34 µs per loop
AFTER:
sage: a = 3
sage: b = 4r
sage: timeit("a < b")
625 loops, best of 3: 147 ns per loop
David
David Roe
sage: 15.factor()
works.
If you're frustrated with the preparser, I'd suggest adding
preparser(off)
to $HOME/.sage/init.sage
David
--
William Stein
> I think that while we're still using Python 2.x, where 2r/3r = 0, we
> absolutely need the preparser. The coercion framework can work with Python
> ints just fine: it's the automatic rounding that kills us. Much better
> speed for large integers is another benefit that you mentioned. Also, there
> are lots of number theoretic functions available on sage integers and not on
> Python ints. So currently
> sage: 15.factor()
> works.
>
> If you're frustrated with the preparser, I'd suggest adding
> preparser(off)
> to $HOME/.sage/init.sage
> David
Also, please _do_ report any issues with speed, external libraries,
etc., that come up.
As you can see above with ticket
http://trac.sagemath.org/sage_trac/ticket/10314 we do care, and will
try to address them!
Regarding loading scripts from the command line and get preparsing, I do either:
sage: load foo.sage
or
sage: attach foo.sage
The nice thing about attach is the file gets auto-reloaded any time it changes.
You can also load python files, e.g., "load foo.py" or "attach
foo.py", and the file won't be preparsed.
-- William
--
William Stein
> absolutely need the preparser.
Yes. Without it, it is far to easy to type something like
x^3 + 2*x^2 - 1/2*x + 5/3
and having that give x^3 + 2*x^2 + 1 would be a total disaster.
However, even with Python 3, the situation won't be much better, due
to 2/3 giving 0.666666... (and this isn't customizable).
William
--
William Stein
>
>> Yep. Since this is such a common case, I wonder if we should modify
>> the Sage integer __richcmp__ method to be more sophisticated, and
>> allow direct comparisons with builtin Python types, without first
>> requiring them to be converted to Sage integers?
>
> That's such a good idea that I did it.
> http://trac.sagemath.org/sage_trac/ticket/10314, ready for review.
See my review. I found a major bug, and have a little idea for an
easy speedup.
This is a great example of the review process in action, by the way.
>
> BEFORE:
> sage: a = 3
> sage: b = 4r
> sage: timeit("a < b")
> 625 loops, best of 3: 1.34 µs per loop
>
> AFTER:
> sage: a = 3
> sage: b = 4r
> sage: timeit("a < b")
> 625 loops, best of 3: 147 ns per loop
>
> David
>