Remove all the bitset access from cython files in combinatorial polyhedron

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

• Outsource functions in bitset.pxi that can be optimized by intrinsics #30596: Outsource functions in bitset.pxi that can be optimized by intrinsics
• Define a sparse bitset structure #30597: Define a sparse bitset structure
• Move bitset.pxi to bitset_base.pxd #30601: Move bitset.pxi to bitset_base.pxd
• Define a new data structure for a combinatorial face #30598: Define a new data structure for a combinatorial face
• Define a new data structure for a list of combinatorial faces #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 Enable SIMD-instructions for Bitsets #27103 and Compile with -march=native #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.

Depends on #30529

CC: @jplab @LaisRast @tscrim

Component: geometry

Keywords: combinatorial polyhedron, bitsets

Author: Jonathan Kliem

Branch/Commit: 82a747d

Reviewer: Travis Scrimshaw

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

[kliem]

comment:1

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.

[sagetrac-git]

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

b7fee53	factor out the algorithm variant with templates
fd5edeb	one more inline
4c2cc9f	always compile all dependend files
349e105	documentation

[sagetrac-git]

Changed commit from 1e4596e to 349e105

[kliem]

comment:3

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.

[kliem]

comment:4

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.

[kliem]

comment:5

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.

[kliem]

Changed commit from 349e105 to 74230a1

[kliem]

Changed branch from u/gh-kliem/face_structure to u/gh-kliem/use_face_structure

[kliem]

comment:6

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:

bb49546	face_list_t
bc8f985	add find and sort
43ee71d	fixes to list_of_faces.pxi
31544ff	merge u/gh-kliem/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/gh-kliem/prepare_conversions_for_face_structure' of git://trac.sagemath.org/sage into u/gh-kliem/use_face_structure_2
df3a254	delete old files
74230a1	use face_list_t and face_t for combinatorial polyhedron

[kliem]

Changed dependencies from #30528, #30529 to #30528, #30529, #30572

[kliem]

comment:9

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

[tscrim]

comment:10

I am essentially happy with this ticket, but I want to wait and see what happens with the design discussion before going forward.

[kliem]

Changed dependencies from #30528, #30529, #30572 to #30528, #30529, #30572, #30571

[kliem]

Changed dependencies from #30528, #30529, #30572, #30571 to #30528, #30529, #30571, #30599

[sagetrac-git]

Changed commit from 74230a1 to f3e851f

[sagetrac-git]

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/gh-kliem/no_more_basic_access' of git://trac.sagemath.org/sage into u/gh-kliem/use_face_structure_2
5b21614	use reference so simplify code
85708b0	Merge branch 'u/gh-kliem/simplify_face_struct_pointer' of git://trac.sagemath.org/sage into u/gh-kliem/use_face_structure_2
2f75805	Merge branch 'u/gh-kliem/prepare_conversions_for_face_structure' of git://trac.sagemath.org/sage into u/gh-kliem/use_face_structure_2
605fc6b	delete old files
f3e851f	use face_list_t and face_t for combinatorial polyhedron

[sagetrac-git]

Changed commit from f3e851f to 298c2f7

[sagetrac-git]

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

7a40b9a	redundant exit; removed semicolon
28bfa02	Merge branch 'u/gh-kliem/data_structure_for_face_list' of git://trac.sagemath.org/sage into u/gh-kliem/use_face_structure
298c2f7	Merge branch 'develop' of git://trac.sagemath.org/sage into u/gh-kliem/use_face_structure

[kliem]

comment:17

Red branch.

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

[kliem]

Changed dependencies from #30528, #30529, #30571, #30599 to #30529, #30599

[kliem]

Changed dependencies from #30529, #30599 to #30529

[sagetrac-git]

Changed commit from 298c2f7 to 82a747d

[sagetrac-git]

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

82a747d

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

[kliem]

comment:21

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

[tscrim]

comment:22

# The universe. <-- Great comment.

LGTM. Hopefully this won't have any issues with other systems that some of the other tickets had.

[tscrim]

Reviewer: Travis Scrimshaw

[kliem]

comment:23

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.

[vbraun]

Changed branch from u/gh-kliem/use_face_structure to 82a747d