Sage: Ticket #13922: Avoid a regression in the creation of homsets
https://trac.sagemath.org/ticket/13922
<p>
By <a class="closed ticket" href="https://trac.sagemath.org/ticket/715" title="#715: defect: Parents probably not reclaimed due to too much caching (closed: fixed)">#715</a> and related tickets, one observes a dramatic regression in the following example.
</p>
<pre class="wiki">sage: p = polar_plot(lambda t: (100/(100+(t-pi/2)^8))*(2-sin(7*t)-cos(30*t)/2), -pi/4, 3*pi/2, color="red",plot_points=1000)
</pre><p>
First of all, it is very strange that the following homset is created several thousands of times:
</p>
<pre class="wiki">Set of Homomorphisms from Integer Ring to Real Interval Field with 64 bits of precision
</pre><p>
This also occurs <em>without</em> <a class="closed ticket" href="https://trac.sagemath.org/ticket/715" title="#715: defect: Parents probably not reclaimed due to too much caching (closed: fixed)">#715</a>. Hence, enabling garbage collection seems not to be to blame.
</p>
<p>
However, the <em>creation time</em> for the homsets increases clearly, which is shown by prun.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/13922
Trac 1.2Simon KingMon, 07 Jan 2013 14:37:31 GMT
https://trac.sagemath.org/ticket/13922#comment:1
https://trac.sagemath.org/ticket/13922#comment:1
<p>
PS: There is almost no regression in this example, if <a class="closed ticket" href="https://trac.sagemath.org/ticket/13014" title="#13014: enhancement: lcm for SR rationals (closed: fixed)">#13014</a> is reverted, as Jeroen reported on sage-devel. Still, both problems should be addressed:
</p>
<ol><li>The previously existing repeated creation of a homset.
</li><li>The new slowdown in the creation of homsets.
</li></ol>
TicketSimon KingMon, 07 Jan 2013 14:42:00 GMT
https://trac.sagemath.org/ticket/13922#comment:2
https://trac.sagemath.org/ticket/13922#comment:2
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/13014" title="#13014: enhancement: lcm for SR rationals (closed: fixed)">#13014</a> has to do with gcd/lcm, and apparently gcd is used quite a lot in this example, according to <a class="ext-link" href="http://trac.sagemath.org/sage_trac/ticket/715#comment:366"><span class="icon"></span>#715, comment:366</a> - WHY??
</p>
TicketVolker BraunMon, 07 Jan 2013 15:22:52 GMT
https://trac.sagemath.org/ticket/13922#comment:3
https://trac.sagemath.org/ticket/13922#comment:3
<p>
I take it that whenever you write <code>pi/2</code> we first see if that can be simplified to just the numerator. Which requires a gcd, and <a class="closed ticket" href="https://trac.sagemath.org/ticket/13014" title="#13014: enhancement: lcm for SR rationals (closed: fixed)">#13014</a> changed gcd of symbolics to be more expensive.
</p>
<p>
Really the example is very poor, a python function returning a symbolic expression. If you just had a symbolic function then the <code>fast_callable</code> trickery could do its job. Just leave out the <code>lambda t:</code> and it is >100 times faster!
</p>
<pre class="wiki">sage: var('t')
t
sage: %time p = polar_plot((100/(100+(t-pi/2)^8))*(2-sin(7*t)-cos(30*t)/2), -pi/4, 3*pi/2, color="red",plot_points=1000)
CPU times: user 0.04 s, sys: 0.00 s, total: 0.04 s
Wall time: 0.05 s
</pre>
TicketSimon KingMon, 07 Jan 2013 15:34:18 GMT
https://trac.sagemath.org/ticket/13922#comment:4
https://trac.sagemath.org/ticket/13922#comment:4
<p>
Indeed, without the lambda, only one set of morphisms is created, namely Set of Morphisms from Set of Python objects of type <code>'sage.ext.fast_eval.FastDoubleFunc'</code> to Symbolic Ring in Category of sets.
</p>
TicketSimon KingMon, 07 Jan 2013 15:41:20 GMT
https://trac.sagemath.org/ticket/13922#comment:5
https://trac.sagemath.org/ticket/13922#comment:5
<p>
I defined <code>f = lambda t: (100/(100+(t-pi/2)^8))*(2-sin(7*t)-cos(30*t)/2)</code> and evaluated it on both integers, rationals and symbolic constants. But alas, no repeated creation of the same homset occurs in the process.
</p>
<p>
So, why are the homsets not taken from cache when calling <code>polar_plot</code>? The same happens with <code>plot</code>, by the way.
</p>
TicketSimon KingMon, 07 Jan 2013 15:57:36 GMT
https://trac.sagemath.org/ticket/13922#comment:6
https://trac.sagemath.org/ticket/13922#comment:6
<p>
Even when setting the number of evaluation points to 3, one gets loads of homsets. So, evaluation is probably not the culprit.
</p>
TicketSimon KingMon, 07 Jan 2013 15:59:25 GMT
https://trac.sagemath.org/ticket/13922#comment:7
https://trac.sagemath.org/ticket/13922#comment:7
<p>
I tried to simplify the circumstances a bit (smaller number of evaluation points, no symbolic expression in the definition of the plot range. However,
</p>
<pre class="wiki">sage: t = var('t')
sage: f = lambda t: (100/(100+(t-pi/2)^8))*(2-sin(7*t)-cos(30*t)/2)
sage: p = plot(f, -4, 3,plot_points=3)
</pre><p>
is still nasty.
</p>
TicketVolker BraunMon, 07 Jan 2013 16:08:05 GMT
https://trac.sagemath.org/ticket/13922#comment:8
https://trac.sagemath.org/ticket/13922#comment:8
<p>
The plot is adaptive, so even if you specify 3 points it uses many more.
</p>
<p>
About the caching, is the problem that the cache gets deleted too quickly? Between two evaluations of the lambda there is nothing that holds a reference to the symbolic expression. So all coercion caches should be free to be garbage collected.
</p>
TicketSimon KingMon, 07 Jan 2013 16:20:37 GMT
https://trac.sagemath.org/ticket/13922#comment:9
https://trac.sagemath.org/ticket/13922#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13922#comment:8" title="Comment 8">vbraun</a>:
</p>
<blockquote class="citation">
<p>
About the caching, is the problem that the cache gets deleted too quickly?
</p>
</blockquote>
<p>
Have we been using weak references to cache homsets prior to <a class="closed ticket" href="https://trac.sagemath.org/ticket/715" title="#715: defect: Parents probably not reclaimed due to too much caching (closed: fixed)">#715</a>?
</p>
<blockquote class="citation">
<p>
Between two evaluations of the lambda there is nothing that holds a reference to the symbolic expression. So all coercion caches should be free to be garbage collected.
</p>
</blockquote>
<p>
Here is the problem:
</p>
<pre class="wiki">QQ.gcd(3.14159,2*3.14159)
</pre><p>
creates two times <code>Set of Homomorphisms from Integer Ring to Real Interval Field with 64 bits of precision in Category of euclidean domains</code>. So, no symbolics involved at this point.
</p>
TicketSimon KingMon, 07 Jan 2013 16:26:21 GMT
https://trac.sagemath.org/ticket/13922#comment:10
https://trac.sagemath.org/ticket/13922#comment:10
<p>
The cache of the Hom function seems not to be used, even though the Hom function is called. Namely, defining
</p>
<pre class="wiki">sage: H = Hom(ZZ, RealIntervalField(prec=64), category=EuclideanDomains())
</pre><p>
I still find that
</p>
<pre class="wiki">sage: QQ.gcd(3.14159,2*3.14159)
</pre><p>
creates two copies of H each time it is called. Odd.
</p>
TicketSimon KingMon, 07 Jan 2013 16:29:12 GMT
https://trac.sagemath.org/ticket/13922#comment:11
https://trac.sagemath.org/ticket/13922#comment:11
<p>
Got it!!!
</p>
<p>
<code>RealIntervalField(prec=64)</code> should be a unique parent, but it isn't! It is created in two different addresses in memory during QQ.gcd(3.14159,2*3.14159). So, apparently the <code>RealIntervalField</code> constructor is not called in <code>QQ.gcd</code>. That would be a clear bug.
</p>
TicketSimon KingMon, 07 Jan 2013 16:32:06 GMT
https://trac.sagemath.org/ticket/13922#comment:12
https://trac.sagemath.org/ticket/13922#comment:12
<p>
My apologies to whoever created <code>QQ.gcd</code>. It now seems that the coercion into <code>QQ</code> is to blame:
</p>
<pre class="wiki">sage: a = QQ(3.14159)
</pre><p>
internally creates a new copy of <code>RealIntervalField(prec=64)</code>, and hence a new homset.
</p>
TicketSimon KingMon, 07 Jan 2013 16:38:16 GMT
https://trac.sagemath.org/ticket/13922#comment:13
https://trac.sagemath.org/ticket/13922#comment:13
<p>
Look into <code>sage.rings.real_mpfi.RealIntervalFieldElement.simplest_rational</code>: It calls <code>RealIntervalField_class</code> directly, but should call the <code>RealField</code> constructor (or, if the overhead of calling a function matters, should look into the cache first).
</p>
TicketSimon KingMon, 07 Jan 2013 16:44:41 GMT
https://trac.sagemath.org/ticket/13922#comment:14
https://trac.sagemath.org/ticket/13922#comment:14
<p>
With the following patch, the homsets are taken from cache. I don't know about timings (calling overhead) yet.
</p>
<div class="wiki-code"><div xmlns="http://www.w3.org/1999/xhtml" class="diff">
<ul class="entries">
<li class="entry">
<h2>
<a>sage/rings/real_mpfi.pyx</a>
</h2>
<pre>diff --git a/sage/rings/real_mpfi.pyx b/sage/rings/real_mpfi.pyx</pre>
<table class="trac-diff inline" summary="Differences" cellspacing="0">
<colgroup><col class="lineno" /><col class="lineno" /><col class="content" /></colgroup>
<thead>
<tr>
<th title="File a/sage/rings/real_mpfi.pyx">
a
</th>
<th title="File b/sage/rings/real_mpfi.pyx">
b
</th>
<td><em></em> </td>
</tr>
</thead>
<tbody class="unmod">
<tr>
<th>2826</th><th>2826</th><td class="l"><span> # First, we try using approximate arithmetic of slightly higher</span></td>
</tr><tr>
<th>2827</th><th>2827</th><td class="l"><span> # precision.</span></td>
</tr><tr>
<th>2828</th><th>2828</th><td class="l"><span> cdef RealIntervalFieldElement highprec</span></td>
</tr>
</tbody><tbody class="mod">
<tr class="first">
<th>2829</th><th> </th><td class="l"><span> highprec = RealIntervalField<del>_class</del>(int(self.prec() * 1.2))(self)</span></td>
</tr>
<tr class="last">
<th> </th><th>2829</th><td class="r"><span> highprec = RealIntervalField<ins></ins>(int(self.prec() * 1.2))(self)</span></td>
</tr>
</tbody><tbody class="unmod">
<tr>
<th>2830</th><th>2830</th><td class="l"><span></span></td>
</tr><tr>
<th>2831</th><th>2831</th><td class="l"><span> cdef Rational try1 = highprec._simplest_rational_helper()</span></td>
</tr>
</tbody>
</table>
</li>
</ul>
</div></div>
TicketSimon KingMon, 07 Jan 2013 16:45:09 GMT
https://trac.sagemath.org/ticket/13922#comment:15
https://trac.sagemath.org/ticket/13922#comment:15
<p>
PS: How could that fix be tested against?
</p>
TicketSimon KingMon, 07 Jan 2013 17:06:04 GMTstatus changed; author set
https://trac.sagemath.org/ticket/13922#comment:16
https://trac.sagemath.org/ticket/13922#comment:16
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Simon King</em>
</li>
</ul>
<p>
The attached patch is preliminary, as it is not tested, and I don't know if I was over-eager to cdefine stuff.
</p>
<p>
Anyway. Without the patch, it is
</p>
<pre class="wiki">sage: %timeit a = QQ.gcd(3.14159,2*3.14159)
125 loops, best of 3: 4.58 ms per loop
sage: var('t')
t
sage: %time p = plot(lambda t: (100/(100+(t-pi/2)^8))*(2-sin(7*t)-cos(30*t)/2), -pi/4, 3*pi/2, color="red",plot_points=1000)
CPU times: user 87.06 s, sys: 0.69 s, total: 87.75 s
Wall time: 88.15 s
</pre><p>
With the patch, it is
</p>
<pre class="wiki">sage: %timeit a = QQ.gcd(3.14159,2*3.14159)
125 loops, best of 3: 2.33 ms per loop
sage: var('t')
t
sage: %time p = plot(lambda t: (100/(100+(t-pi/2)^8))*(2-sin(7*t)-cos(30*t)/2), -pi/4, 3*pi/2, color="red",plot_points=1000)
CPU times: user 55.41 s, sys: 0.00 s, total: 55.41 s
Wall time: 55.48 s
</pre><p>
Would that be enough to fix the regression completely?
</p>
TicketRobert BradshawMon, 07 Jan 2013 18:26:39 GMT
https://trac.sagemath.org/ticket/13922#comment:17
https://trac.sagemath.org/ticket/13922#comment:17
<p>
I haven't tested this yet, but the code looks good to me and clearly fixes a bug.
</p>
TicketNils BruinMon, 07 Jan 2013 21:08:49 GMT
https://trac.sagemath.org/ticket/13922#comment:18
https://trac.sagemath.org/ticket/13922#comment:18
<p>
Not introduced by this patch, so shouldn't be held against it, but ...
</p>
<pre class="wiki">RealIntervalField_cache = {}
</pre><p>
Is a strong cache! So <code>RealIntervalField</code>s get nailed in memory. That's a very good argument for ensuring that "increase precision" leads to a very predictable and sparse list of precisions, to minimize the costs from this.
</p>
TicketSimon KingMon, 07 Jan 2013 21:27:27 GMT
https://trac.sagemath.org/ticket/13922#comment:19
https://trac.sagemath.org/ticket/13922#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13922#comment:18" title="Comment 18">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Not introduced by this patch, so shouldn't be held against it, but ...
</p>
<pre class="wiki">RealIntervalField_cache = {}
</pre><p>
Is a strong cache!
</p>
</blockquote>
<p>
Yes. And since <code>RealIntervalField</code> is a very simple function (taking just one integer and one bool as argument), I would actually suggest to let <code>RealIntervalField_class</code> inherit from <code>UniqueRepresentation</code> and make <code>RealIntervalField</code> and alias for <code>RealIntervalField_class</code>. The point is that <code>UniqueRepresentation</code> will soonish have a weak cache (namely: If all the problems with <a class="closed ticket" href="https://trac.sagemath.org/ticket/715" title="#715: defect: Parents probably not reclaimed due to too much caching (closed: fixed)">#715</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/11521" title="#11521: defect: Use weak references to cache homsets (closed: fixed)">#11521</a> are sorted out). See <a class="closed ticket" href="https://trac.sagemath.org/ticket/12215" title="#12215: defect: Memleak in UniqueRepresentation, @cached_method (closed: fixed)">#12215</a>.
</p>
<p>
The questions are:
</p>
<ol><li>Do we want to the change from a custom constructor function to <code>UniqueRepresentation</code>?
</li><li>Do we want to change it <em>here</em>, or shall we have a quick fix for now and do it properly on a different ticket?
</li></ol><p>
I expect that it would be relatively harmless to use <code>UniqueRepresentation</code> in this case. Shall I try?
</p>
TicketSimon KingMon, 07 Jan 2013 21:35:45 GMT
https://trac.sagemath.org/ticket/13922#comment:20
https://trac.sagemath.org/ticket/13922#comment:20
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13922#comment:19" title="Comment 19">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I expect that it would be relatively harmless to use <code>UniqueRepresentation</code> in this case.
</p>
</blockquote>
<p>
I stand corrected. <code>UniqueRepresentation</code> is a Python class, and thus can not be used as a base class of a Cython class like <code>RealIntervalField_class</code>.
</p>
TicketSimon KingMon, 07 Jan 2013 21:49:31 GMT
https://trac.sagemath.org/ticket/13922#comment:21
https://trac.sagemath.org/ticket/13922#comment:21
<p>
Question to Robert: Is it possible to use a metaclass in Cython?
</p>
<p>
I tried:
</p>
<pre class="wiki">cdef class Test:
__metaclass__ = ClasscallMetaclass
@staticmethod
def __classcall__(cls,data):
print "classcall"
O = super(cls,cls).__new__(cls,data)
cls.__init__(O,data)
return O
def __init__(self, data):
print "init"
class Test2:
__metaclass__ = ClasscallMetaclass
@staticmethod
def __classcall__(cls,data):
print "classcall"
O = super(cls,cls).__new__(cls,data)
cls.__init__(O,data)
return O
def __init__(self, data):
print "init"
</pre><p>
While I obtain
</p>
<pre class="wiki">sage: Test2('bla')
classcall
init
<...Test2 object at 0x6128680>
</pre><p>
I only get
</p>
<pre class="wiki">sage: Test('bla')
init
<...Test object at 0x72eddc0>
</pre><p>
with the Cython function. Hence, it compiles with the metaclass, but apparently it has no effect.
</p>
TicketRobert BradshawMon, 07 Jan 2013 21:54:50 GMT
https://trac.sagemath.org/ticket/13922#comment:22
https://trac.sagemath.org/ticket/13922#comment:22
<p>
I think metaclasses are only supported for non-cdef classes. (This should probably be a compile-time error rather than silently ignoring it.)
</p>
<p>
There's also sage.structure.factory.<a class="missing wiki">UniqueFactory?</a>. It may also be worth holding a strong reference to the last N (for some small N) parents created to avoid creating the same one over and over.
</p>
<p>
In any case, this isn't a regression, so I'd be happy to get this fix in and post a follow-up ticket to ensure uniqueness.
</p>
TicketVolker BraunWed, 30 Jan 2013 15:24:15 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/13922#comment:23
https://trac.sagemath.org/ticket/13922#comment:23
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Volker Braun</em>
</li>
</ul>
<p>
Well then lets get it in ;-)
</p>
TicketJeroen DemeyerWed, 30 Jan 2013 19:15:59 GMTstatus changed
https://trac.sagemath.org/ticket/13922#comment:24
https://trac.sagemath.org/ticket/13922#comment:24
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
The following Cython-generated file needs to be added to <code>.hgignore</code>:
</p>
<pre class="wiki">sage/rings/real_mpfi.h
</pre>
TicketSimon KingWed, 30 Jan 2013 21:29:41 GMTattachment set
https://trac.sagemath.org/ticket/13922
https://trac.sagemath.org/ticket/13922
<ul>
<li><strong>attachment</strong>
set to <em>trac_13922_faster_QQgcd.patch</em>
</li>
</ul>
TicketSimon KingWed, 30 Jan 2013 21:30:27 GMTstatus changed
https://trac.sagemath.org/ticket/13922#comment:25
https://trac.sagemath.org/ticket/13922#comment:25
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13922#comment:24" title="Comment 24">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
The following Cython-generated file needs to be added to <code>.hgignore</code>:
</p>
<pre class="wiki">sage/rings/real_mpfi.h
</pre></blockquote>
<p>
Done. And I hope it is ok if I revert it to "positive review".
</p>
TicketJeroen DemeyerTue, 05 Feb 2013 08:20:35 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/13922#comment:26
https://trac.sagemath.org/ticket/13922#comment:26
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.7.beta3</em>
</li>
</ul>
Ticket