Get gf2x version 1.1 into Sage!

[williamstein]

Check out http://wwwmaths.anu.edu.au/~brent/gf2x.html

It's:

• by very well respected people
• GPL'd (v2 or later)
• Small pure C code
• and Paul Z. says:

for your information, on http://wwwmaths.anu.edu.au/~brent/gf2x.html you will
find an implementation up to 5 times faster than NTL's GF2X (for degree 2^20).

Latest 1.1 version is at http://gf2x.gforge.inria.fr/

Use spkgs at:

• http://boxen.math.washington.edu/home/jdemeyer/spkg/gf2x-1.1.spkg (spkg diff)
• http://boxen.math.washington.edu/home/jdemeyer/spkg/ntl-5.5.2.p1.spkg

Apply to Sage's root:

• attachment: trac_2114-gf2x.patch

Depends on #12447

CC: @zimmermann6 @malb @jpflori @jdemeyer

Component: packages: standard

Keywords: spkg gf2x

Author: Jean-Pierre Flori

Reviewer: Jeroen Demeyer

Merged: sage-5.11.beta1

Issue created by migration from https://trac.sagemath.org/ticket/2114

[williamstein]

comment:1

Emmanuel Thomé to me, Paul, Pierrick
	
show details 2:53 PM (5 hours ago) [gf2x-20070214.tar.gz]
	
	
Reply
	
	
	from	Emmanuel Thomé <Emmanuel.Thome@normalesup.org>
to	wstein@gmail.com,
cc	Paul Zimmermann <Paul.Zimmermann@loria.fr>,
Pierrick Gaudry <gaudry@lix.polytechnique.fr>,
date	Thu, Feb 14, 2008 at 2:53 PM
subject	gf2x package
	
hide details 2:53 PM (5 hours ago) [gf2x-20070214.tar.gz]
	
	
Reply
	
	
On Thu, Feb 14, 2008 at 06:12:34PM +0100, Paul Zimmermann wrote:
> https://github.com/sagemath/sage-prod/issues/2114

For your information, you might find the attached version more
packageable (it can live outside NTL, for instance). Yet, the build
process is still tricky: Auto tuning and so on. Depending on your
preferred practices for sage, your preferred option could be to
statically save the thresholds file per-machine.

Regards,

E.

The "attached version" is here:
http://sage.math.washington.edu/home/was/tmp/gf2x-20070214.tar.gz

[zimmermann6]

comment:2

A new version (0.3.1) is available from http://wwwmaths.anu.edu.au/~brent/gf2x.html.

[zimmermann6]

comment:4

GF2X has now its own development page: http://gf2x.gforge.inria.fr/.
It should be easier to incorporate into Sage now, but maybe it would be better
to include it through NTL, since since NTL 5.5, NTL can be configured to use GF2X as
auxiliary package. In such a way, Sage will benefit from GF2X for all computations with NTL.

[zimmermann6]

comment:5

Note that since ntl-5.5, NTL can now be configured to use GF2X instead of its own routines.
This is probably the easiest way to get GF2X into Sage.

[jpflori]

comment:7

Paul, I'm finally packaging this, only planning to build NTL on top of it, no "native" interface.
Is tuning still highly recommended? Because it really takes a long time.
I was thinking of providing an option (GF2X_TUNE=yes/no, any better idea?) to enable/disable it, not sure what the default should be.
The README suggests it would be yes by default.

[jpflori]

Changed keywords from none to spkg gf2x

[jpflori]

Author: Jean-Pierre Flori

[jpflori]

comment:8

Upped spkgs, with the GF2X_TUNE option off by default (took one hour on a quite recent Xeon (with only one thread, but I did not test whether tuning gets parallelized)).
Set it to yes to perform tuning.

I did not check this actually speeds up NTL, anyone wanting to benchmark the new NTL spkg against the old one please go ahead.

As NTL is a standard spkg, not sure what the way to go is.
Jeroen please decide what to do.

[jpflori]

Spkg diff, for review only.

[jdemeyer]

comment:9

Attachment: ntl-5.5.2.p1.diff.gz

Replying to @jpflori:

Jeroen please decide what to do.

Why should I? You should decide if you want this:
a. as standard package (which requires a discussion on sage-devel and changes to spkg/standard/deps)
b. as optional package (but then NTL needs to work both with and without gf2x)
c. not at all

[jpflori]

comment:10

I say we want this as a standard package and would prefer to avoid an optional stage (just imagine we patch ntl inbetween.
But I thought we needed optional before standard for all packages, so in this case this would be complicated.
So I'll post on sage-devel.

[vbraun]

comment:11

So does it actually speed up things, considering that we disable tuning? If not then forget about it. If yes then I'd be happy to see it included.

[jpflori]

comment:12

Just for hint, my experience playing with FLINT, using gf2x for GF(2) polynomials instead of the basic implementation inside FLINT using long gave an incredible speedup.
And from the maybe 4 years ago comments in the ticket description, it should also seepdup NTL.
I just don't have the time or the motivation to benchmark products of GF(2**n) elements (once you don't use Givaro) right now to prove it is beneficial.

[zimmermann6]

comment:13

Replying to @jpflori:

Paul, I'm finally packaging this, only planning to build NTL on top of it, no "native" interface.
Is tuning still highly recommended? Because it really takes a long time.
I was thinking of providing an option (GF2X_TUNE=yes/no, any better idea?) to enable/disable it, not sure what the default should be.
The README suggests it would be yes by default.

Jean-Pierre,

make tune-lowlevel is still highly recommended, since it will choose the best routine up to 9 words.
It takes a little more than one minute on my 4-year-old laptop (including recompiling the library).

Then you can do say make tune-toom TOOM_TUNING_LIMIT=100 to choose the best algorithm up to say
100 words (i.e., degree < 6400 on a 64-bit computer). It should take a few minutes only.

Paul

[jpflori]

Work Issues: tuning

[jpflori]

comment:14

Ok, I'll do that.
Thanks for the suggestion.

[jpflori]

comment:15

Replying to @jpflori:

Just for hint, my experience playing with FLINT, using gf2x for GF(2) polynomials instead of the basic implementation inside FLINT using long gave an incredible speedup.
And from the maybe 4 years ago comments in the ticket description, it should also seepdup NTL.
I just don't have the time or the motivation to benchmark products of GF(2**n) elements (once you don't use Givaro) right now to prove it is beneficial.

On my pc, multiplying two random elements of GF(2**10000) goes from 103us in Sage 5.9 with old NTL to 21.4us in 5.10.rc0 with NTL+gf2x.

[zimmermann6]

comment:54

Replying to @nexttime:

P.S.: There are other warnings where the return value of fgets() (IIRC) gets discarded / ignored, in tuning-related code. (But in those cases it's IMHO more obvious to the user that the warnings can safely be ignored.)

Leif, thanks, I've fixed a few upstream. It is always nice to get feedback when a package is used in Sage!

Paul

[jdemeyer]

comment:57

I made a few small changes to gf2x to make spkg-install more like most other standard packages. I also re-downloaded the upstream source, as timestamps got messed up somehow.

[jdemeyer]

comment:58

For NTL, I added the hg tag.

[jdemeyer]

Reviewer: Jeroen Demeyer

[nexttime]

comment:61

Replying to @jdemeyer:

I made a few small changes to gf2x to make spkg-install more like most other standard packages. I also re-downloaded the upstream source, as timestamps got messed up somehow.

You didn't fix "gf2x is a C/C+ software package" though... ;-)

Could you attach a diff of your changes?

I don't want to re-review everything. Retesting is odd enough.

[jdemeyer]

Spkg diff, for review only.

[jdemeyer]

Attachment: gf2x-1.1.diff.gz

[jdemeyer]

comment:62

Attachment: gf2x-1.1-jdemeyer.diff.gz

Replying to @nexttime:

You didn't fix "gf2x is a C/C+ software package" though... ;-)

Fixed now.

Could you attach a diff of your changes?

attachment: gf2x-1.1-jdemeyer.diff

[nexttime]

comment:63

Replying to @jdemeyer:

Replying to @nexttime:

You didn't fix "gf2x is a C/C+ software package" though... ;-)

Fixed now.

Could you attach a diff of your changes?

attachment: gf2x-1.1-jdemeyer.diff

I would have dropped the "C++"; if gf2x was (partially) implemented in C++, we'd have to set / change CXXFLAGS as well.

I'd probably also use $CFLAG64 instead of hardcoding -m64.

[nexttime]

comment:64

Did I mention it also builds with clang? ;-)

[jdemeyer]

comment:65

Replying to @nexttime:

I would have dropped the "C++"

The text was taken verbatim from upstream.

[nexttime]

comment:66

Replying to @jdemeyer:

Replying to @nexttime:

I would have dropped the "C++"

The text was taken verbatim from upstream.

I think it's covered by the GPL as well.

[zimmermann6]

comment:67

the C++ part of gf2x is only in the "apps" subdirectory, which contains binaries to be linked with NTL
(we had to use C++ here since NTL is under C++) to check for primitive trinomials. I guess Sage does not use that part, thus indeed only C code is used within Sage.

Paul

[nexttime]

comment:68

Replying to @zimmermann6:

the C++ part of gf2x is only in the "apps" subdirectory, which contains binaries to be linked with NTL
(we had to use C++ here since NTL is under C++) to check for primitive trinomials.

I guess Sage does not use that part, thus indeed only C code is used within Sage.

We can't build those apps (at least not immediately), since we decided to let NTL depend on gf2x.

[jdemeyer]

comment:69

Positive review to everything except my changes (attachment: gf2x-1.1-jdemeyer.diff).

[jpflori]

comment:70

I'm ok with them.

[nexttime]

comment:71

FWIW, I was going to give the previous spkgs positive review right when Jeroen started to change both, so I don't insist on fixing the hardcoded -m64.

[jdemeyer]

Merged: sage-5.11.beta1