zn_poly removal #32841

orlitzky · 2021-11-09T12:53:28Z

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.

CC: @alexjbest

Component: packages: standard

Author: Michael Orlitzky

Branch/Commit: a5ac5fc

Reviewer: Dima Pasechnik

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

The text was updated successfully, but these errors were encountered:

orlitzky · 2021-11-09T13:11:56Z

Branch: u/mjo/ticket/32841

orlitzky · 2021-11-09T13:11:56Z

Author: Michael Orlitzky

orlitzky · 2021-11-09T13:11:56Z

Commit: 8fc2403

orlitzky · 2021-11-09T13:11:56Z

Last 10 new commits:

`3e055e3`	`Trac #32841: remove zn_poly from the library order.`
`3e19fe9`	`Trac #32841: remove zn_poly dependency from sagelib.`
`f9c6481`	`Trac #32841: remove the zn_poly SPKG.`
`c7a6fe2`	`Trac #32841: use zlib instead of zn_poly in a sage-package comment.`
`209ef4c`	`Trac #32841: use zlib instead of zn_poly in package list examples.`
`ca1bdaf`	`Trac #32841: remove zn_poly TARGETS from cygwin github workflows.`
`c8bf248`	`Trac #32841: remove zn_poly section from COPYING.txt.`
`a6e61d5`	`Trac #32841: remove mentions of zn_poly from README.md.`
`cd0d40f`	`Trac #32841: remove zn_poly mention from a thematic tutorial.`
`8fc2403`	`Trac #32841: don't mention zn_poly in flint header comments.`

roed314 · 2021-11-09T23:37:43Z

comment:2

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.

orlitzky · 2021-11-10T00:15:44Z

comment:3

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.

roed314 · 2021-11-10T00:33:35Z

comment:4

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.

orlitzky · 2021-11-10T00:46:13Z

comment:5

Replying to @roed314:

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.

JohnCremona · 2021-11-11T12:17:51Z

comment:6

Has anyone asked David Harvey about this?

orlitzky · 2021-11-11T13:54:48Z

comment:7

Replying to @JohnCremona:

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.

orlitzky · 2021-12-02T18:59:29Z

comment:8

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?

mkoeppe · 2021-12-02T19:14:11Z

comment:9

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.

orlitzky · 2021-12-03T00:58:54Z

comment:10

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?

roed314 · 2021-12-20T08:53:35Z

comment:12

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.

sagetrac-git · 2022-01-13T22:53:38Z

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

sagetrac-git · 2022-01-13T22:53:38Z

Changed commit from 8fc2403 to b0de396

dimpase · 2022-12-07T20:28:49Z

comment:19

needs a rebase

dimpase · 2022-12-07T21:07:02Z

Last 10 new commits:

`076969b`	`Trac #32841: remove zn_poly dependency from sagelib.`
`d800f6c`	`Trac #32841: remove the zn_poly SPKG.`
`d059d60`	`Trac #32841: use zlib instead of zn_poly in a sage-package comment.`
`e683076`	`Trac #32841: use zlib instead of zn_poly in package list examples.`
`46f7623`	`Trac #32841: remove zn_poly TARGETS from cygwin github workflows.`
`8699ed0`	`Trac #32841: remove zn_poly section from COPYING.txt.`
`d590856`	`Trac #32841: remove mentions of zn_poly from README.md.`
`da17a80`	`Trac #32841: remove zn_poly mention from a thematic tutorial.`
`5507887`	`Trac #32841: don't mention zn_poly in flint header comments.`
`a5ac5fc`	`later zn_poly appearances should go, too`

dimpase · 2022-12-07T21:07:02Z

Changed branch from u/mjo/ticket/32841 to u/dimpase/ticket/32841

dimpase · 2022-12-07T21:07:02Z

Changed commit from 752c53d to a5ac5fc

dimpase · 2022-12-07T21:07:02Z

Reviewer: Dima Pasechnik

orlitzky · 2022-12-07T21:14:39Z

comment:21

Thanks, I don't have sage built anywhere at the moment so it would have taken me a lot longer to do that.

dimpase · 2022-12-07T21:23:07Z

comment:22

I'll hit "positive review" as soon as tests are run and OK

dimpase · 2022-12-07T23:30:42Z

comment:23

it works, and so let Sage have one obsolete dependency less.

vbraun · 2022-12-14T22:12:32Z

Changed branch from u/dimpase/ticket/32841 to a5ac5fc

This function isn't used anywhere in the sage library, and according to its own documentation, "is a technology preview. It might disappear or be replaced without a deprecation warning." Today is that day.

This file uses the assert() macro provided by <cassert> in C++. In the past it was included transitively; but soon it won't be, so.

Our interval_products_wrapper() wrapped three different implementations: * ntl_interval_products (ZZ_p version) * ntl_interval_products (zz_p version) * zn_poly_interval_products But "the zn_poly version occasionally fails," and when that happens, the NTL implementation is used anyway. Moreover the wrapper takes a "force_ntl" parameter that allows the user to skip the zn_poly attempt entirely. This is the only place that zn_poly is actually used in sagelib anymore, so this commit removes the underlying zn_poly implementation, and eliminates the "force_ntl" parameter that was propagated throughout the "hypellfrob" code. Now NTL is always used, as if force_ntl was enabled.

…mment. The zn_poly package has been removed, so this could only confuse people if we left it in.

…ples. We have a few doctests that list all sage packages, and expect zn_poly to be the last one listed. Having removed zn_poly, however, zlib is now the terminal package. Here we update all such tests.

…ows. The zn_poly SPKG has been removed, so we should not try to build it as part of the cygwin workflows.

The zn_poly SPKG has been removed, so its license no longer affects that of the larger SageMath project.

Being alphabetically ultimate, the "zn_poly" package appears as an example in a few places within our README.md. This commit replaces those examples with "zlib" instead, as zn_poly has been removed.

This tutorial mentions the Harvey-Kedlaya algorithm that "depends only on NTL and zn_poly." But zn_poly has just been excised from that module, and its SPKG removed from SageMath. This commit changes the wording to say "depends only on NTL" instead.

The flint_wrap.h and flint_ntl_wrap.h headers mention "zn_poly and pari" as reasons for doing something specific. The zn_poly SPKG has been removed, however; so we update those comments to mention only pari.

…ows." This reverts commit 46f7623.

### 📚 Description  Cygwin workflows were mangled by a bad merge, leading to syntax errors even whenever the workflow is parsed. Here we fix this; note that the Cygwin workflow is still not functional afterward (the first step, installation of Cygwin with choco, fails). But this will only affect builds of releases and does not happen for PR CI runs.   Closes #35048 ### 📝 Checklist    - [x] I have made sure that the title is self-explanatory and the description concisely explains the PR. - [x] I have linked an issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation accordingly. ### ⌛ Dependencies

orlitzky added this to the sage-9.5 milestone Nov 9, 2021

orlitzky added c: packages: standard labels Nov 9, 2021

orlitzky added the s: needs review label Nov 9, 2021

orlitzky added s: needs work and removed s: needs review labels Nov 10, 2021

orlitzky added s: needs info and removed s: needs work labels Dec 2, 2021

orlitzky added s: needs review and removed s: needs info labels Dec 15, 2021

mkoeppe modified the milestones: sage-9.5, sage-9.6 Dec 21, 2021

mkoeppe removed this from the sage-9.6 milestone Apr 2, 2022

mkoeppe added this to the sage-9.8 milestone Aug 31, 2022

dimpase added s: positive review and removed s: needs review labels Dec 7, 2022

vbraun removed the s: positive review label Dec 14, 2022

vbraun closed this as completed in d2a2415 Dec 14, 2022

kryzar pushed a commit to kryzar/sage that referenced this issue Feb 6, 2023

Trac sagemath#32841: add missing include to hypellfrob.cpp.

c938e59

This file uses the assert() macro provided by <cassert> in C++. In the past it was included transitively; but soon it won't be, so.

kryzar pushed a commit to kryzar/sage that referenced this issue Feb 6, 2023

Trac sagemath#32841: remove zn_poly from distutils "libraries" fields.

a113340

kryzar pushed a commit to kryzar/sage that referenced this issue Feb 6, 2023

Trac sagemath#32841: remove zn_poly from the library order.

146bc5e

kryzar pushed a commit to kryzar/sage that referenced this issue Feb 6, 2023

Trac sagemath#32841: remove zn_poly dependency from sagelib.

076969b

kryzar pushed a commit to kryzar/sage that referenced this issue Feb 6, 2023

Trac sagemath#32841: remove the zn_poly SPKG.

d800f6c

kryzar pushed a commit to kryzar/sage that referenced this issue Feb 6, 2023

Trac sagemath#32841: use zlib instead of zn_poly in a sage-package co…

d059d60

…mment. The zn_poly package has been removed, so this could only confuse people if we left it in.

kryzar pushed a commit to kryzar/sage that referenced this issue Feb 6, 2023

Trac sagemath#32841: remove zn_poly TARGETS from cygwin github workfl…

46f7623

…ows. The zn_poly SPKG has been removed, so we should not try to build it as part of the cygwin workflows.

kryzar pushed a commit to kryzar/sage that referenced this issue Feb 6, 2023

Trac sagemath#32841: remove zn_poly section from COPYING.txt.

8699ed0

The zn_poly SPKG has been removed, so its license no longer affects that of the larger SageMath project.

mkoeppe added a commit that referenced this issue Feb 9, 2023

Revert "Trac #32841: remove zn_poly TARGETS from cygwin github workfl…

aa9d10e

…ows." This reverts commit 46f7623.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

zn_poly removal #32841

zn_poly removal #32841

orlitzky commented Nov 9, 2021

orlitzky commented Nov 9, 2021

orlitzky commented Nov 9, 2021

orlitzky commented Nov 9, 2021

orlitzky commented Nov 9, 2021

roed314 commented Nov 9, 2021

orlitzky commented Nov 10, 2021

roed314 commented Nov 10, 2021

orlitzky commented Nov 10, 2021

JohnCremona commented Nov 11, 2021

orlitzky commented Nov 11, 2021

orlitzky commented Dec 2, 2021

mkoeppe commented Dec 2, 2021

orlitzky commented Dec 3, 2021

roed314 commented Dec 20, 2021

sagetrac-git mannequin commented Jan 13, 2022

sagetrac-git mannequin commented Jan 13, 2022

dimpase commented Dec 7, 2022

dimpase commented Dec 7, 2022

dimpase commented Dec 7, 2022

dimpase commented Dec 7, 2022

dimpase commented Dec 7, 2022

orlitzky commented Dec 7, 2022

dimpase commented Dec 7, 2022

dimpase commented Dec 7, 2022

vbraun commented Dec 14, 2022

zn_poly removal #32841

zn_poly removal #32841

Comments

orlitzky commented Nov 9, 2021

orlitzky commented Nov 9, 2021

orlitzky commented Nov 9, 2021

orlitzky commented Nov 9, 2021

orlitzky commented Nov 9, 2021

roed314 commented Nov 9, 2021

orlitzky commented Nov 10, 2021

roed314 commented Nov 10, 2021

orlitzky commented Nov 10, 2021

JohnCremona commented Nov 11, 2021

orlitzky commented Nov 11, 2021

orlitzky commented Dec 2, 2021

mkoeppe commented Dec 2, 2021

orlitzky commented Dec 3, 2021

roed314 commented Dec 20, 2021

sagetrac-git mannequin commented Jan 13, 2022

sagetrac-git mannequin commented Jan 13, 2022

dimpase commented Dec 7, 2022

dimpase commented Dec 7, 2022

dimpase commented Dec 7, 2022

dimpase commented Dec 7, 2022

dimpase commented Dec 7, 2022

orlitzky commented Dec 7, 2022

dimpase commented Dec 7, 2022

dimpase commented Dec 7, 2022

vbraun commented Dec 14, 2022