Opened 2 years ago
Closed 20 months ago
#30549 closed enhancement (fixed)
Remove all the bitset access from cython files in combinatorial polyhedron
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.3 
Component:  geometry  Keywords:  combinatorial polyhedron, bitsets 
Cc:  jipilab, ghLaisRast, tscrim  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  82a747d (Commits, GitHub, GitLab)  Commit:  82a747d6fabf5cf8d366851d2dfbcbf7cd57eabc 
Dependencies:  #30529  Stopgaps: 
Description (last modified by )
This goal of this ticket is to use data_structures/biteset.pxi
for the bitset stuff in combinatorial polyhedron and cleanly seperate algorithm and data structure.
This ticket is mostly resolved in smaller tickets:
 #30596: Outsource functions in bitset.pxi that can be optimized by intrinsics
 #30597: Define a sparse bitset structure
 #30601: Move bitset.pxi to bitset_base.pxd
 #30598: Define a new data structure for a combinatorial face
 #30599: Define a new data structure for a list of combinatorial faces 
Changes are:
 Move functions optimizable by intrinsics to a seperate file (
src/sage/data_structures/bitset_intrinsics.h
). (See #27103 and #27122.)  Allow most functions in
bitset.pxi
for fuzed types fuzed types, such that an (yet to be enriched) bitset data structure specialized for combinatorial faces can use it.  Move
bitset.pxi
tobitset_base.pxd
.  Define a data structure
face_s
that gathers properties of a face and corresponding functions.  Define a data structure
face_list_s
that gathers properties of a list of faces and corresponding functions.  The two flavors of the algorithm (simple and standard) are set up as templates by abusing fuzed types. This makes the code much easier to read. Only the changes will be seperated in the code while the compiler compiles two seperate branches for both flavors.
The features of those changes are mainly:
 Less involved signatures of functions.
 Removing duplications of code.
 New flavors of the algorithm can be implemented without messing up all the files.
 We may enrich
face_s
without changing all our code.  Intrinsics can easily applied to bitsets in general.
Change History (24)
comment:1 Changed 2 years ago by
comment:2 Changed 2 years ago by
 Commit changed from 1e4596efe1690719b824fcf5ed26aa7f7d9bac7a to 349e10564a54037efbd4e81bc592cd2d9dc3cbd2
comment:3 Changed 2 years ago by
 Status changed from new to needs_review
I'm happy with the ticket as it is.
Using templates for the two algorithmic variants, the branch prediction has improved significantly. For extreme cases (see below), things got a bit slower. I don't know why.
In a future ticket one can spare allocating the memory for the coatoms in case we are not using the simple/simplicial algorithm. It doesn't seem to make a difference in runtime.
This is an example of slight slowdown:
sage: P = polytopes.permutahedron(6) sage: Q = P.base_extend(QQ).polar(in_affine_span=True) sage: R = P.join(Q) sage: C = CombinatorialPolyhedron(R) sage: %time _ = C.f_vector() CPU times: user 1min 12s, sys: 28.8 ms, total: 1min 12s Wall time: 1min 12s
This is 10 seconds faster on #30040.
I could also play around with constants etc.
This could also all be because the compiler ignores my inline
instructions in places.
Anyway, I can live with the slight slowdown for now, because the structure is so much better for further improvements.
Any suggestions on how to improve things are welcome.
comment:4 Changed 2 years ago by
https://cython.readthedocs.io/en/latest/src/userguide/fusedtypes.html
If this is better, I could move almost everything back to cython again.
The only thing that really needs to be in C/C++ are those 4 functions that I want to optimize with intrinsics later on (there are going to be a few more, but they are all tiny). To my knowledge you cannot do something like
#if __AVX__ def foo(): return 1 #elif __SSE4_1__ def foo(): return 2 #else def foo(): return 3 #endif
in cython.
However I don't know how the performance is, when you include critical C/C++
function via cdef extern from
that will be called a huge number of times.
comment:5 Changed 2 years ago by
 Status changed from needs_review to needs_info
Also I'm happy with it now, the current status would force to move quite a lot of bitsets
to C++. If I want to do it (which I'm not sure of yet) I would need to ask other people about it.
So for now this is a design proposal.
comment:6 Changed 2 years ago by
 Branch changed from u/ghkliem/face_structure to u/ghkliem/use_face_structure
 Commit changed from 349e10564a54037efbd4e81bc592cd2d9dc3cbd2 to 74230a1b34757c60169a4af481f75a1dcc6e24db
I like it much better now.
Timings with this ticket (branch u/ghkliem/use_face_structure
):
(Note that I didn't apply new tricks to the algorithm. Only the data structure has changed.)
sage: P = polytopes.permutahedron(8, backend='normaliz') sage: C = CombinatorialPolyhedron(P) sage: %time _ = C.f_vector() CPU times: user 648 ms, sys: 15 µs, total: 648 ms Wall time: 648 ms sage: P = polytopes.associahedron(['A',10], backend='normaliz') sage: C = CombinatorialPolyhedron(P) sage: %time _ = C.f_vector() CPU times: user 1.97 s, sys: 0 ns, total: 1.97 s Wall time: 1.97 s sage: P = polytopes.permutahedron(7) sage: P1 = P.stack(next(P.face_generator(1))) sage: C = CombinatorialPolyhedron(P1) sage: %time _ = C.f_vector() CPU times: user 242 ms, sys: 0 ns, total: 242 ms Wall time: 241 ms sage: P = polytopes.hypercube(12) sage: P1 = P.stack(next(P.face_generator(1))) sage: C = CombinatorialPolyhedron(P1) sage: %time _ = C.f_vector() CPU times: user 430 ms, sys: 0 ns, total: 430 ms Wall time: 429 ms sage: P = polytopes.permutahedron(6) sage: Q = P.base_extend(QQ).polar(in_affine_span=True) sage: R = P.join(Q) sage: C = CombinatorialPolyhedron(R) sage: %time _ = C.f_vector() CPU times: user 1min 11s, sys: 31.8 ms, total: 1min 11s Wall time: 1min 11s
Timings on #30040:
sage: P = polytopes.permutahedron(8, backend='normaliz') sage: C = CombinatorialPolyhedron(P) sage: %time _ = C.f_vector() CPU times: user 680 ms, sys: 0 ns, total: 680 ms Wall time: 679 ms sage: P = polytopes.associahedron(['A',10], backend='normaliz') sage: C = CombinatorialPolyhedron(P) sage: %time _ = C.f_vector() CPU times: user 2.2 s, sys: 45 µs, total: 2.2 s Wall time: 2.2 s sage: P = polytopes.permutahedron(7) sage: P1 = P.stack(next(P.face_generator(1))) sage: C = CombinatorialPolyhedron(P1) sage: %time _ = C.f_vector() CPU times: user 240 ms, sys: 0 ns, total: 240 ms Wall time: 239 ms sage: P = polytopes.hypercube(12) sage: P1 = P.stack(next(P.face_generator(1))) sage: C = CombinatorialPolyhedron(P1) sage: %time _ = C.f_vector() CPU times: user 414 ms, sys: 0 ns, total: 414 ms Wall time: 413 ms sage: P = polytopes.permutahedron(6) sage: Q = P.base_extend(QQ).polar(in_affine_span=True) sage: R = P.join(Q) sage: C = CombinatorialPolyhedron(R) sage: %time _ = C.f_vector() CPU times: user 1min 4s, sys: 51.6 ms, total: 1min 4s Wall time: 1min 4s
So I would say that there is no performancewise reason to reject the changes.
The branch indicates a bit, how this could be split into seperate tickets that are doable to review.
Last 10 new commits:
bb49546  face_list_t

bc8f985  add find and sort

43ee71d  fixes to list_of_faces.pxi

31544ff  merge u/ghkliem/no_more_basic_access

d42e5ab  remove new declarations for now

7a32286  removed deprecated functions

af27e02  remove doctests that rely on implementation details

fe30622  Merge branch 'u/ghkliem/prepare_conversions_for_face_structure' of git://trac.sagemath.org/sage into u/ghkliem/use_face_structure_2

df3a254  delete old files

74230a1  use face_list_t and face_t for combinatorial polyhedron

comment:7 Changed 2 years ago by
 Description modified (diff)
comment:8 Changed 2 years ago by
 Dependencies changed from #30528, #30529 to #30528, #30529, #30572
comment:9 Changed 2 years ago by
I posted on sage devel on whether the proposed design is acceptable: https://groups.google.com/g/sagedevel/c/jD9BY5Ozlko
comment:10 Changed 2 years ago by
I am essentially happy with this ticket, but I want to wait and see what happens with the design discussion before going forward.
comment:11 Changed 23 months ago by
 Dependencies changed from #30528, #30529, #30572 to #30528, #30529, #30572, #30571
comment:12 Changed 23 months ago by
 Dependencies changed from #30528, #30529, #30572, #30571 to #30528, #30529, #30571, #30599
comment:13 Changed 23 months ago by
 Description modified (diff)
comment:14 Changed 23 months ago by
 Commit changed from 74230a1b34757c60169a4af481f75a1dcc6e24db to f3e851f25544e39e8c1be91e169049f14f435c69
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
02eabff  add find and sort

50317b0  fixes to list_of_faces.pxi

32cf17e  remove pxi file

c81f438  move not inlined functions to pyx file

0a3df96  Merge branch 'u/ghkliem/no_more_basic_access' of git://trac.sagemath.org/sage into u/ghkliem/use_face_structure_2

5b21614  use reference so simplify code

85708b0  Merge branch 'u/ghkliem/simplify_face_struct_pointer' of git://trac.sagemath.org/sage into u/ghkliem/use_face_structure_2

2f75805  Merge branch 'u/ghkliem/prepare_conversions_for_face_structure' of git://trac.sagemath.org/sage into u/ghkliem/use_face_structure_2

605fc6b  delete old files

f3e851f  use face_list_t and face_t for combinatorial polyhedron

comment:15 Changed 23 months ago by
 Status changed from needs_info to needs_review
comment:16 Changed 22 months ago by
 Commit changed from f3e851f25544e39e8c1be91e169049f14f435c69 to 298c2f7e48e4a86024d0f006585445726e8f5ced
Branch pushed to git repo; I updated commit sha1. New commits:
7a40b9a  redundant exit; removed semicolon

28bfa02  Merge branch 'u/ghkliem/data_structure_for_face_list' of git://trac.sagemath.org/sage into u/ghkliem/use_face_structure

298c2f7  Merge branch 'develop' of git://trac.sagemath.org/sage into u/ghkliem/use_face_structure

comment:17 Changed 21 months ago by
 Status changed from needs_review to needs_work
Red branch.
I'll fix it, once all the dependencies are in.
comment:18 Changed 21 months ago by
 Dependencies changed from #30528, #30529, #30571, #30599 to #30529, #30599
comment:19 Changed 21 months ago by
 Dependencies changed from #30529, #30599 to #30529
comment:20 Changed 21 months ago by
 Commit changed from 298c2f7e48e4a86024d0f006585445726e8f5ced to 82a747d6fabf5cf8d366851d2dfbcbf7cd57eabc
Branch pushed to git repo; I updated commit sha1. New commits:
82a747d  Merge branch 'u/ghkliem/use_face_structure' of git://trac.sagemath.org/sage into u/ghkliem/use_face_structure_new

comment:21 Changed 21 months ago by
 Status changed from needs_work to needs_review
Ok, this is back on needs review. Almost all dependencies are gone now.
comment:22 Changed 20 months ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
# The universe.
< Great comment.
LGTM. Hopefully this won't have any issues with other systems that some of the other tickets had.
comment:23 Changed 20 months ago by
Thank you.
Yes, I think it is way more stable, as it just exposes bitsets, which has been working for a while now.
I just didn't think, the intermediate solutions to the end.
comment:24 Changed 20 months ago by
 Branch changed from u/ghkliem/use_face_structure to 82a747d6fabf5cf8d366851d2dfbcbf7cd57eabc
 Resolution set to fixed
 Status changed from positive_review to closed
It's a patch bomb, I know. If anyone knows a reasonable way around it, I'll do it.
Currently, this is working again and I'm happy. And it's so much easier to do some something from then on.
Most of the changes in the cython files are trivial (took me a while to figure out everything though).
The current branch is a bit of regression with nonsimplenonsimplicial polyhedra. It can take much longer. One thing is the unnecessary union of coatoms. Also the branch prediction seems to be bad, because one could know much earlier that the coatom check is useless. I'll think about a solution that works well.
We waste a bit of memory by also allocating enough space for the coatoms in each case, but I wouldn't worry about it for now. In a worst case scenario this needs twice as much memory and much less in many scenarios that have less equal number of vertices/facets. Memory was never an issue for me, it was always time.