Opened 9 years ago
Last modified 8 years ago
#12357 closed defect
Make groupoids garbage collectable — at Version 11
Reported by: | SimonKing | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | memleak | Keywords: | groupoid cache Cernay2012 |
Cc: | nthiery, jpflori | Merged in: | |
Authors: | Simon King | Reviewers: | |
Report Upstream: | N/A | Work issues: | rebase rel #11943 |
Branch: | Commit: | ||
Dependencies: | #715, #12313, #11943 | Stopgaps: |
Description (last modified by )
Currently, the groupoid of an object P can not be garbage collected, even when deleting P.
Even worse: The persistence of Groupoid(P)
also prevents P from being garbage collected.
The attached patch aims at solving it: An external reference to either P or Groupoid(P)
is enough to keep both alive. But without an external reference, both P and Groupoid(P)
become collectable.
Example from the docs:
sage: P = GF(151)['x','y'] sage: n = id(Groupoid(P)) sage: import gc sage: _ = gc.collect() sage: n == id(Groupoid(P)) # indirect doctest True Thus, the groupoid is cached. But when deleting ``P``, its groupoid can be garbage collected as well:: sage: del P sage: _ = gc.collect() sage: P = GF(151)['x','y'] sage: n == id(Groupoid(P)) False TESTS: We test against some corner cases:: sage: Groupoid(None) Traceback (most recent call last): ... TypeError: Groupoid of None is not defined sage: Groupoid(1) Traceback (most recent call last): ... TypeError: 1 must either allow attribute assignment or be instances of <type 'sage.structure.parent.Parent'> sage: class A: pass sage: a = A() sage: Groupoid(a) Groupoid with underlying set <__main__.A instance at ...> sage: Groupoid(a) is Groupoid(a) True
Apply:
Change History (12)
comment:1 Changed 9 years ago by
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
To my surprise, there were no nasty old doctests. Hence, make ptest
went well, with the patch from here and its dependencies!
comment:3 Changed 9 years ago by
Concerning timings:
Without the patch, the groupoid of P is stored in a dictionary, indexed by P. Hence, access to the cache is slow if hash(P)
is slow.
Some data points:
sage: P = GF(151)['x','y'] sage: %timeit G = Groupoid(P) # slow hash 625 loops, best of 3: 20.9 µs per loop sage: %timeit G = Groupoid(ZZ) # fast hash 625 loops, best of 3: 1.75 µs per loop sage: class Bar(Parent): pass ....: sage: P = Bar() sage: %timeit G = Groupoid(P) # slow hash 625 loops, best of 3: 15.3 µs per loop
But with the patch, it is stored as an attribute of P. Hence, it is slow if attribute access is slow. The point is that even slow attribute access is faster than slow hash, and slow attribute access is only little slower than fast hash:
sage: P = GF(151)['x','y'] sage: %timeit G = Groupoid(P) # slow attribute access 625 loops, best of 3: 3.11 µs per loop sage: %timeit G = Groupoid(ZZ) # slow attribute access 625 loops, best of 3: 3.1 µs per loop sage: class Bar(Parent): pass ....: sage: P = Bar() sage: %timeit G = Groupoid(P) # fast attribute access 625 loops, best of 3: 1.59 µs per loop
Hence, I believe that the patch is not only fixing a memory leak, but has the potential to generate a speed-up.
comment:4 Changed 9 years ago by
- Keywords groupoid cache Cernay2012 added
- Status changed from needs_review to needs_info
- Work issues set to tests for None?
This is the simplest patch of the cache problems suite, and it does not depend on #715, so I begin with this one.
I'm a little bit confused by all those tests for None in your patch.
Isn't the first one sufficient?
More specifically, the second test "if S is not None" isn't superfluous ?
And if it is not None, can G be None ? (I guess there is some cython voodoo involved here)
To answer my own question, I guess it is none if S is not a Parent (as in your example with 1).
Once you answer me back, I'll post a reviewer patch with some additional minor corrections.
comment:5 Changed 9 years ago by
- Status changed from needs_info to needs_review
Yes, the test "if S is not None" in line 103 seems redundant, as S being None would result in an error being raised in line 92.
Concerning Cython voodoo: If S is not None and not of type Parent, then G == S
in line 106 would result in a type error (since G is cdefined) - which is desired behaviour. But if S were None, then G == S
in line 106 would not complain, and then line 109 would segfault. This is why there must be a test for the corner case - of course, one test would be enough.
comment:6 Changed 9 years ago by
- Status changed from needs_review to positive_review
- Work issues tests for None? deleted
comment:7 Changed 9 years ago by
The reviewer patch looks fine to me. Thank you!
comment:8 Changed 9 years ago by
- Dependencies changed from #12313 to #715, #12313
comment:9 Changed 9 years ago by
- Milestone changed from sage-5.0 to sage-pending
Moving this to sage-pending for now since it depends on two non-positively reviewed tickets.
comment:10 Changed 9 years ago by
- Dependencies changed from #715, #12313 to #715, #12313, #11943
- Work issues set to rebase rel #11943
comment:11 Changed 9 years ago by
- Description modified (diff)
Done!
Apply trac12357_internal_strong_groupoid_cache.patch trac12357_reviewer.patch
I did not run the full test suite yet. It could be that some silly old doctests use the groupoids in a way they are not intended, such as
Groupoid(1)
. If this is the case, then my patch has to change. Otherwise: Needs review!