Opened 3 months ago

Closed 3 months ago

#31262 closed enhancement (fixed)

Implement non zero chunks for sparse bitsets

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.3
Component: geometry Keywords: combinatorial polyhedron, sparse bitsets
Cc: stumpc5, tscrim Merged in:
Authors: Jonathan Kliem Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: b3212d0 (Commits, GitHub, GitLab) Commit: b3212d0bb74109461114b23d63fc26e604c121f2
Dependencies: #27103 Stopgaps:

Status badges

Description (last modified by gh-kliem)

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.

Change History (13)

comment:1 Changed 3 months ago by gh-kliem

  • Status changed from new to needs_review

comment:2 Changed 3 months ago by gh-kliem

  • Status changed from needs_review to needs_work

Failing doctests.

comment:3 Changed 3 months ago by git

  • Commit changed from 24ff7ccf96a970655e2ce4c4db37cce343bd9c40 to eb6046e8eed53d2511f9a3d4fcf95f034df39108

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

eb6046eimproved documentation and fixed error

comment:4 Changed 3 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:5 Changed 3 months ago by gh-kliem

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.

comment:6 Changed 3 months ago by git

  • Commit changed from eb6046e8eed53d2511f9a3d4fcf95f034df39108 to 4362e2ce0a52f8480793d34667a582d90163bc78

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

4362e2cuse enum to make code a bit more canonical

comment:7 Changed 3 months ago by git

  • Commit changed from 4362e2ce0a52f8480793d34667a582d90163bc78 to fc0f1d96ff897f1897125956d9495e5536888dac

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

fc0f1d9resolve slow down comparison

comment:8 Changed 3 months ago by gh-kliem

  • Description modified (diff)

Cleaner code makes things a bit faster, I suppose.

comment:9 Changed 3 months ago by git

  • Commit changed from fc0f1d96ff897f1897125956d9495e5536888dac to b3212d0bb74109461114b23d63fc26e604c121f2

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

b3212d0two mistakes with no intrinsics

comment:10 Changed 3 months ago by gh-kliem

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.

comment:11 Changed 3 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM.

comment:12 Changed 3 months ago by gh-kliem

Thank you.

comment:13 Changed 3 months ago by vbraun

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