Sage: Ticket #16855: Make finite fields satisfy comparison by identity
https://trac.sagemath.org/ticket/16855
<p>
For efficiency and simplicity, finite fields should compare equal if and only if they are identical. Ideally this would be accomplished by inheriting from <code>WithEqualityById</code>. Since <code>FiniteField</code> is a Cython class and Cython does not support multiple inheritance, we implement this by copying the <code>__hash__()</code> and <code>__richcmp__()</code> methods from <code>WithEqualityById</code>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/16855
Trac 1.2Peter BruinTue, 19 Aug 2014 20:36:49 GMTstatus changed; commit, branch set
https://trac.sagemath.org/ticket/16855#comment:1
https://trac.sagemath.org/ticket/16855#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>fcc623fd5c2e402986de71296032048f05041e3a</em>
</li>
<li><strong>branch</strong>
set to <em>u/pbruin/16855-finite_field_comparison</em>
</li>
</ul>
TicketPeter BruinThu, 21 Aug 2014 11:11:22 GMTcc, commit, branch changed
https://trac.sagemath.org/ticket/16855#comment:2
https://trac.sagemath.org/ticket/16855#comment:2
<ul>
<li><strong>cc</strong>
<em>Nils Bruin</em> added
</li>
<li><strong>commit</strong>
changed from <em>fcc623fd5c2e402986de71296032048f05041e3a</em> to <em>10bcb8df90756b034907059cf965cbfe01dbc5ac</em>
</li>
<li><strong>branch</strong>
changed from <em>u/pbruin/16855-finite_field_comparison</em> to <em>u/pbruin/16855-FiniteField_comparison</em>
</li>
</ul>
<p>
Changing branch to not introduce coercions between different implementations of the same finite field, since this will lead to memory leaks; see Nils Bruin's comments <a class="ext-link" href="https://groups.google.com/d/msg/sage-devel/c8cCvT84CLo/436vAxVoBdMJ"><span class="icon"></span>here</a>.
</p>
TicketSimon KingThu, 21 Aug 2014 14:28:48 GMT
https://trac.sagemath.org/ticket/16855#comment:3
https://trac.sagemath.org/ticket/16855#comment:3
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16855#comment:2" title="Comment 2">pbruin</a>:
</p>
<blockquote class="citation">
<p>
Changing branch to not introduce coercions between different implementations of the same finite field, since this will lead to memory leaks; see Nils Bruin's comments <a class="ext-link" href="https://groups.google.com/d/msg/sage-devel/c8cCvT84CLo/436vAxVoBdMJ"><span class="icon"></span>here</a>.
</p>
</blockquote>
<p>
I thought that the kind of memory leaks he mentions has meanwhile been fixed. IIRC, having non-leaking bidirectional coercion was the motivation of using weak references to (co?)domain and parent of coercion maps.
</p>
<p>
So, can you or Nils give an actual example of a leak caused by bidirectional coercion in the current sage version? Or could you point me to a relevant leak-fixing ticket that has not been merged yet?
</p>
TicketJean-Pierre FloriThu, 21 Aug 2014 14:35:15 GMT
https://trac.sagemath.org/ticket/16855#comment:4
https://trac.sagemath.org/ticket/16855#comment:4
<p>
Do we want coercions anyway?
Wouldn't conversions be enough?
</p>
<p>
I'd say the user ending up with two different implementations of the same finite field (with same defining polynomial) surely knows how she ended up there.
So doing nothing automagically is surely better than arbitrarly choosing one of the possible directions for coercion and pushing everything there, isn't it?
</p>
<p>
Of course if when using a given implem of the finite field, you may end up with a polynomial ring based on another implem, coercion is still needed.
But now that we make sure that different implems are considered different, that should not happen.
</p>
<p>
(I may be talking non sense, I did not look at the code yet.)
</p>
TicketPeter BruinThu, 21 Aug 2014 14:41:52 GMT
https://trac.sagemath.org/ticket/16855#comment:5
https://trac.sagemath.org/ticket/16855#comment:5
<p>
I'll try to see if I can produce a memory leak using multidirectional coercions. Anyway, I think that if we want these coercions, it is probably better to do this on a different ticket.
</p>
TicketPeter BruinThu, 21 Aug 2014 14:56:44 GMT
https://trac.sagemath.org/ticket/16855#comment:6
https://trac.sagemath.org/ticket/16855#comment:6
<p>
The following does not leak memory with the current branch, but does leak memory after applying the additional commit <code>fcc623fd</code> from the other branch:
</p>
<pre class="wiki">import gc
for i in range(10000):
var = 'a' + str(i)
F0 = FiniteField(2^3, var, impl='givaro')
F1 = FiniteField(2^3, var, impl='pari_ffelt')
_ = F0.coerce_map_from(F1)
_ = F1.coerce_map_from(F0)
if(i % 100 == 0):
gc.collect()
print(get_memory_usage())
</pre><p>
[Edit: the correct option is `impl` instead of `implementation`, but it doesn't affect the memory leak.]
</p>
TicketSimon KingThu, 21 Aug 2014 15:26:25 GMT
https://trac.sagemath.org/ticket/16855#comment:7
https://trac.sagemath.org/ticket/16855#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16855#comment:6" title="Comment 6">pbruin</a>:
</p>
<blockquote class="citation">
<p>
The following does not leak memory with the current branch, but does leak memory after applying the additional commit <code>fcc623fd</code> from the other branch:
</p>
</blockquote>
<p>
What is / where to find the "other branch"?
</p>
TicketPeter BruinThu, 21 Aug 2014 15:27:59 GMT
https://trac.sagemath.org/ticket/16855#comment:8
https://trac.sagemath.org/ticket/16855#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16855#comment:7" title="Comment 7">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
What is / where to find the "other branch"?
</p>
</blockquote>
<p>
<code>u/pbruin/16855-finite_field_comparison</code> (see <a class="ticket" href="https://trac.sagemath.org/ticket/16855#comment:2" title="Comment 2">comment:2</a>)
</p>
TicketgitThu, 21 Aug 2014 16:37:36 GMTcommit changed
https://trac.sagemath.org/ticket/16855#comment:9
https://trac.sagemath.org/ticket/16855#comment:9
<ul>
<li><strong>commit</strong>
changed from <em>10bcb8df90756b034907059cf965cbfe01dbc5ac</em> to <em>e1380c03931414a7f9715e936d587976f06807a2</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e1380c03931414a7f9715e936d587976f06807a2"><span class="icon"></span>e1380c0</a></td><td><code>Trac 16855: correct option implemention -> impl</code>
</td></tr></table>
TicketNils BruinThu, 04 Sep 2014 18:35:14 GMT
https://trac.sagemath.org/ticket/16855#comment:10
https://trac.sagemath.org/ticket/16855#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16855#comment:4" title="Comment 4">jpflori</a>:
</p>
<blockquote class="citation">
<p>
Do we want coercions anyway?
Wouldn't conversions be enough?
</p>
</blockquote>
<p>
There is certainly a mechanism in place for caching conversions (as maps) that would lead to exactly the same memory leak. A coercion in one direction combined with a conversion in the other could lead to the same leak.
</p>
<p>
It may be that there are ways to have a conversion and *not* a cached map. In any case, however these things get solved, it's worth convincing yourself that no memory leak has been created via the usual test:
</p>
<pre class="wiki">for p in primerange(<large>):
<create fields with p>
<exercise them (add, multiply, build polynomial rings over them)>
gc.collect()
</pre><p>
and ensure that there is not a large number of finite fields still in memory (or just watch if memory consumption spirals out of control)
</p>
TicketJeroen DemeyerThu, 04 Sep 2014 20:15:44 GMT
https://trac.sagemath.org/ticket/16855#comment:11
https://trac.sagemath.org/ticket/16855#comment:11
<p>
While this ticket makes the bug at <a class="closed ticket" href="https://trac.sagemath.org/ticket/16934" title="#16934: defect: Fix factory keys for finite fields to avoid repeated construction (closed: fixed)">#16934</a> go away, we still have the following bug:
</p>
<pre class="wiki">sage: k1.<a> = GF(17^14, impl="pari_ffelt")
sage: _ = a/2
sage: k2.<a> = GF(17^14, impl="pari_ffelt")
sage: k1 is k2
False
</pre>
TicketgitFri, 31 Oct 2014 10:16:47 GMTcommit changed
https://trac.sagemath.org/ticket/16855#comment:12
https://trac.sagemath.org/ticket/16855#comment:12
<ul>
<li><strong>commit</strong>
changed from <em>e1380c03931414a7f9715e936d587976f06807a2</em> to <em>8d9f33c40df9d5b7bd89833a3b761c80553e152d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8d9f33c40df9d5b7bd89833a3b761c80553e152d"><span class="icon"></span>8d9f33c</a></td><td><code>Merge branch 'develop' into ticket/16855-FiniteField_comparison</code>
</td></tr></table>
TicketPeter BruinFri, 31 Oct 2014 10:21:36 GMT
https://trac.sagemath.org/ticket/16855#comment:13
https://trac.sagemath.org/ticket/16855#comment:13
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16855#comment:11" title="Comment 11">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
While this ticket makes the bug at <a class="closed ticket" href="https://trac.sagemath.org/ticket/16934" title="#16934: defect: Fix factory keys for finite fields to avoid repeated construction (closed: fixed)">#16934</a> go away, we still have the following bug:
</p>
<pre class="wiki">sage: k1.<a> = GF(17^14, impl="pari_ffelt")
sage: _ = a/2
sage: k2.<a> = GF(17^14, impl="pari_ffelt")
sage: k1 is k2
False
</pre></blockquote>
<p>
This was actually solved by <a class="closed ticket" href="https://trac.sagemath.org/ticket/16934" title="#16934: defect: Fix factory keys for finite fields to avoid repeated construction (closed: fixed)">#16934</a>.
</p>
TicketJean-Pierre FloriFri, 31 Oct 2014 14:53:21 GMT
https://trac.sagemath.org/ticket/16855#comment:14
https://trac.sagemath.org/ticket/16855#comment:14
<p>
And this conflicts with <a class="closed ticket" href="https://trac.sagemath.org/ticket/16983" title="#16983: enhancement: Fix finite field modulus handling (closed: fixed)">#16983</a>.
</p>
TicketPeter BruinFri, 31 Oct 2014 15:09:36 GMT
https://trac.sagemath.org/ticket/16855#comment:15
https://trac.sagemath.org/ticket/16855#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16855#comment:14" title="Comment 14">jpflori</a>:
</p>
<blockquote class="citation">
<p>
And this conflicts with <a class="closed ticket" href="https://trac.sagemath.org/ticket/16983" title="#16983: enhancement: Fix finite field modulus handling (closed: fixed)">#16983</a>.
</p>
</blockquote>
<p>
Those conflicts should be resolved by the merge commit from <a class="ticket" href="https://trac.sagemath.org/ticket/16855#comment:12" title="Comment 12">comment:12</a>, or am I missing something? Ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/17165" title="#17165: enhancement: Refactor some generic finite field code (closed: fixed)">#17165</a> also seems to merge normally.
</p>
TicketJean-Pierre FloriFri, 31 Oct 2014 16:06:43 GMT
https://trac.sagemath.org/ticket/16855#comment:16
https://trac.sagemath.org/ticket/16855#comment:16
<p>
I think <a class="closed ticket" href="https://trac.sagemath.org/ticket/16983" title="#16983: enhancement: Fix finite field modulus handling (closed: fixed)">#16983</a> isn't in any beta/rc/final release yet.
The merge is trivial though.
I've just done it and everything is fine for me.
I'd prefer you to do it though as I've done it in a branch with other (non-related so I hardly believe it was the reason for confusing git) stuff merged in.
</p>
TicketPeter BruinFri, 31 Oct 2014 16:39:23 GMT
https://trac.sagemath.org/ticket/16855#comment:17
https://trac.sagemath.org/ticket/16855#comment:17
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16855#comment:16" title="Comment 16">jpflori</a>:
</p>
<blockquote class="citation">
<p>
I think <a class="closed ticket" href="https://trac.sagemath.org/ticket/16983" title="#16983: enhancement: Fix finite field modulus handling (closed: fixed)">#16983</a> isn't in any beta/rc/final release yet.
</p>
</blockquote>
<p>
It is in 6.4.rc0, see <a class="ext-link" href="https://groups.google.com/forum/#!topic/sage-release/xgmJ3nAcUOY"><span class="icon"></span>https://groups.google.com/forum/#!topic/sage-release/xgmJ3nAcUOY</a>
(that is the version I merged with)
</p>
TicketJean-Pierre FloriMon, 03 Nov 2014 10:40:52 GMT
https://trac.sagemath.org/ticket/16855#comment:18
https://trac.sagemath.org/ticket/16855#comment:18
<p>
Oh yes you're right.
I just had a look at the empty "merged in" field.
</p>
TicketJean-Pierre FloriMon, 03 Nov 2014 10:41:54 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/16855#comment:19
https://trac.sagemath.org/ticket/16855#comment:19
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Jean-Pierre Flori</em>
</li>
</ul>
<p>
So I guess it is dark magic I used which confused git.
</p>
TicketPeter BruinMon, 03 Nov 2014 14:39:01 GMT
https://trac.sagemath.org/ticket/16855#comment:20
https://trac.sagemath.org/ticket/16855#comment:20
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16855#comment:18" title="Comment 18">jpflori</a>:
</p>
<blockquote class="citation">
<p>
Oh yes you're right.
I just had a look at the empty "merged in" field.
</p>
</blockquote>
<p>
For some reason that field is not used anymore since the switch to Git. I think that Volker advocates using <code>git log</code> or the release notes to find out when a ticket was merged (which I find unfortunate since those methods are less convenient than the "merged in" field). Anyway, thanks for the review.
</p>
TicketVolker BraunFri, 07 Nov 2014 16:15:21 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/16855#comment:21
https://trac.sagemath.org/ticket/16855#comment:21
<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>branch</strong>
changed from <em>u/pbruin/16855-FiniteField_comparison</em> to <em>8d9f33c40df9d5b7bd89833a3b761c80553e152d</em>
</li>
</ul>
Ticket