Open nbruin opened 12 years ago
I found: Applying the function ringlist
decreases the ref counter of currRing
, while gwalk
increases the counter.
Since the number of references by Sage objects does not change, this is asking for trouble, I suppose.
Anyway. I'd really appreciate if someone could find a copy of the old patch version. I think the new one is worse, and I simply do not have the time to work on it now.
I haven't looked at this ticket, but could you also check that #12188 is resolved, it looks related.
Replying to @jdemeyer:
I haven't looked at this ticket, but could you also check that #12188 is resolved, it looks related.
It certainly looks related. But it isn't resolved with the patches from here.
Replying to @simon-king-jena:
Replying to @nbruin:
We have:
def __dealloc__(self): celement_destruct(&self.x, get_cparent((<Polynomial_template>self)._parent))
and for us:
get_cparent(parent) == <ntl_ZZ_pEContext_class>(parent._modulus)
The
_parent
attribute is a cython slot.Interestingly, there is no complaint about a missing attribute
_parent
. It is_modulus
that is missing.However, it holds a reference to a python-managed object, so I think cython ensures it's properly taken into account in GC cycle counting. But that would suggest to me python could clear this slot to break cycles! So in that case,
Polynomial_template
is never safe. It could be I'm wrong, however.I think you are right. The
__dealloc__
ofPolynomial_template
is unsafe, unless polynomial rings will stay in memory forever. But I'd love to hear that we are wrong, because otherwise each polynomial would need a pointer to the c-data expected to be returned byget_cparent((<Polynomial_template>self)._parent)
, and we'd need to take into account reference counting for the c-parent during creation and deletion of polynomials.Or perhaps there is a way out. We have a polynomial ring R and we have some elements a,b,c,... Each element points to R, and R points to some of its elements, namely to its generators. The problem is that deallocation of the elements is only possible as long as R is alive.
If we'd manually incref R upon creation of an element x, decrefing R when x gets deallocated, then we would ensure that R will survive until the last of its elements is deleted. Or would that mean that the elements will survive as well, because of the reference from R to its generators? Edit: Yes it would.
FYI, the cdefed pointer _parent stuff was added in #12313. Have a look at #12313 comment:13
Replying to @jpflori:
FYI, the cdefed pointer _parent stuff was added in #12313. Have a look at #12313 comment:13
Oh boy. So, do we have another circular dependency, meaning that this ticket depends on #12313? Perhaps we should apply Python's cyclic garbage collector on my trac tickets :(
Anyway, I am currently unable to do any programming, since I very urgently have a manuscript to write.
Replying to @simon-king-jena:
Replying to @jpflori:
FYI, the cdefed pointer _parent stuff was added in #12313. Have a look at #12313 comment:13
Oh boy. So, do we have another circular dependency, meaning that this ticket depends on #12313? Perhaps we should apply Python's cyclic garbage collector on my trac tickets :(
Does #12313 depends on this ticket? I see Jeroen recently put it as a dependency there but with no explanation. I've now quite read everything here, but it still looks mysterious to me why this was done. Any explanation welcomed :)
Trying an explanation:
If I am not mistaken, #715 plus #11521 in these versions have a positive review, without #13447.
Now, why did I put #13447 as an explicit reference at #12313? I guess that is because (1) I thought that #13447 is close to being fixed (I was mistaken...) and (2) the patchbot got confused by the circular dependency #715 <-> #11521.
But who knows. I am currently not really in the condition to do coding.
Description changed:
---
+++
@@ -2,8 +2,4 @@
The present work-around is to permanently store references to these upon creation, thus preventing collection. It would be nice if we could properly solve the problem (or at least establish that the problem is specific to `bsd.math`)
-**Apply**
-
-#13145, #715, #11521, and then [attachment:trac_13447-sanitise_ring_refcount.patch
-
-**Merge together with** #715, #11521
+**Apply** [attachment: trac_13447-sanitise_ring_refcount.patch](https://github.com/sagemath/sage-prod/files/10656332/trac_13447-sanitise_ring_refcount.patch.gz)
Hi!
What's the status of this patch? It's at the bottom of my dependency list for category patches :-)
Cheers, Nicolas
Replying to @nthiery:
What's the status of this patch? It's at the bottom of my dependency list for category patches :-)
IIRC, it was found that part of the problem was an upstream bug, that got fixed. And we meanwhile have a weak cache for polynomial rings. Hence, the original problem seems to be solved.
However, we may see whether it makes sense to use the existing reference counter from Singular, rather than relying on our custom reference counter. It might be conceptually better, though not necessarily more stable.
What do the other participants of this ticket think?
If the leak is now fixed, we could or even should just add some doctest proving it here, and open another ticket for using the singular ref system rather than ours.
Replying to @simon-king-jena:
However, we may see whether it makes sense to use the existing reference counter from Singular, rather than relying on our custom reference counter. It might be conceptually better, though not necessarily more stable.
I think it's a little more than just conceptual. Some rings may be created by direct library calls from sage. Other rings may be generated internally in libsingular. These rings can get mixed up, meaning that a sage created ring might end up being referenced only directly by some internal libsingular data structure and rings created internally to libsingular might end up being referenced by sage.
For reliable, non-leaking memory management you'll have to use the same refcounter in such a situation.
In libecl a different approach is taken: Every lisp object referenced from sage is referenced via a python proxy object that creates a binding to the referenced object in lisp, to prevent garbage collection. The deallocation routine for the proxy includes removal of the lisp binding. We could do that too, but last time it seemed we were relatively close to deciphering libsingular's conventions for handling its refcount.
Replying to @nbruin:
Replying to @simon-king-jena:
However, we may see whether it makes sense to use the existing reference counter from Singular, rather than relying on our custom reference counter. It might be conceptually better, though not necessarily more stable.
I think it's a little more than just conceptual. Some rings may be created by direct library calls from sage. Other rings may be generated internally in libsingular. These rings can get mixed up,
I don't think so.
According to Hans Schönemann, the internal refcount is only relevant in the Singular user interface. One could argue that libsingular replaces the Singular's user interface and should thus use the same refcounting than the user interface. However, internal calls in Singular will not change the refcount.
For reliable, non-leaking memory management you'll have to use the same refcounter in such a situation.
See above: The refcounter is not used internally in Singular (only for the user interface), I think.
Replying to @simon-king-jena:
One could argue that libsingular replaces the Singular's user interface...
To be precise: Our use of libsingular for constructing polynomial rings in Sage could be considered as something like the Singular user interface.
Replying to @simon-king-jena:
To be precise: Our use of libsingular for constructing polynomial rings in Sage could be considered as something like the Singular user interface.
I haven't looked at the code in a long time, but I know that at the time, I noticed that we DO call into the interpreter, at the very least in the doctests that test something about "functions" in singular.
I also recall that in some of the noncommutative stuff, singular goes off and creates a bunch of polynomial rings, in ways that seemed to me equivalent to what happens in the singular interpreter.
Unsurprisingly, those were the areas where we got problems when we started messing with the code.
Replying to @jpflori:
If the leak is now fixed, we could or even should just add some doctest proving it here, and open another ticket for using the singular ref system rather than ours.
It's not fixed. See sage/rings/polynomial/multi_polynomial_libsingular.pyx:369 libsingular multivariate polynomial rings are still nailed in memory.
So what shall we do?
Would it be reasonable, or not, to consider that #12876 does not depend on this guy?
Cheers, Nicolas
From what I read, #13447 was added because the ticket depended on #11521 which was though to depend on #13447. But in the end it was not the case (#11521 is merged now), so just remove it and get your ticket merged!
Replying to @jpflori:
From what I read, #13447 was added because the ticket depended on #11521 which was though to depend on #13447. But in the end it was not the case (#11521 is merged now), so just remove it and get your ticket merged!
Hey, that's excellent news! Thanks for the quick overview. I'll post a rebased and retested patch for #12876 shortly.
I just stumbled into to this in sage/libs/singular/function.pyx:949 in to_python:
elif rtyp == POLY_CMD:
#FIXME
res_poly = MPolynomial_libsingular(self._sage_ring)
res_poly._poly = <poly*>to_convert.data
to_convert.data = NULL
#prevent it getting free, when cleaning the leftv
return res_poly
this looks like the simple transfer of ownership of a reference here, but if some of the comments on this ticket quoting Schoenemann are correct and Singular indeed has a mix of refcounted and non-refcounted uses (depending on whether objects are actively interfaced in the interpreter or not) then this step might need attention: the leftv arriving here almost certainly is coming from the interpreter (via SingularFunction) and the res_poly object possibly shouldn't be considered as such.
Any new attempt at resolving this ticket should probably look into this bit of code too.
Should we have a look how much of the issues tracked here are now fixed by #18905?
I still think we should switch to use Singular's c-slot for refcounting. What we currently do: Create a python object from a libsingular ring*
and put it into a Python dictionary, where the number of references is stored. Wouldn't it be a lot faster to store the number of references in a c-slot?
If we use it, then I still think it makes sense to adopt Singular's convention on that c-slot: It counts the number of references minus one.
My suggestion: For testing, I create a branch based on #18905 that uses both ways of refcounting in parallel, asserting consistency. If that passes doctests, then we can safely remove the old slow refcounting system.
Replying to @simon-king-jena:
If we use it, then I still think it makes sense to adopt Singular's convention on that c-slot: It counts the number of references minus one.
OTOH, it really seems awkward: A fresh ring that we get out of libsingular will have .ref==0
. Thus, it is supposed to have a reference already. But there is no reference yet.
Something else: Currently, each polynomial constitutes a reference to the libsingular ring*
. But I think it is not the job of polynomials to care about managing ring references. Only Sage's polynomial rings should care.
If you have a better way of keeping track of the libsingular ring's then that would be great.
Afaik the reason for keeping a reference to the ring in MPolynomial_libsingular
is efficiency, basically every libsingular call also needs the ring as argument so you want to avoid the extra indirection trough MPolynomialRing_libsingular
.
Replying to @vbraun:
If you have a better way of keeping track of the libsingular ring's then that would be great.
Afaik the reason for keeping a reference to the ring in
MPolynomial_libsingular
is efficiency, basically every libsingular call also needs the ring as argument so you want to avoid the extra indirection troughMPolynomialRing_libsingular
.
Yes, that shortcut still is reasonable and shouldn't be changed. However, there should be no need to take the time and increase the reference count.
Replying to @simon-king-jena:
Yes, that shortcut still is reasonable and shouldn't be changed. However, there should be no need to take the time and increase the reference count.
... because we also have the polynomial ring that keeps a (counted) reference to the libsingular ring.
If I understood correctly, singular functions are supposed to leave the .ref-field alone, unless a ring in the interpreter is concerned. However, I found that using the singular_function
"ringlist" does decrease the reference count for the current ring. That's annoying.
Could it in fact be an artefact of how singular_function
is implemented? If I recall correctly ringlist(R)
is a bit tricky: It should return a list defined in the current ring, but with data defining R. So, perhaps we are somehow messing up currRing
versus the ring that is given as argument.
And then of course the question is under what circumstances it occurs. In the doctests of sage.libs.singular, ringlist
was the only function exhibiting such behaviour. Is it because its argument is a ring? Are there other kernel functions that may change the reference count? Are there library functions that can change the reference count? I think that's highly likely, since there are functions returning a ring that was created inside of the function.
I am trying to revive this ticket.
In a branch that I am currently testing, I change the .ref
field of Singular's ring
struct whenever Sage's ring refcount is operating, and assert that always both refcounts are consistent.
However, in the following example
sage: R.<x,y,z> = GF(3)[]
sage: I = R*R.gens()
sage: I.groebner_basis()
I find that Sage counts 8 references for some ring, but Singular counts 9 references for the same ring. Perhaps Singular is increasing the refcount internally and isn't resetting it, but I need to investigate it.
I found two spots in which the ref counting currently is not consequently done:
SingularFunction.__init__
: In some cases it artificially creates a ring and sets .ref = 1
, but ignores it in Sage's own refcounting.call_function
: When it changes currRingHdl
from the previously used to the current ring, it modifies .ref
but ignores Sage's own refcounting.So, that's where Singular's and Sage's ring refcounts get out of sync.
It turns out that my_awesome_sage_ring
created in SingularFunction.__init__
gives a core dump when being collected. So, there is something fundamentally wrong here.
Replying to @simon-king-jena:
It turns out that
my_awesome_sage_ring
created inSingularFunction.__init__
gives a core dump when being collected. So, there is something fundamentally wrong here.
If I understand correctly, my_awesome_sage_ring
is just some ring that is there to make Singular happy, although it is defunct and cannot be deleted. So, in the current code, its ref count in Singular is increased in order to prevent it from being deleted.
Three potential solutions: Either create a fully fledged ring that can be collected. Or reference it twice, so that it will stay in memory till the Sage session ends (that's what is currently happening). Or find a cleaner solution.
Replying to @simon-king-jena:
Or find a cleaner solution.
Instead of creating a defunct ring, one could use currRing
. That is possible because even directly after starting sage currRing
is available.
Meanwhile I believe that the approach to use libsingular's ring->ref
counter to count ring references will not work. As it turns out, some Singular functions do change the value stored in ->ref
, some don't. Therefore, Sage shouldn't mess with it.
OTOH, the old implementation of refcounting is quite inefficient: Given a ring*
, create a RingWrap, use it as a dictionary key in a defaultdict(int)
that counts the references --- and the creation (and subsequent deletion) of a RingWrap occurs each time a ring*
gets referenced or dereferenced!
If r
is a ring*
for which we want to count references, it would be an improvement to simply use <long>r
as key of the above-mentioned defaultdict(int)
. After all, comparison of the RingWrap of r
would also just rely on <long>r
. So, that approach would be better than the current implementation, because it avoids the creation and deletion of a python wrapper.
But somehow I would find it better to equip MPolynomialRing_libsingular
and all other libsingular wrappers with a new slot cdef int *_ring_ref
. When a new ring is created, the corresponding _ring_ref
would get allocated with a single int. If two different Sage objects wrap the same ring*
then they would also share the same _ring_ref
pointer. And the pointer would be passed as an argument to singular_ring_ref
and singular_ring_delete
, where the int being pointed at would be incremented or decremented, thus counting the number of references.
So, instead of a central defaultdict(int)
storing all reference counts, there would for each ring be a pointer to an int. I implemented it. For debugging, I currently have BOTH the old and the new refcount in parallel and test whether they are consistent. It turns out that they are!
Nonetheless I get segfaults and errors in the doctests, but actually not very many:
sage -t src/sage/rings/polynomial/plural.pyx # Killed due to segmentation fault
sage -t src/sage/rings/polynomial/multi_polynomial_ideal.py # Killed due to segmentation fault
sage -t src/sage/libs/singular/groebner_strategy.pyx # Killed due to segmentation fault
sage -t src/sage/libs/singular/function.pyx # 4 doctests failed
sage -t src/sage/tests/cmdline.py # 1 doctest failed
sage -t src/sage/schemes/curves/curve.py # 1 doctest failed
sage -t src/sage/schemes/curves/affine_curve.py # 1 doctest failed
So, I am confident that the new approach will soon work, and I am also confident that it will be faster than the old approach. But how could it be measured? Ring refcounting also happens in MPolynomial_libsingular
, not only in MPolynomialRing_libsingular
. Hence, a benchmark involving the creation and deletion of many polynomials would probably reveal a speedup.
The commit that I just posted implements the new approach to refcounting:
ring *_ring
), and in addition an int-pointer for the refcount of that ring (`int *_ring_ref)If self
is created using a new ring r
, then we would have
self._ring_ref = <int*>sig_calloc(1, sizeof(int))
self._ring = singular_ring_reference(r, self._ring_ref)
If self
is created using a ring that is referenced by other
, then we would have
self._ring_ref = other._ring_ref
self._ring = singular_ring_reference(other._ring, self._ring_ref)
For deallocation, one does
singular_ring_delete(self._ring, self._ring_ref)
Note that it is not needed to do sig_free(self._ring_ref)
, because this is done inside of singular_ring_delete(self._ring, self._ring_ref)
when there remain no references to self._ring
.
In the commit, I am not removing the old refcounting approach. This is for testing purposes: I assert that the old and the new refcount coincide, to demonstrate that the new approach works.
Next step will be to remove the old refcount, and to find a way to replace the doctests for the old refcount.
Question: Would it make sense to add a function that would automatically test that all rings created after "from sage import all" are properly deleted when Sage is shut down?
New commits:
d6a3d48 | trac13447: new refcount implementation for libsingular rings |
Commit: d6a3d48
Changed author from Nils Bruin, Simon King to Simon King
Changed upstream from None of the above - read trac for reasoning. to none
Changed work issues from Understand why sometimes new_RingWrap
needs an incref and sometimes not to none
Changed reviewer from Simon King to none
PS: So far the ultimate goal to ensure that more rings are collected is not addressed.
Without the branch:
sage: from sage.libs.singular.groebner_strategy import NCGroebnerStrategy ## line 333 ##
....: A.<x,y,z> = FreeAlgebra(QQ, 3) ## line 334 ##
....: H.<x,y,z> = A.g_algebra({y*x:x*y-z, z*x:x*z+2*x, z*y:y*z-2*y}) ## line 335 ##
....: I = H.ideal([y^2, x^2, z^2-H.one()]) ## line 336 ##
....: strat = NCGroebnerStrategy(I) #random ## line 337 ##
....: del strat, I, x,y,z,H, A
....: import gc
....: gc.collect()
....:
155
sage: sum(sage.libs.singular.ring.ring_refcount_dict.values())
17
With the branch:
sage: from sage.libs.singular.groebner_strategy import NCGroebnerStrategy ## line 333 ##
....: A.<x,y,z> = FreeAlgebra(QQ, 3) ## line 334 ##
....: H.<x,y,z> = A.g_algebra({y*x:x*y-z, z*x:x*z+2*x, z*y:y*z-2*y}) ## line 335 ##
....: I = H.ideal([y^2, x^2, z^2-H.one()]) ## line 336 ##
....: strat = NCGroebnerStrategy(I) #random ## line 337 ##
....: del strat, I, x,y,z,H, A
....: import gc
....: gc.collect()
....:
175
sage: sum(sage.libs.singular.ring.ring_refcount_dict.values())
17
But that's not a surprise since the first commit changes the mechanism of the refcount, but not the number of references.
I inserted print statements whenever certain rings/algebras and elements are created or deallocated, and found that in the following code
sage: from sage.libs.singular.groebner_strategy import NCGroebnerStrategy
....: A.<x,y,z> = FreeAlgebra(QQ, 3)
....: H.<x,y,z> = A.g_algebra({y*x:x*y-z, z*x:x*z+2*x, z*y:y*z-2*y})
....: I = H.ideal([y^2, x^2, z^2-H.one()])
....: strat = NCGroebnerStrategy(I)
....: del strat, I, x,y,z,H, A
....: import gc
....: gc.collect()
the G-Algebra H
is garbage collected and its underlying libsingular ring is properly deleted. However, the free algebra is not garbage collected, and the polynomial ring involved in the creation of the free algebra isn't garbage collected either.
So, there is a memory leak, but I suppose it is because of improper strong references in Sage's coercion system, not because of references to libsingular rings.
Here is an assessment for the time needed to increment or decrement the reference count in the various approaches. I am using
from cpython.object cimport Py_EQ, Py_NE
from cysignals.memory cimport sig_calloc, sig_free
from collections import defaultdict
refcount_dict = defaultdict(int)
cdef int total_refcount = 0
cdef class Wrap(object):
cdef void *p
def __hash__(self):
return <long>(self.p)
def __richcmp__(Wrap self, other, int op):
if not (op == Py_EQ or op == Py_NE):
return NotImplemented
if type(other) is not Wrap:
return op != Py_EQ
return (self.p == (<Wrap>other).p) == (op == Py_EQ)
cdef inline wrap(void *p):
cdef Wrap W = Wrap.__new__(Wrap)
W.p = p
return W
cdef inline void *incref1(void *p):
refcount_dict[wrap(p)] += 1
return p
cdef inline void decref1(void *p):
cdef Wrap W = wrap(p)
cdef int c = refcount_dict[W] - 1
if c == 0:
del refcount_dict[W]
else:
refcount_dict[W] = c
cdef inline void *incref2(void *p):
refcount_dict[<long>p] += 1
return p
cdef inline void decref2(void *p):
cdef int c = refcount_dict[<long>p] -1
if c == 0:
del refcount_dict[<long>p]
else:
refcount_dict[<long>p] = c
cdef inline void *incref3(void *p, int *count):
count[0] += 1
return p
cdef inline void decref3(void *p, int *count):
count[0] -= 1
cdef inline void *incref4(void *p, int *count):
global total_refcount
total_refcount += 1
count[0] += 1
return p
cdef inline void decref4(void *p, int *count):
global total_refcount
total_refcount -= 1
count[0] -= 1
cpdef test1(long x):
cdef int i
cdef void *X = <void *>x
for i in range(1000):
X = incref1(X)
decref1(X)
cpdef test2(long x):
cdef int i
cdef void *X = <void *>x
for i in range(1000):
X = incref1(X)
decref1(X)
cpdef test3(long x):
cdef int i
cdef int *Count = <int*>sig_calloc(1, sizeof(int))
cdef void *X = <void *>x
for i in range(1000):
X = incref3(X, Count)
decref3(X, Count)
sig_free(Count)
cpdef test4(long x):
cdef int i
cdef int *Count = <int*>sig_calloc(1, sizeof(int))
cdef void *X = <void *>x
for i in range(1000):
X = incref4(X, Count)
decref4(X, Count)
sig_free(Count)
and with that I get
sage: %timeit test1(123456)
1000 loops, best of 3: 362 µs per loop
sage: %timeit test2(123456)
1000 loops, best of 3: 366 µs per loop
sage: %timeit test3(123456)
The slowest run took 111.51 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 126 ns per loop
sage: %timeit test4(123456)
The slowest run took 46.28 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 129 ns per loop
Conclusion
sage.libs.singular.ring.ring_refcount_dict
I suppose we can afford 3ns loss per 1000 increments and decrements and thus will implement the fourth version of incref/decref. And then we can see if it has an effect on the speed of polynomial arithmetic.
Good news!
With plain Sage, one gets
sage: R.<x,y,z> = QQ[]
sage: %timeit p = 2*x^3+x*y*z-z^2*x^2
The slowest run took 83.44 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 10 µs per loop
whereas with the two commits of the current branch one gets
sage: R.<x,y,z> = QQ[]
sage: %timeit p = 2*x^3+x*y*z-z^2*x^2
The slowest run took 73.46 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 5.37 µs per loop
So, it would already make sense to use this. OTOH, the purpose of this ticket is not to speed-up polynomial arithmetic but to make multivariate polynomial rings collectable. So, I will next try and remove the strong cache for multivariate polynomial rings, and see what will then happen.
Since I have added ring refcounting not only for the ring itself but also for its elements, it could be that the new code is enough stable to survive deletion of polynomials ring without segfaulting. Keep fingers crossed!
Perhaps it would be better to make the libsingular and the other multivariate polynomial rings be separate tickets to have more granular changes as they are largely (completely?) independent. This already seems like a bigger ticket and the other change would likely be a bigger changeset as well.
From a quick look, your proposal seems good, but I would have to read it in more detail to confirm. It might also be good for someone who is more experienced with memory management to look at this, but I am willing to set this to a positive review once I do a more thorough code review.
Branch pushed to git repo; I updated commit sha1. New commits:
70c08b0 | trac13447: Remove the strong cache for multivariate polynomials |
Presently, #715 + #11521 help not permanently keeping parent in memory. In the process we uncovered a hard-but-consistently triggerable problem with the collection of
MPolynomialRing_libsingular
. We have only observed the problem onbsd.math.washington.edu
, MacOSX 10.6 on x86_64.The present work-around is to permanently store references to these upon creation, thus preventing collection. It would be nice if we could properly solve the problem (or at least establish that the problem is specific to
bsd.math
)Depends on #11521
CC: @simon-king-jena @malb @vbraun @gagern @robertwb @sagetrac-ylchapuy @jpflori @burcin
Component: memleak
Author: Simon King
Branch/Commit: public/make_libsingular_multivariate_polynomial_rings_collectable @
b4df239
Reviewer: Travis Scrimshaw
Issue created by migration from https://trac.sagemath.org/ticket/13447