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:

Status badges

Description (last modified by leif)

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

  1. trac_11684_coefficient_speedup.patch
  2. trac_11684_list_speedup.patch

to the Sage library.

Attachments (2)

trac_11684_coefficient_speedup.patch (774 bytes) - added by johanbosman 11 years ago.
To be used after applying the fix of #11685
trac_11684_list_speedup.patch (1.3 KB) - added by SimonKing 11 years ago.
More direct coefficient list creation for NTL polys over finite fields. Apply after Johan's patch

Download all attachments as: .zip

Change History (17)

Changed 11 years ago by johanbosman

To be used after applying the fix of #11685

comment:1 Changed 11 years ago by johanbosman

  • Authors set to Johan Bosman
  • 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 SimonKing

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 johanbosman

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 johanbosman

  • Status changed from needs_review to needs_info

comment:5 Changed 11 years ago by SimonKing

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 SimonKing

  • Authors changed from Johan Bosman to Johan Bosman, Simon King
  • 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 SimonKing

  • 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 johanbosman

I've been travelling all day; I'll start reviewing right now. ;)

comment:9 follow-up: Changed 11 years ago by johanbosman

  • 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 SimonKing

Replying to johanbosman:

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. ;).

Right. That is a copy-and-paste error.

Changed 11 years ago by SimonKing

More direct coefficient list creation for NTL polys over finite fields. Apply after Johan's patch

comment:11 Changed 11 years ago by SimonKing

  • Status changed from needs_work to needs_review

I just updated my patch. So, "needs review" again.

comment:12 Changed 11 years ago by johanbosman

  • 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: Changed 11 years ago by leif

  • Description modified (diff)

Make someone review #11685... ;-)

comment:14 in reply to: ↑ 13 Changed 11 years ago by pbruin

Replying to leif:

Make someone review #11685... ;-)

Done!

comment:15 Changed 11 years ago by leif

  • Merged in set to sage-4.7.2.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.