PARI library interface broken by design

[jdemeyer]

The t0GEN(), t1GEN(),... system in the PARI interface is broken by design. Apply demonstrate_11868.patch​ to see the bug in action.

The problem is that the conversion of b (Python object) to t1 (PARI GEN) uses the PARI stack and therefore it clobbers the previously computed t0.

There is no urgent need to fix this, as the bug doesn't seem to occur in practice (it was discovered when working on #9334). It only occurs when:

1. Calling a PARI function with at least 2 arguments besides self.
2. Apart from the first non-self argument, there should be another argument which is a "complicated" Python type (e.g. a number field element).

As work-around, it is easy to defeat condition 2 by converting arguments to pari before calling the function.

This problem can be solved by using only local variables instead of t0GEN etc.

Apply: trac_11868-t0GEN_new.patch​, trac_11868-remove_workarounds.patch​, 11868_pari_extra.patch​

[jdemeyer]

The t0GEN(), t1GEN(),... system in the PARI interface is broken by design. Apply demonstrate_11868.patch​ to see the bug in action.

[jdemeyer]

Patch to *demonstrate* the bug

[jdemeyer]

Milestone sage-4.7.3 deleted

[pbruin]

eliminate global GEN variables

[pbruin]

The patch contains (slightly) more changes than strictly necessary; this is to make life a bit easier for #15185.

[jdemeyer]

Is it not possible to keep get_nf() as a function returning a GEN without copying?

[jdemeyer]

I agree with the general approach, but have to check the many details...

[jdemeyer]

In the PARI sources, there are various workarounds for #11868, could you undo these workarounds:

devel/sage/sage/schemes/elliptic_curves/ell_point.py:        We need to explicitly call ``pari()`` because of :trac:`11868`::
devel/sage/sage/rings/number_field/number_field.py:            # to work around Trac #11868 -- Jeroen Demeyer
devel/sage/sage/rings/number_field/number_field.py:        # to work around Trac #11868 -- Jeroen Demeyer
devel/sage/sage/libs/pari/gen.pyx:            sage: pari(K).nfhilbert(t, t+2)  # not tested, known bug #11868

[jdemeyer]

Maybe rename get_nf() as _get_nf() to emphazise that it's a private internal function?

[jdemeyer]

One important "detail": it seems this ticket causes a lot more copying of data (because of the gcopy() in cdef GEN toGEN. That's bad.

[jdemeyer]

Maybe the right thing to do is to have things like t0 of type gen instead of GEN and then using t0.g (like we already often do for self).

[pbruin]

Replying to jdemeyer:

In the PARI sources, there are various workarounds for #11868, could you undo these workarounds:

Done, patch on its way.

[pbruin]

remove workarounds for bug related to global GEN variables

[pbruin]

Replying to jdemeyer:

Is it not possible to keep get_nf() as a function returning a GEN without copying?

It is actually even possible that we don't need get_nf() at all, since PARI has higher-level functions like member_pol(), member_diff() etc. that accept various types of number fields. (Maybe these didn't exist when gen.pyx was written?) I'll look into it.

[pbruin]

eliminate the gen.get_nf() method

[pbruin]

It turns out that get_nf() can indeed be done away with entirely.

[pbruin]

Replying to jdemeyer:

One important "detail": it seems this ticket causes a lot more copying of data (because of the gcopy() in cdef GEN toGEN. That's bad.

In an earlier attempt I did make the t0 variables of type gen. I think the reason I changed them back to GEN is to decrease the number of gen objects that had to be created/deleted. The (only) price to pay for this is an extra gcopy() for Sage objects that are converted via their _pari_() method. This is an extremely common case of course. I'll have to think some more about this issue.

[jdemeyer]

Replying to pbruin:

Replying to jdemeyer:

One important "detail": it seems this ticket causes a lot more copying of data (because of the gcopy() in cdef GEN toGEN. That's bad.

In an earlier attempt I did make the t0 variables of type gen. I think the reason I changed them back to GEN is to decrease the number of gen objects that had to be created/deleted. The (only) price to pay for this is an extra gcopy() for Sage objects that are converted via their _pari_() method. This is an extremely common case of course. I'll have to think some more about this issue.

I don't my suggestion would create more gen objects. What usually happens is (with this patch applied):

• some PARI computation creates a GEN on the PARI stack
• _new_gen() calls deepcopy_to_python_heap which copies the object to the Python heap and makes it into a gen object
• toGEN copies the object back to the PARI stack

My proposal is essentially removing the last step.

[jdemeyer]

I found another problem with your patch: you must not do

pari_catch_sig_on()
cdef GEN t0 = P.toGEN(x)

because you should not call Python code within sig_on()/sig_off() and toGEN() potentially calls Python code. So the toGEN should be before pari_catch_sig_on().

[jdemeyer]

I have also been thinking about using a with statement:

cdef GEN r
with to_GEN(s) as t0:
    pari_catch_sig_on
    r = gwhatever(t0)
    pari_catch_sig_off
return new_gen(r)  # Clears stack but doesn't call pari_catch_sig_off()

Then to_GEN would be something like

cimport cython

@cython.final
cdef class to_GEN:
    cdef gen x

    def __init__(to_GEN self, s):
        self.x = s._pari_()

    cdef inline GEN __enter__(to_GEN self):
        return self.x.g

    cdef inline int __exit__(to_GEN self, typ, value, traceback):
        return 0

This looks more complicated, but it has the added advantage that the gen object for s is hidden inside the to_GEN class and that the gen x is kept alive for just the right amount of time. This opens a possibility (not on this ticket) to make deepcopy_to_python_heap() lazy, such that it only activates when the PARI stack is cleared.

[pbruin]

Replying to jdemeyer:

I found another problem with your patch: you must not do

pari_catch_sig_on()
cdef GEN t0 = P.toGEN(x)

because you should not call Python code within sig_on()/sig_off() and toGEN() potentially calls Python code. So the toGEN should be before pari_catch_sig_on().

Yes, I also realised in the meantime that this is a problem. With the current policy of clearing the whole stack at every new_gen(), this means that have to wrap every temporary GEN in a gen if we want it to survive subsequent applications of toGEN(). So I think the best solution is to use gen instead of GEN, as in comment:11. (This is essentially very close to what we currently have.)

[pbruin]

Replying to jdemeyer:

I don't my suggestion would create more gen objects.

It doesn't create any more gen objects than what we have now, but I wanted (and failed for now) to create fewer gen objects than what we have now.

What usually happens is (with this patch applied):

• some PARI computation creates a GEN on the PARI stack
• _new_gen() calls deepcopy_to_python_heap which copies the object to the Python heap and makes it into a gen object
• toGEN copies the object back to the PARI stack

My proposal is essentially removing the last step.

That is what happens for objects with a _pari_() method. For other objects, my idea was to not create any gen object and keep the converted GEN on the PARI stack. Ideally, toGEN() should either leave the temporary GEN in the Python heap (if it comes from an existing gen or from a _pari_() method) or on the PARI stack (if it is converted, withouth an intermediate gen, from a Python object without a _pari_() method).

Anyway, this idea is now defeated for the time being because of comment:18 and comment:20. To implement it, we would need a more fine-grained way of clearing the PARI stack (only clear what you have used, and leave the rest of the stack alone).

Now working on a new patch in the spirit of comment:11.

[pbruin]

eliminate global GEN variables

[pbruin]

trac_11868-t0GEN_new.patch​ replaces trac_11868-t0GEN.patch​ and trac_11868-get_nf.patch​

Apply trac_11868-t0GEN_new.patch, trac_11868-remove_workarounds.patch

[jdemeyer]

I added some small changes, see 11868_pari_extra.patch​. It's not strictly a reviewer patch, since many changes are unrelated to this ticket but just small things I observed while checking your patch.

[pbruin]

Replying to jdemeyer:

I added some small changes, see 11868_pari_extra.patch​. It's not strictly a reviewer patch, since many changes are unrelated to this ticket but just small things I observed while checking your patch.

I will look at this more carefully later; just two questions for now:

• What exactly is a dangerous malloc()?
• In some places (e.g. isprime()), doing P.clear_stack() instead of pari_catch_sig_off() is clearly better because we call a PARI function returing a GEN that would otherwise be left on the stack. In other cases (e.g. ispseudoprime()) we only call a PARI function returning long; is clear_stack() really necessary here?

[jdemeyer]

Replying to pbruin:

• What exactly is a dangerous malloc()?

malloc() inside sig_on() is dangerous because an interrupt during malloc() will almost certainly corrupt the heap. sage_malloc() fixes this, but of course PARI doesn't know about sage_malloc().

is clear_stack() really necessary here?

You're right, it's not needed.

I also noticed that Cython seems unable to optimize P(x), so it might be better to invent a cdef method for that (say, P.togen(x)) which can be more optimized.

[jdemeyer]

Replying to jdemeyer:

I also noticed that Cython seems unable to optimize P(x), so it might be better to invent a cdef method for that (say, P.togen(x)) which can be more optimized.

I changed P(x) to objtogen(x) everywhere, where objtogen is a cdef function (not method). This gives a noticable speed gain.

[jdemeyer]

In objtogen, I also added an extra case for strings which should be faster now.

[pbruin]

Your change to __int__() and __long__() gives a major slowdown due to the importing of Integer (a factor of more than 6 for small examples on my system). The late_import() does look ugly; it may be slightly nicer to inline it in __int__() and __long__() as

global Integer 
if Integer is None: 
    import sage.rings.integer 
    Integer = sage.rings.integer.Integer 

[pbruin]

I agree with the rest of your extra changes.

[pbruin]

For __int__(), I also experimented with first doing

    cdef long i
    try:
        pari_catch_sig_on()
        i = gtolong(self.g)
        pari_catch_sig_off()
        return i
    except PariError:  # overflow
        pass

This gives a speedup of a factor about 2 if there is no overflow, but is very slow if the exception occurs.

[jdemeyer]

gtolong doesn't check for overflow when converting from t_REAL. I used your proposal of

        global Integer
        if Integer is None:
            import sage.rings.integer
            Integer = sage.rings.integer.Integer
        return int(Integer(self))

and added two doctests for conversion t_REAL -> int

[pbruin]

Replying to jdemeyer:

added two doctests for conversion t_REAL -> int

Those doctests don't seem to involve PARI, or am I missing something?

[jdemeyer]

Replying to pbruin:

Those doctests don't seem to involve PARI, or am I missing something?

You're right, I fixed them.

[pbruin]

For the conversion to bool, Cython translates bool(x) into a complicated call to the bool type. Using x != 0 or PyBool_FromLong(x) is more efficient.

[jdemeyer]

Added patch

sage/libs/pari/gen.pyx

@@ -1871 +1871 @@
         pari_catch_sig_on()
         cdef int ret = gequal(a.g, t0.g)
         pari_catch_sig_off()
-        return bool(ret)
+        return ret != 0
 
     def gequal0(gen a):
         r"""
@@ -1893 +1893 @@
         pari_catch_sig_on()
         cdef int ret = gequal0(a.g)
         pari_catch_sig_off()
-        return bool(ret)
+        return ret != 0
 
     def gequal_long(gen a, long b):
         r"""
@@ -1920 +1920 @@
         pari_catch_sig_on()
         cdef int ret = gequalsg(b, a.g)
         pari_catch_sig_off()
-        return bool(ret)
+        return ret != 0
     
 
     ###########################################
@@ -1962 +1962 @@
         pari_catch_sig_on()
         cdef long t = signe(gisprime(self.g, flag))
         P.clear_stack()
-        return bool(t)
+        return t != 0
 
     def qfbhclassno(gen n):
         r"""
@@ -2041 +2041 @@
         pari_catch_sig_on()
         cdef long t = ispseudoprime(self.g, flag)
         pari_catch_sig_off()
-        return bool(t)
+        return t != 0
 
     def ispower(gen self, k=None):
         r"""
@@ -3209 +3209 @@
             [True, False, True, True, True, True, True, True, True, True]
         """
         pari_catch_sig_on()
-        b = bool(bittest(x.g, n))
+        cdef long b = bittest(x.g, n)
         pari_catch_sig_off()
-        return b
+        return b != 0
     
     def bitxor(gen x, y):
         """
@@ -5541 +5541 @@
 
     def issquare(gen x, find_root=False):
         """
-        issquare(x,n): true(1) if x is a square, false(0) if not. If
-        find_root is given, also returns the exact square root if it was
-        computed.
-        """
-        cdef GEN G, t
+        issquare(x,n): ``True`` if x is a square, ``False`` if not. If
+        ``find_root`` is given, also returns the exact square root.
+        """
+        cdef GEN G
+        cdef long t
         cdef gen g
         pari_catch_sig_on()
         if find_root:
-            t = gissquareall(x.g, &G)
-            v = bool(P.new_gen_noclear(t))
-            if v:
-                return v, P.new_gen(G)
+            t = itos(gissquareall(x.g, &G))
+            if t:
+                return True, P.new_gen(G)
             else:
-                pari_catch_sig_off()
-                return v, None
+                P.clear_stack()
+                return False, None
         else:
-            return P.new_gen(gissquare(x.g))
-
+            t = itos(gissquare(x.g))
+            pari_catch_sig_off()
+            return t != 0
 
     def issquarefree(gen self):
         """
@@ -5570 +5570 @@
             False
         """
         pari_catch_sig_on()
-        t = bool(issquarefree(self.g))
+        cdef long t = issquarefree(self.g)
         pari_catch_sig_off()
-        return t
+        return t != 0
 
     def lcm(gen x, y):
         """
@@ -6203 +6203 @@
         """
         cdef gen t0 = objtogen(x)
         pari_catch_sig_on()
-        t = bool(oncurve(self.g, t0.g) == 1)
+        cdef int t = oncurve(self.g, t0.g)
         pari_catch_sig_off()
-        return t
+        return t != 0
 
     def elllocalred(self, p):
         r"""
@@ -8034 +8034 @@
         non-constant polynomial, or False if f is reducible or constant.
         """
         pari_catch_sig_on()
-        return bool(self.new_gen(gisirreducible(self.g)))
-        
-        
+        cdef long t = itos(gisirreducible(self.g))
+        P.clear_stack()
+        return t != 0
+
     def pollead(self, v=-1):
         """
         self.pollead(v): leading coefficient of polynomial or series self,

[pbruin]

Excellent, I'm happy with the current state.