New implementation of unramified p-adics using FLINT and templates

[roed314]

Reimplement Qq using FLINT.

Depends on #20210

CC: @fredrik-johansson @jpflori @saraedum

Component: padics

Keywords: sd59, days71

Author: Julian Rüth, David Roe

Branch/Commit: 56b357c

Reviewer: David Roe, Julian Rüth, Aly Deines

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

[roed314]

comment:3

This ticket is essentially complete at https://github.com/saraedum/sage/tree/Zq. Once #12173 is positively reviewed we'll make some patches and put this up for review.

[jdemeyer]

comment:5

Replying to @roed314:

Once #12173 is positively reviewed

check!

[saraedum]

comment:6

The repository moved to https://github.com/saraedum/sage-renamed/tree/Zq

[roed314]

Commit: ed8db42

[roed314]

Branch: u/saraedum/Zq

[roed314]

Last 10 new commits:

ed8db42	fixup
244b3a8	conversion from finite fields
8f255a9	fix some typos
65d3c03	added matrix_mod_pn
ff52ce0	removed FLINT skip
7b2ad9a	fixed a doctest
fd2ea9f	added flint rep
13a2d60	added an _new_fmpz_poly method
52010f3	switched to powcomputer_
02ffe57	disabled tests for FLINT

[roed314]

Changed branch from u/saraedum/Zq to u/roed/ticket/14304

[roed314]

New commits:

e7afa8f	Improved some_elements()
ef18f02	Adding some docstrings, fixing a few typos.

[roed314]

Changed commit from ed8db42 to e7afa8f

[roed314]

Reviewer: David Roe, Julian Rueth

[roed314]

Author: Julian Rueth, David Roe

[saraedum]

comment:12

I mostly looked at the last two commits. Everything else had already been reviewed before. I did not run doctests. Is there a working patchbot which will run the doctests or do I have to run them manually?

[vbraun]

comment:13

Does not work... please run "make ptestlong"

[roed314]

comment:14

Will do.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e7afa8f to 98a4529

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

98a4529

Fix doctest errors

[jdemeyer]

comment:17

There is invalid use of sig_on() in many places. The following is wrong:

sig_on()
if condition:
    raise Exception
sig_off()

You must put a sig_off() before the raise (or use try/finally).

I also recommend to doctest these exceptions. The doctesting framework catches such invalid use of sig_on().

I also don't like bare except: statements. Be explicit and use except BaseException: or except Exception: instead.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

d0badde

Fixing sig_on/sig_off pairs, adding BaseException to bare except:s

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 98a4529 to d0badde

[roed314]

comment:19

Replying to @jdemeyer:

There is invalid use of sig_on() in many places. The following is wrong:

sig_on()
if condition:
    raise Exception
sig_off()

You must put a sig_off() before the raise (or use try/finally).

Thanks. I fixed them.

I also recommend to doctest these exceptions. The doctesting framework catches such invalid use of sig_on().

All of the instances I found were for problems that we never expect to arise (out of memory errors, etc). So I don't see a reasonable way to doctest these exceptions.

I also don't like bare except: statements. Be explicit and use except BaseException: or except Exception: instead.

I know. :-) I told Julian you didn't like them, but he claimed it was okay since we raised after catching in each case. Anyway, I've changed them to except BaseException:.

[vbraun]

comment:20

For the record, the Python docs say

exception BaseException

The base class for all built-in exceptions. It is not meant to be directly 
inherited by user-defined classes (for that, use Exception).

Nested exception blocks are generally hard to read, quadruply nested exception try/except/finally blocks even more so. Besides the usual advice of breaking long functions up into shorter ones, for the heap cleanup in the face of exceptions make sure that invalid / not yet allocated pointers are NULL. To simplify the cleanup part, free(NULL) is a no-op.

The for i from 0 <= i <= n construct is old, Cython nowadays produces the same C code for the (preferred) Python syntax for i in range(n).

[jdemeyer]

comment:21

Replying to @roed314:

but he claimed it was okay since we raised after catching in each case. Anyway, I've changed them to except BaseException:.

It is technically ok in this case. The reason I don't like except: is that in almost all cases that I have seen, it was a mistake. If you write except BaseException:, it shows that you probably know what you're doing and that it is not a mistake. It is also consistent with "Explicit is better than implicit" from the Zen of Python (import this).

[jdemeyer]

comment:22

sig_on() should be outside the try/finally block (if sig_on() raises a KeyboardInterrupt, then sig_off() should not be called)

sig_on()
try:
    ...
finally:
    sig_off()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d0badde to c647f4a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

e101508	Some sig_on, cython for loop fixes
c647f4a	More sig_on, cython for loop fixes

[roed314]

comment:25

Nested exception blocks are generally hard to read, quadruply nested exception try/except/finally blocks even more so. Besides the usual advice of breaking long functions up into shorter ones, for the heap cleanup in the face of exceptions make sure that invalid / not yet allocated pointers are NULL. To simplify the cleanup part, free(NULL) is a no-op.

What about things like mpz_clear, fmpz_clear and fmpz_poly_clear? If a is an fmpz_poly_t that has not yet had fmpz_poly_init(a) run on it, won't fmpz_poly_clear(a) be a double free?

[roed314]

comment:26

I've addressed the concerns about sig_on and the Cython for loops. I agree that the super-nested try blocks are ugly, but I don't know how to rewrite it safely without this nesting.

[jpflori]

comment:27

Replying to @roed314:

What about things like mpz_clear, fmpz_clear and fmpz_poly_clear? If a is an fmpz_poly_t that has not yet had fmpz_poly_init(a) run on it, won't fmpz_poly_clear(a) be a double free?

Yes, they will and Sage will crash, or at least could. On Linux you can set _MALLOC_CHECK=3 to ensure (or have a higher probability) it will crash in such cases.

[roed314]

comment:28

Replying to @jpflori:

Replying to @roed314:

What about things like mpz_clear, fmpz_clear and fmpz_poly_clear? If a is an fmpz_poly_t that has not yet had fmpz_poly_init(a) run on it, won't fmpz_poly_clear(a) be a double free?

Yes, they will and Sage will crash, or at least could. On Linux you can set _MALLOC_CHECK=3 to ensure (or have a higher probability) it will crash in such cases.

So, does anyone have suggestions on how to rewrite the ugly nested try blocks in PowComputer_flint_unram.__cinit__? Julian and I couldn't think of a better way to do it that would never have a memory leak or a double free.

[jpflori]

comment:29

I'll have a look tomorrow (french time).

[jdemeyer]

comment:30

Replying to @roed314:

So, does anyone have suggestions on how to rewrite the ugly nested try blocks in PowComputer_flint_unram.__cinit__? Julian and I couldn't think of a better way to do it that would never have a memory leak or a double free.

I had a look at the code and the current code actually is never going to work. The C-level functions like fmpz_poly_init and mpz_init never raise exceptions. So, the try/except is pointless. As far as I can tell, there are two kinds of exceptions which can happen: a MemoryError in MPIR or a KeyboardInterrupt. In both cases, the exception will be raised by sig_on() and none of the except blocks are executed.

If you want to be absolutely correct, every single allocation should be wrapped individually in sig_on()/sig_off(). Example for 2 allocations:

sig_on()
alloc1()
sig_off()

try:
    sig_on()
    alloc2()
    sig_off()
except BaseException:
    free1()
    raise

But at least the very deeply nested block on this ticket is allocating extremely little memory (surely less than 1000 bytes), so why not simply

alloc1()
alloc2()

[saraedum]

comment:31

Replying to @jdemeyer:

Replying to @roed314:

So, does anyone have suggestions on how to rewrite the ugly nested try blocks in PowComputer_flint_unram.__cinit__? Julian and I couldn't think of a better way to do it that would never have a memory leak or a double free.

I had a look at the code and the current code actually is never going to work. [...]

You are right. I had misunderstood how sig_on/sig_off worked.

But at least the very deeply nested block on this ticket is allocating extremely little memory (surely less than 1000 bytes), so why not simply

alloc1()
alloc2()

Is this acceptable? In the unlikely case that this allocation fails because we're out of memory, then sage is going to crash right?

[jdemeyer]

comment:32

Replying to @saraedum:

Is this acceptable? In the unlikely case that this allocation fails because we're out of memory, then sage is going to crash right?

Well, at least the very deeply nested allocation in this branch is allocating very little memory. If that already fails, bad things are going to happen anyway.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c647f4a to 60975a4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

4f04d28	Fix PowComputer_flint_unram.__cinit__ to not leak memory when interrupted.
60975a4	Remove the 11-nested try blocks in the interest of code readability, sacrificing some memory-leak resistance

[roed314]

comment:34

Here are two commits; the first has the 11-nested try blocks with "safe" memory handling, and the second removes them for code readability. I'm fine with either approach.

[jdemeyer]

comment:35

This comment is wrong:

While the following allocations have the potential to leak
small amounts of memory when interrupted or when one of the
init methods raises a MemoryError

If you don't have sig_on(), the code cannot be interrupted (unless it's called from within sig_on(), but that would not be a good idea). It also cannot raise a MemoryError, since there is no sig_on() to raise them. Instead of a MemoryError, Sage would simply crash hard.

[roed314]

comment:36

Replying to @jdemeyer:

If you don't have sig_on(), the code cannot be interrupted (unless it's called from within sig_on(), but that would not be a good idea). It also cannot raise a MemoryError, since there is no sig_on() to raise them. Instead of a MemoryError, Sage would simply crash hard.

So the whole block of allocations should be wrapped in a single sig_on()/sig_off()?

[jdemeyer]

comment:37

Replying to @roed314:

So the whole block of allocations should be wrapped in a single sig_on()/sig_off()?

In that case, memory leaks are possible and the comment would be 100% correct.

[jpflori]

comment:38

I see that there is some smartness added to sage_mpir_malloc/... functions in src/c_lib/memory.c, and these functions are hopefully called when mpir_init is (instead of plain malloc/...).

But as far as I now, nothing similar was done for flint, and if that's the case, a failed memory allocation would go undetected anyway (and Sage crash quite quickly with null pointer dereference or similar delicious stuff).

I just looked at flint memory allocation code (flfint_malloc/...), and a failed allocation by malloc would call the flint_memory_error function which calls abort().

[jdemeyer]

comment:39

Replying to @jpflori:

I just looked at flint memory allocation code (flfint_malloc/...), and a failed allocation by malloc would call the flint_memory_error function which calls abort().

That's great because (unlike MPIR which silenty ignores memory errors) an abort() within sig_on() yields a RuntimeError which can safely be handled.

[pjbruin]

comment:40

Why not increment the __allocated counter after every successful allocation and use its value in __dealloc__() to decide which objects have to be deallocated? E.g.

def __cinit__(self, ...):
    sig_on()
    self.__allocated = 0
    fmpz_init(self.fmpz_ccmp); self.__allocated++
    fmpz_init(self.fmpz_cval); self.__allocated++
    ...
    fmpz_poly_init(self.poly_cconv); self.__allocated++
    fmpz_poly_init(self.poly_ctm); self.__allocated++
    ...
    sig_off()

def __dealloc__(self, ...):
    if self.__allocated >= 1:
        fmpz_clear(self.fmpz_ccmp)
    if self.__allocated >= 2:
        fmpz_clear(self.fmpz_cval)
    ...

I hope I'm understanding the problem correctly; I'm just looking at the code and didn't follow the above discussion very closely.

[jdemeyer]

comment:41

For that to work properly, self.__allocated should have type volatile int.

[pjbruin]

comment:42

Replying to @jdemeyer:

For that to work properly, self.__allocated should have type volatile int.

OK, I can believe that. Does Cython support volatile?

[jdemeyer]

comment:43

Replying to @pjbruin:

Replying to @jdemeyer:

For that to work properly, self.__allocated should have type volatile int.

OK, I can believe that. Does Cython support volatile?

Not directly, as far as I know. You can do

cdef extern from *:
    ctypedef int volatile_int "volatile int"

and then use volatile_int.

[vbraun]

comment:44

Agree with the volatile being necessary so that the optimizer doesn't combine the increments into a single += n. But afaik it would still be legal for the optimizer to reorder statements as

    self.__allocated++
    self.__allocated++
    ...
    self.__allocated++
    fmpz_init(self.fmpz_ccmp)
    fmpz_init(self.fmpz_cval)
    ...
    fmpz_poly_init(self.poly_ctm)

So either mark everything that needs to be accessed in-order as volatile. Or use the usual pattern

def __cinit__(self, ...):
    self.fmpz_ccmp = NULL
    self.fmpz_cval = NULL
    sig_on()
    fmpz_init(self.fmpz_ccmp)
    fmpz_init(self.fmpz_cval)
    sig_off()

def __dealloc__(self, ...):
    if self.fmpz_ccmp != NULL:
        fmpz_clear(self.fmpz_ccmp)
    if self.fmpz_ccval != NULL:
        fmpz_clear(self.fmpz_ccval)

[vbraun]

comment:45

I guess that can still be broken by creative reordering of the pointer initialization, so to be 100% safe one would need to split the setting to NULL from the fmpz_init either by

1. a compiler barrier (asm volatile("" ::: "memory") in gcc)
2. move the fmpz_init into __init__
3. RAII (separate classes for each fmpz_poly_t)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

cda1d75

Wrap allocations in sig_on/sig_off

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 60975a4 to cda1d75

[pjbruin]

comment:48

I merged the latest development branch (conflicts in sage/rings/padics/factory.py and sage/rings/padics/pow_computer.pyx), and then got this error while compiling:

Error compiling Cython file:
------------------------------------------------------------
...

        fmpz_poly_content(prime_pow.fmpz_cinv, a)
        fmpz_poly_scalar_divexact_fmpz(out, a, prime_pow.fmpz_cinv)

        fmpz_poly_xgcd(prime_pow.fmpz_cinv2, out, prime_pow.poly_cinv2, out, prime_pow.poly_cinv)
        if fmpz_is_zero(prime_pow.cinv2): raise ValueError("polynomials are not coprime")
                                ^
------------------------------------------------------------

./sage/libs/linkages/padics/fmpz_poly_unram.pxi:343:33: Cannot convert Python object to 'fmpz_t'