#30517 closed defect (fixed)
MemoryError in doctesting combinat/designs/gen_quadrangles_with_spread.pyx
Reported by:  Steven Trogdon  Owned by:  

Priority:  major  Milestone:  sage9.3 
Component:  combinatorial designs  Keywords:  generalised_quadrangle 
Cc:  Dima Pasechnik, ghIvoMaffei  Merged in:  
Authors:  Volker Braun, Frédéric Chapoton  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  c40efe9 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
There are numerous MemoryError
instances in doctesting gen_quadrangles_with_spread.pyx
with a final failure
 sage t long warnlong 127.5 randomseed=0 src/sage/combinat/designs/gen_quadrangles_with_spread.pyx # Bad exit: 1  Total time for all tests: 108.3 seconds cpu time: 0.0 seconds cumulative wall time: 0.0 seconds
See ticket #30223 for background.
Attachments (4)
Change History (51)
Changed 2 years ago by
Attachment:  gen_quadrangles_with_spread.pyx_test.log added 

comment:1 Changed 2 years ago by
comment:2 Changed 2 years ago by
Description:  modified (diff) 

comment:3 Changed 2 years ago by
I ran every command in gen_quadrangles_with_spread.pyx
from the sage prompt without a problem. I'm wondering if there is some weird interaction with the doctesting framework  like memory not being cleared?
comment:4 Changed 2 years ago by
The above test.log was with 9.2.beta11
which uses python3.7
. 9.2.beta12
uses python3.8
and the failure is more catastrophic. I will attach the full doctest with stack and cython backtraces. The doctest consumes about 2 GB of RAM before quitting. I have about 8 GB of total RAM. I do not have debugging symbols compiled in libraries. Doing that would require a significant effort.
Changed 2 years ago by
Attachment:  gen_quadrangles_with_spread.pyxpy3.8_test.log.bz2 added 

full doctest using 9.2.beta12 with stack and cython backtraces
comment:5 Changed 2 years ago by
Cc:  Dima Pasechnik added 

comment:7 followups: 9 25 Changed 2 years ago by
With these changes

src/sage/combinat/designs/gen_quadrangles_with_spread.pyx
diff git a/src/sage/combinat/designs/gen_quadrangles_with_spread.pyx b/src/sage/combinat/designs/gen_quadrangles_with_spread.pyx index 753d935e86..a8c1be9f09 100644
a b def dual_GQ_ovoid(GQ, O): 198 198 sage: t[0].is_generalized_quadrangle(parameters=True) 199 199 (9, 3) 200 200 sage: t = dual_GQ_ovoid(*t) 201 sage: t[0].is_generalized_quadrangle(parameters=True)202 (3, 9)203 sage: all([x in t[0] for x in t[1]])204 True205 201 206 202 207 203 TESTS:: … … def generalised_quadrangle_hermitian_with_ovoid(const int q): 271 267 is_GQ_with_spread, dual_GQ_ovoid 272 268 sage: t = designs.generalised_quadrangle_hermitian_with_ovoid(3) 273 269 sage: t = dual_GQ_ovoid(*t) 274 sage: is_GQ_with_spread(*t, s=3, t=9)275 True
I get no MemoryError
and the doctest passes.
comment:8 Changed 2 years ago by
Replying to fbissey:
Was this with gcc 9 or 10?
This was with gcc 9. But I get the same result with gcc 10.
comment:9 followup: 10 Changed 2 years ago by
Replying to strogdon:
With these changes
src/sage/combinat/designs/gen_quadrangles_with_spread.pyx
diff git a/src/sage/combinat/designs/gen_quadrangles_with_spread.pyx b/src/sage/combinat/designs/gen_quadrangles_with_spread.pyx index 753d935e86..a8c1be9f09 100644
a b def dual_GQ_ovoid(GQ, O): 198 198 sage: t[0].is_generalized_quadrangle(parameters=True) 199 199 (9, 3) 200 200 sage: t = dual_GQ_ovoid(*t) 201 sage: t[0].is_generalized_quadrangle(parameters=True)202 (3, 9)203 sage: all([x in t[0] for x in t[1]])204 True205 201 206 202 207 203 TESTS:: … … def generalised_quadrangle_hermitian_with_ovoid(const int q): 271 267 is_GQ_with_spread, dual_GQ_ovoid 272 268 sage: t = designs.generalised_quadrangle_hermitian_with_ovoid(3) 273 269 sage: t = dual_GQ_ovoid(*t) 274 sage: is_GQ_with_spread(*t, s=3, t=9)275 TrueI get no
MemoryError
and the doctest passes.
In the first part of the diff, you are removing two tests. I am assuming that means that they would fail individually without the other one being present. Is it the case?
The fact that you could run all the command individually without problem means the environment has to be "primed". There is probably a memory leak somewhere that leads to that particular outcome. Finding the leak may not be obvious.
comment:10 Changed 2 years ago by
Replying to fbissey:
Replying to strogdon:
With these changes
src/sage/combinat/designs/gen_quadrangles_with_spread.pyx
diff git a/src/sage/combinat/designs/gen_quadrangles_with_spread.pyx b/src/sage/combinat/designs/gen_quadrangles_with_spread.pyx index 753d935e86..a8c1be9f09 100644
a b def dual_GQ_ovoid(GQ, O): 198 198 sage: t[0].is_generalized_quadrangle(parameters=True) 199 199 (9, 3) 200 200 sage: t = dual_GQ_ovoid(*t) 201 sage: t[0].is_generalized_quadrangle(parameters=True)202 (3, 9)203 sage: all([x in t[0] for x in t[1]])204 True205 201 206 202 207 203 TESTS:: … … def generalised_quadrangle_hermitian_with_ovoid(const int q): 271 267 is_GQ_with_spread, dual_GQ_ovoid 272 268 sage: t = designs.generalised_quadrangle_hermitian_with_ovoid(3) 273 269 sage: t = dual_GQ_ovoid(*t) 274 sage: is_GQ_with_spread(*t, s=3, t=9)275 TrueI get no
MemoryError
and the doctest passes.In the first part of the diff, you are removing two tests. I am assuming that means that they would fail individually without the other one being present. Is it the case?
The fact that you could run all the command individually without problem means the environment has to be "primed". There is probably a memory leak somewhere that leads to that particular outcome. Finding the leak may not be obvious.
I don't know if removing just the first test in the first part of the diff would be sufficient to fix things. I can try just removing the first test. It appeared to me that perhaps t = dual_GQ_ovoid(*t)
was tainted so I removed the second test also. This may be incorrect.
But I do think you are correct in that there is a possible memory leak.
comment:12 Changed 2 years ago by
Cc:  ghIvoMaffei removed 

This also works

src/sage/combinat/designs/gen_quadrangles_with_spread.pyx
diff git a/src/sage/combinat/designs/gen_quadrangles_with_spread.pyx b/src/sage/combinat/designs/gen_quadrangles_with_spread.pyx index 753d935e86..23ec4b3a84 100644
a b def dual_GQ_ovoid(GQ, O): 198 198 sage: t[0].is_generalized_quadrangle(parameters=True) 199 199 (9, 3) 200 200 sage: t = dual_GQ_ovoid(*t) 201 sage: t[0].is_generalized_quadrangle(parameters=True)202 (3, 9)203 201 sage: all([x in t[0] for x in t[1]]) 204 202 True 205 203 … … def generalised_quadrangle_hermitian_with_ovoid(const int q): 271 269 is_GQ_with_spread, dual_GQ_ovoid 272 270 sage: t = designs.generalised_quadrangle_hermitian_with_ovoid(3) 273 271 sage: t = dual_GQ_ovoid(*t) 274 sage: is_GQ_with_spread(*t, s=3, t=9)275 True276 272 sage: t = dual_GQ_ovoid(*( 277 273 ....: designs.generalised_quadrangle_hermitian_with_ovoid(2)))
comment:14 Changed 2 years ago by
Branch:  → public/combinat/30517 

Commit:  → 36837a18013d5e13beb731386f42bcdb646f0e17 
is_GQ_with_spread
internally calls is_generalized_quadrangle
, so the issue lies in the first removed doctest.
In #30223 we had a similar issue with is_generalized_quadrangle
which was called on an incidence structure not manipulated with dual_GQ_ovoid
, so I'm keen to assume that dual_GQ_ovoid
is not the cause of the issue.
I can't reproduce the MemoryError
on my machine so I created a testfunction whose doctests should pretty much cover all operations done in is_generalised_quadrangle
. Could you please run the doctests and let me know all lines (if any) that fail?
New commits:
36837a1  added test function

comment:15 followup: 16 Changed 2 years ago by
we should improve is_generalized_quadrangle
.
there is no need to construct the incidence graph. In the regular+uniform case, i.e. if (s,t) are defined_{ just check that the collinearity graph (aka block graph) is s.r.g. with the correct parameters. }
Otherwise, if neither s nor t are defined, it is not a GQ, for either t or s must be 1. To finish, if s is not 1, take the dual, so now s=1, and the collinearity graph must be complete bipartite.
comment:16 followup: 17 Changed 2 years ago by
Replying to dimpase:
there is no need to construct the incidence graph. In the regular+uniform case, i.e. if (s,t) are defined, just check that the collinearity graph (aka block graph) is s.r.g. with the correct parameters.
I understand that the collinearity graph of a GQ is a srg, but I'm uncertain about the converse. In particular, there are many difference incidence structures that have the same collinearity graph. If we allow duplicate blocks, then an incidence structure which is a regular GQ with a duplicated block is no more a GQ, but its collinearity graph is the same. Perhaps this is just an edgecase and not allowing duplicate blocks would fix the converse, but I'm not sure.
Otherwise, if neither s nor t are defined, it is not a GQ
I don't see why this would be the case, but I trust you. Also you say that if s is not defined, then t must be 1 and vice versa?
now s=1, and the collinearity graph must be complete bipartite.
Consider the incidence structure with blocks [[1, 2], [2, 3]]
.
Then s = 1 and t is not defined.
Its collinearity graph has edges [(1, 2), (2, 3)]
which is complete bipartite K_{2, 1}, but the incidence structure is not a GQ.
I think that more generally complete bipartite K_{n, 1} are not GQ, is this right?
Changed 2 years ago by
Attachment:  quadrangles_with_spread.pyx_newtest.log added 

These are the failures I get with the added tests in test()
comment:17 Changed 2 years ago by
Replying to ghIvoMaffei:
Replying to dimpase:
there is no need to construct the incidence graph. In the regular+uniform case, i.e. if (s,t) are defined, just check that the collinearity graph (aka block graph) is s.r.g. with the correct parameters.
I understand that the collinearity graph of a GQ is a srg, but I'm uncertain about the converse. In particular, there are many difference incidence structures that have the same collinearity graph. If we allow duplicate blocks, then an incidence structure which is a regular GQ with a duplicated block is no more a GQ, but its collinearity graph is the same. Perhaps this is just an edgecase and not allowing duplicate blocks would fix the converse, but I'm not sure.
Otherwise, if neither s nor t are defined, it is not a GQ
I don't see why this would be the case, but I trust you. Also you say that if s is not defined, then t must be 1 and vice versa?
now s=1, and the collinearity graph must be complete bipartite.
Consider the incidence structure with blocks
[[1, 2], [2, 3]]
. Then s = 1 and t is not defined. Its collinearity graph has edges[(1, 2), (2, 3)]
which is complete bipartite K_{2, 1}, but the incidence structure is not a GQ. I think that more generally complete bipartite K_{n, 1} are not GQ, is this right?
right, these are so called degenerate generalised polygons (a number of lines all intersecting in one point). Usually, but not excluded from the definition. Let's exclude this case.
We should also exclude the case of repeated lines.
Note that it is immediate (there cannot be any triangls, but for any point p and line L not on L there is a point collinear on L collinear to p) from the definition of a generalised quadrangle that two nonintersecting lines have the same size. Dually, for any 2 noncollinear points the number of lines on each of then must be the same.
It follows that there are either lines of two different sizes, and you have a "grid" (just 2 lines on each point, so t=1), or all lines are of the same size.
comment:18 followup: 19 Changed 2 years ago by
Doesn't
Using optional=build,dochtml,memlimit,sage
mean that tests limit memory in some way?
Changed 2 years ago by
Attachment:  newtest.pyx_test.log added 

Tests in https://trac.sagemath.org/attachment/ticket/30517/quadrangles_with_spread.pyx_newtest.log may be contaminated by prior failures. Attached are results of just the tests in test()
comment:19 Changed 2 years ago by
Replying to dimpase:
Doesn't
Using optional=build,dochtml,memlimit,sagemean that tests limit memory in some way?
This
Testing files: t [options] <filesdir>  test examples in .py, .pyx, .sage or .tex files. Options: long  include lines with the phrase 'long time' verbose  print debugging output during the test all  test all files optional  also test all examples labeled "# optional"
seems to imply relative to doctesting that files so marked will also be tested. Not sure what the Using optional=...
implies, nor do I know how to change it.
comment:20 followup: 21 Changed 2 years ago by
It seems from reading src/bin/sageruntests
that the default, if there is memlimit
in
optional
, is 3300 MB "per test"
comment:21 followup: 22 Changed 2 years ago by
Replying to dimpase:
It seems from reading
src/bin/sageruntests
that the default, if there ismemlimit
inoptional
, is 3300 MB "per test"
Well, isn't that interesting. Doing
./sage t long verbose warnlong 127.5 randomseed=0 memlimit=0 src/sage/combinat/designs/gen_quadrangles_with_spread.pyx
gives no failing tests. When I use memlimit=0
then memlimit
does not appear
Using optional=build,dochtml,sage
What do you have in your Using
line and how are the optional
items set? Is this really the issue?
comment:22 Changed 2 years ago by
Replying to strogdon:
Using optional=build,dochtml,sageWhat do you have in your
Using
line and how are theoptional
items set? Is this really the issue?
that was just a copy/paste from the log you attached here. By default memlimit
is there.
It could be just few memoryhungry tests run in parallel, and not a memory leak.
comment:23 Changed 2 years ago by
Milestone:  sage9.2 → sage9.3 

comment:24 Changed 22 months ago by
This almost always runs out of memory on the kucalc buildbot:
sage: from sage.combinat.designs.gen_quadrangles_with_spread import is_GQ_with_spread, dual_GQ_ovoid ## line 270 ## sage: t = designs.generalised_quadrangle_hermitian_with_ovoid(3) ## line 272 ## sage: t = dual_GQ_ovoid(*t) ## line 273 ## sage: is_GQ_with_spread(*t, s=3, t=9) ## line 274 ## **********************************************************************  sage t long randomseed=0 src/sage/combinat/designs/gen_quadrangles_with_spread.pyx # Bad exit: 1 
For example, running the last is_GQ_with_spread
command eats about 170Mb per invocation that is never released.
comment:25 Changed 22 months ago by
Replying to strogdon:
With these changes
src/sage/combinat/designs/gen_quadrangles_with_spread.pyx
diff git a/src/sage/combinat/designs/gen_quadrangles_with_spread.pyx b/src/sage/combinat/designs/gen_quadrangles_with_spread.pyx index 753d935e86..a8c1be9f09 100644
a b def dual_GQ_ovoid(GQ, O): 198 198 sage: t[0].is_generalized_quadrangle(parameters=True) 199 199 (9, 3) 200 200 sage: t = dual_GQ_ovoid(*t) 201 sage: t[0].is_generalized_quadrangle(parameters=True)202 (3, 9)203 sage: all([x in t[0] for x in t[1]])204 True205 201 206 202 207 203 TESTS:: … … def generalised_quadrangle_hermitian_with_ovoid(const int q): 271 267 is_GQ_with_spread, dual_GQ_ovoid 272 268 sage: t = designs.generalised_quadrangle_hermitian_with_ovoid(3) 273 269 sage: t = dual_GQ_ovoid(*t) 274 sage: is_GQ_with_spread(*t, s=3, t=9)275 TrueI get no
MemoryError
and the doctest passes.
If you want to tag those up as # known bug
I'll be happy to review
comment:26 Changed 22 months ago by
Commit:  36837a18013d5e13beb731386f42bcdb646f0e17 → a6841da0ccbacea94b6815241b7be02e78dfda32 

comment:27 followup: 28 Changed 22 months ago by
I have added a commit on top of the public branch, just adding the 3 suggested known bug tags
comment:28 Changed 22 months ago by
Replying to chapoton:
I have added a commit on top of the public branch, just adding the 3 suggested known bug tags
Is the def test()
function needed?
comment:29 followup: 30 Changed 22 months ago by
I have not idea. Feel free to remove it and squash the branch if you think this is better.
comment:30 followup: 31 Changed 22 months ago by
comment:31 Changed 22 months ago by
Replying to ghIvoMaffei:
Replying to strogdon:
Is the
def test()
function needed?
def test()
is a function I added it in here to help debug the issue. I guess it can go now that vbraun found the problem.
well, not that Volker found the problem, he found a test to disable to avoid this doctesting issue.
comment:32 Changed 22 months ago by
Commit:  a6841da0ccbacea94b6815241b7be02e78dfda32 → c40efe9f4b94adf9dffd778bbc68fdac997929e1 

Branch pushed to git repo; I updated commit sha1. New commits:
c40efe9  removed test()

comment:33 Changed 22 months ago by
Status:  new → needs_review 

comment:34 Changed 22 months ago by
Authors:  → Volker Braun, Frederic Chapoton 

Reviewers:  → Dima Pasechnik 
Status:  needs_review → positive_review 
comment:36 Changed 22 months ago by
Commit:  c40efe9f4b94adf9dffd778bbc68fdac997929e1 → d10c62d4354e6e722b857e43f92a39e1f745be67 

Status:  positive_review → needs_review 
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
d10c62d  remove "known bug" tags

comment:37 Changed 22 months ago by
Dependencies:  → #31313 

comment:38 Changed 22 months ago by
never ever change something on a positive reviewed ticket unless you have very good reasons
comment:39 Changed 22 months ago by
as you can see here, the former branch had already been used by our release manager
https://github.com/vbraun/sage/commits/develop
so please revert and put back the exact same branch that was here when it was set to positive
comment:40 Changed 22 months ago by
I'm very sorry I goofed things up. I thought it was only closed tickets that should not be messed with.
I also thought it would be easy to revert my commit, so I'm also sorry that I don't know how to "put back the exact same branch that was here". My attempt was rejected:
STDERR: error: failed to push some refs to 'git@trac.sagemath.org:sage.git' STDERR: hint: Updates were rejected because a pushed branch tip is behind its remote
I know very little about git, so, since this didn't work, all I would know how to do is push a reversion commit to undo my erroneous change, but I don't think you want me to do that, because it would add yet another commit to the history. (Maybe a "forced push" would work, but I am not confident enough to try something like that, because my understanding is that it has the potential to mess things up permanently.)
comment:41 Changed 22 months ago by
no problem, errare humanum est. I hope that I have not have sound rude..
I will handle the restoration
comment:42 Changed 22 months ago by
Dependencies:  #31313 

comment:43 Changed 22 months ago by
Branch:  public/combinat/30517 → public/quadrangles_restored 

Commit:  d10c62d4354e6e722b857e43f92a39e1f745be67 → c40efe9f4b94adf9dffd778bbc68fdac997929e1 
@vbraun
the new correct branch name is "public/quadrangles_restored"
comment:44 Changed 22 months ago by
Status:  needs_review → positive_review 

and I am setting back to positive
comment:45 Changed 22 months ago by
Thanks for fixing this! I'm sorry to have made extra work for you.
comment:46 Changed 22 months ago by
Branch:  public/quadrangles_restored → c40efe9f4b94adf9dffd778bbc68fdac997929e1 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:47 Changed 19 months ago by
Authors:  Volker Braun, Frederic Chapoton → Volker Braun, Frédéric Chapoton 

Commit:  c40efe9f4b94adf9dffd778bbc68fdac997929e1 
log of failed doctest