Opened 11 years ago

Closed 9 years ago

#12142 closed enhancement (fixed)

Speed up PARI finite field operations

Reported by: johanbosman Owned by: AlexGhitza
Priority: major Milestone: sage-5.12
Component: basic arithmetic Keywords:
Cc: mderickx, jpflori Merged in: sage-5.12.beta3
Authors: Peter Bruin Reviewers: Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14817, #14818, #14832, #14833 Stopgaps:

Status badges

Description (last modified by jdemeyer)

Let us perform a simple addition of finite field elements that are represented using PARI.

sage: F.<a> = GF(3^11)
sage: x = F.random_element()
sage: y = F.random_element()
sage: %timeit x + y
625 loops, best of 3: 13.2 µs per loop

Let us now measure how much time the *actual* addition takes:

sage: vx = x._FiniteField_ext_pariElement__value
sage: vy = y._FiniteField_ext_pariElement__value
sage: %timeit vx + vy
625 loops, best of 3: 4.6 µs per loop

This means two thirds of the execution time is used to wrap a ribbon around the result and only one third for the actual addition!

But in fact Pari has a faster implementation for finite fields than this! This was already mentioned at http://groups.google.com/group/sage-nt/browse_thread/thread/e2dbbc72caeb589a

sage: def pari_ffelt(x): parix=pari(x); return parix.lift().subst(parix.variable(), "ffgen((%s).mod)"%parix) 

sage: px = pari_ffelt(x)
sage: py = pari_ffelt(y)
sage: %timeit px + py
625 loops, best of 3: 2.43 µs per loop

For multiplication, we have the following timings:

sage: %timeit x * y
625 loops, best of 3: 18.2 µs per loop
sage: %timeit vx * vy
625 loops, best of 3: 8.4 µs per loop
sage: %timeit px * py
625 loops, best of 3: 3.33 µs per loop

This ticket implements an interface to PARI's FFELT type for non-prime finite fields. It can be tested by constructing finite fields as follows, for p prime and n >= 2:

sage: F.<a> = FiniteField(p^n, impl='pari_ffelt')

This implementation should probably become the default for non-prime finite fields of characteristic > 2 and cardinality > 216, superseding the existing PARI polmod implementation. This switch is the goal of ticket #14888.

Apply:

Attachments (6)

trac_12142-singular_conversion.patch (4.7 KB) - added by pbruin 10 years ago.
trac_12142-FiniteField_pari_ffelt.patch (53.1 KB) - added by pbruin 10 years ago.
based on 5.11.beta3
trac_12142-FiniteField_pari_ffelt.improved.patch (54.7 KB) - added by pbruin 10 years ago.
more speedups in element construction; initialisation from None allowed
trac_12142-reviewer.patch (1.4 KB) - added by jpflori 10 years ago.
Reviewer patch, trivial typo.
trac_12142-doctest.patch (1.1 KB) - added by pbruin 10 years ago.
add doctest
trac_12142-remove_cinit.patch (996 bytes) - added by pbruin 10 years ago.

Download all attachments as: .zip

Change History (30)

comment:1 Changed 11 years ago by pbruin

Cc: pbruin added

comment:2 Changed 10 years ago by mderickx

Cc: mderickx added

comment:3 Changed 10 years ago by jpflori

Cc: jpflori added

Just a reminder for myself, it would also be nice to have a common cython interface to deal with finite fields elements, surely using templates as for polynomials.

comment:4 Changed 10 years ago by pbruin

Authors: Peter Bruin
Cc: pbruin removed

I have been working on an interface to PARI's implementation of finite fields (t_FFELT). Like for the other interfaces (except the existing PARI polmod implementation), the field class is written in Python and the element class in Cython. I hope to upload a patch soon after cleaning up the documentation and fixing a minor problem.

The speed improvement for addition and multiplication relative to the current implementation appears to vary roughly from a factor 3 to a factor 12, depending on the size of the field.

For small fields, this PARI interface is (of course) much slower than Givaro (a factor 4-6 for F_{310}). For fields of characteristic 2, it is slower than NTL+gf2x, but the difference is not that dramatic.

comment:5 Changed 10 years ago by pbruin

Dependencies: #14817, #14818, #14832, #14833

This ticket led to several other patches, which I put into separate tickets; see the list of dependencies. The dependence on #14817 is optional.

A patch for this ticket is now practically ready.

comment:6 Changed 10 years ago by pbruin

Work issues: conversion from/to Singular

The attached patch implements a new class FiniteField_pari_ffelt and associated element class FiniteFieldElement_pari_ffelt. There is currently one doctest failure, related to conversion from and to Singular.

Changed 10 years ago by pbruin

comment:7 Changed 10 years ago by pbruin

Description: modified (diff)
Status: newneeds_review
Work issues: conversion from/to Singular

OK, converting between FiniteFieldElement and Singular was an easy generalisation of existing code. I will try to make a small table comparing the performance of the various implementations. In the meantime this is ready to be reviewed.

comment:8 Changed 10 years ago by pbruin

Here are some timings for addition and multiplication in the various implementations:

x, y random elements of a field of p^n elements
all times in microseconds

Addition:  %timeit -c -r 1 x + y

(p, n)     ntl/gf2e  givaro  pari_ffelt  pari_mod

(2, 15)    0.85      0.45    0.95        15.1
(2, 5000)  1.06      ----    1.84        3300

(3, 10)    ----      0.47    1.14        12.5
(3, 80)    ----      ----    1.75        44

(251, 2)   ----      0.51    1.30        9.0

Multiplication:  %timeit -c -r 1 x * y

(p, n)     ntl/gf2e  givaro  pari_ffelt  pari_mod

(2, 15)    1.11      0.61    1.51        22
(2, 1000)  5.0       ----    61          1060

(3, 10)    ----      0.57    4.0         19
(3, 80)    ----      ----    36          99

(251, 2)   ----      0.56    1.69        12.1

comment:9 Changed 10 years ago by pbruin

Status: needs_reviewneeds_work

Initialisation of finite field elements is too slow, and computing a/b raises a ZeroDivisionError if a = 0... A fix will be ready soon.

Changed 10 years ago by pbruin

based on 5.11.beta3

comment:10 Changed 10 years ago by pbruin

Status: needs_workneeds_review

Changed 10 years ago by pbruin

more speedups in element construction; initialisation from None allowed

comment:11 Changed 10 years ago by pbruin

Description: modified (diff)

comment:12 Changed 10 years ago by pbruin

Description: modified (diff)

Changed 10 years ago by jpflori

Attachment: trac_12142-reviewer.patch added

Reviewer patch, trivial typo.

comment:13 Changed 10 years ago by jpflori

Description: modified (diff)
Reviewers: Jean-Pierre Flori
Status: needs_reviewpositive_review

Patches look fine, doctests pass and there is indeed a very nice speedup.

comment:14 Changed 10 years ago by pbruin

For patchbot:

Apply trac_12142-FiniteField_pari_ffelt.improved.patch, trac_12142-singular_conversion.patch, trac_12142-reviewer.patch

comment:15 Changed 10 years ago by pbruin

Apply trac_12142-FiniteField_pari_ffelt.improved.patch, trac_12142-singular_conversion.patch, trac_12142-reviewer.patch 

Changed 10 years ago by pbruin

Attachment: trac_12142-doctest.patch added

add doctest

comment:16 Changed 10 years ago by pbruin

Description: modified (diff)

The next patch removes the Cython constructor __cinit__(), which is unnecessary since it just sets an attribute to NULL which is already guaranteed to be NULL. Actually, it just comments it out with an explanation for future reference. This should fix the remaining doctest failure and may give another slight speed improvement.

(I'm leaving this as "positive_review" since I can't set it back to "needs_review" immediately. The change is not entirely trivial, though.)

Version 0, edited 10 years ago by pbruin (next)

Changed 10 years ago by pbruin

comment:17 Changed 10 years ago by pbruin

Status: positive_reviewneeds_work

comment:18 Changed 10 years ago by pbruin

Status: needs_workneeds_review

comment:19 Changed 10 years ago by jpflori

Status: needs_reviewpositive_review

This change looks ok to me, and is very well documented.

I did not really pay attention to the doctests missing as you were copying from a large previous Sage file. Maybe we could take this opportunity to fix it as well and so increase coverage.

comment:20 Changed 10 years ago by jdemeyer

Description: modified (diff)
Milestone: sage-5.11sage-5.12
Summary: Speed up Pari finite field operationsSpeed up PARI finite field operations

comment:21 Changed 10 years ago by jdemeyer

Haven't read the code of #12142, but does pickling work properly and has it been doctested? If not, then #14888 should be set back to needs_work.

comment:22 Changed 10 years ago by pbruin

Yes, it works and there are doctests. Finite field elements are not implemented as type gen (as in libs/pari/gen.pyx), so the fact that pickling does not work for a gen that happens to be a t_FFELT does not affect this ticket.

comment:23 in reply to:  19 Changed 10 years ago by pbruin

Replying to jpflori:

I did not really pay attention to the doctests missing as you were copying from a large previous Sage file. Maybe we could take this opportunity to fix it as well and so increase coverage.

Actually the doctest coverage of all files in sage/rings/finite_rings is 100%, except integer_mod.pyx, which has a coverage of only 99/150 functions. Apart from that, I think I saw one or two colons that should be double colons. I don't think it is really worth the trouble to spend time on that in this ticket.

comment:24 Changed 9 years ago by jdemeyer

Merged in: sage-5.12.beta3
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.