Opened 9 months ago

Closed 4 months ago

#31245 closed enhancement (fixed)

Implement parallel f-vector for polytopes

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.4
Component: geometry Keywords: parallel f-vector
Cc: jipilab, gh-LaisRast, stumpc5, tscrim Merged in:
Authors: Jonathan Kliem Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 4c0a4ae (Commits, GitHub, GitLab) Commit: 4c0a4ae74c28680e48080c39c5e3b171a79a9ad3
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-kliem)

This ticket parallelizes the f-vector for polytopes.

Each thread has its private structure with which it does partial jobs. Depending on the parallelization depth, there is one job per face of fixed codimension (usually 1,2 or 3). After everything has finished, the partial f-vectors will be added.

Actually, every face is visited and thus the code could be modified in the future, to explore other properties of faces then just the dimension. The parallelization seems to work well with at least 40 threads (for computations taking long enough such that this pays off, see https://arxiv.org/pdf/1905.01945.pdf).

Also the algorithm does work in other situations (simplicial complex, lattice of flats of a matroid) and this parallel structure could be used for this as well.

On the downside, sig_on()/sig_off() doesn't work with with multiple threads and has to be replaced by a simple sig_check(). Also raising errors in parallel code results in terrible slow down. Hence the errors are replaced by returning the exception value. In case of a bug there won't be any traceback anymore, but at least also no segmenation fault.

Before:

sage: P = P.base_extend(QQ)                                                                                                                                   
sage: P = P.base_extend(QQ)                                                                                                                                   
sage: Q = P.join(P.polar(in_affine_span=True))                                                                                                                
sage: C = CombinatorialPolyhedron(Q)                                                                                                                          
sage: %time C.f_vector()                                                                                                                                      
CPU times: user 111 ms, sys: 186 µs, total: 111 ms
Wall time: 111 ms
(1, 150, 3990, 25590, 69450, 95402, 69450, 25590, 3990, 150, 1)

sage: P = polytopes.Birkhoff_polytope(5)                                                                                                                      
sage: C = CombinatorialPolyhedron(P)                                                                                                                          
sage: %time C.f_vector()                                                                                                                                      
CPU times: user 584 ms, sys: 25 µs, total: 584 ms
Wall time: 583 ms
(1, 120, 5040, 50250, 233400, 631700, 1113700, 1367040, 1220550, 817150, 419225, 167200, 52120, 12600, 2300, 300, 25, 1)

# Using the <simple> version of the algorithm.
sage: P = polytopes.associahedron(['A', 11], backend='normaliz')                                                                                              
sage: C = CombinatorialPolyhedron(P)                                                                                                                          
sage: %time C.f_vector()                                                                                                                                      
CPU times: user 37.9 s, sys: 17.2 ms, total: 37.9 s
Wall time: 37.9 s
(1, 208012, 1144066, 2735810, 3730650, 3197700, 1790712, 659736, 157080, 23100, 1925, 77, 1)

After (machine has 4 cores):

sage: P = polytopes.permutahedron(5)                                                                                                                          
sage: P = P.base_extend(QQ)                                                                                                                                   
sage: Q = P.join(P.polar(in_affine_span=True))                                                                                                                
sage: C = CombinatorialPolyhedron(Q)                                                                                                                          
sage: %time C.f_vector(num_threads=1)                                                                                                                         
CPU times: user 107 ms, sys: 0 ns, total: 107 ms
Wall time: 107 ms
(1, 150, 3990, 25590, 69450, 95402, 69450, 25590, 3990, 150, 1)

sage: C = CombinatorialPolyhedron(Q)                                                                                                                          
sage: %time C.f_vector(num_threads=2)                                                                                                                         
CPU times: user 108 ms, sys: 0 ns, total: 108 ms
Wall time: 55.6 ms
(1, 150, 3990, 25590, 69450, 95402, 69450, 25590, 3990, 150, 1)

sage: C = CombinatorialPolyhedron(Q)                                                                                                                          
sage: %time C.f_vector(num_threads=4)                                                                                                                         
CPU times: user 147 ms, sys: 52 µs, total: 147 ms
Wall time: 38.6 ms
(1, 150, 3990, 25590, 69450, 95402, 69450, 25590, 3990, 150, 1)

sage: C = CombinatorialPolyhedron(Q)                                                                                                                          
sage: %time C.f_vector(num_threads=8)                                                                                                                         
CPU times: user 236 ms, sys: 0 ns, total: 236 ms
Wall time: 31.2 ms
(1, 150, 3990, 25590, 69450, 95402, 69450, 25590, 3990, 150, 1)

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

sage: C = CombinatorialPolyhedron(P)                                                                                                                          
sage: %time C.f_vector(num_threads=2)                                                                                                                         
CPU times: user 363 ms, sys: 0 ns, total: 363 ms
Wall time: 181 ms
(1, 120, 5040, 50250, 233400, 631700, 1113700, 1367040, 1220550, 817150, 419225, 167200, 52120, 12600, 2300, 300, 25, 1)

sage: C = CombinatorialPolyhedron(P)                                                                                                                          
sage: %time C.f_vector(num_threads=4)                                                                                                                         
CPU times: user 459 ms, sys: 0 ns, total: 459 ms
Wall time: 117 ms
(1, 120, 5040, 50250, 233400, 631700, 1113700, 1367040, 1220550, 817150, 419225, 167200, 52120, 12600, 2300, 300, 25, 1)

sage: C = CombinatorialPolyhedron(P)                                                                                                                          
sage: %time C.f_vector(num_threads=8)                                                                                                                         
CPU times: user 776 ms, sys: 154 µs, total: 776 ms
Wall time: 103 ms
(1, 120, 5040, 50250, 233400, 631700, 1113700, 1367040, 1220550, 817150, 419225, 167200, 52120, 12600, 2300, 300, 25, 1)


# Using the <simple> version of the algorithm.
sage: P = polytopes.associahedron(['A', 11], backend='normaliz')                                                                                              
sage: C = CombinatorialPolyhedron(P)                                                                                                                          
sage: %time C.f_vector(num_threads=1)                                                                                                                         
CPU times: user 33.5 s, sys: 0 ns, total: 33.5 s
Wall time: 33.5 s
(1, 208012, 1144066, 2735810, 3730650, 3197700, 1790712, 659736, 157080, 23100, 1925, 77, 1)

sage: C = CombinatorialPolyhedron(P)                                                                                                                          
sage: %time C.f_vector(num_threads=2)                                                                                                                         
CPU times: user 34.4 s, sys: 3.49 ms, total: 34.4 s
Wall time: 17.2 s
(1, 208012, 1144066, 2735810, 3730650, 3197700, 1790712, 659736, 157080, 23100, 1925, 77, 1)

sage: C = CombinatorialPolyhedron(P)                                                                                                                          
sage: %time C.f_vector(num_threads=4)                                                                                                                         
CPU times: user 35.9 s, sys: 15.5 ms, total: 35.9 s
Wall time: 9 s
(1, 208012, 1144066, 2735810, 3730650, 3197700, 1790712, 659736, 157080, 23100, 1925, 77, 1)

sage: C = CombinatorialPolyhedron(P)                                                                                                                          
sage: %time C.f_vector(num_threads=8)                                                                                                                         
CPU times: user 1min 6s, sys: 31.3 ms, total: 1min 6s
Wall time: 8.44 s
(1, 208012, 1144066, 2735810, 3730650, 3197700, 1790712, 659736, 157080, 23100, 1925, 77, 1)

Change History (49)

comment:1 Changed 9 months ago by gh-kliem

  • Status changed from new to needs_review

comment:2 Changed 9 months ago by gh-kliem

  • Description modified (diff)

comment:3 follow-up: Changed 9 months ago by tscrim

  • Reviewers set to Travis Scrimshaw

The sig_check() outside the loop is unnecessary:

     cdef size_t j
+    sig_check()
     for j in range(n_faces):
+        sig_check()
         if (is_not_maximal_fused(new_faces, j, algorithm) or  # Step 2
                 is_contained_in_one_fused(new_faces.faces[j], visited_all, algorithm)):  # Step 3
             is_not_new_face[j] = True

Likewise here:

         face_list_t visited_all) nogil except -1:
 
     cdef size_t output
-    sig_on()
+    sig_check()
     if faces.polyhedron_is_simple:
         output = get_next_level_fused(faces, new_faces, visited_all, <simple> 0)
     else:
         output = get_next_level_fused(faces, new_faces, visited_all, <standard> 0)
-    sig_off()
     return output
 
 cdef inline size_t bit_rep_to_coatom_rep(face_t face, face_list_t coatoms, size_t *output):

Here you either need the sig_on/sig_off or some more targeted checking. I don't see the point in performing a single check here.

Otherwise LGTM.

comment:4 Changed 9 months ago by git

  • Commit changed from d051f283c08d117bd51d2167fb3d0ccf641dd620 to 0dae7a061df9a2f05f9ef2d43602cc04fb351fb0

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

0dae7a0remove redundant sig_checks

comment:5 Changed 9 months ago by git

  • Commit changed from 0dae7a061df9a2f05f9ef2d43602cc04fb351fb0 to e3bdc617538af4ab8cdcf147fd74f4e62da5ff2a

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

609bd92do not delete all duplicates
5c6cceefix index
e3bdc61pull in 31226 and fix merge conflict

comment:6 Changed 9 months ago by gh-kliem

  • Dependencies set to #31226

comment:7 in reply to: ↑ 3 Changed 9 months ago by gh-kliem

Replying to tscrim:

The sig_check() outside the loop is unnecessary:

     cdef size_t j
+    sig_check()
     for j in range(n_faces):
+        sig_check()
         if (is_not_maximal_fused(new_faces, j, algorithm) or  # Step 2
                 is_contained_in_one_fused(new_faces.faces[j], visited_all, algorithm)):  # Step 3
             is_not_new_face[j] = True

Likewise here:

         face_list_t visited_all) nogil except -1:
 
     cdef size_t output
-    sig_on()
+    sig_check()
     if faces.polyhedron_is_simple:
         output = get_next_level_fused(faces, new_faces, visited_all, <simple> 0)
     else:
         output = get_next_level_fused(faces, new_faces, visited_all, <standard> 0)
-    sig_off()
     return output
 
 cdef inline size_t bit_rep_to_coatom_rep(face_t face, face_list_t coatoms, size_t *output):

Here you either need the sig_on/sig_off or some more targeted checking. I don't see the point in performing a single check here.

Otherwise LGTM.

I removed the redundant sig_checks.

As mentioned, sig_on, sig_off doesn't work well with parallelization. It crashes hard because sig_on, sig_off doesn't appear in correct order anymore.

Wrapping prange in sig_on/sig_off has a large performance penalty (8.45 s -> 9 s).

Currently there is one sig_check before checking that a face is inclusion maximal. One can add more sig checks, which wouldn't affect performance much for large examples, but for the small examples there is a penalty of about 50 percent.

I think the current solution should be fine: The largest thing I ever computed with this algorithm, which took about a month on 40 cores, had 11,665,781 vertices and 162 facets. In this case between the sig_checks A &~ B == 0 is performed for about 2 billion bits. Currently, without intrinsics, I get:

sage: B = Bitset((randint(0,2**20) for _ in range(2**19)))                                                                                                    
sage: %timeit B.issubset(B)                                                                                                                                   
6.18 µs ± 9.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
sage: %timeit B.intersection_update(B)                                                                                                                        
6.02 µs ± 2.72 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

On this rate performing this for 2 billion bits should take about 12 ms. And even if the example has many more coatoms, in the worst case (completely unrealistic, because the dimension is not 1 and more memory is needed for other dimensions and probably for other threads), there are bitwise operations performed twice for the entire RAM. Say, we have 1 TB RAM, this would then take 96 seconds. Okay, that is long, but in any realistic sceanrio it would only take about a second, even with 1 TB RAM.

To sum up, I think the current amount of sig_checks suffices for the next years until more than 1 TB RAM is common (and even then, it doubt that there is an application for such a large example, as it would take forever to compute).

comment:8 Changed 9 months ago by gh-kliem

  • Branch changed from u/gh-kliem/first_parallel_version_of_face_iterator to u/gh-kliem/first_parallel_version_of_face_iterator_reb
  • Commit changed from e3bdc617538af4ab8cdcf147fd74f4e62da5ff2a to 928ea608dc56698cd8df3d71b8266e75c28670eb

Rebased.

I didn't have this ticket here ready when writing #30445.

Eventually, one could also store edges/ridges or any sort of face in parallel. This would also help with applications for simplicial complexes and lattice of flats of manifolds.

But that should be left for another time.


New commits:

6a2a9b4fix merge conflict with develop in particual #30445
928ea60remove redundant allocation

comment:9 Changed 9 months ago by tscrim

  • Status changed from needs_review to positive_review

Thank you. This is quite a nice improvement.

comment:10 Changed 9 months ago by gh-kliem

Thank you.

comment:11 Changed 9 months ago by vbraun

On the kucalc buildbot:

[sagelib-9.3.beta6] [1/1] gcc -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -O2 -g -march=native -fPIC -I/var/lib/buildbot/slave/sage_git/build/local/lib/python3.9/site-packages/cysignals -I./sage/data_structures -I./sage/cpython -Isage/cpython -Isage/data_structures -I/var/lib/buildbot/slave/sage_git/build/build/pkgs/sagelib/src -I/var/lib/buildbot/slave/sage_git/build/local/include/python3.9 -I/var/lib/buildbot/slave/sage_git/build/local/lib/python3.9/site-packages/numpy/core/include -Ibuild/cythonized -I/var/lib/buildbot/slave/sage_git/build/local/include/python3.9 -c build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c -o build/temp.linux-x86_64-3.9/build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.o -fno-strict-aliasing -DCYTHON_CLINE_IN_TRACEBACK=1 -fopenmp -std=c99
[sagelib-9.3.beta6] In file included from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:660:0:
[sagelib-9.3.beta6] /var/lib/buildbot/slave/sage_git/build/local/lib/python3.9/site-packages/cysignals/struct_signals.h:45:1: sorry, unimplemented: ‘_Atomic’ with OpenMP
[sagelib-9.3.beta6]  typedef volatile _Atomic int cy_atomic_int;
[sagelib-9.3.beta6]  ^
[sagelib-9.3.beta6] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c: In function ‘__pyx_f_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_13face_iterator_prepare_face_iterator_for_partial_job’:
[sagelib-9.3.beta6] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:9035:54: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
[sagelib-9.3.beta6]    __pyx_t_2 = ((__pyx_v_structure->current_dimension == (__pyx_v_structure->dimension - __pyx_v_parallelization_depth)) != 0);
[sagelib-9.3.beta6]                                                       ^
[sagelib-9.3.beta6] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:9322:84: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
[sagelib-9.3.beta6]      __pyx_t_1 = (((__pyx_v_parallel_struct->current_job_id[__pyx_v_current_depth]) == -1L) != 0);
[sagelib-9.3.beta6]                                                                                     ^
[sagelib-9.3.beta6] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:9673:54: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
[sagelib-9.3.beta6]    __pyx_t_1 = ((__pyx_v_structure->current_dimension != ((__pyx_v_structure->dimension - __pyx_v_parallelization_depth) - 1)) != 0);
[sagelib-9.3.beta6]                                                       ^
[sagelib-9.3.beta6] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c: In function ‘__Pyx_InitGlobals’:
[sagelib-9.3.beta6] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:23283:1: warning: ‘PyEval_InitThreads’ is deprecated [-Wdeprecated-declarations]
[sagelib-9.3.beta6]  PyEval_InitThreads();
[sagelib-9.3.beta6]  ^
[sagelib-9.3.beta6] In file included from /var/lib/buildbot/slave/sage_git/build/local/include/python3.9/Python.h:145:0,
[sagelib-9.3.beta6]                  from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:52:
[sagelib-9.3.beta6] /var/lib/buildbot/slave/sage_git/build/local/include/python3.9/ceval.h:130:37: note: declared here
[sagelib-9.3.beta6]  Py_DEPRECATED(3.9) PyAPI_FUNC(void) PyEval_InitThreads(void);
[sagelib-9.3.beta6]                                      ^
[sagelib-9.3.beta6] error: command '/usr/bin/gcc' failed with exit code 1

comment:12 Changed 9 months ago by vbraun

  • Status changed from positive_review to needs_work

comment:13 Changed 9 months ago by gh-kliem

This appears to be an issue with python 3.5 to 3.7 according to https://bugs.python.org/issue25150

From this I get that this can be "fixed" by doing this specific module as a C++ extension (or by requiring system python >= 3.8, but that isn't an option for the moment).

I'll check if I can reproduce this with system python 3.7 (need to rebuild first).

comment:14 Changed 9 months ago by gh-kliem

Actually, that is a problem with cysignals that should be fixed there.

comment:15 Changed 9 months ago by git

  • Commit changed from 928ea608dc56698cd8df3d71b8266e75c28670eb to baf80deaca74b037c11e5eee914009e216f3beed

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

baf80detry disabling CYSIGNALS_C_ATOMIC

comment:17 Changed 9 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:18 Changed 9 months ago by tscrim

  • Status changed from needs_review to positive_review

Back off to the builbots.

comment:19 follow-up: Changed 7 months ago by vbraun

Build fails on various buildbots:

[sagelib-9.3.beta7] [1/1] gcc -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -O2 -g -march=native -O2 -g -march=native -fPIC -UCYSIGNALS_C_ATOMIC -I/home/buildbot/slave/sage_git/build/local/lib/python3.9/site-packages/cysignals -I./sage/data_structures -I./sage/cpython -Isage/cpython -I/home/buildbot/slave/sage_git/build/build/pkgs/sagelib/src -I/home/buildbot/slave/sage_git/build/local/include/python3.9 -I/home/buildbot/slave/sage_git/build/local/lib/python3.9/site-packages/numpy/core/include -Ibuild/cythonized -I/home/buildbot/slave/sage_git/build/local/include/python3.9 -c build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c -o build/temp.linux-x86_64-3.9/build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.o -fno-strict-aliasing -DCYTHON_CLINE_IN_TRACEBACK=1 -fopenmp -std=c99
[sagelib-9.3.beta7] In file included from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:662:0:
[sagelib-9.3.beta7] /home/buildbot/slave/sage_git/build/local/lib/python3.9/site-packages/cysignals/struct_signals.h:45:1: sorry, unimplemented: ‘_Atomic’ with OpenMP
[sagelib-9.3.beta7]  typedef volatile _Atomic int cy_atomic_int;
[sagelib-9.3.beta7]  ^~~~~~~
[sagelib-9.3.beta7] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c: In function ‘__pyx_f_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_13face_iterator_prepare_face_iterator_for_partial_job’:
[sagelib-9.3.beta7] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:9037:54: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
[sagelib-9.3.beta7]    __pyx_t_2 = ((__pyx_v_structure->current_dimension == (__pyx_v_structure->dimension - __pyx_v_parallelization_depth)) != 0);
[sagelib-9.3.beta7]                                                       ^~
[sagelib-9.3.beta7] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:9324:84: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
[sagelib-9.3.beta7]      __pyx_t_1 = (((__pyx_v_parallel_struct->current_job_id[__pyx_v_current_depth]) == -1L) != 0);
[sagelib-9.3.beta7]                                                                                     ^~
[sagelib-9.3.beta7] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:9675:54: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
[sagelib-9.3.beta7]    __pyx_t_1 = ((__pyx_v_structure->current_dimension != ((__pyx_v_structure->dimension - __pyx_v_parallelization_depth) - 1)) != 0);
[sagelib-9.3.beta7]                                                       ^~
[sagelib-9.3.beta7] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c: In function ‘__Pyx_InitGlobals’:
[sagelib-9.3.beta7] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:23285:1: warning: ‘PyEval_InitThreads’ is deprecated [-Wdeprecated-declarations]
[sagelib-9.3.beta7]  PyEval_InitThreads();
[sagelib-9.3.beta7]  ^~~~~~~~~~~~~~~~~~
[sagelib-9.3.beta7] In file included from /home/buildbot/slave/sage_git/build/local/include/python3.9/Python.h:145:0,
[sagelib-9.3.beta7]                  from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:54:
[sagelib-9.3.beta7] /home/buildbot/slave/sage_git/build/local/include/python3.9/ceval.h:130:37: note: declared here
[sagelib-9.3.beta7]  Py_DEPRECATED(3.9) PyAPI_FUNC(void) PyEval_InitThreads(void);
[sagelib-9.3.beta7]                                      ^~~~~~~~~~~~~~~~~~
[sagelib-9.3.beta7] error: command '/usr/bin/gcc' failed with exit code 1
[sagelib-9.3.beta7] 
[sagelib-9.3.beta7] real	0m3.325s
[sagelib-9.3.beta7] user	0m2.798s
[sagelib-9.3.beta7] sys	0m0.563s
Makefile:2233: recipe for target 'sagelib-no-deps' failed

comment:20 Changed 7 months ago by git

  • Commit changed from baf80deaca74b037c11e5eee914009e216f3beed to da65d28f81ddb7a865d0af830d14bb4132c3c1cb
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

da65d28Revert "try disabling CYSIGNALS_C_ATOMIC"

comment:21 Changed 7 months ago by gh-kliem

  • Dependencies changed from #31226 to #31226, #31455

comment:22 Changed 7 months ago by gh-kliem

  • Milestone changed from sage-9.3 to sage-9.4

I don't think this is going to happen with 9.3 anymore, if this is waiting on a cysignals patch/update.

comment:23 Changed 7 months ago by git

  • Commit changed from da65d28f81ddb7a865d0af830d14bb4132c3c1cb to 405ef3e3bb65ac1c610727c590daf75c19048c45

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

405ef3eMerge branch 'u/gh-kliem/first_parallel_version_of_face_iterator_reb' of git://trac.sagemath.org/sage into u/gh-kliem/first_parallel_version_of_face_iterator_reb2

comment:24 in reply to: ↑ 19 Changed 7 months ago by gh-kliem

This bug isn't too hard to reproduce actually:

https://github.com/kliem/sage/runs/2064520070?check_suite_focus=true

Seems to be connected to older GCC.

Replying to vbraun:

Build fails on various buildbots:

[sagelib-9.3.beta7] [1/1] gcc -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -O2 -g -march=native -O2 -g -march=native -fPIC -UCYSIGNALS_C_ATOMIC -I/home/buildbot/slave/sage_git/build/local/lib/python3.9/site-packages/cysignals -I./sage/data_structures -I./sage/cpython -Isage/cpython -I/home/buildbot/slave/sage_git/build/build/pkgs/sagelib/src -I/home/buildbot/slave/sage_git/build/local/include/python3.9 -I/home/buildbot/slave/sage_git/build/local/lib/python3.9/site-packages/numpy/core/include -Ibuild/cythonized -I/home/buildbot/slave/sage_git/build/local/include/python3.9 -c build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c -o build/temp.linux-x86_64-3.9/build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.o -fno-strict-aliasing -DCYTHON_CLINE_IN_TRACEBACK=1 -fopenmp -std=c99
[sagelib-9.3.beta7] In file included from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:662:0:
[sagelib-9.3.beta7] /home/buildbot/slave/sage_git/build/local/lib/python3.9/site-packages/cysignals/struct_signals.h:45:1: sorry, unimplemented: ‘_Atomic’ with OpenMP
[sagelib-9.3.beta7]  typedef volatile _Atomic int cy_atomic_int;
[sagelib-9.3.beta7]  ^~~~~~~
[sagelib-9.3.beta7] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c: In function ‘__pyx_f_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_13face_iterator_prepare_face_iterator_for_partial_job’:
[sagelib-9.3.beta7] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:9037:54: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
[sagelib-9.3.beta7]    __pyx_t_2 = ((__pyx_v_structure->current_dimension == (__pyx_v_structure->dimension - __pyx_v_parallelization_depth)) != 0);
[sagelib-9.3.beta7]                                                       ^~
[sagelib-9.3.beta7] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:9324:84: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
[sagelib-9.3.beta7]      __pyx_t_1 = (((__pyx_v_parallel_struct->current_job_id[__pyx_v_current_depth]) == -1L) != 0);
[sagelib-9.3.beta7]                                                                                     ^~
[sagelib-9.3.beta7] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:9675:54: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
[sagelib-9.3.beta7]    __pyx_t_1 = ((__pyx_v_structure->current_dimension != ((__pyx_v_structure->dimension - __pyx_v_parallelization_depth) - 1)) != 0);
[sagelib-9.3.beta7]                                                       ^~
[sagelib-9.3.beta7] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c: In function ‘__Pyx_InitGlobals’:
[sagelib-9.3.beta7] build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:23285:1: warning: ‘PyEval_InitThreads’ is deprecated [-Wdeprecated-declarations]
[sagelib-9.3.beta7]  PyEval_InitThreads();
[sagelib-9.3.beta7]  ^~~~~~~~~~~~~~~~~~
[sagelib-9.3.beta7] In file included from /home/buildbot/slave/sage_git/build/local/include/python3.9/Python.h:145:0,
[sagelib-9.3.beta7]                  from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.c:54:
[sagelib-9.3.beta7] /home/buildbot/slave/sage_git/build/local/include/python3.9/ceval.h:130:37: note: declared here
[sagelib-9.3.beta7]  Py_DEPRECATED(3.9) PyAPI_FUNC(void) PyEval_InitThreads(void);
[sagelib-9.3.beta7]                                      ^~~~~~~~~~~~~~~~~~
[sagelib-9.3.beta7] error: command '/usr/bin/gcc' failed with exit code 1
[sagelib-9.3.beta7] 
[sagelib-9.3.beta7] real	0m3.325s
[sagelib-9.3.beta7] user	0m2.798s
[sagelib-9.3.beta7] sys	0m0.563s
Makefile:2233: recipe for target 'sagelib-no-deps' failed

comment:25 Changed 7 months ago by gh-kliem

  • Dependencies changed from #31226, #31455 to #31474

comment:26 Changed 7 months ago by gh-kliem

  • Status changed from needs_review to needs_work

This might need more work, as the flag -fopenmp isn't understood everywhere: https://github.com/kliem/sage/pull/40/checks?check_run_id=2076988665

So we should probably check out at configure time, whether our compiler supports this, similar to https://trac.sagemath.org/ticket/27122.

comment:27 Changed 7 months ago by gh-kliem

  • Dependencies changed from #31474 to #31474, #31499

comment:28 Changed 7 months ago by git

  • Commit changed from 405ef3e3bb65ac1c610727c590daf75c19048c45 to 27baa071a64d5f93ca49d5ca4c18ae8ca7fa892a

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

55a4634merge with current develop
6edd48bdefine cython aliases OPENMP_CFLAGS and OPENMP_CXXFLAGS
71f8950fixes to get the aliases to work
b76dc3cadd doctest that shows how use cython.parallel.prange
07cb470Merge branch 'u/gh-kliem/check_openmp_at_configuration' of git://trac.sagemath.org/sage into u/gh-kliem/first_parallel_version_of_face_iterator_reb
27baa07use OPENMP_CFLAGS

comment:29 Changed 7 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:30 Changed 7 months ago by gh-kliem

comment:31 Changed 7 months ago by git

  • Commit changed from 27baa071a64d5f93ca49d5ca4c18ae8ca7fa892a to ae482a4d07ebc5f68fe78b37a32919c85b94aef5

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

a9d3dfesplit to account for multiple arguments
ae482a4Merge branch 'u/gh-kliem/check_openmp_at_configuration' of git://trac.sagemath.org/sage into u/gh-kliem/first_parallel_version_of_face_iterator_reb

comment:32 Changed 6 months ago by tscrim

  • Status changed from needs_review to positive_review

comment:33 Changed 6 months ago by gh-kliem

Thanks again.

comment:34 Changed 5 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:35 Changed 5 months ago by gh-kliem

  • Branch changed from u/gh-kliem/first_parallel_version_of_face_iterator_reb to u/gh-kliem/first_parallel_version_of_face_iterator_reb2
  • Commit changed from ae482a4d07ebc5f68fe78b37a32919c85b94aef5 to 2474ccc2d1b7fcbead0a5f9eb27470c9ee365e00

New commits:

2474cccMerge branch 'u/gh-kliem/first_parallel_version_of_face_iterator_reb' of git://trac.sagemath.org/sage into u/gh-kliem/first_parallel_version_of_face_iterator_reb2

comment:36 Changed 5 months ago by git

  • Commit changed from 2474ccc2d1b7fcbead0a5f9eb27470c9ee365e00 to fdbe95f9cf2b4787a59a459231074a7c528397f3

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

499af5dremove SAGE_HAVE_OPENMP
7b3da21move to sage_conf.py.in
927291fsimplifications
d71c54aset default
7d3f230more solid check
4f42440sage.env.cython_aliases: Do not fail if one of the listed libraries is not known to pkgconfig
3cb8f90sage.env.cython_aliases: Make module lapack optional; generalize the interface
c3cc31emerge in 31384
70a8791Merge branch 'u/gh-kliem/check_openmp_at_configuration' of git://trac.sagemath.org/sage into u/gh-kliem/first_parallel_version_of_face_iterator_reb2
fdbe95fuse cython.parallel.threadid instead of omp_get_thread_num

comment:37 Changed 5 months ago by gh-kliem

  • Status changed from needs_work to needs_review

I'm not sure this was actually a merge conflict.

But even on my laptop with OPENMP support I got missing symbols. Don't exactly understand this.

However, we can't use openmp.omp_get_num_threads for obvious reasons, because it doesn't have to be defined. Instead we should use cython.parallel.threadid, which takes care of this. It is supposed to work, just like prange.

comment:38 Changed 5 months ago by tscrim

  • Status changed from needs_review to positive_review

Works for me. Let's try this again...

comment:39 Changed 5 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:40 Changed 5 months ago by mkoeppe

  • Branch changed from u/gh-kliem/first_parallel_version_of_face_iterator_reb2 to u/mkoeppe/first_parallel_version_of_face_iterator_reb2

comment:41 Changed 5 months ago by mkoeppe

  • Commit changed from fdbe95f9cf2b4787a59a459231074a7c528397f3 to 4ae6966e49618739268625fbe5b9767ca6175200
  • Dependencies changed from #31474, #31499 to #31499
  • Status changed from needs_work to positive_review

New commits:

4ae6966Merge tag '9.4.beta0' into t/31245/first_parallel_version_of_face_iterator_reb2

comment:42 Changed 4 months ago by vbraun

  • Status changed from positive_review to needs_work

Segfaults reliably on OSX

sage -t --long --random-seed=0 src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx  # Killed due to segmentation fault
sage -t --long --random-seed=0 src/sage/geometry/polyhedron/base.py  # Killed due to segmentation fault

Debugger:

$ sage -sh
(sage-sh) sudo lldb ./local/bin/python3
(lldb) target create "./local/bin/python3"
Current executable set to '/Users/buildbot-sage/slave/sage_git/build/local/bin/python3' (x86_64).
(lldb) rfrom
error: 'rfrom' is not a valid command.
(lldb) r
Process 81901 launched: '/Users/buildbot-sage/slave/sage_git/build/local/bin/python3' (x86_64)
Python 3.9.5 (default, Jun  8 2021, 19:13:24) 
[Clang 12.0.5 (clang-1205.0.22.9)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from sage.all import *
>>> line = Polyhedron(lines=[[0,1]])
>>> line.vertex_graph() ## line 7185 ##
base.cpython-39-darwin.so was compiled with optimization - stepping may behave oddly; variables may not be available.
Process 81901 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
    frame #0: 0x00000001142ae934 base.cpython-39-darwin.so`__pyx_gb_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_4base_23CombinatorialPolyhedron_24_compute_edges_or_ridges_5generator29(__pyx_generator=0x0000000114562160, __pyx_tstate=0x0000000100508140, __pyx_sent_value=0x00000001003a8580) at base.c:28817:74 [opt]
   28814	  __pyx_t_2 = __pyx_t_1;
   28815	  for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
   28816	    __pyx_cur_scope->__pyx_v_i = __pyx_t_3;
-> 28817	    __pyx_t_4 = ((PyObject *)__pyx_f_4sage_5rings_7integer_smallInteger((__pyx_cur_scope->__pyx_outer_scope->__pyx_v_f_vector[__pyx_cur_scope->__pyx_v_i]))); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 3071, __pyx_L1_error)
   28818	    __Pyx_GOTREF(__pyx_t_4);
   28819	    __pyx_r = __pyx_t_4;
   28820	    __pyx_t_4 = 0;
Target 0: (python3) stopped.
(lldb) 
error: No auto repeat.
(lldb) bt
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
  * frame #0: 0x00000001142ae934 base.cpython-39-darwin.so`__pyx_gb_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_4base_23CombinatorialPolyhedron_24_compute_edges_or_ridges_5generator29(__pyx_generator=0x0000000114562160, __pyx_tstate=0x0000000100508140, __pyx_sent_value=0x00000001003a8580) at base.c:28817:74 [opt]
    frame #1: 0x00000001033bc4fa cachefunc.cpython-39-darwin.so`__Pyx_Coroutine_SendEx(self=0x0000000114562160, value=0x00000001003a8580, closing=<unavailable>) at cachefunc.c:28545:14 [opt]
    frame #2: 0x00000001001573c0 libpython3.9.dylib`PySequence_Tuple + 144
    frame #3: 0x00000001142abde3 base.cpython-39-darwin.so`__pyx_f_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_4base_23CombinatorialPolyhedron__compute_edges_or_ridges(__pyx_v_self=<unavailable>, __pyx_v_dual=<unavailable>, __pyx_v_do_edges=<unavailable>) at base.c:29447:19 [opt]
    frame #4: 0x00000001142b7aa7 base.cpython-39-darwin.so`__pyx_pw_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_4base_23CombinatorialPolyhedron_23edges [inlined] __pyx_f_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_4base_23CombinatorialPolyhedron__compute_edges(__pyx_v_self=<unavailable>, __pyx_v_dual=<unavailable>) at base.c:43309:15 [opt]
    frame #5: 0x00000001142b7a9b base.cpython-39-darwin.so`__pyx_pw_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_4base_23CombinatorialPolyhedron_23edges [inlined] __pyx_pf_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_4base_23CombinatorialPolyhedron_22edges(__pyx_v_self=0x0000000114235ca0, __pyx_v_names=0x0000000000000000) at base.c:14187 [opt]
    frame #6: 0x00000001142b742a base.cpython-39-darwin.so`__pyx_pw_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_4base_23CombinatorialPolyhedron_23edges(__pyx_v_self=0x0000000114235ca0, __pyx_args=<unavailable>, __pyx_kwds=<unavailable>) at base.c:13668 [opt]
    frame #7: 0x00000001001ab7c5 libpython3.9.dylib`cfunction_call + 69
    frame #8: 0x00000001142ca4d7 base.cpython-39-darwin.so`__pyx_gb_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_4base_23CombinatorialPolyhedron_12vertex_graph_2generator13 [inlined] __Pyx_PyObject_Call(func=0x0000000114569860, arg=<unavailable>, kw=0x0000000100722e80) at base.c:52465:14 [opt]
    frame #9: 0x00000001142ca49a base.cpython-39-darwin.so`__pyx_gb_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_4base_23CombinatorialPolyhedron_12vertex_graph_2generator13(__pyx_generator=0x0000000112ae5b80, __pyx_tstate=<unavailable>, __pyx_sent_value=<unavailable>) at base.c:14600 [opt]
    frame #10: 0x00000001033bc4fa cachefunc.cpython-39-darwin.so`__Pyx_Coroutine_SendEx(self=0x0000000112ae5b80, value=0x00000001003a8580, closing=<unavailable>) at cachefunc.c:28545:14 [opt]
    frame #11: 0x00000001001573c0 libpython3.9.dylib`PySequence_Tuple + 144
    frame #12: 0x00000001142b86c8 base.cpython-39-darwin.so`__pyx_pw_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_4base_23CombinatorialPolyhedron_25vertex_graph [inlined] __pyx_pf_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_4base_23CombinatorialPolyhedron_24vertex_graph(__pyx_v_self=<unavailable>, __pyx_v_names=0x0000000000000000) at base.c:14808:15 [opt]
    frame #13: 0x00000001142b85bb base.cpython-39-darwin.so`__pyx_pw_4sage_8geometry_10polyhedron_24combinatorial_polyhedron_4base_23CombinatorialPolyhedron_25vertex_graph(__pyx_v_self=<unavailable>, __pyx_args=<unavailable>, __pyx_kwds=<unavailable>) at base.c:14515 [opt]
    frame #14: 0x00000001001759c3 libpython3.9.dylib`method_vectorcall_VARARGS_KEYWORDS + 275
    frame #15: 0x000000010024bc1b libpython3.9.dylib`call_function + 411
    frame #16: 0x0000000100248c0b libpython3.9.dylib`_PyEval_EvalFrameDefault + 27147
    frame #17: 0x000000010016d5b5 libpython3.9.dylib`function_code_fastcall + 229
    frame #18: 0x000000010016f89c libpython3.9.dylib`method_vectorcall + 204
    frame #19: 0x000000010024bc1b libpython3.9.dylib`call_function + 411
    frame #20: 0x0000000100248c2e libpython3.9.dylib`_PyEval_EvalFrameDefault + 27182
    frame #21: 0x000000010024c9d4 libpython3.9.dylib`_PyEval_EvalCode + 2580
    frame #22: 0x0000000100242107 libpython3.9.dylib`PyEval_EvalCode + 87
    frame #23: 0x000000010028c45f libpython3.9.dylib`PyRun_InteractiveOneObjectEx + 847
    frame #24: 0x000000010028ba59 libpython3.9.dylib`PyRun_InteractiveLoopFlags + 169
    frame #25: 0x000000010028b97c libpython3.9.dylib`PyRun_AnyFileExFlags + 60
    frame #26: 0x00000001002a84ea libpython3.9.dylib`Py_RunMain + 2362
    frame #27: 0x00000001002a87ec libpython3.9.dylib`pymain_main + 348
    frame #28: 0x00000001002a883b libpython3.9.dylib`Py_BytesMain + 43
    frame #29: 0x00007fff20394621 libdyld.dylib`start + 1
    frame #30: 0x00007fff20394621 libdyld.dylib`start + 1

comment:43 Changed 4 months ago by gh-kliem

Thanks Volker for the precise log.

Unfortunately, I neither understand the problem nor can reproduce it. I could just disable OpenMP with clang by default and hope this solves the problem.

comment:44 Changed 4 months ago by gh-kliem

  • Branch changed from u/mkoeppe/first_parallel_version_of_face_iterator_reb2 to u/gh-kliem/first_parallel_version_of_face_iterator_reb3
  • Commit changed from 4ae6966e49618739268625fbe5b9767ca6175200 to 4c0a4ae74c28680e48080c39c5e3b171a79a9ad3
  • Dependencies #31499 deleted
  • Status changed from needs_work to needs_review

I think I tracked it down. I assumed that

cdef bint do_f_vector

is initialized to zero, which apparently isn't always the case.

Then Volkers report also makes sense.


New commits:

bfb4efbMerge branch 'u/mkoeppe/first_parallel_version_of_face_iterator_reb2' of git://trac.sagemath.org/sage into u/mkoeppe/first_parallel_version_of_face_iterator_reb3
4c0a4aeinitialize do_f_vector

comment:45 Changed 4 months ago by gh-kliem

I really don't understand why this pops out just now and not earlier.

comment:46 follow-up: Changed 4 months ago by vbraun

Uninitialized variables are whatever the RAM content is when they enter scope. However, any RAM region that you get from the OS is zeroed out (so you can't read content from older processes). So uninitialized variables tend to be zero initially, but the longer the program runs the more likely it becomes that the variable occupies a previously-used memory location.

More precisely, only global and static C variables are guaranteed to be initialized to zero, local variables are not.

Valgrind can detect these things for you (i.e. when you read uninitialized memory)

comment:47 in reply to: ↑ 46 Changed 4 months ago by gh-kliem

Replying to vbraun:

Uninitialized variables are whatever the RAM content is when they enter scope. However, any RAM region that you get from the OS is zeroed out (so you can't read content from older processes). So uninitialized variables tend to be zero initially, but the longer the program runs the more likely it becomes that the variable occupies a previously-used memory location.

More precisely, only global and static C variables are guaranteed to be initialized to zero, local variables are not.

Valgrind can detect these things for you (i.e. when you read uninitialized memory)

Thank you for the explanation.

Once I found out where the problem lies, I wasn't that confused anymore. I originally thought it had something to do with the current ticket, but it doesn't, it just appears now, probably because it now gets stabely compiled in a slightly different way.

In this case it is actually a mistake I made (which I in theory knew about, when I made it). I never meant to assume anything on an unitialized bint: There where two cases and depending on the case I would set it to True and False and then I added special handling for corner cases and forgot to initialize the bint.

I didn't know that RAM is zeroed out before the process, but once you mention it, of course this is how it ought to be.

comment:48 Changed 4 months ago by tscrim

  • Status changed from needs_review to positive_review

Hopefully this will be the last iteration of this. Sorry for having to redo this a bunch of times Volker; I just haven't been able to locally recreate any of the issues.

comment:49 Changed 4 months ago by vbraun

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