Opened 5 years ago

Closed 5 years ago

#16855 closed enhancement (fixed)

Make finite fields satisfy comparison by identity

Reported by: pbruin Owned by:
Priority: minor Milestone: sage-6.4
Component: finite rings Keywords: finite field comparison
Cc: jpflori, SimonKing, nbruin Merged in:
Authors: Peter Bruin Reviewers: Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: 8d9f33c (Commits) 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 5 years ago by pbruin

  • Branch set to u/pbruin/16855-finite_field_comparison
  • Commit set to fcc623fd5c2e402986de71296032048f05041e3a
  • Status changed from new to needs_review

comment:2 follow-up: Changed 5 years ago by pbruin

  • Branch changed from u/pbruin/16855-finite_field_comparison to u/pbruin/16855-FiniteField_comparison
  • Cc nbruin added
  • Commit changed from fcc623fd5c2e402986de71296032048f05041e3a to 10bcb8df90756b034907059cf965cbfe01dbc5ac

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.

comment:3 in reply to: ↑ 2 Changed 5 years ago by SimonKing

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 non-leaking 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 leak-fixing ticket that has not been merged yet?

comment:4 follow-up: Changed 5 years ago by jpflori

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 5 years ago by pbruin

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 follow-up: Changed 5 years ago by 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:

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.]

Last edited 5 years ago by pbruin (previous) (diff)

comment:7 in reply to: ↑ 6 ; follow-up: Changed 5 years ago by SimonKing

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 in reply to: ↑ 7 Changed 5 years ago by pbruin

Replying to SimonKing:

What is / where to find the "other branch"?

u/pbruin/16855-finite_field_comparison (see comment:2)

comment:9 Changed 5 years ago by git

  • Commit changed from 10bcb8df90756b034907059cf965cbfe01dbc5ac to e1380c03931414a7f9715e936d587976f06807a2

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

e1380c0Trac 16855: correct option implemention -> impl

comment:10 in reply to: ↑ 4 Changed 5 years ago by nbruin

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 follow-up: Changed 5 years ago by jdemeyer

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: _ = PolynomialRing(k1, 'x')(a/2)
sage: k2.<a> = GF(17^14, impl="pari_ffelt")
sage: k1 is k2
False
Version 1, edited 5 years ago by jdemeyer (previous) (next) (diff)

comment:12 Changed 5 years ago by git

  • Commit changed from e1380c03931414a7f9715e936d587976f06807a2 to 8d9f33c40df9d5b7bd89833a3b761c80553e152d

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

8d9f33cMerge branch 'develop' into ticket/16855-FiniteField_comparison

comment:13 in reply to: ↑ 11 Changed 5 years ago by pbruin

Replying to jdemeyer:

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

This was actually solved by #16934.

comment:14 follow-up: Changed 5 years ago by jpflori

And this conflicts with #16983.

comment:15 in reply to: ↑ 14 Changed 5 years ago by pbruin

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 follow-up: Changed 5 years ago by jpflori

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 (non-related so I hardly believe it was the reason for confusing git) stuff merged in.

comment:17 in reply to: ↑ 16 Changed 5 years ago by pbruin

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/sage-release/xgmJ3nAcUOY (that is the version I merged with)

Last edited 5 years ago by pbruin (previous) (diff)

comment:18 follow-up: Changed 5 years ago by jpflori

Oh yes you're right. I just had a look at the empty "merged in" field.

comment:19 Changed 5 years ago by jpflori

  • Reviewers set to Jean-Pierre Flori
  • Status changed from needs_review to positive_review

So I guess it is dark magic I used which confused git.

comment:20 in reply to: ↑ 18 Changed 5 years ago by pbruin

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 5 years ago by vbraun

  • Branch changed from u/pbruin/16855-FiniteField_comparison to 8d9f33c40df9d5b7bd89833a3b761c80553e152d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.