Coercion from ZZ['x'] to Integers(n)['x'] is VERY slow

[sagetrac-jlopez]

As reported by Fredrik Johansson in #12173 this is a horrible horror:

sage: a = ZZ['x'](range(100000))
sage: R = Integers(3)['x']
sage: %time R(a);
CPU times: user 39.38 s, sys: 28.55 s, total: 67.93 s
Wall time: 71.19 s

CC: @fredrik-johansson @sagetrac-jlopez @simon-king-jena

Component: coercion

Keywords: days45

Reviewer: Jean-Pierre Flori

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

[sagetrac-jlopez]

comment:1

Pruning the command shows the whole time is spent calling R._element_constructor_(a) so we should take a look on how that function works to see what's going on.

sage: %prun R(a);
         22 function calls in 66.593 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1   66.592   66.592   66.593   66.593 polynomial_ring.py:290(_element_constructor_)
        1    0.000    0.000   66.593   66.593 <string>:1(<module>)
        2    0.000    0.000    0.000    0.000 polynomial_ring.py:716(__hash__)
        6    0.000    0.000    0.000    0.000 {isinstance}
        3    0.000    0.000    0.000    0.000 {cmp}
        1    0.000    0.000    0.000    0.000 {method 'has_coerce_map_from' of 'sage.structure.parent.Parent' objects}
        3    0.000    0.000    0.000    0.000 integer_mod_ring.py:1030(__cmp__)
        3    0.000    0.000    0.000    0.000 {method 'base_ring' of 'sage.structure.category_object.CategoryObject' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {method 'parent' of 'sage.structure.element.Element' objects}

[sagetrac-jlopez]

comment:2

As a point of comparison, if we convert the polynomial back into a list then the operation runs about 500x faster:

sage: %time R(list(a));
CPU times: user 0.12 s, sys: 0.02 s, total: 0.14 s
Wall time: 0.14 s

So we probably have a 'lost in coercion' situation here.

[tscrim]

comment:4

The main problem is in compiled files (which is why %prun doesn't see it). In particular polynomial_modz_flint.pyx _element_constructor_ calls Polynomial_template's __init__() which converts a into a list of coefficients, which then reconstructs the polynomial by adding individual monomials together.

Where the time is taken is each time a monomial is added, a new polynomial is created. A partial solution is to convert polynomial inputs in _element_consturctor_ to a list and do that (this runs fast because it just does the coefficient coercion and sets the coefficient list of the new polynomial). I haven't looked too deeply into a general solution yet (I don't quite know if this is the only case where this slowdown occurs), but I would suspect one exists.

Best,

Travis

[tscrim]

Author: Travis Scrimshaw

[tscrim]

comment:5

Well, I should say that's where it used to be...it's now in polynomial_ring.py.

Something even more scary to me, this did not scale linearly with n:

sage: a = ZZ['x'](range(30000)) 
sage: R = Integers(3)['x']
sage: %time L = R(a)
CPU times: user 4.48 s, sys: 0.03 s, total: 4.52 s
Wall time: 4.61 s
sage: a = ZZ['x'](range(60000))
sage: %time L = R(a)
CPU times: user 17.84 s, sys: 0.09 s, total: 17.93 s
Wall time: 18.22 s

However I'm uploading a patch which just checks if it is a polynomial, and if so, it handles it as if it were a list. With the patch:

sage: a = ZZ['x'](range(1000000)) # Note the number of 0's
sage: R = Integers(3)['x']
sage: %time L = R(a)
CPU times: user 2.00 s, sys: 0.19 s, total: 2.18 s
Wall time: 2.55 s

To be honest, I'm still not perfectly happy with this solution since feels like a hack. If someone else can find an example of a significant slowdown which is not caught by this patch, please share. However as it stands, this patch is ready for review.

Best

Travis

[robertwb]

comment:6

Won't this patch break

sage: R.<x> = ZZ[]
sage: S.<y> = R[]
sage: S._element_constructor_(x^2)
 x^2

I think polynomial_template should be fixed, at the cost of requiring a couple more special methods.

[tscrim]

comment:7

Replying to @robertwb:

Won't this patch break

sage: R.<x> = ZZ[]
sage: S.<y> = R[]
sage: S._element_constructor_(x^2)
 x^2

Yes it does:

sage: S._element_constructor_(x^2)
y^2

I think polynomial_template should be fixed, at the cost of requiring a couple more special methods.

I'll see what I can do.

Thanks,

Travis

[tscrim]

Changed implementation

[tscrim]

Changed keywords from none to days45

[tscrim]

comment:8

Attachment: trac_13257-modn_conversion_speedup-ts.patch.gz

I've changed the fix to have Polynomial_template just convert the input polynomial into a list of coefficients and then pass that list back as a corresponding call the the original class's __init__() (rather than back to Polynomial_template) to take advantage of the specific implementations. This doesn't work quite as well for GF2, but that was significantly faster before anyways.

My timings with the patch:

sage: a = ZZ['x'](range(100000))
sage: R = Integers(3)['x']
sage: %time L = R(a)
CPU times: user 0.22 s, sys: 0.05 s, total: 0.26 s
Wall time: 0.35 s
sage: type(L)
sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint

sage: S = GF(3)['x']
sage: %time L = S(a)
CPU times: user 0.22 s, sys: 0.00 s, total: 0.22 s
Wall time: 0.26 s
sage: type(L)
sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint

sage: T = GF(2)['x'] % different because it uses NTL
CPU times: user 1.40 s, sys: 0.00 s, total: 1.40 s
Wall time: 1.50 s
sage: %time L = T(list(a))
CPU times: user 1.06 s, sys: 0.00 s, total: 1.06 s
Wall time: 1.16 s
sage: type(L)
sage.rings.polynomial.polynomial_gf2x.Polynomial_GF2X

Ready for review again.

Thanks,

Travis

[jpflori]

Reviewer: Jean-Pierre Flori

[jpflori]

comment:9

I think the horrible horror has been fixed in #12173 itself.
At least it takes 0 sec on my computer to perform this (except for Integers(2) where it is slightly solwer, 0.41 sec, surely because NTL is slow :)).

So I propose to close this as duplicate.

[jpflori]

Changed author from Travis Scrimshaw to none

[tscrim]

comment:10

Agreed. On 5.10.beta5:

sage: %time L = R(a)
CPU times: user 0.06 s, sys: 0.00 s, total: 0.07 s
Wall time: 0.07 s