Do not cache the result of is_Field externally

[simon-king-jena]

In #11900, a cache has been introduced to sage.rings.ring.is_Field, in order to speed things up. Unfortunately, that caused the following leak:

sage: p = 1
sage: import gc
sage: gc.collect()
662
sage: for i in range(100):
....:     p = next_prime(p)
....:     R = ZZ.quotient(p)
....:     t = R in Fields()
....:     _ = gc.collect()
....:     print len([X for X in gc.get_objects() if isinstance(X, sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic)]),
....:     
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

I think the cleanest solution is:

• deprecate is_Field
• instead, use an uncached function _is_Field
• in the sage tree, replace is_Field(R) by R in Fields()

Rationale:

is_Field(R) (or _is_Field(R)) will change R.category() into a sub-category of Fields(). But then, the next call to "R in Fields()" will be very fast. Hence, there is no reason (speed-wise) to cache is_Field. Actually, R in Fields() should be faster than is_Field(R) anyway, because of the cythonisation.

Depends on #11310
Depends on #12215
Depends on #11521
Depends on #12313
Depends on #13089
Depends on #12995

CC: @nbruin @jpflori

Component: memleak

Author: Simon King

Reviewer: Nils Bruin

Merged: sage-5.8.beta0

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

[simon-king-jena]

comment:1

Timings

I made some benchmarks, based on most tests from #11900 and one new test. This is on my laptop, hence the timings differ from the ones that I stated on #11900.

sage-5.2.rc0 plus the memleak patches #12969, #715, #12215, #11521, #12313

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 7.60 s, sys: 0.24 s, total: 7.85 s
Wall time: 8.00 s
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 6.03 s, sys: 0.21 s, total: 6.24 s
Wall time: 7.83 s
sage: def test(E):
....:     for p in prime_range(10000):
....:         if p != 389:
....:             G = E.change_ring(GF(p)).abelian_group()
....:
sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 31.59 s, sys: 0.21 s, total: 31.79 s
Wall time: 31.85 s
sage: %time for E in cremona_curves([11..100]): S = E.integral_points(both_signs=False)
CPU times: user 19.15 s, sys: 0.43 s, total: 19.58 s
Wall time: 20.13 s
sage: W.<z> = CyclotomicField(13)
sage: %time M = Matrix(W, 2, 3, [10^30*(1-z)^13, 1, 2, 3, 4, z]).echelon_form()
CPU times: user 3.81 s, sys: 0.01 s, total: 3.82 s
Wall time: 3.82 s

Here is a new test. First, with "cold" cache:

sage: L = [ZZ.quotient(p) for p in prime_range(10000)]
sage: %time X = [R in Fields() for R in L]
CPU times: user 0.42 s, sys: 0.01 s, total: 0.43 s
Wall time: 0.44 s

And now with a "warm" cache:

sage: %timeit X = [R in Fields() for R in L]
625 loops, best of 3: 1.37 ms per loop

If one adds the tests from here, one gets:

age: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 7.46 s, sys: 0.33 s, total: 7.79 s
Wall time: 7.80 s
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 5.82 s, sys: 0.15 s, total: 5.97 s
Wall time: 6.12 s
sage: def test(E):
....:     for p in prime_range(10000):
....:         if p != 389:
....:             G = E.change_ring(GF(p)).abelian_group()
....:
sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 31.43 s, sys: 0.10 s, total: 31.52 s
Wall time: 31.58 s
sage: %time for E in cremona_curves([11..100]): S = E.integral_points(both_signs=False)
CPU times: user 19.04 s, sys: 0.17 s, total: 19.22 s
Wall time: 19.26 s
sage: W.<z> = CyclotomicField(13)
sage: %time M = Matrix(W, 2, 3, [10^30*(1-z)^13, 1, 2, 3, 4, z]).echelon_form()
CPU times: user 2.88 s, sys: 0.00 s, total: 2.89 s
Wall time: 2.90 s
sage: L = [ZZ.quotient(p) for p in prime_range(10000)]
sage: %time X = [R in Fields() for R in L]
CPU times: user 0.40 s, sys: 0.00 s, total: 0.41 s
Wall time: 0.41 s
sage: %timeit X = [R in Fields() for R in L]
625 loops, best of 3: 1.29 ms per loop

Hence, no test became slower, but some became clearly faster - in particular the one with echelon form computation. I think an echelon form computation was were Nils noticed the memory leak.

Fixing a memory leak

I just noticed that I forgot to add the following test to my patch. But anyway, a memory leak has been fixed that hadn't, before:

sage: import gc
sage: _ = gc.collect()
sage: len([X for X in gc.get_objects() if isinstance(X, sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic)])
1
sage: for i in prime_range(100):
....:     R = ZZ.quotient(i)
....:     t = R in Fields()
....:     
sage: _ = gc.collect()
sage: len([X for X in gc.get_objects() if isinstance(X, sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic)])
2

However, not all is good. There is still another leak left, quite likely due to coercion.

sage: for i in prime_range(100):
....:     R = ZZ.quotient(i)
....:     t = 1 + R.one()
....:     
sage: _ = gc.collect()
sage: len([X for X in gc.get_objects() if isinstance(X, sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic)])
26

My suggestion is to deal with the remaining leak on a different ticket. But first I need to add one test to my patch...

[simon-king-jena]

Author: Simon King

[simon-king-jena]

comment:2

The doc test is added.

I did not run the full test suite yet. But I think I'll already change it into "needs review".

[simon-king-jena]

comment:3

Oops, I think that the new doc test will only work with the other memleak fixes. If this turns out to be correct, I will need to update the dependencies.

[simon-king-jena]

comment:4

I don't know what the patchbot is trying to do. According to the logs, it looks like sage won't even start. But it does for me! Admittedly, I work with a prerelease of 5.2 (not 5.3).

[simon-king-jena]

Dependencies: #11310, #715, #12215, #11521, #12313

[simon-king-jena]

comment:5

The patch would not apply to sage-5.3.beta2, because of #11310. Since I worked on top of the other memleak fixes, I name them as dependencies as well.

[simon-king-jena]

Work Issues: Cope with import changes in sage/schemes

[simon-king-jena]

comment:6

Too bad. The patch bot is right: The current patch won't work with sage-5.3.beta2, there is an import error at startup. It is in sage/schemes --- again.

[simon-king-jena]

comment:7

The reason is #13089.

[simon-king-jena]

Changed dependencies from #11310, #715, #12215, #11521, #12313 to #11310, #715, #12215, #11521, #12313, #13089

[simon-king-jena]

Changed work issues from Cope with import changes in sage/schemes to none

[simon-king-jena]

comment:8

The patch is rebased with respect to #13089. With the stated dependencies on top of sage-5.3.beta2, sage does start. So, I hope that the patchbot can work fine...

[simon-king-jena]

comment:9

#715 and #11521 are mutually dependent, but #715 needs to be applied first. By consequence, the patchbot got confused when I stated both as dependency here. Hope it works now...

[simon-king-jena]

Changed dependencies from #11310, #715, #12215, #11521, #12313, #13089 to #11310, #12215, #11521, #12313, #13089

[simon-king-jena]

comment:10

The patchbot reports

sage -t  -force_lib devel/sage-13370/sage/rings/padics/padic_base_leaves.py # 1 doctests failed
sage -t  -force_lib devel/sage-13370/sage/rings/polynomial/infinite_polynomial_element.py # Killed/crashed

I do not get that crash, but I do get the error in padic_base_leaves.py. The strange thing is:

sage: K = Qp(17)
sage: S = Zp(17,40)
sage: K.has_coerce_map_from(S)
True

but in the doctest the last line returns "False".

In other words, there is yet again a case where the absence of a coerce map is cached when this is wrong. I really thought I had fixed that problem in #12969!!

[simon-king-jena]

comment:11

Arrgh, it is even worse!

When I take the complete failing test, namely

            sage: K = Qp(17)
            sage: K(1) + 1 #indirect doctest
            2 + O(17^20)                                                                                                                                                                                  
            sage: K.has_coerce_map_from(ZZ)                                                                                                                                                               
            True                                                                                                                                                                                          
            sage: K.has_coerce_map_from(int)
            True
            sage: K.has_coerce_map_from(QQ)
            True
            sage: K.has_coerce_map_from(RR)
            False
            sage: K.has_coerce_map_from(Qp(7))
            False
            sage: K.has_coerce_map_from(Qp(17,40))
            False
            sage: K.has_coerce_map_from(Qp(17,10))
            True
            sage: K.has_coerce_map_from(Zp(17,40))
            True

then every answer is as expected. But when I run the same thing as part of the test suit eof sage.rings.padic_base_leaves, then the last line returns "False".

Hence, there is a side effect from another test. And keep in mind that this side-effect results in wrongly caching the absence of a coercion, even though the patch only changes the syntax for detecting fields.

[simon-king-jena]

comment:12

It is worse than worse: According to the patchbot, the problem in padic_base_leaves also occurs with #12313, i.e., before applying #13370. But I do not get that error!

Hence: The patchbot finds a wrong coercion cache with #12313, which I only find with #12313. And the patchbot finds a segfault with #12313, that I do not find.

[simon-king-jena]

comment:13

I inserted some lines into sage.structure.parent that print type(S) and id(S) whenever the absence of a coercion gets cached. And I inserted a line into the failing test that prints type and id of the object that fails.

It turns out that by the test

sage: K.has_coerce_map_from(Qp(17,40))

in line 478 of sage/rings/padics/padic_base_leaves.py, the absence of a coercion gets cached for an object of type sage.rings.padics.padic_base_leaves.pAdicFieldCappedRelative_with_category under the address 79378272. However, a few lines below, when the test fails, the object at address 79378272 is of type sage.rings.padics.padic_base_leaves.pAdicRingCappedRelative_with_category (Ring, not Field!!)

Hence, it seems that the following happens: The absence of a coercion from Qp(17,40) to K is correctly cached. But because of all my weakref patches, Qp(17,40) gets garbage collected. For an unknown reason, the corresponding item in the coercion cache does not get removed, and by coincidence the old address of Qp(17,40) is now used for Zp(17,40). But since the coercion cache is now operating with the addresses of keys, it gets the wrong item. That would explain why the error is so difficult to reproduce.

If this is true, then we have to understand why the callback function of the weak reference to Qp(17,40) is not called as soon as Qp(17,40) gets garbage collected.

[simon-king-jena]

comment:14

My hope was that the new fixes in #715 and #12313 ("let the __delitem__ methods not only remove stuff from the buckets but also from the reference cache") would also fix the problem here. But unfortunately that isn't the case. And since the patch bot is currently not usable, I can not tell whether the meta-problem ("The patchbot finds the error already with #12313 but I don't, and the patchbot finds an additional error with #13370 but I don't.") persists.

[simon-king-jena]

comment:45

I am not sure if #13145 really fixed the problem, or it was just accidentally (these segfaults seem awfully flaky).

Anyway, I have updated the main patch at #715, avoiding a potential name conflict of attributes of Action and RingHomomorphism - just in case...

Kicking the patchbot now...

[simon-king-jena]

comment:46

No segfault this time. I am retrying without #13145.

[simon-king-jena]

Changed dependencies from #11310, #12215, #11521, #12313, #13089, #13145 to #11310, #12215, #11521, #12313, #13089

[simon-king-jena]

comment:47

Is there someone who'd review this?

[simon-king-jena]

Changed dependencies from #11310, #12215, #11521, #12313, #13089 to #11310, #12215, #11521, #12313, #13089, #12995

[simon-king-jena]

comment:48

Needs to be rebased on top of sage-5.7.beta2

[simon-king-jena]

comment:49

Patch is updated!

[nbruin]

comment:50

I'm all in favour of the idea of the patch. However, the bot seems to indicate there's still some work to do.

[simon-king-jena]

comment:51

Right. Polyhedron seems to be new, so that this rather old patch did not take care of it.

[simon-king-jena]

Attachment: trac13370_deprecate_is_field.patch.gz

Deprecate is_Field(R) in favour of R in Fields().

[simon-king-jena]

comment:52

I have updated the patch, and I hope it'll make the patchbot happy. At least, all tests in sage/geometry pass. Needs review!

[nbruin]

comment:53

Cool stuff! Works for me, so positive review. Note that in [comment:1] you also noted the issue that is now the topic of #14058.

[jdemeyer]

Reviewer: Nils Bruin

[nbruin]

comment:55

Something that struck me. With the current trick,

sage: R=ZZ.quo(7)
sage: %timeit R in Fields()

is going to be pretty efficient, because the category of R reflects it's a field after the first test. However,

sage: R=ZZ.quo(15)
sage: %timeit R in Fields()

probably isn't efficient (but it probably wasn't before either), because there's no way to register it's NOT a field in its category.

I recognize that frequently asking whether a field is indeed a field will happen a lot, whereas frequently confirming something is NOT a field will probably be considerably less common, so perhaps it's not a problem. It does reflect that this solution is accomplishing something quite different from just making is_Field efficient without external cache.

[jdemeyer]

Merged: sage-5.8.beta0

[jdemeyer]

comment:57

Please see #14158 for a blocker follow-up.