Opened 11 years ago
Closed 11 years ago
#11684 closed defect (fixed)
Obtaining coefficients of polynomials over finite fields is extremely slow
Reported by: | johanbosman | Owned by: | tbd |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7.2 |
Component: | performance | Keywords: | polynomials, finite fields |
Cc: | Merged in: | sage-4.7.2.alpha3 | |
Authors: | Johan Bosman, Simon King | Reviewers: | Simon King, Johan Bosman |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #11685 | Stopgaps: |
Description (last modified by )
If we have a polynomial over a finite field and we want to obtain its coefficients, then there seems to be a lot of conversion overhead. It is a lot slower than multiplying such polynomials:
sage: K.<a> = GF(5^3) sage: P = PolynomialRing(K, 'x') sage: f = P.random_element(100) sage: timeit('f.list()') 5 loops, best of 3: 115 ms per loop sage: timeit('f * f') 625 loops, best of 3: 794 µs per loop
If, on the other hand, we do not use NTL, then we can obtain the coefficient list without any delays, though in that case multiplication is a lot slower:
sage: P = PolynomialRing(K, 'x', implementation='not NTL') sage: f = P(f) sage: timeit('f.list()') 625 loops, best of 3: 968 ns per loop sage: timeit('f * f') 25 loops, best of 3: 12.3 ms per loop
This performance issue occurs in both 4.7 and 4.7.1.rc1.
Apply
to the Sage library.
Attachments (2)
Change History (17)
Changed 11 years ago by
comment:1 Changed 11 years ago by
- Dependencies set to #11685
- Status changed from new to needs_review
The uploaded patch improves the speed slightly:
sage: K.<a> = GF(5^3) sage: P = PolynomialRing(K, 'x') sage: f = P.random_element(100) sage: timeit('f.list()') 125 loops, best of 3: 2.92 ms per loop
A real fix would of course be an NTL wrapper for finite fields, which is a huge project that may not get finished soon.
comment:2 Changed 11 years ago by
The code of list()
currently does [self[i] for i in range(celement_len(&self.x, _parent))]
. You improved the __getitem__
method.
But still, calling the __getitem__
method over and over again seems to create a lot of overhead. I am sure that NTL provides a method that returns the list of coefficients. So, why not use that instead?
And if that is impossible, note that most lines of __getitem__
are concerned with preparatory steps, namely:
cdef ZZ_pE_c c_pE cdef cparent _parent _parent = get_cparent(self._parent) _parent[0].restore() c_pE = ZZ_pEX_coeff(self.x, i) K = self._parent.base_ring()
I am pretty sure that it is possible to do these preparatory steps only once. Hence, I suggest to be a bit more "explicit" in the list()
method, rather than calling self[i]
.
Of course, in addition to that, one should also keep your improvement of __getitem__
.
comment:3 Changed 11 years ago by
The problem is that Sage uses NTL for polynomials over finite fields, but not for elements of finite fields. So simply using NTL's list method wouldn't work (unfortunately). I'll try to see whether a direct list() method will improve speed further. Though I suspect that 99% of the running time goes into
K(ZZ_pE_c_to_list(c_pE))
so that the gain will be negligible.
comment:4 Changed 11 years ago by
- Status changed from needs_review to needs_info
comment:5 Changed 11 years ago by
I already created a patch for the more direct approach. I am now running doc tests. The additional speed gain in your example is something like 20%.
comment:6 Changed 11 years ago by
- Status changed from needs_info to needs_review
At least the tests in devel/sage/doc pass. Hence, I have already posted my patch. Here are the timings:
sage: K.<a> = GF(5^3) sage: P = PolynomialRing(K, 'x') sage: f = P.random_element(100)
#11685 only:
sage: timeit('f.list()') 5 loops, best of 3: 79.9 ms per loop
#11685 with your patch:
sage: timeit('f.list()') 125 loops, best of 3: 2.36 ms per loop
All patches:
sage: timeit('f.list()') 125 loops, best of 3: 2.03 ms per loop
OK, that's only a gain of 14%. But I had one run where it took 2.42 ms with one patch and 1.98 ms with both patches (that's why I stated 20% in my previous post).
Anyway, does the second patch make sense? I am currently running doc tests, so that probably I can review both #11685 and your patch from here.
comment:7 Changed 11 years ago by
- Reviewers set to Simon King
I already stated that your patch improves the __getitem__
method considerably, and I can confirm the resulting speedup in list()
.
The long doctests of both devel/sage-main/doc and devel/sage-main/sage pass. Hence, I give your patch a positive review.
Of course I can not review my own patch. So, I'd appreciate if you could have a look on it.
comment:8 Changed 11 years ago by
I've been travelling all day; I'll start reviewing right now. ;)
comment:9 follow-up: ↓ 10 Changed 11 years ago by
- Status changed from needs_review to needs_work
There's a declaration
cdef ZZ_pE_c c_pE
in your code but it isn't used. So you might as well leave it out. ;).
comment:10 in reply to: ↑ 9 Changed 11 years ago by
Replying to johanbosman:
There's a declaration
cdef ZZ_pE_c c_pEin your code but it isn't used. So you might as well leave it out. ;).
Right. That is a copy-and-paste error.
Changed 11 years ago by
More direct coefficient list creation for NTL polys over finite fields. Apply after Johan's patch
comment:11 Changed 11 years ago by
- Status changed from needs_work to needs_review
I just updated my patch. So, "needs review" again.
comment:12 Changed 11 years ago by
- Reviewers changed from Simon King to Simon King, Johan Bosman
- Status changed from needs_review to positive_review
The code looks okay now, all doctests pass, and the documentation builds fine.
comment:13 follow-up: ↓ 14 Changed 11 years ago by
- Description modified (diff)
Make someone review #11685... ;-)
comment:14 in reply to: ↑ 13 Changed 11 years ago by
comment:15 Changed 11 years ago by
- Merged in set to sage-4.7.2.alpha3
- Resolution set to fixed
- Status changed from positive_review to closed
To be used after applying the fix of #11685