Opened 8 years ago
Closed 8 years ago
#16855 closed enhancement (fixed)
Make finite fields satisfy comparison by identity
Reported by:  Peter Bruin  Owned by:  

Priority:  minor  Milestone:  sage6.4 
Component:  finite rings  Keywords:  finite field comparison 
Cc:  JeanPierre Flori, Simon King, Nils Bruin  Merged in:  
Authors:  Peter Bruin  Reviewers:  JeanPierre Flori 
Report Upstream:  N/A  Work issues:  
Branch:  8d9f33c (Commits, GitHub, GitLab)  Commit:  8d9f33c40df9d5b7bd89833a3b761c80553e152d 
Dependencies:  Stopgaps: 
Description
For efficiency and simplicity, finite fields should compare equal if and only if they are identical. Ideally this would be accomplished by inheriting from WithEqualityById
. Since FiniteField
is a Cython class and Cython does not support multiple inheritance, we implement this by copying the __hash__()
and __richcmp__()
methods from WithEqualityById
.
Change History (21)
comment:1 Changed 8 years ago by
Branch:  → u/pbruin/16855finite_field_comparison 

Commit:  → fcc623fd5c2e402986de71296032048f05041e3a 
Status:  new → needs_review 
comment:2 followup: 3 Changed 8 years ago by
Branch:  u/pbruin/16855finite_field_comparison → u/pbruin/16855FiniteField_comparison 

Cc:  Nils Bruin added 
Commit:  fcc623fd5c2e402986de71296032048f05041e3a → 10bcb8df90756b034907059cf965cbfe01dbc5ac 
comment:3 Changed 8 years ago by
Replying to pbruin:
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 here.
I thought that the kind of memory leaks he mentions has meanwhile been fixed. IIRC, having nonleaking bidirectional coercion was the motivation of using weak references to (co?)domain and parent of coercion maps.
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 leakfixing ticket that has not been merged yet?
comment:4 followup: 10 Changed 8 years ago by
Do we want coercions anyway? Wouldn't conversions be enough?
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?
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.
(I may be talking non sense, I did not look at the code yet.)
comment:5 Changed 8 years ago by
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.
comment:6 followup: 7 Changed 8 years ago by
The following does not leak memory with the current branch, but does leak memory after applying the additional commit fcc623fd
from the other branch:
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())
[Edit: the correct option is `impl` instead of `implementation`, but it doesn't affect the memory leak.]
comment:7 followup: 8 Changed 8 years ago by
Replying to pbruin:
The following does not leak memory with the current branch, but does leak memory after applying the additional commit
fcc623fd
from the other branch:
What is / where to find the "other branch"?
comment:8 Changed 8 years ago by
comment:9 Changed 8 years ago by
Commit:  10bcb8df90756b034907059cf965cbfe01dbc5ac → e1380c03931414a7f9715e936d587976f06807a2 

Branch pushed to git repo; I updated commit sha1. New commits:
e1380c0  Trac 16855: correct option implemention > impl

comment:10 Changed 8 years ago by
Replying to jpflori:
Do we want coercions anyway? Wouldn't conversions be enough?
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.
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:
for p in primerange(<large>): <create fields with p> <exercise them (add, multiply, build polynomial rings over them)> gc.collect()
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)
comment:11 followup: 13 Changed 8 years ago by
While this ticket makes the bug at #16934 go away, we still have the following bug:
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
comment:12 Changed 8 years ago by
Commit:  e1380c03931414a7f9715e936d587976f06807a2 → 8d9f33c40df9d5b7bd89833a3b761c80553e152d 

Branch pushed to git repo; I updated commit sha1. New commits:
8d9f33c  Merge branch 'develop' into ticket/16855FiniteField_comparison

comment:13 Changed 8 years ago by
comment:15 Changed 8 years ago by
Replying to jpflori:
And this conflicts with #16983.
Those conflicts should be resolved by the merge commit from comment:12, or am I missing something? Ticket #17165 also seems to merge normally.
comment:16 followup: 17 Changed 8 years ago by
I think #16983 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 (nonrelated so I hardly believe it was the reason for confusing git) stuff merged in.
comment:17 Changed 8 years ago by
Replying to jpflori:
I think #16983 isn't in any beta/rc/final release yet.
It is in 6.4.rc0, see https://groups.google.com/forum/#!topic/sagerelease/xgmJ3nAcUOY (that is the version I merged with)
comment:18 followup: 20 Changed 8 years ago by
Oh yes you're right. I just had a look at the empty "merged in" field.
comment:19 Changed 8 years ago by
Reviewers:  → JeanPierre Flori 

Status:  needs_review → positive_review 
So I guess it is dark magic I used which confused git.
comment:20 Changed 8 years ago by
Replying to jpflori:
Oh yes you're right. I just had a look at the empty "merged in" field.
For some reason that field is not used anymore since the switch to Git. I think that Volker advocates using git log
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.
comment:21 Changed 8 years ago by
Branch:  u/pbruin/16855FiniteField_comparison → 8d9f33c40df9d5b7bd89833a3b761c80553e152d 

Resolution:  → fixed 
Status:  positive_review → closed 
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 here.