Opened 23 months ago

Last modified 16 months ago

#28866 closed defect

doctest killed due to abort in geometry/polyhedron/base.py — at Version 16

Reported by: slabbe Owned by:
Priority: major Milestone: sage-9.1
Component: geometry Keywords:
Cc: mkoeppe, jipilab, mjo Merged in:
Authors: Jonathan Kliem Reviewers:
Report Upstream: N/A Work issues:
Branch: public/28866 (Commits, GitHub, GitLab) Commit: b4498366a92cefa30f99424bcf919c7202e4c746
Dependencies: #29198, #29200 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 (16)

comment:1 Changed 23 months 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 23 months 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 23 months ago by slabbe

  • Description modified (diff)

comment:4 Changed 23 months ago by slabbe

  • Cc mkoeppe jplabbe added

comment:5 follow-up: Changed 23 months 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 23 months 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 22 months 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 22 months ago by embray

  • Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

comment:9 Changed 20 months ago by gh-kliem

  • Dependencies set to #29198

comment:10 follow-up: Changed 20 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 20 months ago by jipilab

  • Cc jipilab added; jplabbe removed

comment:12 in reply to: ↑ 10 Changed 20 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. I now get a different error message (Memory error):

Doctesting 1 file.
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)  # 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))  # 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)
      File "sage/categories/action.pyx", line 438, in sage.categories.action.PrecomposedAction._act_ (build/cythonized/sage/categories/action.c:6958)
        return self._action._act_(g, x)
      File "sage/structure/coerce_actions.pyx", line 153, in sage.structure.coerce_actions.ActedUponAction._act_ (build/cythonized/sage/structure/coerce_actions.c:4479)
        return (<Element>x)._acted_upon_(g, not self._is_left)
      File "sage/structure/element.pyx", line 927, in sage.structure.element.Element._acted_upon_ (build/cythonized/sage/structure/element.c:8608)
        cpdef _acted_upon_(self, x, bint self_on_left):
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py", line 4616, in _acted_upon_
        return self.dilation(actor)
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py", line 4442, in dilation
        new_vertices = [ list(scalar*v.vector()) for v in self.vertex_generator() ]
      File "/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py", line 4442, in <listcomp>
        new_vertices = [ list(scalar*v.vector()) for v in self.vertex_generator() ]
    MemoryError
**********************************************************************

and the traceback that follows continues further than earlier:

...
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
----------------------------------------------------------------------
Last edited 20 months ago by slabbe (previous) (diff)

comment:13 Changed 20 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 19 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 19 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 19 months ago by slabbe (previous) (diff)

comment:16 Changed 19 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).

Note: See TracTickets for help on using tickets.