Opened 8 years ago

Closed 7 years ago

#13257 closed defect (worksforme)

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

Reported by: jlopez Owned by: robertwb
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: coercion Keywords: days45
Cc: fredrik.johansson, jlopez, SimonKing Merged in:
Authors: Reviewers: Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by 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

Attachments (1)

trac_13257-modn_conversion_speedup-ts.patch (1.7 KB) - added by tscrim 7 years ago.
Changed implementation

Download all attachments as: .zip

Change History (12)

comment:1 Changed 8 years ago by jlopez

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}

comment:2 Changed 8 years ago by jlopez

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.

Last edited 8 years ago by jlopez (previous) (diff)

comment:3 Changed 8 years ago by jlopez

  • Description modified (diff)

comment:4 Changed 7 years ago by tscrim

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

comment:5 Changed 7 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Status changed from new to needs_review

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

comment:6 follow-up: Changed 7 years ago by robertwb

  • Status changed from needs_review to needs_work

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.

comment:7 in reply to: ↑ 6 Changed 7 years ago by tscrim

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

Changed 7 years ago by tscrim

Changed implementation

comment:8 Changed 7 years ago by tscrim

  • Keywords days45 added
  • Status changed from needs_work to needs_review

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

comment:9 Changed 7 years ago by jpflori

  • Authors Travis Scrimshaw deleted
  • Milestone changed from sage-5.10 to sage-duplicate/invalid/wontfix
  • Reviewers set to Jean-Pierre Flori
  • Status changed from needs_review to positive_review

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.

comment:10 Changed 7 years ago by tscrim

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

comment:11 Changed 7 years ago by jdemeyer

  • Resolution set to worksforme
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.