Opened 15 years ago

Closed 10 years ago

#2114 closed defect (fixed)

Get gf2x version 1.1 into Sage!

Reported by: was Owned by: somebody
Priority: major Milestone: sage-5.11
Component: packages: standard Keywords: spkg gf2x
Cc: zimmerma, malb, jpflori, jdemeyer Merged in: sage-5.11.beta1
Authors: Jean-Pierre Flori Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12447 Stopgaps:

Status badges

Description (last modified by jdemeyer)

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:

Apply to Sage's root:

Attachments (4)

ntl-5.5.2.p1.diff (1.1 KB) - added by jpflori 10 years ago.
Spkg diff, for review only.
trac_2114-gf2x.patch (1.6 KB) - added by jpflori 10 years ago.
gf2x-1.1.diff (3.5 KB) - added by jdemeyer 10 years ago.
Spkg diff, for review only.
gf2x-1.1-jdemeyer.diff (2.4 KB) - added by jdemeyer 10 years ago.

Download all attachments as: .zip

Change History (76)

comment:1 Changed 15 years ago by was

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:
> http://trac.sagemath.org/sage_trac/ticket/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

comment:2 Changed 14 years ago by zimmerma

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

comment:3 Changed 14 years ago by zimmerma

Cc: zimmerma added

comment:4 Changed 13 years ago by zimmerma

Report Upstream: N/A

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.

comment:5 Changed 13 years ago by zimmerma

Cc: malb added

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.

comment:6 Changed 11 years ago by jpflori

Cc: jpflori added

comment:7 Changed 10 years ago by 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.

comment:8 Changed 10 years ago by jpflori

Authors: Jean-Pierre Flori
Cc: jdemeyer added
Description: modified (diff)
Keywords: spkg gf2x added
Status: newneeds_review
Summary: get gf2x into Sage!Get gf2x version 1.1 into Sage!

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.

Changed 10 years ago by jpflori

Attachment: ntl-5.5.2.p1.diff added

Spkg diff, for review only.

comment:9 in reply to:  8 Changed 10 years ago by jdemeyer

Status: needs_reviewneeds_info

Replying to jpflori:

Jeroen please decide what to do.

Why should I? You should decide if you want this:

  1. as standard package (which requires a discussion on sage-devel and changes to spkg/standard/deps)
  2. as optional package (but then NTL needs to work both with and without gf2x)
  3. not at all

comment:10 Changed 10 years ago by jpflori

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.

comment:11 Changed 10 years ago by vbraun

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.

comment:12 Changed 10 years ago by 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(2n) elements (once you don't use Givaro) right now to prove it is beneficial.

comment:13 in reply to:  7 Changed 10 years ago by zimmerma

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

comment:14 Changed 10 years ago by jpflori

Work issues: tuning

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

comment:15 in reply to:  12 Changed 10 years ago by jpflori

Status: needs_infoneeds_review

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(2n) elements (once you don't use Givaro) right now to prove it is beneficial.

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

comment:16 Changed 10 years ago by jpflori

Status: needs_reviewneeds_work

comment:17 Changed 10 years ago by jpflori

New spkg up and diff updated. Pleas ignore the broken tuning.diff I posted.

comment:18 Changed 10 years ago by jpflori

Status: needs_workneeds_review
Work issues: tuning

comment:19 Changed 10 years ago by jpflori

Status: needs_reviewneeds_work
Work issues: tuning

Wrong spelling...

comment:20 Changed 10 years ago by jpflori

Status: needs_workneeds_review
Work issues: tuning

Should be ok now.

comment:21 Changed 10 years ago by jdemeyer

Status: needs_reviewneeds_work

This needs a patch to spkg/standard/deps and spkg/install.

comment:22 Changed 10 years ago by zimmerma

while trying gf2x-1.1 on my laptop, I hit a bug due to the fact that the tuning gave GF2X_MUL_TOOM4_ALWAYS_THRESHOLD=16, whereas a value at least 30 is required. The following patch will avoid this problem (or detect it earlier). It is against the development version but should be easily adapted to 1.1:

--- toom.c      (revision 148)
+++ toom.c      (working copy)
@@ -1,6 +1,6 @@
 /* This file is part of the gf2x library.
 
-   Copyright 2007, 2008, 2009
+   Copyright 2007, 2008, 2009, 2013
    Richard Brent, Pierrick Gaudry, Emmanuel Thome', Paul Zimmermann
 
    This program is free software; you can redistribute it and/or modify it
@@ -53,6 +53,9 @@
     if (n < GF2X_MUL_TOOMW_THRESHOLD)
        return GF2X_SELECT_KARA;                // KarMul
 
+#if GF2X_MUL_TOOM4_ALWAYS_THRESHOLD < 30
+#error "GF2X_MUL_TOOM4_ALWAYS_THRESHOLD must be >= 30"
+#endif
     if (n >= GF2X_MUL_TOOM4_ALWAYS_THRESHOLD)
        return GF2X_SELECT_TC4;         // Toom4Mul

comment:23 Changed 10 years ago by zimmerma

oh, I understand what happened now. I did make tune-toom TOOM_TUNING_LIMIT=16 which sets automatically GF2X_MUL_TOOM4_ALWAYS_THRESHOLD to 16. When running make tune-toom TOOM_TUNING_LIMIT=nnn, one should always have nnn at least 30.

Paul

comment:24 Changed 10 years ago by jpflori

Description: modified (diff)
Status: needs_workneeds_review

I've used 100 as a limit so it should be ok.

comment:25 Changed 10 years ago by leif

Waaaaah! Just created (or rather finished) an NTL 5.5.2.p1 spkg (fixing hardcoded make) at #14692... 8-/

comment:26 in reply to:  25 Changed 10 years ago by leif

Replying to leif:

Waaaaah! Just created (or rather finished) an NTL 5.5.2.p1 spkg (fixing hardcoded make) at #14692... 8-/

Ok, I've rebased your .p1 on mine:

http://boxen.math.washington.edu/home/leif/Sage/spkgs/ntl-5.5.2.p2.spkg

  • .hgtags

    diff --git a/.hgtags b/.hgtags
    a b  
    1173d22601a79e226c590bb93cc842391e9e8f8d11 ntl-5.5.2
    225cf2d2f43b4d9cf1fc3cf8e9bb54efc58ccf2b4f ntl-5.5.2.p0
    33c7af41e56a64bdef778ee579beda9d54943105fe ntl-5.5.2.p1
     44984ca9298a7310c9378ca8cd391dc8a1ba85d9f ntl-5.5.2.p2
  • SPKG.txt

    diff --git a/SPKG.txt b/SPKG.txt
    a b  
    1818
    1919== Dependencies ==
    2020 * gmp
     21 * gf2x
    2122
    2223== Special Update/Build Instructions ==
    2324 * We need to modfiy new.h to accomodate Singular
     
    3435
    3536== Changelog ==
    3637
     38=== ntl-5.5.2.p2 (Jean-Pierre Flori, June 5th 2013) ===
     39 * #2114: Build NTL with gf2x support.
     40
    3741=== ntl-5.5.2.p1 (Leif Leonhardy, June 5th 2013) ===
    3842 * #14692: Patch upstream to use `$(MAKE)` (instead of `make`) in the generated
    3943   Makefile (and in two scripts called from the Makefile which in turn invoke
  • spkg-install

    diff --git a/spkg-install b/spkg-install
    a b  
    8686        CC="$CC" CFLAGS="$CFLAGS $SHAREDFLAGS" \
    8787        CXX="$CXX" CXXFLAGS="$CXXFLAGS $SHAREDFLAGS" \
    8888        LDFLAGS="$LDFLAGS" LIBTOOL_LINK_FLAGS="$LIBTOOL_LINK_FLAGS" \
    89         NTL_GMP_LIP=on NTL_STD_CXX=on \
     89        NTL_GMP_LIP=on NTL_GF2X_LIB=on NTL_STD_CXX=on \
    9090        LIBTOOL=../../libtool/libtool
    9191
    9292    if [ $? -ne 0 ]; then

comment:27 Changed 10 years ago by leif

Description: modified (diff)

comment:28 Changed 10 years ago by leif

W.r.t. gf2x:

The following doesn't work (-O0 never takes effect):

if [ "$SAGE64" = "yes" ]; then
    echo "Building a 64-bit version of gf2x."
    ABI="64"; export ABI
    CFLAGS="-O2 -g -m64 $CFLAGS"; export CFLAGS
else
    CFLAGS="-O2 -g $CFLAGS"; export CFLAGS
fi

if [ "$SAGE_DEBUG" = "yes" ]; then
    echo "Building a debug version of gf2x."
    CFLAGS="-O0 -g $CFLAGS"; export CFLAGS
fi

$SAGE_LOCAL should be quoted in the rm commands in spkg-install.

comment:29 Changed 10 years ago by leif

Minor thing: "Patching gf2x." gets printed even when no patch gets applied.

comment:30 Changed 10 years ago by leif

P.S.: For other spkgs, we (currently) use SAGE_TUNE_<package name>[={yes,no}] (where <package name> can be both upper or lower case). And the new variable should probably get documented in devel/sage/doc/en/installation/source.rst (section "Environment variables").

GF2X_TUNE=full really takes ages, and uses a lot of memory (so far up to 2 GB resident / 2.5 GB virtual).

comment:31 Changed 10 years ago by leif

gf2x.c: In function 'gf2x_mul_pool_init':
gf2x.c:82:24: warning: argument to 'sizeof' in 'memset' call is the same expression as the destination; did you mean to dereference it? [-Wsizeof-pointer-memaccess]
     memset(p, 0, sizeof(p));
                        ^

? :-)

comment:32 in reply to:  31 Changed 10 years ago by leif

Replying to leif:

gf2x.c: In function 'gf2x_mul_pool_init':
gf2x.c:82:24: warning: argument to 'sizeof' in 'memset' call is the same expression as the destination; did you mean to dereference it? [-Wsizeof-pointer-memaccess]
     memset(p, 0, sizeof(p));
                        ^

Harmless, but warning could be avoided by using sizeof(gf2x_mul_pool_t) or sizeof(p[0]) instead in

void gf2x_mul_pool_init(gf2x_mul_pool_t p)
{
    memset(p, 0, sizeof(p));
}
Last edited 10 years ago by leif (previous) (diff)

comment:33 Changed 10 years ago by leif

Otherwise (i.e., modulo mentioned issues) looks ok (and apparently works; Linux x86 and x86_64, GCC 4.4.3 / 4.7.2 / 4.8.0, with SAGE_CHECK=yes, some doctests run).


Building with GF2X_TUNE=full finally took more than four and a half hours, admittedly on a not-so-fast (but otherwise almost idle, dual-core) machine...

comment:34 Changed 10 years ago by zimmerma

I've fixed the warning reported in comment 31 upstream, thanks.

Paul

comment:35 Changed 10 years ago by jpflori

Thanks leif, I'll take all these sensible remarks into account.

comment:36 Changed 10 years ago by jdemeyer

Also $SAGE_ROOT/COPYING.txt should be updated (keeping in mind #12447).

Last edited 10 years ago by jdemeyer (previous) (diff)

comment:37 Changed 10 years ago by jdemeyer

Status: needs_reviewneeds_work

comment:38 Changed 10 years ago by jdemeyer

Dependencies: #12447

comment:39 Changed 10 years ago by jpflori

I've not found doc for the other tune variables in the doc, so I'll postpone adding the doc until we've listed all that has to be documented.

I'm aware that we always print the patching message, it saves a few lines of script...

Changed 10 years ago by jpflori

Attachment: trac_2114-gf2x.patch added

comment:40 Changed 10 years ago by jpflori

Status: needs_workneeds_review

comment:41 Changed 10 years ago by jpflori

If you prefer, I can include Paul's patch so that we will actually be patching gf2x.

comment:42 Changed 10 years ago by zimmerma

my patch (from comment 22) is not needed if you do tune-toom TOOM_TUNING_LIMIT=nnn with nnn at least 30.

Paul

comment:43 Changed 10 years ago by jpflori

I meant leif's patch in fact, the one from comment http://trac.sagemath.org/sage_trac/ticket/2114#comment:32 suppressing a warning.

comment:44 Changed 10 years ago by zimmerma

ok, here is the change I did upstream:

--- gf2x.c	(revision 150)
+++ gf2x.c	(working copy)
@@ -79,7 +79,7 @@
 
 void gf2x_mul_pool_init(gf2x_mul_pool_t p)
 {
-    memset(p, 0, sizeof(p));
+    memset(p, 0, sizeof(gf2x_mul_pool_t));
 }
 
 void gf2x_mul_pool_clear(gf2x_mul_pool_t p)

Paul

comment:45 Changed 10 years ago by jpflori

Thanks Paul. If leif rants, I'll include it.

But IMHO we can wait for the gf2x 1.2 release to get this warning suppressed. I think that getting gf2x in Sage quickly is a more important matter.

comment:46 in reply to:  45 Changed 10 years ago by leif

Replying to jpflori:

Thanks Paul. If leif rants, I'll include it.

The "rant" addressed upstream, and (as expected) reached it... ;-)

I don't care whether you include a patch here.

comment:47 Changed 10 years ago by leif

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

comment:48 in reply to:  39 ; Changed 10 years ago by leif

Replying to jpflori:

I've not found doc for the other tune variables in the doc, so I'll postpone adding the doc until we've listed all that has to be documented.

Hmmm... If you at least create a meta-ticket to record what has to be documented...


I'm aware that we always print the patching message, it saves a few lines of script...

I'm using either ls ../patches/*.patch >/dev/null 2>&1 && ..., or simply "Applying patches to upstream (if any) ..."

comment:49 Changed 10 years ago by leif

Btw., ptestlong passed with Sage 5.10.rc0 on Linux x86_64.

comment:50 in reply to:  48 Changed 10 years ago by jpflori

Status: needs_reviewneeds_work

Replying to leif:

Replying to jpflori:

I've not found doc for the other tune variables in the doc, so I'll postpone adding the doc until we've listed all that has to be documented.

Hmmm... If you at least create a meta-ticket to record what has to be documented...

Done, see #14698 (you're cc'ed there anyway).


I'm aware that we always print the patching message, it saves a few lines of script...

I'm using either ls ../patches/*.patch >/dev/null 2>&1 && ..., or simply "Applying patches to upstream (if any) ..."

Ok, it's true it's simple enough, I'll change that.

comment:51 Changed 10 years ago by jpflori

Work issues: rebase ntl spkg

Done.

Now the NTL spkg should be rebased when #14692 is done.

Last edited 10 years ago by jpflori (previous) (diff)

comment:52 Changed 10 years ago by jpflori

Or the converse.

comment:53 Changed 10 years ago by jpflori

Description: modified (diff)
Status: needs_workneeds_review
Work issues: rebase ntl spkg

As #14692 needs more work, let's base it on top of this ticket rather than the other way around.

comment:54 in reply to:  47 Changed 10 years ago by zimmerma

Replying to leif:

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

comment:55 Changed 10 years ago by jdemeyer

Description: modified (diff)

comment:56 Changed 10 years ago by jdemeyer

Description: modified (diff)

comment:57 Changed 10 years ago by 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.

comment:58 Changed 10 years ago by jdemeyer

Description: modified (diff)

For NTL, I added the hg tag.

comment:59 Changed 10 years ago by jdemeyer

Milestone: sage-5.10sage-5.11
Reviewers: Jeroen Demeyer

comment:60 Changed 10 years ago by jdemeyer

Component: basic arithmeticpackages: standard

comment:61 in reply to:  57 ; Changed 10 years ago by leif

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.

Changed 10 years ago by jdemeyer

Attachment: gf2x-1.1.diff added

Spkg diff, for review only.

Changed 10 years ago by jdemeyer

Attachment: gf2x-1.1-jdemeyer.diff added

comment:62 in reply to:  61 ; Changed 10 years ago by jdemeyer

Replying to leif:

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

Fixed now.

Could you attach a diff of your changes?

gf2x-1.1-jdemeyer.diff

comment:63 in reply to:  62 ; Changed 10 years ago by leif

Replying to jdemeyer:

Replying to leif:

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

Fixed now.

Could you attach a diff of your changes?

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.

comment:64 Changed 10 years ago by leif

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

comment:65 in reply to:  63 ; Changed 10 years ago by jdemeyer

Replying to leif:

I would have dropped the "C++"

The text was taken verbatim from upstream.

comment:66 in reply to:  65 Changed 10 years ago by leif

Replying to jdemeyer:

Replying to leif:

I would have dropped the "C++"

The text was taken verbatim from upstream.

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

comment:67 Changed 10 years ago by zimmerma

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

comment:68 in reply to:  67 Changed 10 years ago by leif

Replying to zimmerma:

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.

comment:69 Changed 10 years ago by jdemeyer

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

comment:70 Changed 10 years ago by jpflori

Status: needs_reviewpositive_review

I'm ok with them.

comment:71 Changed 10 years ago by leif

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.

comment:72 Changed 10 years ago by jdemeyer

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