Fix another "recursion depth exceeded" in memory deallocation for weak dictionaries

[nthiery]

See: #10963 and follow up for details

This is a follow up to #13394 #15069, and a blocker for #10963.

Depends on #15432

CC: @sagetrac-sage-combinat @vbraun @jdemeyer @simon-king-jena

Component: performance

Author: Nils Bruin

Branch/Commit: u/SimonKing/ticket/15506 @ 6147777

Reviewer: Simon King

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

[nbruin]

Branch: u/nbruin/ticket/15506

[nbruin]

comment:2

This should do the trick for WeakValueDictionary. Merge #15367 to get the same benefit for MonoDict and TripleDict.

Code that verifies the problem has been solved:

sage: class A: pass
sage: from sage.misc.weak_dict import WeakValueDictionary
sage: a=A(); prev=a;
sage: M=WeakValueDictionary()
sage: for i in range(10^3+10): newA = A(); M[newA] = prev; prev = newA
sage: del a

This used to fail, but with the code on this branch it works.

---

New commits:

[5de9c7c](https://github.com/sagemath/sagetrac-mirror/commit/5de9c7c)

trac 15506: ensure that WeakValueDictionary deletes entries via a list, so that we benefit from Python's trashcan

[nbruin]

Commit: 5de9c7c

[sagetrac-git]

Changed commit from 5de9c7c to e23ec99

[sagetrac-git]

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

[e23ec99](https://github.com/sagemath/sagetrac-mirror/commit/e23ec99)	Merge branch 'ticket/15432' into ticket/15506
[4ac6866](https://github.com/sagemath/sagetrac-mirror/commit/4ac6866)	trac #15432: Code context manager in iterator via try/finally. This saves an entire class and some reference management.Z
[8b70d1d](https://github.com/sagemath/sagetrac-mirror/commit/8b70d1d)	trac #15432: also equip iteration context with a weak reference
[9bb9241](https://github.com/sagemath/sagetrac-mirror/commit/9bb9241)	trac #15432: use a callback class object holding a weak reference for sage.misc.weak_dict.WeakValueDictionary

[nbruin]

comment:4

Oops... while we're at it, we should merge #15432 as well. Do I need to merge #15367 into this branch as well or do we leave that separate?

[nthiery]

comment:5

That was quick :-) Thank you Nils!

Is there a reason for not putting the above code that verifies the solution as a doctest?

Other than that, what shall we do? Backport this ticket and its dependencies to mercurial, or move #10963 to git?

[nbruin]

comment:6

Replying to @nthiery:

Is there a reason for not putting the above code that verifies the solution as a doctest?

No, if you want to add a doctest, go ahead.

Backport this ticket and its dependencies to mercurial, or move #10963 to git?

I have no preference. Given that you'd have to backport #15367 as well, I think you'd better bite the bullet and go with git.

[nthiery]

comment:7

Replying to @nbruin:

Replying to @nthiery:

Is there a reason for not putting the above code that verifies the solution as a doctest?

No, if you want to add a doctest, go ahead.

Backport this ticket and its dependencies to mercurial, or move #10963 to git?

I have no preference. Given that you'd have to backport #15367 as well, I think you'd better bite the bullet and go with git.

I am fine with both, as long as it goes quickly. Volker, Jeroen, what do you think from a release management point of view?

[jdemeyer]

comment:8

I don't see a good reason to force this ticket in Sage 5.13. So it should not be a blocker and should be postponed to Sage 6.0 which means git.

[vbraun]

comment:12

can we get this reviewed? ;-)

[simon-king-jena]

comment:13

Replying to @vbraun:

can we get this reviewed? ;-)

I suppose this is independent of the patch:

File "src/sage/dev/sagedev.py", line 89, in sage.dev.sagedev.SageDev
Failed example:
    dev._sagedev
Exception raised:
    Traceback (most recent call last):
      File "/tmp/tmpo1ll9a-sage-git-temp-15506/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
        self.execute(example, compiled, test.globs)
      File "/tmp/tmpo1ll9a-sage-git-temp-15506/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute
        exec compiled in globs
      File "<doctest sage.dev.sagedev.SageDev[0]>", line 1, in <module>
        dev._sagedev
      File "lazy_import.pyx", line 312, in sage.misc.lazy_import.LazyImport.__getattr__ (sage/misc/lazy_import.c:2402)
      File "lazy_import.pyx", line 248, in sage.misc.lazy_import.LazyImport._get_object (sage/misc/lazy_import.c:1885)
      File "/tmp/tmpo1ll9a-sage-git-temp-15506/local/lib/python2.7/site-packages/sage/dev/sagedev_wrapper.py", line 250, in <module>
        dev = SageDevWrapper(SageDev())
      File "/tmp/tmpo1ll9a-sage-git-temp-15506/local/lib/python2.7/site-packages/sage/dev/sagedev.py", line 171, in __init__
        self.__branch_to_ticket = SavingDict(ticket_file)
      File "/tmp/tmpo1ll9a-sage-git-temp-15506/local/lib/python2.7/site-packages/sage/dev/saving_dict.py", line 116, in __init__
        self._write()
      File "/tmp/tmpo1ll9a-sage-git-temp-15506/local/lib/python2.7/site-packages/sage/dev/saving_dict.py", line 236, in _write
        assert os.path.abspath(self._filename).startswith(SAGE_TMP), error
    AssertionError: write attempt to a saving_dict in a doctest

[simon-king-jena]

comment:14

Is it really needed to additionally import this during startup:

+New:
+    sage.combinat.binary_recurrence_sequences
+    sage.libs.pari.handle_error
+    sage.misc.weak_dict

I am particularly talking about binary recurrence sequences.

[simon-king-jena]

comment:15

Has this really been introduced by this branch:

    0015-Trac-14320-More-doctests-from-the-book-Calcul-math-m.patch:37 +    sage: R100 = RealField(100) # précision : 100 bits.$
    0015-Trac-14320-More-doctests-from-the-book-Calcul-math-m.patch:43 +    sage: Rdefaut = RealField()  # précision par défaut de 53 bits$
    0015-Trac-14320-More-doctests-from-the-book-Calcul-math-m.patch:64 +    sage: x = 1.0         # x appartient à RealField()$
    0015-Trac-14320-More-doctests-from-the-book-Calcul-math-m.patch:65 +    sage: x = 0.1e+1      # idem : x appartient à RealField()$
    0015-Trac-14320-More-doctests-from-the-book-Calcul-math-m.patch:67 +    sage: x = RDF(1)      # x est un flottant double précision machine$
    0015-Trac-14320-More-doctests-from-the-book-Calcul-math-m.patch:68 +    sage: x = RDF(1.)     # idem : x est un flottant double précision$
    0015-Trac-14320-More-doctests-from-the-book-Calcul-math-m.patch:72 +    sage: x = R(1)        # x est un flottant de précision 20 bits$

Or is this from #14320?

[nbruin]

comment:16

Concerning additional imports and Calcul-math things:

None of that is directly effected by commits on this ticket, so it has to from the state of "master" on which this branch is based.

This ticket is only meant to change weak_dict.pyx and does not introduce any import statements there. Feel free to use the commits here to build a new branch based on a different tree if there are things in the way (note that #15432 has been merged in the branch here; without it there's only one commit here)

[simon-king-jena]

comment:17

Replying to @nbruin:

Concerning additional imports and Calcul-math things:

None of that is directly effected by commits on this ticket, so it has to from the state of "master" on which this branch is based.

OK, so, it is a bug in the plugins.

This ticket is only meant to change weak_dict.pyx and does not introduce any import statements there. Feel free to use the commits here to build a new branch based on a different tree if there are things in the way (note that #15432 has been merged in the branch here; without it there's only one commit here)

And now I am really confused.

In #15432, you introduce a weak reference from the callback to the weak value dictionary. Namely, on #15432, you point out that when passing the weak value dictionary to the callback via a closure then there are examples requiring many garbage collections to clear a weak value dictionary.

Now, you revert this change. Can you explain why you did so? Doesn't this re-introduce the problem that you fixed in #15432? If not: Why not? And why did you merge #15432 into this branch? What is left from #15432 in the HEAD of this branch?

[simon-king-jena]

comment:18

Hm. I just tested that the problematic behaviour (namely: Numerous garbage collection cycles required to clear the dict) does not occur with your branch. Could it perhaps be the case that I was (again) reading in a wrong way the diff shown by trac?

[nbruin]

comment:19

Replying to @simon-king-jena:

And why did you merge #15432 into this branch?

I figured that this was the new way to express a "dependency" on another ticket. It results in the branch I would have ended up with if I had started this ticket based on the branch there.

What is left from #15432 in the HEAD of this branch?

Everything, I think. I really just merged and it did so without conflict. Certainly all the commits listed at #15432 show up in the history here.

[simon-king-jena]

comment:20

Then perhaps I was misreading what trac showed me as diff.

I now took #15432, merged with master, and compare it with the branch from here, merged with master.

These are the differences I see with git diff ticket/15432 ticket/15506:

• You put certain to-be-deleted things into tuples, in order to use Python's trashcan.
• You remove the _IterationContext and replace it by cdef methods. So, instead of a context, you have try: self._enter_iter() ... finally: self._exit_iter(). I suppose that's for speed.

So, are these the changes I have to review here?

Best regards,
Simon

[nbruin]

comment:21

Replying to @simon-king-jena:

These are the differences I see with git diff ticket/15432 ticket/15506:

• You put certain to-be-deleted things into tuples, in order to use Python's trashcan.

Correct (isn't it a list rather than a tuple? Doesn't matter for our purposes, though).

• You remove the _IterationContext and replace it by cdef methods. So, instead of a context, you have try: self._enter_iter() ... finally: self._exit_iter(). I suppose that's for speed.

That's from #15432. It's more than speed: it also saves us from having to keep a weakened reference in the IterationContext, so it makes it easier to avoid circular references. I was actually surprised to see the complication that a context produced here.

In addition to these changes, #15432 also introduces an WeakKeyDictionary eraser class to make it possible to keep a weak reference (and avoid circular references).

I'd recommend just reviewing all of this here and be done with it (unless you feel any of this is controversial of course)

[vbraun]

comment:22

Simon, are you still reviewing this and #15432? The list of commits in question is https://github.com/sagemath/sagetrac-mirror/commits/u%2Fnbruin%2Fticket%2F15506&qt=range&q=develop..u%2Fnbruin%2Fticket%2F15506

[vbraun]

Dependencies: #15432

[vbraun]

Author: Nils Bruin

[simon-king-jena]

comment:23

Since #15432 is a dependency, I'll review this first. I am building the #15432-branch right now (after merging the develop branch).

[simon-king-jena]

comment:24

Am I right that I don't need to push a merge with my review-commit from #15432, since there is no merge conflict?

[vbraun]

comment:25

Yes, if there is no conflict then you don't have to merge.

[simon-king-jena]

Reviewer: Simon King

[simon-king-jena]

Changed branch from u/nbruin/ticket/15506 to u/SimonKing/ticket/15506

[simon-king-jena]

Changed commit from e23ec99 to 6147777

[simon-king-jena]

comment:26

I have added the example from commit:2 as a doc test (otherwise the fix wouldn't be tested against).

All tests pass (including the new one), and the code makes sense. I only wonder if we can use Python's trashcan in a different more efficient way (such as to avoid the creation of a list of length two during deletion of a dictionary item). But I think this ticket is about fixing a bug in the first place, and if we see the need for yet more efficiency, we can open another ticket.

I.e.: Positive review.

[nthiery]

comment:27

Yeah, that's a nice Chrismas present :-) Thanks Simon, thanks Nils!