Opened 10 years ago

Last modified 10 months ago

#13376 needs_info enhancement

Optional SPKG for SmallJac

Reported by: pavpanchekha Owned by: tbd
Priority: major Milestone: sage-wishlist
Component: packages: optional Keywords:
Cc: jpflori, kedlaya Merged in:
Authors: Pavel Panchekha, Drew Sutherland Reviewers: R. Andrew Ohana
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by slelievre)

Smalljac is a library and set of programs for computing L-polynomials and Jacobian group structures of low genus curves over finite fields. Given a curve C of genus 1 or 2 defined over Q or a quadratic number field, it will efficiently compute either the sequence of L-polynomials or Jacobian group structures arising from the reduction of C at all primes of good reduction up to a specified norm bound.

This set of SPKGs and the corresponding patch to Sage 5.6 add support for using smallJac from Sage.

  • EllipticCurve.aplist can be run with algorithm="smalljac", yielding run times of six times faster on a single core.
  • EllipticCurve.aplists provides more usable representation the above, and supports number fields (multiple reductions per prime norm). See the documentation for more, but in general aplist couldn't be made very easy to use for the number field case.
  • EllipticCurve.grouplists gives the abelian groups isomorphic to various reductions of a curve.
  • EllipticCurve.lpolylists yields the L-Polynomials of reductions of a curve.
  • EllipticCurve.guess_sato_tate_group attempts to guess the Sato-Tate group of the Jacobian of a curve of genus 1 or 2 based on the distribution of its L-polynomial coefficients.
  • EllipticCurve.moments yields the moments of the distribution of coefficients of the L-Polynomials.
  • EllipticCurve.trace_histogram gives a very simple histogram for the distribution of traces of Frobenius of a curve, reduced at a range of primes.

For all of the above methods (except aplist), identical functionality exists (with the same name) for genus 2 curves. All of the above methods also parallelize over multiple cores (currently, to a power of two cores). For large problems, this achieves approximately linear speedup; for example, computing the first billion traces of Frobenius of an ordinary elliptic curve is 178 times faster on 32 cores.

For each of these features, there is Sage documentation docstring-style documentation.

The SPKGs only compile and work on 64-bit machines, since SmallJac? only supports 64-bit architectures, and require GMP. Two SPKGs are provided, since SmallJac? depends on ff_poly, but so does some of Drew Sutherland's other code, so it makes sense to split the two. They've been tested to work on a completely clean install of Sage on at least two differently-configured machines.

The patch has been tested to apply cleanly to 5.6.

SPKGs are available at http://www.mit.edu/~pavpan/. Install first the ff_poly package and then the smalljac package, with the normal Sage package installation mechanisms. Then apply the patch to a fresh branch of the source code and recompile that branch.

The "Software" section of Drew Sutherland's page links to a tarball for SmallJac 4.1.3.

Attachments (6)

ff_poly-1.0.4.spkg (295.2 KB) - added by pavpanchekha 10 years ago.
SPKG for ff_poly
smalljac-4.0.14.spkg (222.4 KB) - added by pavpanchekha 10 years ago.
SPKG for smalljac
smalljac-4.0.14.patch (70.9 KB) - added by pavpanchekha 10 years ago.
Patch to Sage 5.2 to support interfacing with SmallJac?
ff_poly-1.1.2.spkg (297.6 KB) - added by pavpanchekha 9 years ago.
smalljac-4.0.23.spkg (224.9 KB) - added by pavpanchekha 9 years ago.
smalljac-4.0.23.patch (84.4 KB) - added by pavpanchekha 9 years ago.
Patch to Sage 5.6

Download all attachments as: .zip

Change History (36)

Changed 10 years ago by pavpanchekha

SPKG for ff_poly

Changed 10 years ago by pavpanchekha

SPKG for smalljac

Changed 10 years ago by pavpanchekha

Patch to Sage 5.2 to support interfacing with SmallJac?

comment:1 Changed 9 years ago by jpflori

  • Cc jpflori added

Changed 9 years ago by pavpanchekha

Changed 9 years ago by pavpanchekha

comment:2 Changed 9 years ago by pavpanchekha

I've attached three more files -- SPKGs for up-to-date versions of smalljac and ff_poly, and a patch against Sage 5.6. The list of features is identical -- bug fixes, performance improvements, and basic stabilization has happened in the mean time.

comment:3 follow-up: Changed 9 years ago by ohanar

a few of quick comments:

  • don't touch unrelated files (e.g. sage/numerical/backends/glpk_backend.pxd)
  • it would probably make more sense to default to smalljac over pari if it is installed
  • it would help if your trac ticket included installation instructions at the bottom, and if it is ready to be reviewed, you should change the status to needs review

also, I'm not the most knowledgeable on the matter, but my understanding was that optional packages need to work on all supported platforms, so it might be more of an experimental package since it doesn't work on 32bit platforms

comment:4 follow-up: Changed 9 years ago by ohanar

This currently doesn't work at all since you didn't add the file sage/libs/smalljac/*. Also, please do not attach spkgs to tickets in the future, instead post a link to the file.

comment:5 in reply to: ↑ 4 Changed 9 years ago by leif

Replying to ohanar:

Also, please do not attach spkgs to tickets in the future, instead post a link to the file.

Note that this doesn't even depend on its size; in general, binary files shouldn't be attached.

By convention, we also add which patch to apply (in which order) to which of the Sage repositories to the ticket's description.

Also, the 'Authors' field is empty...

comment:6 Changed 9 years ago by fbissey

Don't like the spkgs. Both SPKG.txt aren't updated to reflect the version changes. The first thing that I see in both is

#!/usr/bin/env bash

CFLAGS="-fPIC -mtune=k8 -pedantic -std=gnu99"
LDFLAGS="-static"

-fPIC and -static are kind of opposite but you will want to fold a library that you only know how to build static into a shared object so you need the -fPIC. Would be better to build shared in the first place. Is the "-mtune=k8" the thing that impose 64bitness? Anyway that assume way too much about the underlying cpu even on x86_64. We have people working on arm and ppc64, that's 64bit too.

When you say 64bit do you mean x86_64 as in "I have used simmd instructions that are only available on this cpus"(pet hate) or something else?

If you have used x86_64 specific instructions I am not sure we can ever move this out of optional since we support (or at least aim to) a larger range of hardware.

And just looking I have found assembly....

comment:7 in reply to: ↑ 3 ; follow-ups: Changed 9 years ago by pavpanchekha

Replying to ohanar:

  • don't touch unrelated files (e.g. sage/numerical/backends/glpk_backend.pxd)

My mistake, sorry. I've updated the patch file to remove such garbage and add the actual files instead.

  • it would probably make more sense to default to smalljac over pari if it is installed

This seemed like a more controversial option, though of course that wouldn't be a problem.

  • it would help if your trac ticket included installation instructions at the bottom, and if it is ready to be reviewed, you should change the status to needs review

Will do. I read through the developer guide, but either forgot or didn't see things like this.

Replying to ohanar:

Also, please do not attach spkgs to tickets in the future, instead post a link to the file.

Alright. Links to the two SPKGs are at http://www.mit.edu/~pavpan/. They have small updates from the ones included above.

Replying to leif:

Also, the 'Authors' field is empty...

Where?

Replying to fbissey:

Anyway that assume way too much about the underlying cpu even on x86_64.

When you say 64bit do you mean x86_64 as in "I have used simmd instructions that are only available on this cpus"(pet hate) or something else?

And just looking I have found assembly....

No, I think the meaning (and I am not Drew Sutherland so I do not know exactly) is that fast 64-bit integer operations are assumed throughout, and some algorithms are optimized to use the extra registers available on 64-bit systems. The single assembly instruction used is that which yields the high bit of an unsigned integer. This can always be written as a loop, but that will hurt performance. I do not know if such an instruction is available on arm, ppc, or elsewhere.

-fPIC and -static are kind of opposite but you will want to fold a library that you only know how to build static into a shared object so you need the -fPIC. Would be better to build shared in the first place.

I believe static compilation is for performance reasons. I can ask Drew Sutherland how important that is. The compilation certainly works without it. Similarly the tuning parameter, though suggesting to GCC that it is compiling to a platform with a full x86_64 register set and integer size is again important to performance.

comment:8 Changed 9 years ago by pavpanchekha

  • Description modified (diff)
  • Status changed from new to needs_review

comment:9 in reply to: ↑ 7 Changed 9 years ago by leif

Replying to pavpanchekha:

Replying to leif:

Also, the 'Authors' field is empty...

Where?

In the ticket description above. (You have to click "Modify ticket" below to see how to edit them.)


Replying to fbissey:

Anyway that assume way too much about the underlying cpu even on x86_64.

When you say 64bit do you mean x86_64 as in "I have used simmd instructions that are only available on this cpus"(pet hate) or something else?

And just looking I have found assembly....

No, I think the meaning (and I am not Drew Sutherland so I do not know exactly) is that fast 64-bit integer operations are assumed throughout, and some algorithms are optimized to use the extra registers available on 64-bit systems. The single assembly instruction used is that which yields the high bit of an unsigned integer. This can always be written as a loop, but that will hurt performance. I do not know if such an instruction is available on arm, ppc, or elsewhere.

Anyway, the code should be portable, i.e., such code should only be used conditionally, depending on the platform, and have a (presumably) slow C implementation as a last resort. Note that even GMP has plain C implementations for all of its functions. (At the very least, the spkg-install script should check whether the assumptions the code makes are true, and otherwise exit with an appropriate error message.)

-fPIC and -static are kind of opposite but you will want to fold a library that you only know how to build static into a shared object so you need the -fPIC. Would be better to build shared in the first place.

I believe static compilation is for performance reasons. I can ask Drew Sutherland how important that is. The compilation certainly works without it. Similarly the tuning parameter, though suggesting to GCC that it is compiling to a platform with a full x86_64 register set and integer size is again important to performance.

GCC probably "knows" more about the platform it is compiling on (especially on x86/x86_64) or for than most of us. ;-)

-mtune btw. doesn't really affect the instruction set GCC compiles for, but the selection out of and ordering of these. (-march, on some platforms -mcpu, and other target-dependent -m... options specify the architecture and hence the available instruction set of the target CPU.)

comment:10 Changed 9 years ago by nbruin

This code is absolutely state-of-the-art for what it does and it would be a shame to not have it available in sage, at least on platforms where it works (which is by far the most common platform presently!).

I agree that installation should work on all platforms sage supports, but that installation could consist of installing a routine that successfully tells "I'm not available on this platform". Correct usage of the library could then include "first check if it's available" and provide an alternative (via gp for some things perhaps) if it's not.

This is not so different from, say, the Magma interface, which is part of sage but only does something useful when Magma is actually available.

comment:11 in reply to: ↑ 7 ; follow-up: Changed 9 years ago by ohanar

  • Authors set to R. Andrew Ohana
  • Status changed from needs_review to needs_work

Replying to pavpanchekha:

Replying to ohanar:

  • don't touch unrelated files (e.g. sage/numerical/backends/glpk_backend.pxd)

My mistake, sorry. I've updated the patch file to remove such garbage and add the actual files instead.

The unrelated changes are still there.

Ok, some needed changes to the sage patch:

  • Full documentation and doctest coverage -- right now the _smalljac methods have no doctests, and sage.libs.smalljac has next to no documentation and no doctests
  • All doctests not flagged as optional need to pass without smalljac installed
  • Make sure your patch is properly exported from mercurial, so that it has all the relevant metadata (author, commit message, date, etc.)

comment:12 Changed 9 years ago by ohanar

  • Authors R. Andrew Ohana deleted
  • Reviewers set to R. Andrew Ohana

err, oops :)

comment:13 Changed 9 years ago by pavpanchekha

  • Authors set to Pavel Panchekha, Drew Sutherland

comment:14 in reply to: ↑ 11 Changed 9 years ago by pavpanchekha

Replying to ohanar:

Ok, some needed changes to the sage patch:

  • Full documentation and doctest coverage -- right now the _smalljac methods have no doctests, and sage.libs.smalljac has next to no documentation and no doctests
  • All doctests not flagged as optional need to pass without smalljac installed
  • Make sure your patch is properly exported from mercurial, so that it has all the relevant metadata (author, commit message, date, etc.)

I'll try to get these done. I have grad school visitations for the next few weeks, after that will almost certainly have time. It doesn't seem like the changes you're requesting are very hard to do, just need to think of good full test suites.

comment:15 Changed 9 years ago by leif

Both spkg-install scripts are pretty messy and certainly need work. I'll see if I find the time to fix them (presumably rewriting them from scratch... ;-) ).

The Mercurial repository of ff_poly's spkg contains traces of files in src/; looks like .hgignore had been created too late.

comment:16 follow-up: Changed 9 years ago by leif

W.r.t. the inline assembly: It shouldn't be too hard to port it to non-x86_64 systems (probably by using potentially slow[er] C implementations -- at the risk of making SmallJac slower than other implementations in Sage). (Most of the assembly, i.e., macros and inline functions using asm(), is in ff_poly-*/src/asm.h; cstd.h also uses asm() in two places, for the mentioned "high bit" and "low bit" inline functions. For the latter two, one could presumably use GCC's more portable __builtin_* -- at low or no expense -- as well.)

Unfortunately AFAICS the code also implicitly assumes that sizeof(unsigned long)==8 (instead of using uint64_t where appropriate), which makes it pretty hard to port it to 32-bit systems (or other systems on which that assumption is false).

comment:17 in reply to: ↑ 16 ; follow-up: Changed 9 years ago by nbruin

Replying to leif:

Unfortunately AFAICS the code also implicitly assumes that sizeof(unsigned long)==8 (instead of using uint64_t where appropriate), which makes it pretty hard to port it to 32-bit systems (or other systems on which that assumption is false).

It seems C99 guarantees the existence of uint_fast64_t. Perhaps using that would be portable?

comment:18 in reply to: ↑ 17 ; follow-up: Changed 9 years ago by leif

Replying to nbruin:

Replying to leif:

Unfortunately AFAICS the code also implicitly assumes that sizeof(unsigned long)==8 (instead of using uint64_t where appropriate), which makes it pretty hard to port it to 32-bit systems (or other systems on which that assumption is false).

It seems C99 guarantees the existence of uint_fast64_t. Perhaps using that would be portable?

? Using uint64_t would be portable.

With uint_fast64_t, you may (at some point in the future...) run into problems because the assumption is sizeof(unsigned long)==8, not >=8, at least in most cases. (128-bit quantities are currently split into two unsigned longs; it would of course be worth using native integral types there if available.)

comment:19 Changed 9 years ago by leif

Another remark:

Although the spkg-install scripts currently do not use this target, make install uses cp -v ... in both Makefiles, which isn't portable either.

(And while SmallJacs's make all also builds four executables, its make install only installs the library and header files. install still depends on all.)

Changed 9 years ago by pavpanchekha

Patch to Sage 5.6

comment:21 Changed 9 years ago by pavpanchekha

I've updated the patch to include doctests for all methods (except the few private Cython ones, which cannot have doctests as they are private methods. Even those have documentation.). All doctests should be labeled with "# optional: smalljac";

Patch is also properly exported now.

As for fixing the spkg_install file, I would love to hear what should be changed. I tried to stick to the template in the developer guide.

comment:22 Changed 6 years ago by kedlaya

  • Cc kedlaya added

comment:23 Changed 5 years ago by kedlaya

My understanding from Drew is that this project is defunct, so I propose to close this ticket as duplicate/wontfix. Hope still springs eternal at #965.

comment:24 Changed 5 years ago by pavpanchekha

The project is defunct, in the sense that I haven't touched the code in 5 years. But I still have the code, and could get up to speed again.

I believe the status is that the patch needs review and also updating to modern Sage. I'm happy to port to modern Sage if that means it will be merged—is there any interest in reviewing an updated patch and shepherding it to merge?

comment:25 Changed 5 years ago by kedlaya

Absolutely!

comment:26 Changed 5 years ago by kedlaya

Drew reports that smalljac 5.0 is on the way (hopefully by the end of the year), and will involve a bunch of new code. So maybe it is better to hold off on any action until then.

comment:27 Changed 5 years ago by pavpanchekha

Ok, I'll wait.

comment:28 in reply to: ↑ 18 Changed 5 years ago by nbruin

Replying to leif:

Replying to nbruin:

Replying to leif:

Unfortunately AFAICS the code also implicitly assumes that sizeof(unsigned long)==8 (instead of using uint64_t where appropriate), which makes it pretty hard to port it to 32-bit systems (or other systems on which that assumption is false).

It seems C99 guarantees the existence of uint_fast64_t. Perhaps using that would be portable?

? Using uint64_t would be portable.

Yes, but the standard seems to not guarantee its existence:

http://en.cppreference.com/w/cpp/types/integer

making me believe you could have a C99-compliant compiler on a 32bit system that does not provide uint_64_t. Perhaps all our target systems do provide it, in which case it's probably a good choice.

It seems that C99 does guarantee the existence of uint_fast64_t (but indeed not that it is exactly 8 bytes long).

With uint_fast64_t, you may (at some point in the future...) run into problems because the assumption is sizeof(unsigned long)==8, not >=8, at least in most cases. (128-bit quantities are currently split into two unsigned longs; it would of course be worth using native integral types there if available.)

Version 0, edited 5 years ago by nbruin (next)

comment:29 Changed 2 years ago by mkoeppe

  • Milestone set to sage-wishlist
  • Status changed from needs_work to needs_info

Setting spkg proposals that have not seen recent activity to "sage-wishlist".

comment:30 Changed 10 months ago by slelievre

  • Description modified (diff)
Note: See TracTickets for help on using tickets.