Opened 10 years ago
Closed 9 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 )
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)
Change History (12)
comment:1 Changed 10 years ago by
comment:2 Changed 10 years ago by
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.
comment:3 Changed 10 years ago by
- Description modified (diff)
comment:4 Changed 9 years ago by
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 9 years ago by
- 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: ↓ 7 Changed 9 years ago by
- 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 9 years ago by
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
comment:8 Changed 9 years ago by
- 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 9 years ago by
- 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 9 years ago by
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 9 years ago by
- Resolution set to worksforme
- Status changed from positive_review to closed
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.