Opened 2 years ago

Closed 2 years ago

Last modified 2 years ago

#30596 closed enhancement (fixed)

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

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.2
Component: cython Keywords: bitset, cython, intrinsics
Cc: Travis Scrimshaw Merged in:
Authors: Jonathan Kliem Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 49a95f3 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description

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

Change History (19)

comment:1 Changed 2 years ago by gh-kliem

Status: newneeds_review

comment:2 Changed 2 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

LGTM.

comment:3 Changed 2 years ago by gh-kliem

Thank you.

comment:4 Changed 2 years ago by François Bissey

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.

comment:5 Changed 2 years ago by Travis Scrimshaw

I am not able to reproduce this on my machine.

comment:6 Changed 2 years ago by François Bissey

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

comment:7 in reply to:  6 Changed 2 years ago by Travis Scrimshaw

Replying to fbissey:

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.

comment:8 Changed 2 years ago by François Bissey

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.

comment:9 Changed 2 years ago by Travis Scrimshaw

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.

comment:10 Changed 2 years ago by François Bissey

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.

comment:11 Changed 2 years ago by Travis Scrimshaw

It is using my system gcc:

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

comment:12 Changed 2 years ago by Travis Scrimshaw

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?

comment:13 Changed 2 years ago by François Bissey

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.

Last edited 2 years ago by François Bissey (previous) (diff)

comment:14 Changed 2 years ago by François Bissey

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

comment:15 Changed 2 years ago by François Bissey

Well

  • sage/data_structures/bitset_intrinsics.h

    a b  
    99#############################################################################
    1010*/
    1111
    12 inline int _bitset_isempty(mp_limb_t* bits, mp_bitcnt_t limbs){
     12static inline int _bitset_isempty(mp_limb_t* bits, mp_bitcnt_t limbs){
    1313    /*
    1414    Test whether bits is empty.  Return True (i.e., 1) if the set is
    1515    empty, False (i.e., 0) otherwise.
    inline int _bitset_isempty(mp_limb_t* bits, mp_bitcnt_t limbs){ 
    2424    return mpn_cmp(bits+1, bits, limbs-1) == 0;
    2525}
    2626
    27 inline int _bitset_eq(mp_limb_t* a, mp_limb_t* b, mp_bitcnt_t limbs){
     27static inline int _bitset_eq(mp_limb_t* a, mp_limb_t* b, mp_bitcnt_t limbs){
    2828    /*
    2929    Compare bitset a and b.  Return True (i.e., 1) if the sets are
    3030    equal, and False (i.e., 0) otherwise.
    inline int _bitset_eq(mp_limb_t* a, mp_limb_t* b, mp_bitcnt_t limbs){ 
    3232    return mpn_cmp(a, b, limbs) == 0;
    3333}
    3434
    35 inline int _bitset_issubset(mp_limb_t* a, mp_limb_t* b, mp_bitcnt_t limbs){
     35static inline int _bitset_issubset(mp_limb_t* a, mp_limb_t* b, mp_bitcnt_t limbs){
    3636    /*
    3737    Test whether a is a subset of b (i.e., every element in a is also
    3838    in b).

did the trick, I have a successful build now.

comment:16 Changed 2 years ago by Volker Braun

Branch: u/gh-kliem/bitset_outsource_functions_optimizable_by_intrinsics49a95f3f11e7c5b42397066a4d56636df60019fd
Resolution: fixed
Status: positive_reviewclosed

comment:17 Changed 2 years ago by Travis Scrimshaw

Commit: 49a95f3f11e7c5b42397066a4d56636df60019fd

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

comment:18 Changed 2 years ago by François Bissey

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.

comment:19 Changed 2 years ago by François Bissey

Follow up is at #30675.

Note: See TracTickets for help on using tickets.