Opened 2 years ago

Closed 20 months ago

Last modified 18 months ago

#28866 closed defect (fixed)

doctest killed due to abort in geometry/polyhedron/base.py

Reported by: slabbe Owned by:
Priority: major Milestone: sage-9.1
Component: geometry Keywords:
Cc: mkoeppe, jipilab, mjo Merged in:
Authors: Jonathan Kliem Reviewers: Sébastien Labbé, Michael Orlitzky, Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: c701c31 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by slabbe)

On a clean develop branch running SageMath version 9.1.beta9, Release Date: 2020-03-29, I get:

$ sage -t --long --memlimit=3600 src/sage/geometry/polyhedron/base.py 
too many failed tests, not using stored timings
Running doctests with ID 2020-04-01-21-12-24-30fbb892.
Git branch: develop
Using --optional=4ti2,build,cbc,ccache,cryptominisat,dochtml,dot2tex,e_antic,glucose,latte_int,lidia,lrslib,memlimit,normaliz,notedown,openssl,pandoc_attributes,pycosat,pynormaliz,rst2ipynb,sage,sage_numerical_backends_coin,sage_numerical_backends_cplex,sage_numerical_backends_gurobi
Doctesting 1 file.
sage -t --long src/sage/geometry/polyhedron/base.py
    [1485 tests, 26.12 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 26.4 seconds
    cpu time: 24.0 seconds
    cumulative wall time: 26.1 seconds

while

sage -t --long --memlimit=3500 src/sage/geometry/polyhedron/base.py 

or

sage -t --long src/sage/geometry/polyhedron/base.py

gives

Using --optional=4ti2,build,cbc,ccache,cryptominisat,dochtml,dot2tex,e_antic,glucose,latte_int,lidia,lrslib,memlimit,normaliz,notedown,openssl,pandoc_attributes,pycosat,pynormaliz,rst2ipynb,sage,sagenb
Doctesting 1 file.
sage -t --long src/sage/geometry/polyhedron/base.py
**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 7172, in sage.geometry.polyhedron.base.Polyhedron_base.integral_points
Failed example:
    P = 1/10*polytopes.hypercube(14)
Exception raised:
    Traceback (most recent call last):
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1123, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.base.Polyhedron_base.integral_points[12]>", line 1, in <module>
        P = Integer(1)/Integer(10)*polytopes.hypercube(Integer(14))
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/library.py", line 2749, in hypercube
        return Polyhedron(vertices=list(itertools.product([1, -1], repeat=dim)), base_ring=ZZ, backend=backend)
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/constructor.py", line 626, in Polyhedron
        return parent(Vrep, Hrep, convert=convert, verbose=verbose)
      File "sage/structure/parent.pyx", line 902, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9245)
        return mor._call_with_args(x, args, kwds)
      File "sage/structure/coerce_maps.pyx", line 180, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (build/cythonized/sage/structure/coerce_maps.c:5081)
        raise
      File "sage/structure/coerce_maps.pyx", line 175, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (build/cythonized/sage/structure/coerce_maps.c:4969)
        return C._element_constructor(x, *args, **kwds)
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/parent.py", line 525, in _element_constructor_
        return self.element_class(self, Vrep, Hrep, **kwds)
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py", line 121, in __init__
        self._init_from_Vrepresentation(vertices, rays, lines, **kwds)
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/backend_ppl.py", line 93, in _init_from_Vrepresentation
        self._init_Vrepresentation_from_ppl(minimize)
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/backend_ppl.py", line 161, in _init_Vrepresentation_from_ppl
        gs = self._ppl_polyhedron.minimized_generators()
      File "ppl/polyhedron.pyx", line 335, in ppl.polyhedron.Polyhedron.minimized_generators
    RuntimeError: Aborted
**********************************************************************

...

    Killed due to abort
**********************************************************************
Tests run before process (pid=19555) failed:
sage: p = polytopes.hypercube(2) ## line 71 ##
sage: from sage.geometry.polyhedron.base import is_Polyhedron ## line 72 ##
sage: is_Polyhedron(p) ## line 73 ##
True

...

sage: v = [(1,0,7,-1), (-2,-2,4,-3), (-1,-1,-1,4), (2,9,0,-5), (-2,-1,5,1)] ## line 7164 ##
sage: simplex = Polyhedron(v); simplex ## line 7165 ##
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 5 vertices
sage: len(simplex.integral_points()) ## line 7167 ##
49
sage: P = 1/10*polytopes.hypercube(14) ## line 7172 ##
sig_error() without sig_on()

----------------------------------------------------------------------
sage -t --long src/sage/geometry/polyhedron/base.py  # Killed due to abort
----------------------------------------------------------------------

Change History (59)

comment:1 Changed 2 years ago by slabbe

  • Summary changed from doctest killed due to abord in geometry/polyhedron/base.py to doctest killed due to abort in geometry/polyhedron/base.py

comment:2 Changed 2 years ago by slabbe

On the same machine, the following works, but takes long time

sage: %time P = 1/10*polytopes.hypercube(14)
CPU times: user 8.08 s, sys: 76 ms, total: 8.16 s
Wall time: 8.15 s

is it normal that it takes soo long?

comment:3 Changed 2 years ago by slabbe

  • Description modified (diff)

comment:4 Changed 2 years ago by slabbe

  • Cc mkoeppe jplabbe added

comment:5 follow-up: Changed 2 years ago by gh-kliem

Is there a particular reason for testing this? Otherwise I would just mark it as not tested.

This points out that the hypercube is set up the wrong way. It takes much much longer to set it up from vertices than from inequalities:

sage: %time P = polytopes.hypercube(14)
CPU times: user 2.73 s, sys: 11 ms, total: 2.74 s
Wall time: 2.74 s
sage: %time Q = Polyhedron(ieqs=P.inequalities())
CPU times: user 401 ms, sys: 3.95 ms, total: 405 ms
Wall time: 404 ms

With #28880 we could just provide both Vrepresentation and Hrepresentation whenever possible (for example when dilating). If the backend does not allow setting up from both, then at least the shorter representation will be chosen.

comment:6 in reply to: ↑ 5 Changed 2 years ago by mkoeppe

Replying to gh-kliem:

Is there a particular reason for testing this? Otherwise I would just mark it as not tested.

This is a doctest for the integral_points method. The point of the doctest is the following line, which took very long before I implemented a simple rounding improvement. It's fine with me to mark the test "long time" or "not tested".

[...] the hypercube is set up the wrong way. It takes much much longer to set it up from vertices than from inequalities: [...] With #28880 we could just provide both Vrepresentation and Hrepresentation whenever possible (for example when dilating). If the backend does not allow setting up from both, then at least the shorter representation will be chosen.

Yes, that would be the best fix for the hypercube.

comment:7 Changed 2 years ago by gh-kliem

Setting up the hypercube with Hrep will involve shuffling of vertices.

I would like to wait with this until #28646 is through.

comment:8 Changed 2 years ago by embray

  • Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

comment:9 Changed 22 months ago by gh-kliem

  • Dependencies set to #29198

comment:10 follow-up: Changed 22 months ago by gh-kliem

  • Dependencies changed from #29198 to #29198, #29200

Once both #29198 and #29200 are done, this should be fine.

comment:11 Changed 21 months ago by jipilab

  • Cc jipilab added; jplabbe removed

comment:12 in reply to: ↑ 10 Changed 21 months ago by slabbe

Replying to gh-kliem:

Once both #29198 and #29200 are done, this should be fine.

I tested with both #29198 and #29200. The line P = 1/10*polytopes.hypercube(14) now seems ok.

But my computer still fails testing that file later on possibly around line 9198... Strange...

...
sage: P = Polyhedron(V) ## line 9066 ##
sage: P.affine_hull() ## line 9067 ##
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 6 vertices
sage: P.affine_hull(orthonormal=True) ## line 9069 ##
sage: P.affine_hull(orthonormal=True, extend=True) ## line 9073 ##
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 6 vertices
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 9075 ##
0
sage: P = polytopes.cube() ## line 9139 ##
sage: P = Polyhedron(vertices=[[1, 0], [0, 1]]) ## line 9146 ##
sage: P = Polyhedron(ambient_dim=2, vertices=[]) ## line 9155 ##
sage: P = Polyhedron(vertices=[[1, 0], [0, 1]], rays=[[1, 0]]) ## line 9162 ##
sage: P = Polyhedron(vertices=[[1, 0], [0, 1]], lines=[[1, 0]]) ## line 9175 ##
sage: P = polytopes.dodecahedron(); P ## line 9188 ##
A 3-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^3 defined as the convex hull of 20 vertices
sage: P = polytopes.dodecahedron(exact=False); P ## line 9198 ##
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 20 vertices
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 9206 ##
0

**********************************************************************
----------------------------------------------------------------------
sage -t --long src/sage/geometry/polyhedron/base.py  # Bad exit: 1
----------------------------------------------------------------------
Version 1, edited 21 months ago by slabbe (previous) (next) (diff)

comment:13 Changed 21 months ago by gh-kliem

Is it possible that your run has very little memory available?

I can get the tests to pass even with a memorylimit of 1400 MB. However, there are many obvious ways to reduce the memory usage, especially in this specific test:

  • Set up the hypercube with a tuple instead of a list of vertices. (Iterator doesn't work, we need to compare the length of Vrep and Hrep).
  • Set up dilation with a tuple of vertices instead of a list of vertices.
  • Use backend field instead of ppl in this specific test (it seems that polyhedra with backend ppl are pretty large objects compared to field).

comment:14 Changed 21 months ago by gh-kliem

  • Authors set to Jonathan Kliem
  • Branch set to public/28866
  • Commit set to b4498366a92cefa30f99424bcf919c7202e4c746
  • Status changed from new to needs_review

Does this solve the problem?


New commits:

b449836attempt to reduce memory usage of doctest

comment:15 Changed 20 months ago by slabbe

With the current branch, sage -t --long --memlimit=3400 src/sage/geometry/polyhedron/base.py return a Bad exit and setting --memlimit=3500 returns [1485 tests, 24.67 s] All tests passed! So it seems testing the file uses somewhere between 3400 and 3500 MB. On my machine, the default --memlimit is 3300 MB which explains the issue.

sage -t --help

gives:

Usage: sage -t [options] filenames

Options:

...

  -m MEMLIMIT, --memlimit=MEMLIMIT
                        maximum virtual memory to allow each test process, in
                        megabytes; no limit if zero or less, but tests tagged
                        "optional - memlimit" are skipped if no limit is set
                        (default: 3300 MB)

What is the default memlimit on your machine?

Last edited 20 months ago by slabbe (previous) (diff)

comment:16 Changed 20 months ago by slabbe

  • Description modified (diff)

For comparison, I updated the description of the ticket with info about memlimit (3600 is ok, but 3500 fails on my machine on the latest develop version 9.1.beta9).

comment:17 Changed 20 months ago by slabbe

Can this be related to the optional packages I have installed?

Using --optional=4ti2,build,cbc,ccache,cryptominisat,dochtml,dot2tex,e_antic,
glucose,latte_int,lidia,lrslib,memlimit,normaliz,notedown,openssl,
pandoc_attributes,pycosat,pynormaliz,rst2ipynb,sage,
sage_numerical_backends_coin,sage_numerical_backends_cplex,
sage_numerical_backends_gurobi

On a another machine, I am able to run the test with --memlimit=2900 but not with --memlimit=2800. That other machine have the following optional packages installed:

Using --optional=4ti2,build,cbc,ccache,cryptominisat,dochtml,dot2tex,e_antic,
flask,flask_autoindex,flask_babel,flask_oldsessions,flask_openid,flask_silk,
fricas,glucose,latte_int,lidia,lrslib,memlimit,normaliz,notedown,openssl,
pandoc_attributes,pycosat,pynormaliz,python2,python_openid,rst2ipynb,sage,
sagenb,speaklater,twisted
Last edited 20 months ago by slabbe (previous) (diff)

comment:18 follow-up: Changed 20 months ago by gh-kliem

As far as I know the default is the same everywhere. 3300MB. As already mentioned the following passes (also on 9.1.beta9):

sage -t --long --memlimit=1400 src/sage/geometry/polyhedron/base.py

So maybe that is not an issue of polyhedron/base.py, but that your sage eats up memory at startup.

comment:19 in reply to: ↑ 18 Changed 20 months ago by slabbe

So maybe that is not an issue of polyhedron/base.py, but that your sage eats up memory at startup.

Yes, but I get that issue only for that file.

comment:20 follow-up: Changed 20 months ago by gh-kliem

The other thing you could try is doing a garbage collection somewhere along the way in the doctests. I don't know, if that would make a difference. One could hide this somewhere in some TESTS section.

comment:21 Changed 20 months ago by slabbe

Removing the doctest on a clean develop branch as follows allows me to make --memlimit=3500 to pass but --memlimit=3400 is not enough. So, this doctest is not the bigest issue in that file.

  • src/sage/geometry/polyhedron/base.py

    diff --git a/src/sage/geometry/polyhedron/base.py b/src/sage/geometry/polyhedron/base.py
    index c2e114a..7f3f4e7 100644
    a b class Polyhedron_base(Element): 
    79457945
    79467946        A case where rounding in the right direction goes a long way::
    79477947
    7948             sage: P = 1/10*polytopes.hypercube(14)  # long time
    7949             sage: P.integral_points()  # long time
     7948            sage: P = 1/10*polytopes.hypercube(14)  # long time   # not tested
     7949            sage: P.integral_points()  # long time                # not tested
    79507950            ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),)
    79517951
    79527952        Finally, the 3-d reflexive polytope number 4078::

comment:22 in reply to: ↑ 20 ; follow-up: Changed 20 months ago by slabbe

Replying to gh-kliem:

The other thing you could try is doing a garbage collection somewhere along the way in the doctests. I don't know, if that would make a difference. One could hide this somewhere in some TESTS section.

This seems to work! I added one at one place and I do not get the bad exit anymore. I will report something in a few minutes.

comment:23 in reply to: ↑ 22 Changed 20 months ago by slabbe

This seems to work!

It worked the first time (no Bad exit, only a bunch of memory errors), but I never was able to reproduce it. Adding a bunch of import gc;gc.collect() does not make a difference.

Last edited 20 months ago by slabbe (previous) (diff)

comment:24 Changed 20 months ago by gh-kliem

Then I guess the only thing one could do is work through the file and reduce memory usage in doctests (or in general) wherever this seems to be a problem.

comment:25 Changed 20 months ago by slabbe

It would be nice if there would exist something like

  --warn-long           warn if tests take more time than SECONDS

for memory.

comment:26 Changed 20 months ago by gh-kliem

Well, but as we already found out, this is difficult to estimate.

Anyway, it's a good project either way to reduce memory usage. So we could do that.

comment:27 Changed 20 months ago by slabbe

I just saw in the doc of sage -t --help that --gc=ALWAYS calls gc.collect() before every test. But even with this option, sage -t --long --gc=ALWAYS src/sage/geometry/polyhedron/base.py finishes with a bad exit. It seems to fail at two different places (the one we know + another).

If I do the following changes:

  • src/sage/geometry/polyhedron/base.py

    diff --git a/src/sage/geometry/polyhedron/base.py b/src/sage/geometry/polyhedron/base.py
    index c2e114a..9911d7f 100644
    a b class Polyhedron_base(Element): 
    79457945
    79467946        A case where rounding in the right direction goes a long way::
    79477947
    7948             sage: P = 1/10*polytopes.hypercube(14)  # long time
    7949             sage: P.integral_points()  # long time
     7948            sage: P = 1/10*polytopes.hypercube(14)  # long time    # not tested
     7949            sage: P.integral_points()  # long time                 # not tested
    79507950            ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),)
    79517951
    79527952        Finally, the 3-d reflexive polytope number 4078::
    class Polyhedron_base(Element): 
    82298229        EXAMPLES::
    82308230
    82318231            sage: quadrangle = Polyhedron(vertices=[(0,0),(1,0),(0,1),(2,3)])
    8232             sage: quadrangle.combinatorial_automorphism_group().is_isomorphic(groups.permutation.Dihedral(4))
     8232            sage: quadrangle.combinatorial_automorphism_group().is_isomorphic(groups.permutation.Dihedral(4)) # not tested
    82338233            True
    82348234            sage: quadrangle.restricted_automorphism_group()
    82358235            Permutation Group with generators [()]

Then, I get All tests passed! for sage -t --long --gc=ALWAYS src/sage/geometry/polyhedron/base.py.

So can we reduce the memory used in those two tests? Maybe reducing 14 to 8 in the first. In the second, I don't know?

(but that will not be enough since sage -t --long src/sage/geometry/polyhedron/base.py return a Bad exit even the the two not tested)

Last edited 20 months ago by slabbe (previous) (diff)

comment:28 follow-ups: Changed 20 months ago by gh-kliem

Have you tried backend field instead, as in the branch of this ticket.

+    sage: P = 1/10*polytopes.hypercube(14, backend='field')
-    sage: P = 1/10*polytopes.hypercube(14)

should reduce memory usage significantly.

It seems wrong that

sage: quadrangle.combinatorial_automorphism_group().is_isomorphic(groups.permutation.Dihedral(4))

should take a lot of memory.

comment:29 in reply to: ↑ 28 Changed 20 months ago by slabbe

Replying to gh-kliem:

Have you tried backend field instead, as in the branch of this ticket.

+    sage: P = 1/10*polytopes.hypercube(14, backend='field')
-    sage: P = 1/10*polytopes.hypercube(14)

should reduce memory usage significantly.

It does not seem sufficient since sage -t --long --gc=ALWAYS src/sage/geometry/polyhedron/base.py works when this test is marked as not tested and return Bad Exit if backend='field' is used.

But sage -t --long --gc=ALWAYS src/sage/geometry/polyhedron/base.py works if I replace the test by sage: P = 1/10*polytopes.hypercube(8, backend='field') or sage: P = 1/10*polytopes.hypercube(8). So reducing from 14 to 8 seems to help more than using 'field' backend.

comment:30 in reply to: ↑ 28 ; follow-up: Changed 20 months ago by slabbe

Replying to gh-kliem:

It seems wrong that

sage: quadrangle.combinatorial_automorphism_group().is_isomorphic(groups.permutation.Dihedral(4))

should take a lot of memory.

I agree but this what I obtain:

  • Using 1/10*polytopes.hypercube(8) + using --gc=ALWAYS + marking the quadrangle ... is_isomorphic test as not tested works fine
  • Using 1/10*polytopes.hypercube(8) + using --gc=ALWAYS return a Bad exit with the following message:
sage -t --long src/sage/geometry/polyhedron/base.py
**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 7949, in sage.geometry.polyhedron.base.Polyhedron_base.integral_points
Failed example:
    P.integral_points()  # long time
Expected:
    ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),)
Got:
    ((0, 0, 0, 0, 0, 0, 0, 0),)
**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 8232, in sage.geometry.polyhedron.base.Polyhedron_base.combinatorial_automorphism_group
Failed example:
    quadrangle.combinatorial_automorphism_group().is_isomorphic(groups.permutation.Dihedral(4))
Exception raised:
    Traceback (most recent call last):
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1123, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.base.Polyhedron_base.combinatorial_automorphism_group[1]>", line 1, in <module>
        quadrangle.combinatorial_automorphism_group().is_isomorphic(groups.permutation.Dihedral(Integer(4)))
      File "sage/misc/lazy_import.pyx", line 321, in sage.misc.lazy_import.LazyImport.__getattr__ (build/cythonized/sage/misc/lazy_import.c:3536)
        return getattr(self.get_object(), attr)
      File "sage/misc/lazy_import.pyx", line 188, in sage.misc.lazy_import.LazyImport.get_object (build/cythonized/sage/misc/lazy_import.c:2347)
        return self._get_object()
      File "sage/misc/lazy_import.pyx", line 220, in sage.misc.lazy_import.LazyImport._get_object (build/cythonized/sage/misc/lazy_import.c:2586)
        self._object = getattr(__import__(self._module, {}, {}, [self._name]), self._name)
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/groups/groups_catalog.py", line 105, in <module>
        from sage.groups.lie_gps import catalog as lie
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/groups/lie_gps/catalog.py", line 5, in <module>
        from sage.groups.lie_gps.nilpotent_lie_group import NilpotentLieGroup as Nilpotent
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/groups/lie_gps/nilpotent_lie_group.py", line 23, in <module>
        from sage.manifolds.differentiable.manifold import DifferentiableManifold
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/manifolds/differentiable/manifold.py", line 448, in <module>
        from sage.manifolds.manifold import TopologicalManifold
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/manifolds/manifold.py", line 341, in <module>
        from sage.manifolds.structure import(
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/manifolds/structure.py", line 34, in <module>
        from sage.manifolds.differentiable.manifold_homset import \
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/manifolds/differentiable/manifold_homset.py", line 49, in <module>
        from sage.manifolds.differentiable.integrated_curve import IntegratedCurve
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/manifolds/differentiable/integrated_curve.py", line 123, in <module>
        from scipy.integrate import ode
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/scipy/integrate/__init__.py", line 92, in <module>
        from ._ode import *
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/scipy/integrate/_ode.py", line 92, in <module>
        from . import vode as _vode
    ImportError: /home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/scipy/integrate/vode.cpython-37m-x86_64-linux-gnu.so: failed to map segment from shared object
**********************************************************************
2 items had failures:
   1 of  15 in sage.geometry.polyhedron.base.Polyhedron_base.combinatorial_automorphism_group
   1 of  34 in sage.geometry.polyhedron.base.Polyhedron_base.integral_points
Process DocTestWorker-1:
Traceback (most recent call last):
  File "/home/slabbe/GitBox/sage/local/lib/python3.7/multiprocessing/process.py", line 297, in _bootstrap
    self.run()
  File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 2172, in run
    task(self.options, self.outtmpfile, msgpipe, self.result_queue)
  File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 2525, in __call__
    result_queue.put(result, False)
  File "/home/slabbe/GitBox/sage/local/lib/python3.7/multiprocessing/queues.py", line 87, in put
    self._start_thread()
  File "/home/slabbe/GitBox/sage/local/lib/python3.7/multiprocessing/queues.py", line 170, in _start_thread
    self._thread.start()
  File "/home/slabbe/GitBox/sage/local/lib/python3.7/threading.py", line 847, in start
    _start_new_thread(self._bootstrap, ())
RuntimeError: can't start new thread
    Bad exit: 1
**********************************************************************
Tests run before process (pid=32760) failed:
[...]

Maybe what happens at line 8232 with the quadrangle is just the moment where the memory gets busted. But, then, why when I mark the quadrangle line 8232 as not tested does it suddenly work?

comment:31 in reply to: ↑ 30 Changed 20 months ago by slabbe

Maybe what happens at line 8232 with the quadrangle is just the moment where the memory gets busted. But, then, why when I mark the quadrangle line 8232 as not tested does it suddenly work?

To challenge this hypothesis, I moved the method combinatorial_automorphism_group containing the quadrangle test at the very bottom of the file, and this is what I now get:

**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 9180, in sage.geometry.polyhedron.base.Polyhedron_base.combinatorial_automorphism_group
Failed example:
    quadrangle.combinatorial_automorphism_group().is_isomorphic(groups.permutation.Dihedral(4))
Exception raised:
...
... same ImportError + Bad exit stuff ...
...

so there is something happening with that particular quadrangle line...

comment:32 follow-up: Changed 20 months ago by gh-kliem

Also

+    sage: P = polytopes.hypercube(14, backend='field', intervals=[[-1/10,1/10]]*14)
-    sage: P = 1/10*polytopes.hypercube(14)

should be even better. This avoids creating an the vertices twice.

comment:33 Changed 20 months ago by slabbe

With P = 1/10*polytopes.hypercube(8) and separating the quadrangle line into parts, I get that sage -t --long --gc=ALWAYS src/sage/geometry/polyhedron/base.py works when:

            sage: G = quadrangle.combinatorial_automorphism_group()
            sage: D4 = groups.permutation.Dihedral(4) # not tested
            sage: G.is_isomorphic(D4)                 # not tested

and fails with bad exit when

            sage: G = quadrangle.combinatorial_automorphism_group()
            sage: D4 = groups.permutation.Dihedral(4)
            sage: G.is_isomorphic(D4)                 # not tested

What happens with the part groups.permutation.Dihedral(4) is a mystery for me. Traceback is below:

    D4 = groups.permutation.Dihedral(4)
Exception raised:
    Traceback (most recent call last):
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1123, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.base.Polyhedron_base.combinatorial_automorphism_group[3]>", line 1, in <module>
        D4 = groups.permutation.Dihedral(Integer(4))
      File "sage/misc/lazy_import.pyx", line 321, in sage.misc.lazy_import.LazyImport.__getattr__ (build/cythonized/sage/misc/lazy_import.c:3536)
        return getattr(self.get_object(), attr)
      File "sage/misc/lazy_import.pyx", line 188, in sage.misc.lazy_import.LazyImport.get_object (build/cythonized/sage/misc/lazy_import.c:2347)
        return self._get_object()
      File "sage/misc/lazy_import.pyx", line 220, in sage.misc.lazy_import.LazyImport._get_object (build/cythonized/sage/misc/lazy_import.c:2586)
        self._object = getattr(__import__(self._module, {}, {}, [self._name]), self._name)
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/groups/groups_catalog.py", line 105, in <module>
        from sage.groups.lie_gps import catalog as lie
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/groups/lie_gps/catalog.py", line 5, in <module>
        from sage.groups.lie_gps.nilpotent_lie_group import NilpotentLieGroup as Nilpotent
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/groups/lie_gps/nilpotent_lie_group.py", line 23, in <module>
        from sage.manifolds.differentiable.manifold import DifferentiableManifold
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/manifolds/differentiable/manifold.py", line 448, in <module>
        from sage.manifolds.manifold import TopologicalManifold
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/manifolds/manifold.py", line 341, in <module>
        from sage.manifolds.structure import(
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/manifolds/structure.py", line 34, in <module>
        from sage.manifolds.differentiable.manifold_homset import \
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/manifolds/differentiable/manifold_homset.py", line 49, in <module>
        from sage.manifolds.differentiable.integrated_curve import IntegratedCurve
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/manifolds/differentiable/integrated_curve.py", line 123, in <module>
        from scipy.integrate import ode
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/scipy/integrate/__init__.py", line 92, in <module>
        from ._ode import *
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/scipy/integrate/_ode.py", line 92, in <module>
        from . import vode as _vode
    ImportError: /home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/scipy/integrate/vode.cpython-37m-x86_64-linux-gnu.so: failed to map segment from shared object

comment:34 in reply to: ↑ 32 Changed 20 months ago by slabbe

Replying to gh-kliem:

Also

+    sage: P = polytopes.hypercube(14, backend='field', intervals=[[-1/10,1/10]]*14)
-    sage: P = 1/10*polytopes.hypercube(14)

should be even better. This avoids creating an the vertices twice.

It does not help on my machine when running sage -bt --long --gc=ALWAYS src/sage/geometry/polyhedron/base.py:

sage -t --long src/sage/geometry/polyhedron/base.py
**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 7948, in sage.geometry.polyhedron.base.Polyhedron_base.integral_points
Failed example:
    P = 1/10*polytopes.hypercube(14, backend='field', intervals=[[-1/10,1/10]]*14)  # long time
Exception raised:
    Traceback (most recent call last):
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1123, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.base.Polyhedron_base.integral_points[12]>", line 1, in <module>
        P = Integer(1)/Integer(10)*polytopes.hypercube(Integer(14), backend='field', intervals=[[-Integer(1)/Integer(10),Integer(1)/Integer(10)]]*Integer(14))  # long time
      File "sage/rings/rational.pyx", line 2414, in sage.rings.rational.Rational.__mul__ (build/cythonized/sage/rings/rational.c:20776)
        return coercion_model.bin_op(left, right, operator.mul)
      File "sage/structure/coerce.pyx", line 1201, in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:10056)
        return (<Action>action)._act_(x, y)
    MemoryError
**********************************************************************
[...]
...  and eventually bad exit ...

comment:35 follow-up: Changed 20 months ago by mjo

  • Cc mjo added

So long as we're making micro-optimizations, can the inner lists be turned into tuples, too? E.g.

- ieqs = tuple([0]*(dim+1) for _ in range(2*dim))
+ ieqs = tuple(itertools.repeat(tuple(itertools.repeat(0,dim+1)),2*dim))
- cp = tuple(itertools.product([-1,1], repeat=dim))
+ cp = tuple(itertools.product((-1,1), repeat=dim))
- cp = tuple(itertools.product([0,1], repeat=dim))
+ cp = tuple(itertools.product((0,1), repeat=dim))

It looks like we're looping through a lot of structures twice, too. This pattern repeats itself:

new_inequalities = tuple(f.vector()*one for f in self.inequality_generator())
for f in new_inequalities:
    f[0] *= scalar

The comprehension could be modified to spit out the right thing the first time through, or at the very least we could use map() with a lambda to apply the "multiply the first coordinate by <scalar>" function as the tuple is built.

Last edited 20 months ago by mjo (previous) (diff)

comment:36 Changed 20 months ago by gh-kliem

  • Branch changed from public/28866 to public/28866-reb
  • Commit changed from b4498366a92cefa30f99424bcf919c7202e4c746 to 753c836d140e5ae802d678f0c8f7916f2a2e9952
  • Dependencies #29198, #29200 deleted

New commits:

ba6964fattempt to reduce memory usage of doctest
1ceacb6list -> tuples; tuples -> generators
753c836do not generate unneeded tuple at initialization

comment:37 in reply to: ↑ 35 Changed 20 months ago by gh-kliem

Thanks. I went to generators now.

This has the advantage that ppl doesn't waste time creating a tuple, which it won't need later. Also all we need the input vertices/rays/lines/inequalities/equations to be good for is to be iterable exactly one time. So I would consider it to be a waste creating a tuple for that. Now I'm passing the prefered representation to __init__, which will discard the other one if the backend doesn't support precomputed data.

Anyway, I don't know how much this is really worth it.

Replying to mjo:

So long as we're making micro-optimizations, can the inner lists be turned into tuples, too? E.g.

- ieqs = tuple([0]*(dim+1) for _ in range(2*dim))
+ ieqs = tuple(itertools.repeat(tuple(itertools.repeat(0,dim+1)),2*dim))
- cp = tuple(itertools.product([-1,1], repeat=dim))
+ cp = tuple(itertools.product((-1,1), repeat=dim))
- cp = tuple(itertools.product([0,1], repeat=dim))
+ cp = tuple(itertools.product((0,1), repeat=dim))

It looks like we're looping through a lot of structures twice, too. This pattern repeats itself:

new_inequalities = tuple(f.vector()*one for f in self.inequality_generator())
for f in new_inequalities:
    f[0] *= scalar

The comprehension could be modified to spit out the right thing the first time through, or at the very least we could use map() with a lambda to apply the "multiply the first coordinate by <scalar>" function as the tuple is built.

comment:38 Changed 20 months ago by mjo

It's probably only a small improvement, but anything helps. The new approach LGTM. There's one more [-1,1] list that can be made into a tuple,

diff --git a/src/sage/geometry/polyhedron/library.py b/src/sage/geometry/polyhe$
index 82f96b2d76..03410c1ed8 100644
--- a/src/sage/geometry/polyhedron/library.py
+++ b/src/sage/geometry/polyhedron/library.py
@@ -2980,7 +2980,7 @@ class Polytopes():
         """
         verts = tuple((ZZ**dim).basis())
         verts += tuple(-v for v in verts)
-        ieqs = ((1,) + x for x in itertools.product([-1,1], repeat=dim))
+        ieqs = ((1,) + x for x in itertools.product((-1,1), repeat=dim))
         parent = Polyhedra(ZZ, dim, backend=backend)
         return parent([verts, [], []], [ieqs, []], Vrep_minimal=True, Hrep_min$

but, aside from that, this is probably a good point to commit the improvements and start anew if the doctests cause further problems.

comment:39 Changed 20 months ago by mjo

Oh, and I guess you should add doctests for the two other possible arguments for pref_rep.

comment:40 Changed 20 months ago by git

  • Commit changed from 753c836d140e5ae802d678f0c8f7916f2a2e9952 to 12ecb78f8bfa82ea937922537601b3e695fc762d

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

42ac714fix failing doctests
12ecb78added doctests

comment:41 Changed 20 months ago by mjo

  • Reviewers set to Michael Orlitzky
  • Status changed from needs_review to positive_review

Pending a ptestlong, I'm able to run the polyhedron tests without problem. Thanks!

comment:42 follow-ups: Changed 20 months ago by slabbe

I just checked the most recent branch and

sage -t --long --memlimit=3500 src/sage/geometry/polyhedron/base.py 

now works ok on my machine. But unfortunately, --memlimit=3400 does not (error is raised at the quadrangle line again). But, I guess my computer is an exception?

I would have suggested the following change which is more in the spirit of Python3:

-    new_vertices = map(lambda v : tuple(scalar*x for x in v._vector), self.vertex_generator())
-    new_rays     = map(lambda r : tuple(sign*x   for x in r._vector), self.ray_generator())
+    new_vertices = (tuple(scalar*x for x in v._vector) for v in self.vertex_generator())
+    new_rays     = (tuple(sign*x   for x in r._vector) for r in self.ray_generator())
Last edited 20 months ago by slabbe (previous) (diff)

comment:43 in reply to: ↑ 42 ; follow-up: Changed 20 months ago by mjo

ok :(

Replying to slabbe:

I just checked the most recent branch and

sage -t --long --memlimit=3500 src/sage/geometry/polyhedron/base.py 

now works ok on my machine. But unfortunately, --memlimit=3400 does not (error is raised at the quadrangle line again). But, I guess my computer is an exception?

Yeah, but this still shouldn't be this hard to figure out. How much RAM does your system have and is swap enabled? I'm able to go as low as 1300 on my ancient Phenom II with 6GB of RAM:

$ sage -t --long --memlimit=1300 src/sage/geometry/polyhedron/base.py 
too many failed tests, not using stored timings
Running doctests with ID 2020-04-08-10-52-30-009fba13.
Git branch: public/28866-reb
Using --optional=build,dochtml,memlimit,sage
Doctesting 1 file.
sage -t --long src/sage/geometry/polyhedron/base.py
    [1439 tests, 117.73 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 118.5 seconds
    cpu time: 95.5 seconds
    cumulative wall time: 117.7 seconds

One difference that I suspect between you and (Jonathan and I) is the optimization flags passed to the compiler while building sage. I think we both use -march=native for everything, and you could be getting some SPKG built non-optimally to the point where one of these methods wastes a ton of memory. If you're up for it, you could try

$ export CFLAGS="-O2 -march=native" CXXFLAGS="-O2 -march=native" FCFLAGS="-O2 -march=native"
$ git clean -x -f -d
$ ./bootstrap
$ make build

to wipe your sage installation and rebuild everything from scratch with those optimization flags. That may improve your memory usage (and would be another reason to hope for Jonathan's -march=native branch to get merged), but it's admittedly a stab in the dark.

I would have suggested the following change...

That looks sensible if you want to add it.

comment:44 Changed 20 months ago by mjo

There are also a lot of doctest examples in src/sage/geometry/polyhedron/base.py that could be split into separate chunks with :: rather than grouped together, sharing a context. That may help encourage garbage collection of the objects defined in earlier examples.

comment:45 in reply to: ↑ 42 Changed 20 months ago by gh-kliem

Replying to slabbe:

I just checked the most recent branch and

sage -t --long --memlimit=3500 src/sage/geometry/polyhedron/base.py 

now works ok on my machine. But unfortunately, --memlimit=3400 does not (error is raised at the quadrangle line again). But, I guess my computer is an exception?

I would have suggested the following change which is more in the spirit of Python3:

-    new_vertices = map(lambda v : tuple(scalar*x for x in v._vector), self.vertex_generator())
-    new_rays     = map(lambda r : tuple(sign*x   for x in r._vector), self.ray_generator())
+    new_vertices = (tuple(scalar*x for x in v._vector) for v in self.vertex_generator())
+    new_rays     = (tuple(sign*x   for x in r._vector) for r in self.ray_generator())

I agree, you can go ahead and push that change.

comment:46 Changed 20 months ago by mjo

More wild speculation: this is also the only module I've seen that has doctests within a WARNING block. There is a tiny chance that a series of unfortunate events leads to those doctests not being GC'ed. But that still wouldn't explain why you're seeing different results than we are.

comment:47 Changed 20 months ago by git

  • Commit changed from 12ecb78f8bfa82ea937922537601b3e695fc762d to 93237d608f4a7768e5e206b9cded35c6b801b421
  • Status changed from positive_review to needs_review

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

93237d628866: avoid map of a lambda function

comment:48 in reply to: ↑ 43 ; follow-up: Changed 20 months ago by slabbe

Yeah, but this still shouldn't be this hard to figure out. How much RAM does your system have and is swap enabled?

I'm sorry, can you teach me how I can figure this out?

One difference that I suspect between you and (Jonathan and I) is the optimization flags passed to the compiler while building sage. I think we both use -march=native for everything, and you could be getting some SPKG built non-optimally to the point where one of these methods wastes a ton of memory. If you're up for it, you could try

Ok, I will test that.

comment:49 in reply to: ↑ 48 ; follow-up: Changed 20 months ago by mjo

Replying to slabbe:

I'm sorry, can you teach me how I can figure this out?

There's probably nothing unusual here, but:

$ cat /proc/meminfo

should show the relevant stuff on linux. On mac or windows I would have to resort to google.

comment:50 in reply to: ↑ 49 ; follow-up: Changed 20 months ago by slabbe

$ cat /proc/meminfo

should show the relevant stuff on linux. On mac or windows I would have to resort to google.

This is the output on the machine having trouble:

$ cat /proc/meminfo
MemTotal:       16356316 kB
MemFree:         3011884 kB
MemAvailable:   14369868 kB
Buffers:         1356356 kB
Cached:          7550684 kB
SwapCached:         1856 kB
Active:          4893152 kB
Inactive:        5302360 kB
Active(anon):     398700 kB
Inactive(anon):   971972 kB
Active(file):    4494452 kB
Inactive(file):  4330388 kB
Unevictable:          48 kB
Mlocked:              48 kB
SwapTotal:       2928636 kB
SwapFree:        2868372 kB
[...]

comment:51 Changed 20 months ago by slabbe

(Note that when I pushed the branch on the ticket, it automatically set the ticket to needs_review again (it seems to be a new feature), so I let you review my commit)

comment:52 Changed 20 months ago by gh-kliem

  • Reviewers changed from Michael Orlitzky to Sébastien Labbé, Michael Orlitzky
  • Status changed from needs_review to positive_review

comment:53 in reply to: ↑ 50 Changed 20 months ago by mjo

Replying to slabbe:

This is the output on the machine having trouble:

Nothing unusual.

Another thing I thought of: if recompiling everything with -march=native -O2 doesn't help... maybe there's some system package being used that was built without optimizations...

$ grep 'will use system' config.log

should show which which system packages are being used.

comment:54 Changed 20 months ago by vbraun

  • Status changed from positive_review to needs_work

On Python 2:

File "src/sage/geometry/polyhedron/base.py", line 160, in sage.geometry.polyhedron.base.Polyhedron_base.__init__
Failed example:
    p = Polyhedron_field(parent, Vrep, 'nonsense',
                         Vrep_minimal=True, Hrep_minimal=True, pref_rep='Vrep')
Expected:
    Traceback (most recent call last):
    ...
    TypeError: _init_Hrepresentation() takes 3 positional arguments but 9 were given
Got:
    <BLANKLINE>
    Traceback (most recent call last):
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1123, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.base.Polyhedron_base.__init__[13]>", line 2, in <module>
        Vrep_minimal=True, Hrep_minimal=True, pref_rep='Vrep')
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.py", line 172, in __init__
        self._init_from_Vrepresentation_and_Hrepresentation(Vrep, Hrep)
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/geometry/polyhedron/backend_field.py", line 163, in _init_from_Vrepresentation_and_Hrepresentation
        self._init_Hrepresentation(*Hrep)
    TypeError: _init_Hrepresentation() takes exactly 3 arguments (9 given)
**********************************************************************
1 item had failures:
   1 of  15 in sage.geometry.polyhedron.base.Polyhedron_base.__init__
    [1443 tests, 1 failure, 37.42 s]
----------------------------------------------------------------------
sage -t --long src/sage/geometry/polyhedron/base.py  # 1 doctest failed
----------------------------------------------------------------------

comment:55 Changed 20 months ago by git

  • Commit changed from 93237d608f4a7768e5e206b9cded35c6b801b421 to c701c31a5937138ff67895d43269205870de150b

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

ab4f49apython2 doctests
c701c31Merge branch 'public/28866-reb' of git://trac.sagemath.org/sage into public/28866-reb

comment:56 Changed 20 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:57 Changed 20 months ago by mkoeppe

  • Reviewers changed from Sébastien Labbé, Michael Orlitzky to Sébastien Labbé, Michael Orlitzky, Matthias Koeppe
  • Status changed from needs_review to positive_review

Looks good to me

comment:58 Changed 20 months ago by vbraun

  • Branch changed from public/28866-reb to c701c31a5937138ff67895d43269205870de150b
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:59 Changed 18 months ago by gh-kliem

  • Commit c701c31a5937138ff67895d43269205870de150b deleted

I introduced a bug in this ticket: The double description for intervals is completely wrong.

Please review #29904.

Note: See TracTickets for help on using tickets.