Outsource functions in bitset.pxi that can be optimized by intrinsics

[kliem]

We move functions that can easily optimized by CPU-specific instructions to a new file bitset_intrinsics.h.

CC: @tscrim

Component: cython

Keywords: bitset, intrinsics

Author: Jonathan Kliem

Branch: 49a95f3

Reviewer: Travis Scrimshaw

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

[tscrim]

comment:2

LGTM.

[tscrim]

Reviewer: Travis Scrimshaw

[kliem]

comment:3

Thank you.

[kiwifb]

comment:4

I got an issue when building the documentation on sage-on-gentoo with this

Traceback (most recent call last):
  File "sage_setup/docbuild/__main__.py", line 1, in <module>
    from sage_setup.docbuild import main
  File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_8/sage_setup/docbuild/__init__.py", line 58, in <module>
    import sage.all
  File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_8/build/lib/sage/all.py", line 129, in <module>
    from sage.data_structures.all import *
  File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_8/build/lib/sage/data_structures/all.py", line 3, in <module>
    from .bitset import Bitset, FrozenBitset
ImportError: /dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_8/build/lib/sage/data_structures/bitset.cpython-38-x86_64-linux-gnu.so: undefined symbol: _bitset_issubset

when examining the module more closely I see the following

ldd -r /dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_8/build/lib/sage/data_structures/bitset.cpython-38-x86_64-linux-gnu.so | grep _bit
undefined symbol: _bitset_issubset      (/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_8/build/lib/sage/data_structures/bitset.cpython-38-x86_64-linux-gnu.so)
undefined symbol: _bitset_isempty       (/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_8/build/lib/sage/data_structures/bitset.cpython-38-x86_64-linux-gnu.so)
undefined symbol: _bitset_eq    (/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_8/build/lib/sage/data_structures/bitset.cpython-38-x86_64-linux-gnu.so)

I am using gmp-6.0.2 with gcc-10.

[tscrim]

comment:5

I am not able to reproduce this on my machine.

[kiwifb]

comment:6

And the bot is green. This is very weird and why just those three? Volker is trying to merge this ticket at the moment and I am suspecting he may be seeing this or a variation.
It is not impossible that there is a bad interaction with another ticket.

Have you tried it together with #30572? Obviously same author and reviewers :)

[tscrim]

comment:7

Replying to @kiwifb:

Have you tried it together with #30572? Obviously same author and reviewers :)

I just tried both of them (well, more precisely, merging in #30572 and then rebuilding the doc), and I didn't have the problem either. Let me know if there is any information I can provide that might help you figure it out.

[kiwifb]

comment:8

Which version of gcc do you use? It seems that in C99 which is the default for C of gcc-10 in Gentoo inline is not always what you think it is.
https://stackoverflow.com/questions/19068705/undefined-reference-when-calling-inline-function
https://stackoverflow.com/questions/16245521/c99-inline-function-in-c-file

If I understand correctly some of these functions should be static inline.

[tscrim]

comment:9

My system gcc is 7.5.0, but I don't know if that is what Sage is using to compile. Is there an easy way for me to check if that is what Sage is using? IIRC, I have done a make distclean run somewhat recently before building.

[kiwifb]

comment:10

I guess ./sage -sh and then echo $CC should help you figure out which compiler is used. I would think 7.5.0 default to C99 too. I am going to run some test build shortly to figure out if using static for those functions solves the issue. I am somewhat weary of the fact that only three of these end up undefined. May be it'd be clearer if I understood the code and the standard better. But I am worried for some other compiler some other functions may end undefined.

[tscrim]

comment:11

It is using my system gcc:

(sage-sh) uqtscrim@SMP-36PQ8T2:sage$ echo $CC
gcc

[tscrim]

comment:12

Maybe we then ask that this not be included in 9.2 this late in the process, but instead in 9.3.beta0 so it can get broad testing across the developer group?

[kiwifb]

comment:13

I'd do a which gcc from sage-sh to be sure.

I am not sure how late we are in the 9.2 process. I have a feeling we have some objectives for 9.2 and we'll go for as long as it take. We already had a few more betas than usual.

[kiwifb]

comment:14

Well, the documentation has started to build now - instead of bailing out straight away as it would previously.

[kiwifb]

comment:15

Well

--- a/sage/data_structures/bitset_intrinsics.h
+++ b/sage/data_structures/bitset_intrinsics.h
@@ -9,7 +9,7 @@
 #############################################################################
 */
 
-inline int _bitset_isempty(mp_limb_t* bits, mp_bitcnt_t limbs){
+static inline int _bitset_isempty(mp_limb_t* bits, mp_bitcnt_t limbs){
     /*
     Test whether bits is empty.  Return True (i.e., 1) if the set is
     empty, False (i.e., 0) otherwise.
@@ -24,7 +24,7 @@ inline int _bitset_isempty(mp_limb_t* bits, mp_bitcnt_t limbs){
     return mpn_cmp(bits+1, bits, limbs-1) == 0;
 }
 
-inline int _bitset_eq(mp_limb_t* a, mp_limb_t* b, mp_bitcnt_t limbs){
+static inline int _bitset_eq(mp_limb_t* a, mp_limb_t* b, mp_bitcnt_t limbs){
     /*
     Compare bitset a and b.  Return True (i.e., 1) if the sets are
     equal, and False (i.e., 0) otherwise.
@@ -32,7 +32,7 @@ inline int _bitset_eq(mp_limb_t* a, mp_limb_t* b, mp_bitcnt_t limbs){
     return mpn_cmp(a, b, limbs) == 0;
 }
 
-inline int _bitset_issubset(mp_limb_t* a, mp_limb_t* b, mp_bitcnt_t limbs){
+static inline int _bitset_issubset(mp_limb_t* a, mp_limb_t* b, mp_bitcnt_t limbs){
     /*
     Test whether a is a subset of b (i.e., every element in a is also
     in b).

did the trick, I have a successful build now.

[vbraun]

Changed branch from u/gh-kliem/bitset_outsource_functions_optimizable_by_intrinsics to 49a95f3

[tscrim]

comment:17

I guess then perhaps we need to make it a followup ticket...

[tscrim]

Changed commit from 49a95f3 to none

[kiwifb]

comment:18

That would be nice. Although I must say I find it strange to be the only one spotting this. I would have expected some bots to fail too. There may be something more that causes the failure, even if adding static fixes it.

[kiwifb]

comment:19

Follow up is at #30675.