efficiency problem with polynomials (SymbolicRing vs PolynomialRing)

[zimmermann6]

Consider the following example:

sage: var('a,b,c')
(a, b, c)
sage: time d=expand((a+b+c+1)^100)
CPU times: user 2.45 s, sys: 0.07 s, total: 2.52 s
Wall time: 2.53 s

I thought it would be more efficient to use PolynomialRing(),
but it is not:

sage: P.<a,b,c> = PolynomialRing(QQ)
sage: time d=(a+b+c+1)^100
CPU times: user 10.28 s, sys: 0.07 s, total: 10.35 s
Wall time: 12.59 s

However if one wants to factor d, then PolynomialRing is faster
(SymbolicRing seems to loop forever):

sage: time e = d.factor()
CPU times: user 28.87 s, sys: 0.36 s, total: 29.23 s
Wall time: 34.20 s

Component: performance

Issue created by migration from https://trac.sagemath.org/ticket/8158

[zimmermann6]

comment:2

PolynomialRing is still slower with Sage 5.11, even with integer coefficients:

+--------------------------------------------------------------------+
| Sage Version 5.11, Release Date: 2013-08-13                        |
| Type "notebook()" for the browser-based notebook interface.        |
| Type "help()" for help.                                            |
+--------------------------------------------------------------------+
sage: var('a,b,c')
(a, b, c)
sage: %time d=expand((a+b+c+1)^100)
CPU times: user 16.35 s, sys: 0.26 s, total: 16.61 s
Wall time: 18.59 s
sage: P.<a,b,c> = PolynomialRing(QQ)
sage: %time d=(a+b+c+1)^100
CPU times: user 34.35 s, sys: 0.08 s, total: 34.42 s
Wall time: 35.80 s
sage: P.<a,b,c> = PolynomialRing(ZZ)
sage: %time d=(a+b+c+1)^100         
CPU times: user 32.29 s, sys: 0.07 s, total: 32.36 s
Wall time: 34.89 s

Paul

[mezzarobba]

comment:4

I doubt there is much to do here except reduce the overhead of the singular interface (especially regarding memory management) or singular itself. On my system, ginac (1.6.2) is already faster than singular (3.1.6):

 > time(expand((a+b+c+1)^100));
1.184s

> timer=1;
> ring r=0,(a,b,c),lp;
> poly p=(a+b+c+1)^100;
//used time: 1.95 sec

Both interfaces have comparable overhead (sage 6.2.beta4):

sage: %time _=expand((a+b+c+1)^100)
CPU times: user 3.13 s, sys: 16 ms, total: 3.14 s
Wall time: 3.14 s

sage: P.<a,b,c> = PolynomialRing(QQ,order='lex')
sage: %time _=(a+b+c+1)^100
CPU times: user 5.59 s, sys: 8 ms, total: 5.6 s
Wall time: 5.59 s

but not for the same reason—the advantage of standalone singular over libsingular called from sage seems to be due in large part to its faster memory allocator, and we can make the singular version significantly faster by forcing sage to use tcmalloc instead of the system malloc():

$ LD_PRELOAD="/usr/lib/libtcmalloc.so.4" sage
...
sage: var('a,b,c')
(a, b, c)
sage: %time _=expand((a+b+c+1)^100)
CPU times: user 2.89 s, sys: 36 ms, total: 2.92 s
Wall time: 2.92 s
sage: P.<a,b,c> = PolynomialRing(QQ,order='lex')
sage: %time _=(a+b+c+1)^100
CPU times: user 3.4 s, sys: 12 ms, total: 3.41 s
Wall time: 3.41 s

[zimmermann6]

comment:5

the speedup obtained with tcmalloc is impressive, could this be useful in other parts of Sage?

Paul