RFC: zn_poly removal

[Michael Orlitzky]

Trac: https://trac.sagemath.org/ticket/32841

In short, zn_poly is one of "those" packages. Abandoned in 2008, and
kept on life support by sage developers ever since. Despite our
efforts, the build system remains crazy and it would take a good bit of
time to re-do the whole thing using autotools or cmake or whatever to
make it reliable and easy to package.

And it turns out, the sage library doesn't really need it any more. The
one thing it does is done better by NTL.

I'm posting here because it's a standard SPKG, but I think removal is a
clear win in this case. Smaller tarballs, faster build times, easier on
packagers, and no more time wasted updating zn_poly for new compilers
and operating systems.

But if any number theorists think I've overlooked something, please
speak up.

[Alex J Best]

I agree the situation with zn_poly is a mess, but I think it would be good to do some actual benchmarks to check if the NTL code is faster or comparable to the zn_poly version, I don't see any data in the ticket but you do say "The one thing it does is done better by NTL" so maybe you already did some?

Computing zeta functions of hyperelliptic curves is pretty fundamental thing to do for many applications in arithmetic geometry, and performance is important there, so it would really be a shame if those applications got significantly slower.

The decision of whether its worth the maintainence burden should be done with full knowledge of what we are losing, if it turns out its nothing, thats great!

I also this the claim that it's only used in one place undersells it a little bit, the wrapped function `interval_products` is used both in the hyperelliptic_curves and cyclic_covers modules (since 2018) (https://github.com/sagemath/sage/search?q=interval_products), though they are admittedly very related applications, there are a range of parameters with which this code may be called.

[Alex J Best]

I must correct myself: the interval products code via NTL is not used for cyclic covers as the force NTL flag is set to true there (thanks David Roe!)

[Michael Orlitzky]

On Tue, 2021-11-09 at 10:54 -0800, Alex J Best wrote:
> I agree the situation with zn_poly is a mess, but I think it would be good
> to do some actual benchmarks to check if the NTL code is faster or
> comparable to the zn_poly version, I don't see any data in the ticket but
> you do say "The one thing it does is done better by NTL" so maybe you
> already did some?

It would be hard to benchmark without knowing where zn_poly fails. The
only function in sagelib that uses zn_poly is in hypellfrob.cpp, and it
has a comment at the top:

Note that the zn_poly version occasionally fails; this happens more 
frequently for smaller p, but is extremely rare for larger p. This 
wrapper detects this and falls back on the zz_p/ZZ_p versions, which 
should never fail.

That's what I meant by "NTL does it better," and any benchmark would
have to take into consideration the attempts that failed and were
actually made with NTL instead. Certainly those cases are slower than
if we'd just used NTL the first time.

[Michael Orlitzky]

On Tue, 2021-11-09 at 10:58 -0800, Alex J Best wrote:
> I must correct myself: the interval products code via NTL is not used for
> cyclic covers as the force NTL flag is set to true there (thanks David Roe!)

Unless I misread commit 54e89297, you've set force_ntl=1 yourself
inside the exposed interval_products() function:

c.restore_c()
interval_products_wrapper(out, mm0, mm1, targ, 1)
sig_off()

[Alex J Best]

Right, that seems like a fair benchmark to me, does zn_poly (falling back to ntl) run faster than the force ntl = 1 version in enough ranges of variables to justify its continued existence?

Knowing whether it failed and fell back (and hence was slower) or just is simply slower doesn't seem to matter compared to the end result, knowing where its slower.

Yes exactly, I forgot now why we decided to use force ntl=1 for cyclic covers, and indeed I forgot that we did force it completely, I really have no idea the reasons that went into that decision anymore unfortunately.

[Dima Pasechnik]

I think we'd be fine dropping zn_poly even if it is 2 or 3 times faster.

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/7062f8ee-226c-41d6-ab95-ad0b0094d908n%40googlegroups.com.

[Michael Orlitzky]

On 2021-11-11 11:18:03, Alex J Best wrote:
> Right, that seems like a fair benchmark to me, does zn_poly (falling back
> to ntl) run faster than the force ntl = 1 version in enough ranges of
> variables to justify its continued existence?
> Knowing whether it failed and fell back (and hence was slower) or just is
> simply slower doesn't seem to matter compared to the end result, knowing
> where its slower.
>

For what it's worth, I did overlook a few indirect uses of
interval_products_wrapper(). It's called by hypellfrob::matrix(),
which I didn't realize was visible in hypellfrob.h. I've set the
ticket to needs_work temporarily for want of benchmarks.

> Yes exactly, I forgot now why we decided to use force ntl=1 for cyclic
> covers, and indeed I forgot that we did force it completely, I really have
> no idea the reasons that went into that decision anymore unfortunately.
>

https://i.redd.it/chyhl5fj4zg41.jpg