Opened 9 months ago

Last modified 3 months ago

#32841 needs_review enhancement

zn_poly removal

Reported by: mjo Owned by:
Priority: major Milestone: sage-9.7
Component: packages: standard Keywords:
Cc: alexjbest Merged in:
Authors: Michael Orlitzky Reviewers:
Report Upstream: N/A Work issues:
Branch: u/mjo/ticket/32841 (Commits, GitHub, GitLab) Commit: 752c53daf632dae66a04422713bc5f98944c143b
Dependencies: Stopgaps:

Status badges

Description

The zn_poly SPKG is used by sage in only one place. In hypellfrob.cpp's interval_products_wrapper(), there is a case...

if (!force_ntl  &&  modulus <= (1UL << (ULONG_BITS - 1)) - 1)
{
   // Small modulus; let's try using zn_poly if we're allowed.
   ...

But sometimes that fails, and the fallback is to use NTL anyway. The zn_poly project was abandoned upstream in 2008:

https://web.maths.unsw.edu.au/~davidharvey/code/zn_poly/index.html

We've forked it to keep it building on modern systems,

https://gitlab.com/sagemath/zn_poly

but the build system is still a mess. Erik started an autotools branch (https://gitlab.com/sagemath/zn_poly/-/tree/autotooling), but it never got finished, because the source layout is a bit weird for autotools and it should most likely be redone from scratch.

And zn_poly is not packaged in Gentoo because of how many hacks it still requires to build on a distro with stronger user experience expectations:

https://github.com/cschwan/sage-on-gentoo/blob/master/sci-libs/zn_poly/zn_poly-0.9.2.ebuild

In short, we're not getting a lot of benefit out of zn_poly these days, and nothing breaks if we remove it, because the one function that uses it falls back to the more-reliable NTL anyway.

In this ticket we remove the zn_poly SPKG, to avoid having to rewrite its build system some day.

Change History (17)

comment:1 Changed 9 months ago by mjo

  • Authors set to Michael Orlitzky
  • Branch set to u/mjo/ticket/32841
  • Commit set to 8fc2403286c81c70782922f4270fff119fbdc701
  • Status changed from new to needs_review

Last 10 new commits:

3e055e3Trac #32841: remove zn_poly from the library order.
3e19fe9Trac #32841: remove zn_poly dependency from sagelib.
f9c6481Trac #32841: remove the zn_poly SPKG.
c7a6fe2Trac #32841: use zlib instead of zn_poly in a sage-package comment.
209ef4cTrac #32841: use zlib instead of zn_poly in package list examples.
ca1bdafTrac #32841: remove zn_poly TARGETS from cygwin github workflows.
c8bf248Trac #32841: remove zn_poly section from COPYING.txt.
a6e61d5Trac #32841: remove mentions of zn_poly from README.md.
cd0d40fTrac #32841: remove zn_poly mention from a thematic tutorial.
8fc2403Trac #32841: don't mention zn_poly in flint header comments.

comment:2 Changed 9 months ago by roed

There's a discussion on sage-devel about how much/whether we're giving up speed by switching from zn_poly to NTL. I'd like to do some benchmarking before removing this package.

comment:3 Changed 9 months ago by mjo

No problem, I'm not in a hurry.

Is it even possible to hit the zn_poly branch from within the normal sage user interface? The only call to interval_products_wrapper() I see (before or after this branch) passes force_ntl=1. You could still conceivably call it directly from within your own library, though.

comment:4 follow-up: Changed 9 months ago by roed

Yes. Line 257 of hypellfrob.pyx calls hypellfrob_matrix, which has force_ntl=0 by default. This function is called various places: matrix_of_frobenius in sage.schemes.elliptic_curves.padics, frobenius_matrix and count_points in sage.schemes.hyperelliptic_curves.hyperelliptic_finite_field.py.

comment:5 in reply to: ↑ 4 Changed 9 months ago by mjo

  • Status changed from needs_review to needs_work

Replying to roed:

Yes...

Ah, I didn't see matrix() at the bottom of hypellfrob.h. Ok. Do you have a plan for benchmarking? I can throw random inputs at it but I don't want to unfairly bias the results with poor choices for test cases.

comment:6 follow-up: Changed 9 months ago by cremona

Has anyone asked David Harvey about this?

comment:7 in reply to: ↑ 6 Changed 9 months ago by mjo

Replying to cremona:

Has anyone asked David Harvey about this?

No, but his webpage is pretty clear:

Current status

zn_poly is no longer maintained.

It's maintained by the sage team and essentially has been (via patches) for over a decade. With all due respect, if he's not going to help maintain the code, what can his opinion change?

If there's a huge performance regression (I'll need help with realistic test cases that don't make zn_poly fail and fall back to NTL unusually often), then we'll have to keep it around until NTL gets faster. But otherwise, the decision whether to keep it for nostalgia's sake alone should rest with the people who are going to have to maintain it.

comment:8 Changed 8 months ago by mjo

  • Status changed from needs_work to needs_info

I've been throwing examples at this for an hour or so. I've hacked my local tree to make hypellfrob take a force_ntl parameter, and to alert me when zn_poly fails and falls back to NTL. I've been picking my p,Q,N by hand for lack of a better approach.

I'll cut to the chase: the biggest difference between the two in favor of zn_poly is on the order of...

sage: %timeit hypellfrob(p, 3, f, force_ntl=False)
864 ms ± 5.09 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit hypellfrob(p, 3, f, force_ntl=True)
1.2 s ± 5.06 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Typically, they're a bit closer together, with zn_poly having a slight edge. And when zn_poly fails, of course, the NTL-only strategy wins by a huge margin (however long it takes zn_poly to fail).

So the question is, is a slowdown like this (for the cases that zn_poly can handle) a deal-breaker, considering the improvement in the cases it cannot?

comment:9 follow-up: Changed 8 months ago by mkoeppe

My suggestion would be to downgrade zn_poly to "experimental" and to change the defaults to the code path that does not use it, but to still keep the code that calls zn_poly for a little while as an option. Instead of force_ntl, how about an algorithm parameter, similar to what many other functions accept.

comment:10 in reply to: ↑ 9 Changed 8 months ago by mjo

Replying to mkoeppe:

My suggestion would be to downgrade zn_poly to "experimental" and to change the defaults to the code path that does not use it, but to still keep the code that calls zn_poly for a little while as an option. Instead of force_ntl, how about an algorithm parameter, similar to what many other functions accept.

I'm willing to do this, but first, can I selfishly request at least one user come forward who would actually use it?

comment:11 Changed 8 months ago by mjo

  • Cc alexjbest added
  • Status changed from needs_info to needs_review

comment:12 Changed 8 months ago by roed

As one of the people who initially requested a speed comparison, I'm content with the removal of zn_poly rather than making mjo put the work into making it experimental. I think that the speed difference is not worth the maintenance burden.

I'll check with Alex to see if he agrees, and then am happy to review this.

comment:13 Changed 8 months ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6

comment:14 Changed 7 months ago by git

  • Commit changed from 8fc2403286c81c70782922f4270fff119fbdc701 to b0de3967569471d56509dec45d2269485c24d8e3

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

8defe99Trac #32841: remove zn_poly from the library order.
6525bdaTrac #32841: remove zn_poly dependency from sagelib.
be482a3Trac #32841: remove the zn_poly SPKG.
9c9344bTrac #32841: use zlib instead of zn_poly in a sage-package comment.
d4c75e9Trac #32841: use zlib instead of zn_poly in package list examples.
c14762dTrac #32841: remove zn_poly TARGETS from cygwin github workflows.
d393f7bTrac #32841: remove zn_poly section from COPYING.txt.
fc63ad7Trac #32841: remove mentions of zn_poly from README.md.
78841eeTrac #32841: remove zn_poly mention from a thematic tutorial.
b0de396Trac #32841: don't mention zn_poly in flint header comments.

comment:15 Changed 4 months ago by mkoeppe

  • Milestone changed from sage-9.6 to sage-9.7

comment:16 Changed 4 months ago by git

  • Commit changed from b0de3967569471d56509dec45d2269485c24d8e3 to d49f959bbec52f51fb6e68238e3d3f587ae78f0f

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

bc4829dTrac #32841: remove zn_poly from the library order.
bb8e1e1Trac #32841: remove zn_poly dependency from sagelib.
38d52c1Trac #32841: remove the zn_poly SPKG.
98a75c8Trac #32841: use zlib instead of zn_poly in a sage-package comment.
73ed717Trac #32841: use zlib instead of zn_poly in package list examples.
ee4ad0fTrac #32841: remove zn_poly TARGETS from cygwin github workflows.
f700a4bTrac #32841: remove zn_poly section from COPYING.txt.
9c11ac9Trac #32841: remove mentions of zn_poly from README.md.
d18bd78Trac #32841: remove zn_poly mention from a thematic tutorial.
d49f959Trac #32841: don't mention zn_poly in flint header comments.

comment:17 Changed 3 months ago by git

  • Commit changed from d49f959bbec52f51fb6e68238e3d3f587ae78f0f to 752c53daf632dae66a04422713bc5f98944c143b

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

3f80162Trac #32841: remove zn_poly from the library order.
cdf2a3bTrac #32841: remove zn_poly dependency from sagelib.
a0d2752Trac #32841: remove the zn_poly SPKG.
17786a8Trac #32841: use zlib instead of zn_poly in a sage-package comment.
41718b3Trac #32841: use zlib instead of zn_poly in package list examples.
8681e82Trac #32841: remove zn_poly TARGETS from cygwin github workflows.
275f9a7Trac #32841: remove zn_poly section from COPYING.txt.
5170681Trac #32841: remove mentions of zn_poly from README.md.
aaaa272Trac #32841: remove zn_poly mention from a thematic tutorial.
752c53dTrac #32841: don't mention zn_poly in flint header comments.
Note: See TracTickets for help on using tickets.