portable bit manipulation

[boothby]

This one might be somewhat controversial. I'd like to support a variety of compilers and platforms (specifically MSVC which doesn't define __builtin_* and ARM which doesn't even have a popcount instruction), and the portable snippets package handles this beautifully.

This patch inserts a compile-time check for inclusion of the builtin.h header file from the above, which provides __builtin_popcount and __builtin_ffsll. The approach I'm taking in minorminer is to haul portable-snippets in as a submodule, and make it appear as a system-level header. Working with submodules is a little obnoxious, but I'd already bit that bullet when incorporating glasgow-subgraph-solver as a submodule.

If you're interested in expanding your build system to take advantage of this #include you'd probably want to do something similar or perhaps just crib the CC0-licenced builtin.h file directly. That said, I'm bypassing your build system, so these few lines are sufficient for me. I'm happy to entertain shed-painting (is GLASGOW_SUBGRAPH_SOLVER_PORTABLE_BUILTINS really the right name for this) and different approaches to the problem.

Thanks!

[ciaranm]

C++20 adds https://en.cppreference.com/w/cpp/header/bit to the standard library, which is probably the correct long-term approach. Is this supported on all the compilers you're interested in? My "what C++ version to use" heuristic has been "whatever's in the current Ubuntu LTS release", which means C++20 is now an option.

[boothby]

I'm already nervous about c++17! Speaking personally, my heuristic is about 5 years so compiler-writers have time to shake the bugs out. But that's all feeling; I'll ask around the people who actually handle CI etc. at D-Wave and see if they've got strong reasons.

One fast answer I can figure out myself: my windows build stuff is currently on appveyor using MSVC 2019 14.29, which doesn't support C++20. However, if I'm patient, one of the CI wizards will eventually migrate me away from appveyor so that isn't a hard no.

[boothby]

That said... yes, that would be just fine! Worst case, I could provide the implementation details of <bit> myself, just as I have with boost.

If you started using tricky c++20 features like ranges, then there may be more of a challenge.

[boothby]

Drat. I may have been overly optimistic about bodging my own STL file into my build, as MSVC is quite unhappy. Please hold off on this one for now. I'll get back to you on upgrading to C++20 wholesale.

[boothby]

After quite a bit of digging, I have found a rather immovable obstacle: D-Wave supports less-than-current Python versions and operating systems, and for some of those version combinations, it is quite impossible to build C++20 code. My attempts at providing my own <bit> library have failed. @ciaranm would you be willing to accept the PR in a state similar to the original, perhaps with the option to use <bit> as below?

#ifdef USE_PORTABLE_SNIPPETS
#include <builtin.h>
int popcount(unsigned long long x) {
    return psnip_builtin_popcountll(x);
}
int countr_zero(unsigned long long x) {
    return psnip_builtin_ctzll(x);
}
#else
#include <bit>
using std::popcount;
using std::countr_zero;
#endif

[ciaranm]

Sorry for being slow -- I've been travelling, and am slowly catching up on my email backlog. Yes, I'd be happy to accept portability code for earlier C++ versions, so long as it can be done so reasonably cleanly like your suggestion.

[boothby]

No need to apologize, thanks for being understanding! I've just updated the PR to reflect the above. I'm going to leave the WIP on for just a little longer so I can double-check that it's going to work on my end.

[boothby]

I had to make a minor change; moving the implementation details into the cc file to prevent the compiler from emitting multiple implementations. The version as-is works on my end, if it's alright with you. Thanks for your patience!

[ciaranm]

Ah, I'm afraid this doesn't compile for me without the portable bitset things enabled. I think there are three issues combining here. First, main.mk will need to specify -std=c++20 instead of 17. Second, using only declares a name rather than defining it, so the link fails with that fixed. And third, countr_zero and __builtin_ctzll return different things.

Is there a strong reason not to put the #ifdef inside the header file, rather than the source file, and just to have two different implementations of the relevant bits of code? This will probably simplify things, and as an added bonus won't stop the compiler from inlining. It might be a bit of duplication, but perhaps this is the cleanest thing to do, given the differences between countr_zero and ctz...

[boothby]

My reasoning for moving code into the source file is that my cython build was producing two implementations in different compilation units and the linker wasn't having it. That's my mistake, I have not been testing your build. I'll find a solution that works for both. Thanks for your patience.

I'm not seeing a difference in the output of countr_zero and __builtin_ctzll. On what input do you see a difference?

Here's my test: https://godbolt.org/z/dY7cPzxoM

[boothby]

Okay, that was a bit of a rollercoaster. The issue with my test is that I was not running with optimization flags; so GCC's undefined behavior was behaving in the manner that I wanted. With optimization, its behavior is different. Not a compiler bug [1]. Yay! That's easy enough to work around; I test the input to countr_zero rather than the output.

Working around the differences between your build system was a small adventure of its own, but ultimately there is a graceful solution: I've hidden the code that wraps portable-snippets in an anonymous namespace so it doesn't appear in multiple compilation units (which, I learned, you are cleverly avoiding with the ar -nr command in your build system -- a technique not available to me).

I have tested this using your build system; and updated it to c++20. The patch is ready to go, except that I've put a note into README.md where you'll want to update with your newer build environment. Oh, and while you're there: I had to do a little workaround in 53226d4; see the commit message for an alternative (relevant if your boost is >1.81)

[1] https://stackoverflow.com/questions/64695111/gcc-wrong-compile-time-evaluation-of-builtin-ctz-in-some-situations-with-o2

[ciaranm]

Thanks very much for this.