Opened 8 years ago

Closed 6 years ago

#11868 closed defect (fixed)

PARI library interface broken by design

Reported by: jdemeyer Owned by: was
Priority: major Milestone: sage-5.13
Component: interfaces Keywords: t0GEN t1GEN gen
Cc: Merged in: sage-5.13.beta5
Authors: Peter Bruin Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #864, #9640, #10018 Stopgaps:

Description (last modified by 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

Attachments (6)

demonstrate_11868.patch (1.0 KB) - added by jdemeyer 8 years ago.
Patch to *demonstrate* the bug
trac_11868-t0GEN.patch (71.2 KB) - added by pbruin 6 years ago.
eliminate global GEN variables
trac_11868-remove_workarounds.patch (3.0 KB) - added by pbruin 6 years ago.
remove workarounds for bug related to global GEN variables
trac_11868-get_nf.patch (5.3 KB) - added by pbruin 6 years ago.
eliminate the gen.get_nf() method
trac_11868-t0GEN_new.patch (73.4 KB) - added by pbruin 6 years ago.
eliminate global GEN variables
11868_pari_extra.patch (63.3 KB) - added by jdemeyer 6 years ago.

Download all attachments as: .zip

Change History (47)

comment:1 Changed 8 years ago by jdemeyer

  • Description modified (diff)

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

Changed 8 years ago by jdemeyer

Patch to *demonstrate* the bug

comment:2 Changed 8 years ago by jdemeyer

  • Description modified (diff)

comment:3 Changed 8 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

Changed 6 years ago by pbruin

eliminate global GEN variables

comment:4 Changed 6 years ago by pbruin

  • Authors set to Peter Bruin
  • Description modified (diff)
  • Milestone set to sage-5.13
  • Status changed from new to needs_review

comment:5 Changed 6 years ago by pbruin

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

comment:6 follow-up: Changed 6 years ago by jdemeyer

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

comment:7 Changed 6 years ago by jdemeyer

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

comment:8 follow-up: Changed 6 years ago by jdemeyer

  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_review to needs_work

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

comment:9 Changed 6 years ago by jdemeyer

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

comment:10 follow-up: Changed 6 years ago by 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.

comment:11 Changed 6 years ago by 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).

comment:12 in reply to: ↑ 8 Changed 6 years ago by pbruin

Replying to jdemeyer:

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

Done, patch on its way.

Changed 6 years ago by pbruin

remove workarounds for bug related to global GEN variables

comment:13 Changed 6 years ago by pbruin

  • Description modified (diff)

comment:14 in reply to: ↑ 6 Changed 6 years ago by 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.

Changed 6 years ago by pbruin

eliminate the gen.get_nf() method

comment:15 Changed 6 years ago by pbruin

  • Description modified (diff)

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

comment:16 in reply to: ↑ 10 ; follow-up: Changed 6 years ago by 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.

comment:17 in reply to: ↑ 16 ; follow-up: Changed 6 years ago by 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.

comment:18 follow-up: Changed 6 years ago by 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().

comment:19 Changed 6 years ago by 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.

comment:20 in reply to: ↑ 18 Changed 6 years ago by 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.)

comment:21 in reply to: ↑ 17 Changed 6 years ago by 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.

Changed 6 years ago by pbruin

eliminate global GEN variables

comment:22 Changed 6 years ago by pbruin

  • Description modified (diff)
  • Status changed from needs_work to needs_review

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

comment:23 Changed 6 years ago by jdemeyer

  • Dependencies set to #864

comment:24 Changed 6 years ago by jdemeyer

  • Dependencies changed from #864 to #864, #9640, #10018

comment:25 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:26 follow-up: Changed 6 years ago by 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.

comment:27 in reply to: ↑ 26 ; follow-up: Changed 6 years ago by 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?

comment:28 in reply to: ↑ 27 ; follow-up: Changed 6 years ago by 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.

comment:29 in reply to: ↑ 28 Changed 6 years ago by 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.

comment:30 Changed 6 years ago by jdemeyer

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

comment:31 Changed 6 years ago by 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 

comment:32 Changed 6 years ago by pbruin

I agree with the rest of your extra changes.

comment:33 Changed 6 years ago by 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.

comment:34 follow-up: Changed 6 years ago by 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

comment:35 in reply to: ↑ 34 ; follow-up: Changed 6 years ago by 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?

comment:36 in reply to: ↑ 35 Changed 6 years ago by jdemeyer

Replying to pbruin:

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

You're right, I fixed them.

comment:37 Changed 6 years ago by 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.

comment:38 Changed 6 years ago by jdemeyer

Added patch

  • sage/libs/pari/gen.pyx

    diff --git a/sage/libs/pari/gen.pyx b/sage/libs/pari/gen.pyx
    a b  
    18711871        pari_catch_sig_on()
    18721872        cdef int ret = gequal(a.g, t0.g)
    18731873        pari_catch_sig_off()
    1874         return bool(ret)
     1874        return ret != 0
    18751875
    18761876    def gequal0(gen a):
    18771877        r"""
     
    18931893        pari_catch_sig_on()
    18941894        cdef int ret = gequal0(a.g)
    18951895        pari_catch_sig_off()
    1896         return bool(ret)
     1896        return ret != 0
    18971897
    18981898    def gequal_long(gen a, long b):
    18991899        r"""
     
    19201920        pari_catch_sig_on()
    19211921        cdef int ret = gequalsg(b, a.g)
    19221922        pari_catch_sig_off()
    1923         return bool(ret)
     1923        return ret != 0
    19241924   
    19251925
    19261926    ###########################################
     
    19621962        pari_catch_sig_on()
    19631963        cdef long t = signe(gisprime(self.g, flag))
    19641964        P.clear_stack()
    1965         return bool(t)
     1965        return t != 0
    19661966
    19671967    def qfbhclassno(gen n):
    19681968        r"""
     
    20412041        pari_catch_sig_on()
    20422042        cdef long t = ispseudoprime(self.g, flag)
    20432043        pari_catch_sig_off()
    2044         return bool(t)
     2044        return t != 0
    20452045
    20462046    def ispower(gen self, k=None):
    20472047        r"""
     
    32093209            [True, False, True, True, True, True, True, True, True, True]
    32103210        """
    32113211        pari_catch_sig_on()
    3212         b = bool(bittest(x.g, n))
     3212        cdef long b = bittest(x.g, n)
    32133213        pari_catch_sig_off()
    3214         return b
     3214        return b != 0
    32153215   
    32163216    def bitxor(gen x, y):
    32173217        """
     
    55415541
    55425542    def issquare(gen x, find_root=False):
    55435543        """
    5544         issquare(x,n): true(1) if x is a square, false(0) if not. If
    5545         find_root is given, also returns the exact square root if it was
    5546         computed.
    5547         """
    5548         cdef GEN G, t
     5544        issquare(x,n): ``True`` if x is a square, ``False`` if not. If
     5545        ``find_root`` is given, also returns the exact square root.
     5546        """
     5547        cdef GEN G
     5548        cdef long t
    55495549        cdef gen g
    55505550        pari_catch_sig_on()
    55515551        if find_root:
    5552             t = gissquareall(x.g, &G)
    5553             v = bool(P.new_gen_noclear(t))
    5554             if v:
    5555                 return v, P.new_gen(G)
     5552            t = itos(gissquareall(x.g, &G))
     5553            if t:
     5554                return True, P.new_gen(G)
    55565555            else:
    5557                 pari_catch_sig_off()
    5558                 return v, None
     5556                P.clear_stack()
     5557                return False, None
    55595558        else:
    5560             return P.new_gen(gissquare(x.g))
    5561 
     5559            t = itos(gissquare(x.g))
     5560            pari_catch_sig_off()
     5561            return t != 0
    55625562
    55635563    def issquarefree(gen self):
    55645564        """
     
    55705570            False
    55715571        """
    55725572        pari_catch_sig_on()
    5573         t = bool(issquarefree(self.g))
     5573        cdef long t = issquarefree(self.g)
    55745574        pari_catch_sig_off()
    5575         return t
     5575        return t != 0
    55765576
    55775577    def lcm(gen x, y):
    55785578        """
     
    62036203        """
    62046204        cdef gen t0 = objtogen(x)
    62056205        pari_catch_sig_on()
    6206         t = bool(oncurve(self.g, t0.g) == 1)
     6206        cdef int t = oncurve(self.g, t0.g)
    62076207        pari_catch_sig_off()
    6208         return t
     6208        return t != 0
    62096209
    62106210    def elllocalred(self, p):
    62116211        r"""
     
    80348034        non-constant polynomial, or False if f is reducible or constant.
    80358035        """
    80368036        pari_catch_sig_on()
    8037         return bool(self.new_gen(gisirreducible(self.g)))
    8038        
    8039        
     8037        cdef long t = itos(gisirreducible(self.g))
     8038        P.clear_stack()
     8039        return t != 0
     8040
    80408041    def pollead(self, v=-1):
    80418042        """
    80428043        self.pollead(v): leading coefficient of polynomial or series self,

Changed 6 years ago by jdemeyer

comment:39 Changed 6 years ago by pbruin

Excellent, I'm happy with the current state.

comment:40 Changed 6 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:41 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.13.beta5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.