Opened 7 years ago
Closed 7 years ago
#18241 closed enhancement (fixed)
Great speedup in polytopes construction with generic backend
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage6.7 
Component:  geometry  Keywords:  
Cc:  vbraun, ncohen  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  c5b15bf (Commits, GitHub, GitLab)  Commit:  c5b15bf0297ee8626e9dcadf75a325aad49673af 
Dependencies:  #18215  Stopgaps: 
Description (last modified by )
Construction of polytopes with number field coordinates are very slow. There are several reasons for that:
 quadratic number field element hash is slow (already solved in #18215)
NumberField.__cmp__
is slow we can avoid many useless copies and recomputations in the algorithm
Vrep2Hrep
andHrep2Vrep
After applying the branch the speedup is really cool. Using polyhedron_test.py I got
Before
sage: %runfile polyhedron_test.py sage: %time gr = great_rhombicuboctahedron() CPU times: user 4.66 s, sys: 24 ms, total: 4.68 s Wall time: 4.66 s
After
sage: %runfile polyhedron_test.py sage: %time gr = great_rhombicuboctahedron() CPU times: user 292 ms, sys: 28 ms, total: 320 ms Wall time: 306 ms
(But I am still not able to build the 600cell)
Modifications with the branch:
 In the double description file
 use
itertools
instead of whateversage/combinat/*
 use
base_ring.zero()
andbase_ring.one()
instead of the Python integer0
and1
. That prevents many coercions.  make the method
add_inequality
so that the object is changed inplace instead of returning a new instance. I had to change the type of the attribute fromtuples
tolists
.  add a cache for matrix spaces (see #18231). These are the methods
_matrix_space
and_matrix
 implement a cache for the method
.zero_set
(note that this was needed because the object is no more immutable,self.A
will grow inadd_inequality
)
 use
 Start with a trivial case in
NumberField.__cmp__
.
Attachments (1)
Change History (28)
comment:1 Changed 7 years ago by
 Branch set to u/vdelecroix/18241
 Commit set to 99c670831a4064246d2cdb2aec32a3e51fd4fd7c
 Description modified (diff)
 Status changed from new to needs_review
Changed 7 years ago by
comment:2 Changed 7 years ago by
 Description modified (diff)
comment:3 followup: ↓ 4 Changed 7 years ago by
Could you say in the ticket's description what the branch does?
Every single thing that you do without explanation, the reviewer has to figure out from the diff file.
comment:4 in reply to: ↑ 3 Changed 7 years ago by
 Description modified (diff)
Replying to ncohen:
Could you say in the ticket's description what the branch does?
Every single thing that you do without explanation, the reviewer has to figure out from the diff file.
done!
comment:5 followup: ↓ 6 Changed 7 years ago by
 Status changed from needs_review to needs_work
Looks like your mutable object is also hashable
sage: DD.__hash__() 1042963791458606606 sage: DD.add_inequality(vector([1,0,0])) sage: DD.__hash__() 1000165618804906370
comment:6 in reply to: ↑ 5 Changed 7 years ago by
Replying to ncohen:
Looks like your mutable object is also hashable
sage: DD.__hash__() 1042963791458606606 sage: DD.add_inequality(vector([1,0,0])) sage: DD.__hash__() 1000165618804906370
F****** Sage objects!
cdef class SageObject: ... def __hash__(self): return hash(self.__repr__())
comment:7 Changed 7 years ago by
Unless all SageObject? must be immutable, I guess that it should be removed (in another ticket that will become another war)
comment:8 followup: ↓ 9 Changed 7 years ago by
Actually, no...
sage: class A: ....: pass sage: hash(A()) 9223363253024015589
We should probably make SageObject.__hash__
raise a NotImplementedError
comment:9 in reply to: ↑ 8 Changed 7 years ago by
Replying to ncohen:
Actually, no...
sage: class A: ....: pass sage: hash(A()) 9223363253024015589We should probably make
SageObject.__hash__
raise aNotImplementedError
Or
class A: __hash__ = None
comment:10 Changed 7 years ago by
 Commit changed from 99c670831a4064246d2cdb2aec32a3e51fd4fd7c to 3c573aef7df1659213bec2614f9ba2b788c1f4fa
Branch pushed to git repo; I updated commit sha1. New commits:
3c573ae  Trac 18241: simpler import + remove SageObject inheritance

comment:11 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:12 followup: ↓ 13 Changed 7 years ago by
About this branch:
zero_set
: why don't you just callDD.zero_set.clear_cache()
instead of rewriting the caching mechanism? If you do want to keep thisself.cache
please make the name more specific.
A_matrix
: returns a pointer toward a mutable internal object.
 Err
Add an inequality to the double description with the inequality ``a`` added.
 I do not like this '_matrix' function very much. Its name is not very clear (
matrix_from_cached_vector_space
?) but what about just doing this 'if' twice (it is called twice)?
Nathann
comment:13 in reply to: ↑ 12 ; followup: ↓ 14 Changed 7 years ago by
Replying to ncohen:
About this branch:
zero_set
: why don't you just callDD.zero_set.clear_cache()
instead of rewriting the caching mechanism? If you do want to keep thisself.cache
please make the name more specific.
Nope. If you call the function with the same ray
argument you do not want to recompute it from scratch.
 I do not like this '_matrix' function very much. Its name is not very clear (
matrix_from_cached_vector_space
?) but what about just doing this 'if' twice (it is called twice)?
Me neither. That's why I opened #18231. The function just constructs a matrix, why the name is badly chosen? You will get the very same answer as calling matrix(self.problem.base_ring(), data)
. Except that it is faster. What about .build_matrix
and .build_matrix_space
?
I do not understand you remark about the if
.
comment:14 in reply to: ↑ 13 Changed 7 years ago by
Hello,
Nope. If you call the function with the same
ray
argument you do not want to recompute it from scratch.
Oh, okay. Then change the cache's name please
 I do not like this '_matrix' function very much. Its name is not very clear (
matrix_from_cached_vector_space
?) but what about just doing this 'if' twice (it is called twice)?Me neither. That's why I opened #18231.
Then should it be really fixed inside of this class? Or do we keep this code as it is and try to solve the #18231 instead.
The function just constructs a matrix, why the name is badly chosen? You will get the very same answer as calling
matrix(self.problem.base_ring(), data)
. Except that it is faster.
Precisely because the name does not reflect the difference. matrix_from_cached_vector_space
does.
What about
.build_matrix
and.build_matrix_space
?
I hate this class already.
I do not understand you remark about the
if
.
Oh. Well, because all that 'matrix' does is a if. If it is not a function of its own, you just have to copy this 'if' around.
Nathann
comment:15 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:16 Changed 7 years ago by
 Commit changed from 3c573aef7df1659213bec2614f9ba2b788c1f4fa to 770ad60c6812e524b6d957b2179bd486e2d3896e
Branch pushed to git repo; I updated commit sha1. New commits:
770ad60  Trac 18241: move code in double_description.py

comment:17 Changed 7 years ago by
 Status changed from needs_work to needs_review
 I get rid of
def _matrix
and moveProblem._matrix_space > DoubleDescription.matrix_space
.  I changed
.cache > .zero_set_cache
 I modified the output of
zero_set
to return Python sets instead of tuple (since the most important operation on them is the intersection)
Needs review again.
comment:18 followup: ↓ 20 Changed 7 years ago by
Yoooooooooooooo !
Looks good, almost good to go. Just two things:
 This sentence repeats itself
Add an inequality to the double description with the inequality ``a`` added.
 What is the difference between those two lines?
lines = self._linear_subspace.matrix().rows() lines = self._linear_subspace.basis_matrix().rows()
Nathann
comment:19 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:20 in reply to: ↑ 18 Changed 7 years ago by
Hello,
Replying to ncohen:
 What is the difference between those two lines?
lines = self._linear_subspace.matrix().rows() lines = self._linear_subspace.basis_matrix().rows()
linear_subspace.matrix
calls linear_subspace.basis_matrix
. Having aliases is cool, but avoiding using them is cooler ;)
Vincent
comment:21 Changed 7 years ago by
 Commit changed from 770ad60c6812e524b6d957b2179bd486e2d3896e to c5b15bf0297ee8626e9dcadf75a325aad49673af
comment:22 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:23 followup: ↓ 24 Changed 7 years ago by
 Status changed from needs_review to positive_review
Okayyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
comment:24 in reply to: ↑ 23 Changed 7 years ago by
Replying to ncohen:
Okayyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
Great! Thanks. It becomes reasonable to start using the generic backend.
Next step: avoid the recomputation of vertices! The algorithm is currently
INPUT: vertices OUTPUT: (vertices, hyperplanes) ALGO: 1. compute hyperplanes from vertices (with no redundancy) 2. recompute vertices from hyperplanes (with no redundancy) 3. return (vertices, hyperplanes)
And it is precisely step 2 which takes an infinite amount of time for the 600cell!
comment:26 Changed 7 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_work to positive_review
comment:27 Changed 7 years ago by
 Branch changed from u/vdelecroix/18241 to c5b15bf0297ee8626e9dcadf75a325aad49673af
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Trac 18215: Faster hash for quadratic number fields
Trac 18241: better double description (Hrep2Vrep, Vrep2Hrep)
Trac 18241: tiny modifs in constructor/parent
Trac 18241: trivial case in NumberField.__cmp__