Implement non zero chunks for sparse bitsets

kliem commented 3 years ago

For very large and challenging computations, most of the elements of the face lattice contain rather few atoms/bits. With little changes to the code, we can just collect the non zero chunks (64,128 or 256 bits).

RoaringBitmap performs better (starting with maybe 100,000 bits, but not with less, as container contain 64k bits), but that would add an extra dependency and make things more complicated.

To avoid code duplications, we also gather some functions in bitset_intrinsics.h that work just the same (e.g. intersection and union). (This actually accounts for most changes by this ticket.)

Before (on #27103):

sage: P = polytopes.Birkhoff_polytope(5)                                                                                                                                                                                                                                                                                                                                   
sage: C = CombinatorialPolyhedron(P)                                                                                                                                                                                                                                                                                                                                       
sage: %time _ = C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 468 ms, sys: 0 ns, total: 468 ms
Wall time: 467 ms

sage: P = polytopes.Birkhoff_polytope(5)                                                                                                                                                                                                                                                                                                                                   
sage: C = CombinatorialPolyhedron(P)                                                                                                                                                                                                                                                                                                                                       
sage: %time _ = C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 440 ms, sys: 0 ns, total: 440 ms
Wall time: 439 ms

sage: P = polytopes.hypercube(14)                                                                                                                                                                                                                                                                                                                                          
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time _ = C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 5.13 s, sys: 4.03 ms, total: 5.14 s
Wall time: 5.13 s
sage: P = polytopes.hypercube(15)                                                                                                                                                                                                                                                                                                                                          
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time _ = C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 30 s, sys: 32 ms, total: 30 s
Wall time: 30 s

sage: P = polytopes.permutahedron(6)                                                                                                                                                                                                                                                                                                                                       
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time _ = C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 1.68 ms, sys: 6 µs, total: 1.68 ms
Wall time: 1.69 ms
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 89.1 ms, sys: 4 µs, total: 89.1 ms
Wall time: 88.9 ms

sage: P = polytopes.permutahedron(8, backend='normaliz')                                                                                                                                                                                                                                                                                                                   
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time _ = C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 14.2 s, sys: 8 ms, total: 14.2 s
Wall time: 14.2 s

sage: P = polytopes.associahedron(['A', 11], backend='normaliz')                                                                                                                                                                                                                                                                                                           
sage: C = CombinatorialPolyhedron(P)                                                                                                                                                                                                                                                                                                                                       
sage: %time _ = C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 24.3 s, sys: 8.01 ms, total: 24.3 s
Wall time: 24.3 s

After:

# Slight slowdown for few atoms.
sage: P = polytopes.Birkhoff_polytope(5)                                                                                                                                                                                                                                                                                                                                   
sage: C = CombinatorialPolyhedron(P)                                                                                                                                                                                                                                                                                                                                       
sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 475 ms, sys: 0 ns, total: 475 ms
Wall time: 474 ms
(1, 120, 5040, 50250, 233400, 631700, 1113700, 1367040, 1220550, 817150, 419225, 167200, 52120, 12600, 2300, 300, 25, 1)

sage: P = polytopes.hypercube(14)                                                                                                                                                                                                                                                                                                                                          
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 1.67 s, sys: 0 ns, total: 1.67 s
Wall time: 1.66 s
(1, 16385, 131069, 487383, 1117948, 1769482, 2047331, 1788501, 1200342, 622908, 248963, 75361, 16640, 2470, 197, 1)
sage: P = polytopes.hypercube(15)                                                                                                                                                                                                                                                                                                                                          
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 7.28 s, sys: 8 ms, total: 7.28 s
Wall time: 7.28 s
(1, 32769, 278525, 1105876, 2723539, 4657926, 5866861, 5629624, 4196907, 2454738, 1128127, 404404, 110929, 22386, 3059, 226, 1)

sage: P = polytopes.permutahedron(6)                                                                                                                                                                                                                                                                                                                                       
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 1.44 ms, sys: 79 µs, total: 1.52 ms
Wall time: 1.52 ms
(1, 721, 1987, 1956, 808, 120, 1)
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 20.8 ms, sys: 0 ns, total: 20.8 ms
Wall time: 20.9 ms
(1, 5041, 16251, 19761, 11144, 2860, 267, 1)
sage: P = polytopes.permutahedron(8, backend='normaliz')                                                                                                                                                                                                                                                                                                                   
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 616 ms, sys: 8 ms, total: 624 ms
Wall time: 623 ms
(1, 40321, 148899, 215690, 154215, 56022, 9489, 572, 1)

# No change for simplicial/simple polytopes.
sage: P = polytopes.associahedron(['A', 11], backend='normaliz')                                                                                                                                                                                                                                                                                                           
sage: C = CombinatorialPolyhedron(P)                                                                                                                                                                                                                                                                                                                                       
sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 24.3 s, sys: 16.3 ms, total: 24.3 s
Wall time: 24.3 s
(1, 208012, 1144066, 2735810, 3730650, 3197700, 1790712, 659736, 157080, 23100, 1925, 77, 1)

This is the last subsequent improvement in comparison to sage 8.9 mentioned in https://arxiv.org/abs/1905.01945.

Follow ups:

Move things from geometry/polyhedron/combinatorial_polyhedron to a more general location.
Some renamings for lattices in general face -> element.
Expose to simplical complexes.
Expose to lattice of flats of matroids.

Depends on #27103

CC: @stumpc5 @tscrim

Component: geometry

Keywords: combinatorial polyhedron, sparse bitsets

Author: Jonathan Kliem

Branch/Commit: b3212d0

Reviewer: Travis Scrimshaw

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

kliem commented 3 years ago

comment:2

Failing doctests.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 24ff7cc to eb6046e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

eb6046e improved documentation and fixed error

kliem commented 3 years ago

comment:5

Possibly it might make sense to factor this ticket in two:

One that removes duplicates in bitset_intrinsics.h.
One that actually adds the slight modifications for sparse bitsets.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from eb6046e to 4362e2c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

4362e2c use enum to make code a bit more canonical

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

fc0f1d9 resolve slow down comparison

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 4362e2c to fc0f1d9

kliem commented 3 years ago

Description changed:

--- 
+++ 
@@ -75,37 +75,37 @@
 sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
 sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
 sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
-CPU times: user 1.71 s, sys: 0 ns, total: 1.71 s
-Wall time: 1.71 s
+CPU times: user 1.67 s, sys: 0 ns, total: 1.67 s
+Wall time: 1.66 s
 (1, 16385, 131069, 487383, 1117948, 1769482, 2047331, 1788501, 1200342, 622908, 248963, 75361, 16640, 2470, 197, 1)
 sage: P = polytopes.hypercube(15)                                                                                                                                                                                                                                                                                                                                          
 sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
 sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
 sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
-CPU times: user 7.54 s, sys: 4 ms, total: 7.54 s
-Wall time: 7.54 s
+CPU times: user 7.28 s, sys: 8 ms, total: 7.28 s
+Wall time: 7.28 s
 (1, 32769, 278525, 1105876, 2723539, 4657926, 5866861, 5629624, 4196907, 2454738, 1128127, 404404, 110929, 22386, 3059, 226, 1)

 sage: P = polytopes.permutahedron(6)                                                                                                                                                                                                                                                                                                                                       
 sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
 sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
 sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
-CPU times: user 1.45 ms, sys: 0 ns, total: 1.45 ms
-Wall time: 1.55 ms
+CPU times: user 1.44 ms, sys: 79 µs, total: 1.52 ms
+Wall time: 1.52 ms
 (1, 721, 1987, 1956, 808, 120, 1)
 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 20.8 ms, sys: 27 µs, total: 20.8 ms
-Wall time: 20.7 ms
+CPU times: user 20.8 ms, sys: 0 ns, total: 20.8 ms
+Wall time: 20.9 ms
 (1, 5041, 16251, 19761, 11144, 2860, 267, 1)
 sage: P = polytopes.permutahedron(8, backend='normaliz')                                                                                                                                                                                                                                                                                                                   
 sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
 sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
 sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
-CPU times: user 665 ms, sys: 4 µs, total: 665 ms
-Wall time: 664 ms
+CPU times: user 616 ms, sys: 8 ms, total: 624 ms
+Wall time: 623 ms
 (1, 40321, 148899, 215690, 154215, 56022, 9489, 572, 1)

 # No change for simplicial/simple polytopes.

kliem commented 3 years ago

comment:8

Cleaner code makes things a bit faster, I suppose.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from fc0f1d9 to b3212d0

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

b3212d0 two mistakes with no intrinsics

kliem commented 3 years ago

comment:10

All doctests pass on my side. With the current setup:

AVX2, AVX, SSE4.1
AVX, SSE4.1 (only geometry/polyhedron and data_structure/ tested)
SSE4.1
no intrinsics.

tscrim commented 3 years ago

comment:11

LGTM.

tscrim commented 3 years ago

Reviewer: Travis Scrimshaw

kliem commented 3 years ago

comment:12

Thank you.

vbraun commented 3 years ago

Changed branch from u/gh-kliem/small_improvements_for_sparse_bitsets to b3212d0

sagemath / sage

Implement non zero chunks for sparse bitsets #31262