Opened 2 years ago

Closed 22 months ago

Last modified 19 months ago

#30517 closed defect (fixed)

MemoryError in doctesting combinat/designs/gen_quadrangles_with_spread.pyx

Reported by: Steven Trogdon Owned by:
Priority: major Milestone: sage-9.3
Component: combinatorial designs Keywords: generalised_quadrangle
Cc: Dima Pasechnik, gh-Ivo-Maffei 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:

Status badges

Description (last modified by Steven Trogdon)

There are numerous MemoryError instances in doctesting gen_quadrangles_with_spread.pyx with a final failure

----------------------------------------------------------------------
sage -t --long --warn-long 127.5 --random-seed=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)

gen_quadrangles_with_spread.pyx_test.log (17.8 KB) - added by Steven Trogdon 2 years ago.
gen_quadrangles_with_spread.pyx-py3.8_test.log.bz2 (14.3 KB) - added by Steven Trogdon 2 years ago.
full doctest using 9.2.beta12 with stack and cython backtraces
quadrangles_with_spread.pyx_newtest.log (13.1 KB) - added by Steven Trogdon 2 years ago.
These are the failures I get with the added tests in test()
newtest.pyx_test.log (2.1 KB) - added by Steven Trogdon 2 years ago.
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()

Download all attachments as: .zip

Change History (51)

Changed 2 years ago by Steven Trogdon

comment:1 Changed 2 years ago by Steven Trogdon

log of failed doctest

comment:2 Changed 2 years ago by Steven Trogdon

Description: modified (diff)

comment:3 Changed 2 years ago by Steven Trogdon

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 Steven Trogdon

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 Steven Trogdon

full doctest using 9.2.beta12 with stack and cython backtraces

comment:5 Changed 2 years ago by Steven Trogdon

Cc: Dima Pasechnik added

comment:6 Changed 2 years ago by François Bissey

Was this with gcc 9 or 10?

comment:7 Changed 2 years ago by Steven Trogdon

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): 
    198198        sage: t[0].is_generalized_quadrangle(parameters=True)
    199199        (9, 3)
    200200        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         True
    205201
    206202
    207203    TESTS::
    def generalised_quadrangle_hermitian_with_ovoid(const int q): 
    271267              is_GQ_with_spread, dual_GQ_ovoid
    272268        sage: t = designs.generalised_quadrangle_hermitian_with_ovoid(3)
    273269        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 in reply to:  6 Changed 2 years ago by Steven Trogdon

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 in reply to:  7 ; Changed 2 years ago by François Bissey

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): 
    198198        sage: t[0].is_generalized_quadrangle(parameters=True)
    199199        (9, 3)
    200200        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         True
    205201
    206202
    207203    TESTS::
    def generalised_quadrangle_hermitian_with_ovoid(const int q): 
    271267              is_GQ_with_spread, dual_GQ_ovoid
    272268        sage: t = designs.generalised_quadrangle_hermitian_with_ovoid(3)
    273269        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.

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 in reply to:  9 Changed 2 years ago by Steven Trogdon

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): 
    198198        sage: t[0].is_generalized_quadrangle(parameters=True)
    199199        (9, 3)
    200200        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         True
    205201
    206202
    207203    TESTS::
    def generalised_quadrangle_hermitian_with_ovoid(const int q): 
    271267              is_GQ_with_spread, dual_GQ_ovoid
    272268        sage: t = designs.generalised_quadrangle_hermitian_with_ovoid(3)
    273269        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.

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:11 Changed 2 years ago by Dima Pasechnik

Cc: gh-Ivo-Maffei added

I've cc'd the author, Ivo.

comment:12 Changed 2 years ago by Steven Trogdon

Cc: gh-Ivo-Maffei 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): 
    198198        sage: t[0].is_generalized_quadrangle(parameters=True)
    199199        (9, 3)
    200200        sage: t = dual_GQ_ovoid(*t)
    201         sage: t[0].is_generalized_quadrangle(parameters=True)
    202         (3, 9)
    203201        sage: all([x in t[0] for x in t[1]])
    204202        True
    205203
    def generalised_quadrangle_hermitian_with_ovoid(const int q): 
    271269              is_GQ_with_spread, dual_GQ_ovoid
    272270        sage: t = designs.generalised_quadrangle_hermitian_with_ovoid(3)
    273271        sage: t = dual_GQ_ovoid(*t)
    274         sage: is_GQ_with_spread(*t, s=3, t=9)
    275         True
    276272        sage: t = dual_GQ_ovoid(*(
    277273        ....: designs.generalised_quadrangle_hermitian_with_ovoid(2)))

comment:13 Changed 2 years ago by Steven Trogdon

Cc: gh-Ivo-Maffei added

I didn't mean to remove the Cc

comment:14 Changed 2 years ago by gh-Ivo-Maffei

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 test-function 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:

36837a1added test function

comment:15 Changed 2 years ago by Dima Pasechnik

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.

Last edited 2 years ago by Dima Pasechnik (previous) (diff)

comment:16 in reply to:  15 ; Changed 2 years ago by gh-Ivo-Maffei

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 edge-case 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 Steven Trogdon

These are the failures I get with the added tests in test()

comment:17 in reply to:  16 Changed 2 years ago by Dima Pasechnik

Replying to gh-Ivo-Maffei:

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 edge-case 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 non-intersecting lines have the same size. Dually, for any 2 non-collinear 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 Changed 2 years ago by Dima Pasechnik

Doesn't

Using --optional=build,dochtml,memlimit,sage

mean that tests limit memory in some way?

Last edited 2 years ago by Dima Pasechnik (previous) (diff)

Changed 2 years ago by Steven Trogdon

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 in reply to:  18 Changed 2 years ago by Steven Trogdon

Replying to dimpase:

Doesn't

Using --optional=build,dochtml,memlimit,sage

mean that tests limit memory in some way?

This

Testing files:

  -t [options] <files|dir> -- 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 Changed 2 years ago by Dima Pasechnik

It seems from reading src/bin/sage-runtests that the default, if there is memlimit in --optional, is 3300 MB "per test"

comment:21 in reply to:  20 ; Changed 2 years ago by Steven Trogdon

Replying to dimpase:

It seems from reading src/bin/sage-runtests that the default, if there is memlimit in --optional, is 3300 MB "per test"

Well, isn't that interesting. Doing

./sage -t --long --verbose --warn-long 127.5 --random-seed=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 in reply to:  21 Changed 2 years ago by Dima Pasechnik

Replying to strogdon:

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?

that was just a copy/paste from the log you attached here. By default memlimit is there.

It could be just few memory-hungry tests run in parallel, and not a memory leak.

comment:23 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-9.3

comment:24 Changed 22 months ago by Volker Braun

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 --random-seed=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 170kb per invocation that is never released.

Version 0, edited 22 months ago by Volker Braun (next)

comment:25 in reply to:  7 Changed 22 months ago by Volker Braun

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): 
    198198        sage: t[0].is_generalized_quadrangle(parameters=True)
    199199        (9, 3)
    200200        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         True
    205201
    206202
    207203    TESTS::
    def generalised_quadrangle_hermitian_with_ovoid(const int q): 
    271267              is_GQ_with_spread, dual_GQ_ovoid
    272268        sage: t = designs.generalised_quadrangle_hermitian_with_ovoid(3)
    273269        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.

If you want to tag those up as # known bug I'll be happy to review

comment:26 Changed 22 months ago by git

Commit: 36837a18013d5e13beb731386f42bcdb646f0e17a6841da0ccbacea94b6815241b7be02e78dfda32

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

08b8890Merge branch 'public/combinat/30517' in 9.3.b6
a6841daadding known bug tags

comment:27 Changed 22 months ago by Frédéric Chapoton

I have added a commit on top of the public branch, just adding the 3 suggested known bug tags

comment:28 in reply to:  27 Changed 22 months ago by Steven Trogdon

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 Changed 22 months ago by Frédéric Chapoton

I have not idea. Feel free to remove it and squash the branch if you think this is better.

comment:30 in reply to:  29 ; Changed 22 months ago by gh-Ivo-Maffei

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.

comment:31 in reply to:  30 Changed 22 months ago by Dima Pasechnik

Replying to gh-Ivo-Maffei:

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 git

Commit: a6841da0ccbacea94b6815241b7be02e78dfda32c40efe9f4b94adf9dffd778bbc68fdac997929e1

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

c40efe9removed test()

comment:33 Changed 22 months ago by Dima Pasechnik

Status: newneeds_review

comment:34 Changed 22 months ago by Dima Pasechnik

Authors: Volker Braun, Frederic Chapoton
Reviewers: Dima Pasechnik
Status: needs_reviewpositive_review

comment:35 Changed 22 months ago by Volker Braun

Followup for the underlying issue at #31313

comment:36 Changed 22 months ago by git

Commit: c40efe9f4b94adf9dffd778bbc68fdac997929e1d10c62d4354e6e722b857e43f92a39e1f745be67
Status: positive_reviewneeds_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

d10c62dremove "known bug" tags

comment:37 Changed 22 months ago by Dave Morris

Dependencies: #31313

The memory leak was fixed at #31313, so I removed the "known bug" tags. I think it is cleaner to do that here, instead of on #31313. Revert my PR if I am wrong.

comment:38 Changed 22 months ago by Frédéric Chapoton

never ever change something on a positive reviewed ticket unless you have very good reasons

comment:39 Changed 22 months ago by Frédéric Chapoton

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 Dave Morris

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 Frédéric Chapoton

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 Frédéric Chapoton

Dependencies: #31313

comment:43 Changed 22 months ago by Frédéric Chapoton

Branch: public/combinat/30517public/quadrangles_restored
Commit: d10c62d4354e6e722b857e43f92a39e1f745be67c40efe9f4b94adf9dffd778bbc68fdac997929e1

@vbraun

the new correct branch name is "public/quadrangles_restored"

comment:44 Changed 22 months ago by Frédéric Chapoton

Status: needs_reviewpositive_review

and I am setting back to positive

comment:45 Changed 22 months ago by Dave Morris

Thanks for fixing this! I'm sorry to have made extra work for you.

comment:46 Changed 22 months ago by Volker Braun

Branch: public/quadrangles_restoredc40efe9f4b94adf9dffd778bbc68fdac997929e1
Resolution: fixed
Status: positive_reviewclosed

comment:47 Changed 19 months ago by Matthias Köppe

Authors: Volker Braun, Frederic ChapotonVolker Braun, Frédéric Chapoton
Commit: c40efe9f4b94adf9dffd778bbc68fdac997929e1
Note: See TracTickets for help on using tickets.