Opened 7 months ago

Closed 4 months ago

#30549 closed enhancement (fixed)

Remove all the bitset access from cython files in combinatorial polyhedron

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.3
Component: geometry Keywords: combinatorial polyhedron, bitsets
Cc: jipilab, gh-LaisRast, 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:

Status badges

Description (last modified by gh-kliem)

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:

  1. Move functions optimizable by intrinsics to a seperate file ( src/sage/data_structures/bitset_intrinsics.h). (See #27103 and #27122.)
  2. 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.
  3. Move bitset.pxi to bitset_base.pxd.
  4. Define a data structure face_s that gathers properties of a face and corresponding functions.
  5. Define a data structure face_list_s that gathers properties of a list of faces and corresponding functions.
  6. 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 7 months ago by gh-kliem

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 non-simple-non-simplicial 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.

comment:2 Changed 7 months ago by git

  • Commit changed from 1e4596efe1690719b824fcf5ed26aa7f7d9bac7a to 349e10564a54037efbd4e81bc592cd2d9dc3cbd2

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

b7fee53factor out the algorithm variant with templates
fd5edebone more inline
4c2cc9falways compile all dependend files
349e105documentation

comment:3 Changed 7 months ago by gh-kliem

  • 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 7 months ago by gh-kliem

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 7 months ago by gh-kliem

  • 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 7 months ago by gh-kliem

  • Branch changed from u/gh-kliem/face_structure to u/gh-kliem/use_face_structure
  • Commit changed from 349e10564a54037efbd4e81bc592cd2d9dc3cbd2 to 74230a1b34757c60169a4af481f75a1dcc6e24db

I like it much better now.

Timings with this ticket (branch u/gh-kliem/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 performance-wise 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:

bb49546face_list_t
bc8f985add find and sort
43ee71dfixes to list_of_faces.pxi
31544ffmerge u/gh-kliem/no_more_basic_access
d42e5abremove new declarations for now
7a32286removed deprecated functions
af27e02remove doctests that rely on implementation details
fe30622Merge branch 'u/gh-kliem/prepare_conversions_for_face_structure' of git://trac.sagemath.org/sage into u/gh-kliem/use_face_structure_2
df3a254delete old files
74230a1use face_list_t and face_t for combinatorial polyhedron

comment:7 Changed 7 months ago by gh-kliem

  • Description modified (diff)

comment:8 Changed 7 months ago by gh-kliem

  • Dependencies changed from #30528, #30529 to #30528, #30529, #30572

comment:9 Changed 7 months ago by gh-kliem

I posted on sage devel on whether the proposed design is acceptable: https://groups.google.com/g/sage-devel/c/jD9BY5Ozlko

comment:10 Changed 7 months ago by tscrim

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 7 months ago by gh-kliem

  • Dependencies changed from #30528, #30529, #30572 to #30528, #30529, #30572, #30571

comment:12 Changed 7 months ago by gh-kliem

  • Dependencies changed from #30528, #30529, #30572, #30571 to #30528, #30529, #30571, #30599

comment:13 Changed 7 months ago by gh-kliem

  • Description modified (diff)

comment:14 Changed 7 months ago by git

  • Commit changed from 74230a1b34757c60169a4af481f75a1dcc6e24db to f3e851f25544e39e8c1be91e169049f14f435c69

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

02eabffadd find and sort
50317b0fixes to list_of_faces.pxi
32cf17eremove pxi file
c81f438move not inlined functions to pyx file
0a3df96Merge branch 'u/gh-kliem/no_more_basic_access' of git://trac.sagemath.org/sage into u/gh-kliem/use_face_structure_2
5b21614use reference so simplify code
85708b0Merge branch 'u/gh-kliem/simplify_face_struct_pointer' of git://trac.sagemath.org/sage into u/gh-kliem/use_face_structure_2
2f75805Merge branch 'u/gh-kliem/prepare_conversions_for_face_structure' of git://trac.sagemath.org/sage into u/gh-kliem/use_face_structure_2
605fc6bdelete old files
f3e851fuse face_list_t and face_t for combinatorial polyhedron

comment:15 Changed 7 months ago by gh-kliem

  • Status changed from needs_info to needs_review

comment:16 Changed 6 months ago by git

  • Commit changed from f3e851f25544e39e8c1be91e169049f14f435c69 to 298c2f7e48e4a86024d0f006585445726e8f5ced

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

7a40b9aredundant exit; removed semicolon
28bfa02Merge branch 'u/gh-kliem/data_structure_for_face_list' of git://trac.sagemath.org/sage into u/gh-kliem/use_face_structure
298c2f7Merge branch 'develop' of git://trac.sagemath.org/sage into u/gh-kliem/use_face_structure

comment:17 Changed 5 months ago by gh-kliem

  • Status changed from needs_review to needs_work

Red branch.

I'll fix it, once all the dependencies are in.

comment:18 Changed 5 months ago by gh-kliem

  • Dependencies changed from #30528, #30529, #30571, #30599 to #30529, #30599

comment:19 Changed 5 months ago by gh-kliem

  • Dependencies changed from #30529, #30599 to #30529

comment:20 Changed 5 months ago by git

  • Commit changed from 298c2f7e48e4a86024d0f006585445726e8f5ced to 82a747d6fabf5cf8d366851d2dfbcbf7cd57eabc

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

82a747dMerge branch 'u/gh-kliem/use_face_structure' of git://trac.sagemath.org/sage into u/gh-kliem/use_face_structure_new

comment:21 Changed 5 months ago by gh-kliem

  • Status changed from needs_work to needs_review

Ok, this is back on needs review. Almost all dependencies are gone now.

comment:22 Changed 4 months ago by tscrim

  • 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 4 months ago by gh-kliem

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 4 months ago by vbraun

  • Branch changed from u/gh-kliem/use_face_structure to 82a747d6fabf5cf8d366851d2dfbcbf7cd57eabc
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.