Closed seblabbe closed 4 years ago
seblabbe
commented
4 years ago 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 sis it normal that it takes soo long?
seblabbe
commented
4 years ago Description changed:
---
+++
@@ -8,6 +8,42 @@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:
+...
Killed due to abort
kliem
commented
4 years ago 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 msWith #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
commented
4 years ago 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
commented
4 years ago Setting up the hypercube with Hrep will involve shuffling of vertices.
I would like to wait with this until #28646 is through.
embray
commented
4 years ago Ticket retargeted after milestone closed
kliem
commented
4 years ago Dependencies: #29198
kliem
commented
4 years ago Once both #29198 and #29200 are done, this should be fine.
kliem
commented
4 years ago Changed dependencies from #29198 to #29198, #29200
seblabbe
commented
4 years ago 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
----------------------------------------------------------------------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:
field instead of ppl in this specific test (it seems that polyhedra with backend ppl are pretty large objects compared to field).kliem
commented
4 years ago Does this solve the problem?
New commits:
b449836 | attempt to reduce memory usage of doctest |
kliem
commented
4 years ago Branch: public/28866
kliem
commented
4 years ago Author: Jonathan Kliem
seblabbe
commented
4 years ago 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 --helpgives:
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
commented
4 years ago 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
commented
4 years ago Description changed:
---
+++
@@ -1,3 +1,28 @@
+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
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_gurobiOn 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,twistedAs 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.pySo maybe that is not an issue of polyhedron/base.py, but that your sage eats up memory at startup.
seblabbe
commented
4 years ago 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
commented
4 years ago 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.
seblabbe
commented
4 years ago 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.
diff --git a/src/sage/geometry/polyhedron/base.py b/src/sage/geometry/polyhedron/base.py
index c2e114a..7f3f4e7 100644
--- a/src/sage/geometry/polyhedron/base.py
+++ b/src/sage/geometry/polyhedron/base.py
@@ -7945,8 +7945,8 @@ class Polyhedron_base(Element):
A case where rounding in the right direction goes a long way::
- sage: P = 1/10*polytopes.hypercube(14) # long time
- sage: P.integral_points() # long time
+ sage: P = 1/10*polytopes.hypercube(14) # long time # not tested
+ sage: P.integral_points() # long time # not tested
((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),)
Finally, the 3-d reflexive polytope number 4078::Replying to @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
TESTSsection.
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.
seblabbe
commented
4 years ago 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.
kliem
commented
4 years ago 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.
seblabbe
commented
4 years ago It would be nice if there would exist something like
--warn-long warn if tests take more time than SECONDSfor memory.
kliem
commented
4 years ago 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.
seblabbe
commented
4 years ago 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:
diff --git a/src/sage/geometry/polyhedron/base.py b/src/sage/geometry/polyhedron/base.py
index c2e114a..9911d7f 100644
--- a/src/sage/geometry/polyhedron/base.py
+++ b/src/sage/geometry/polyhedron/base.py
@@ -7945,8 +7945,8 @@ class Polyhedron_base(Element):
A case where rounding in the right direction goes a long way::
- sage: P = 1/10*polytopes.hypercube(14) # long time
- sage: P.integral_points() # long time
+ sage: P = 1/10*polytopes.hypercube(14) # long time # not tested
+ sage: P.integral_points() # long time # not tested
((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),)
Finally, the 3-d reflexive polytope number 4078::
@@ -8229,7 +8229,7 @@ class Polyhedron_base(Element):
EXAMPLES::
sage: quadrangle = Polyhedron(vertices=[(0,0),(1,0),(0,1),(2,3)])
- sage: quadrangle.combinatorial_automorphism_group().is_isomorphic(groups.permutation.Dihedral(4))
+ sage: quadrangle.combinatorial_automorphism_group().is_isomorphic(groups.permutation.Dihedral(4)) # not tested
True
sage: quadrangle.restricted_automorphism_group()
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)
kliem
commented
4 years ago 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.
seblabbe
commented
4 years ago Replying to @kliem:
Have you tried backend
fieldinstead, 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.
seblabbe
commented
4 years ago Replying to @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:
1/10*polytopes.hypercube(8) + using --gc=ALWAYS + marking the quadrangle ... is_isomorphic test as not tested works fine1/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?
seblabbe
commented
4 years ago Maybe what happens at line
8232with the quadrangle is just the moment where the memory gets busted. But, then, why when I mark the quadrangle line8232as 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...
kliem
commented
4 years ago 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.
seblabbe
commented
4 years ago 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 testedand fails with bad exit when
sage: G = quadrangle.combinatorial_automorphism_group()
sage: D4 = groups.permutation.Dihedral(4)
sage: G.is_isomorphic(D4) # not testedWhat 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 objectReplying to @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 ...
orlitzky
commented
4 years ago 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] *= scalarThe 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
kliem
commented
4 years ago kliem
commented
4 years ago Changed dependencies from #29198, #29200 to none
kliem
commented
4 years ago Changed branch from public/28866 to public/28866-reb
kliem
commented
4 years ago 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 @orlitzky:
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] *= scalarThe 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" function as the tuple is built.
orlitzky
commented
4 years ago 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.
orlitzky
commented
4 years ago Oh, and I guess you should add doctests for the two other possible arguments for pref_rep.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313
commented
4 years ago 7ed8c4ca-6d56-4ae9-953a-41e42b4ed313
commented
4 years ago orlitzky
commented
4 years ago Reviewer: Michael Orlitzky
orlitzky
commented
4 years ago Pending a ptestlong, I'm able to run the polyhedron tests without problem. Thanks!
seblabbe
commented
4 years ago 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())ok :(
Replying to @seblabbe:
I just checked the most recent branch and
sage -t --long --memlimit=3500 src/sage/geometry/polyhedron/base.pynow works ok on my machine. But unfortunately,
--memlimit=3400does not (error is raised at thequadrangleline 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 secondsOne 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 buildto 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.
On a clean develop branch running
SageMath version 9.1.beta9, Release Date: 2020-03-29, I get:while
or
gives
CC: @mkoeppe @jplab @orlitzky
Component: geometry
Author: Jonathan Kliem
Branch:
c701c31Reviewer: Sébastien Labbé, Michael Orlitzky, Matthias Koeppe
Issue created by migration from https://trac.sagemath.org/ticket/28866