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: |
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,
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
- Branch set to u/mjo/ticket/32841
- Commit set to 8fc2403286c81c70782922f4270fff119fbdc701
- Status changed from new to needs_review
comment:2 Changed 9 months ago by
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
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: ↓ 5 Changed 9 months ago by
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
- 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: ↓ 7 Changed 9 months ago by
Has anyone asked David Harvey about this?
comment:7 in reply to: ↑ 6 Changed 9 months ago by
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
- 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: ↓ 10 Changed 8 months ago by
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
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 callszn_poly
for a little while as an option. Instead offorce_ntl
, how about analgorithm
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
- Cc alexjbest added
- Status changed from needs_info to needs_review
comment:12 Changed 8 months ago by
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
- Milestone changed from sage-9.5 to sage-9.6
comment:14 Changed 7 months ago by
- Commit changed from 8fc2403286c81c70782922f4270fff119fbdc701 to b0de3967569471d56509dec45d2269485c24d8e3
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
8defe99 | Trac #32841: remove zn_poly from the library order.
|
6525bda | Trac #32841: remove zn_poly dependency from sagelib.
|
be482a3 | Trac #32841: remove the zn_poly SPKG.
|
9c9344b | Trac #32841: use zlib instead of zn_poly in a sage-package comment.
|
d4c75e9 | Trac #32841: use zlib instead of zn_poly in package list examples.
|
c14762d | Trac #32841: remove zn_poly TARGETS from cygwin github workflows.
|
d393f7b | Trac #32841: remove zn_poly section from COPYING.txt.
|
fc63ad7 | Trac #32841: remove mentions of zn_poly from README.md.
|
78841ee | Trac #32841: remove zn_poly mention from a thematic tutorial.
|
b0de396 | Trac #32841: don't mention zn_poly in flint header comments.
|
comment:15 Changed 4 months ago by
- Milestone changed from sage-9.6 to sage-9.7
comment:16 Changed 4 months ago by
- Commit changed from b0de3967569471d56509dec45d2269485c24d8e3 to d49f959bbec52f51fb6e68238e3d3f587ae78f0f
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
bc4829d | Trac #32841: remove zn_poly from the library order.
|
bb8e1e1 | Trac #32841: remove zn_poly dependency from sagelib.
|
38d52c1 | Trac #32841: remove the zn_poly SPKG.
|
98a75c8 | Trac #32841: use zlib instead of zn_poly in a sage-package comment.
|
73ed717 | Trac #32841: use zlib instead of zn_poly in package list examples.
|
ee4ad0f | Trac #32841: remove zn_poly TARGETS from cygwin github workflows.
|
f700a4b | Trac #32841: remove zn_poly section from COPYING.txt.
|
9c11ac9 | Trac #32841: remove mentions of zn_poly from README.md.
|
d18bd78 | Trac #32841: remove zn_poly mention from a thematic tutorial.
|
d49f959 | Trac #32841: don't mention zn_poly in flint header comments.
|
comment:17 Changed 3 months ago by
- Commit changed from d49f959bbec52f51fb6e68238e3d3f587ae78f0f to 752c53daf632dae66a04422713bc5f98944c143b
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
3f80162 | Trac #32841: remove zn_poly from the library order.
|
cdf2a3b | Trac #32841: remove zn_poly dependency from sagelib.
|
a0d2752 | Trac #32841: remove the zn_poly SPKG.
|
17786a8 | Trac #32841: use zlib instead of zn_poly in a sage-package comment.
|
41718b3 | Trac #32841: use zlib instead of zn_poly in package list examples.
|
8681e82 | Trac #32841: remove zn_poly TARGETS from cygwin github workflows.
|
275f9a7 | Trac #32841: remove zn_poly section from COPYING.txt.
|
5170681 | Trac #32841: remove mentions of zn_poly from README.md.
|
aaaa272 | Trac #32841: remove zn_poly mention from a thematic tutorial.
|
752c53d | Trac #32841: don't mention zn_poly in flint header comments.
|
Last 10 new commits:
Trac #32841: remove zn_poly from the library order.
Trac #32841: remove zn_poly dependency from sagelib.
Trac #32841: remove the zn_poly SPKG.
Trac #32841: use zlib instead of zn_poly in a sage-package comment.
Trac #32841: use zlib instead of zn_poly in package list examples.
Trac #32841: remove zn_poly TARGETS from cygwin github workflows.
Trac #32841: remove zn_poly section from COPYING.txt.
Trac #32841: remove mentions of zn_poly from README.md.
Trac #32841: remove zn_poly mention from a thematic tutorial.
Trac #32841: don't mention zn_poly in flint header comments.