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

[seblabbe]

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

CC: @mkoeppe @jplab @orlitzky

Component: geometry

Author: Jonathan Kliem

Branch: c701c31

Reviewer: Sébastien Labbé, Michael Orlitzky, Matthias Koeppe

Issue created by migration from https://trac.sagemath.org/ticket/28866

[seblabbe]

comment:2

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?

[kliem]

comment:5

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.

[mkoeppe]

comment:6

Replying to @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.

[kliem]

comment:7

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

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

[embray]

comment:8

Ticket retargeted after milestone closed

[kliem]

Dependencies: #29198

[kliem]

comment:10

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

[kliem]

Changed dependencies from #29198 to #29198, #29200

[seblabbe]

comment:12

Replying to @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
----------------------------------------------------------------------

[kliem]

comment:13

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).

[kliem]

comment:14

Does this solve the problem?

---

New commits:

b449836

attempt to reduce memory usage of doctest

[kliem]

Branch: public/28866

[kliem]

Commit: b449836

[kliem]

Author: Jonathan Kliem

[seblabbe]

comment:15

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?

[seblabbe]

comment:16

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).

[seblabbe]

comment:17

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

[kliem]

comment:18

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.

[seblabbe]

comment:19

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.

[kliem]

comment:20

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.

[sagetrac-git]

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

93237d6

28866: avoid map of a lambda function

[seblabbe]

comment:48

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.

[orlitzky]

comment:49

Replying to @seblabbe:

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.

[seblabbe]

comment:50

$ 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
[...]

[seblabbe]

comment:51

(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)

[kliem]

Changed reviewer from Michael Orlitzky to Sébastien Labbé, Michael Orlitzky

[orlitzky]

comment:53

Replying to @seblabbe:

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.

[vbraun]

comment:54

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

[sagetrac-git]

Changed commit from 93237d6 to c701c31

[sagetrac-git]

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

ab4f49a	python2 doctests
c701c31	Merge branch 'public/28866-reb' of git://trac.sagemath.org/sage into public/28866-reb

[mkoeppe]

Changed reviewer from Sébastien Labbé, Michael Orlitzky to Sébastien Labbé, Michael Orlitzky, Matthias Koeppe

[mkoeppe]

comment:57

Looks good to me

[vbraun]

Changed branch from public/28866-reb to c701c31

[kliem]

Changed commit from c701c31 to none

[kliem]

comment:59

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

Please review #29904.