C ++에서 유지 관리 가능하고 빠른 컴파일 타임 비트 마스크를 작성하는 방법
다음과 같은 코드가 있습니다.
#include <bitset>
enum Flags { A = 1, B = 2, C = 3, D = 5,
E = 8, F = 13, G = 21, H,
I, J, K, L, M, N, O };
void apply_known_mask(std::bitset<64> &bits) {
const Flags important_bits[] = { B, D, E, H, K, M, L, O };
std::remove_reference<decltype(bits)>::type mask{};
for (const auto& bit : important_bits) {
mask.set(bit);
}
bits &= mask;
}
Clang> = 3.6 은 현명한 작업을 수행하고 이것을 단일 and명령어로 컴파일합니다 (그런 다음 다른 곳에서는 인라인 됨).
apply_known_mask(std::bitset<64ul>&): # @apply_known_mask(std::bitset<64ul>&)
and qword ptr [rdi], 775946532
ret
그러나 내가 시도한 모든 버전의 GCC는 이것을 정적으로 DCE 해야하는 오류 처리를 포함하는 거대한 혼란으로 컴파일합니다. 다른 코드에서는 코드 important_bits와 동일한 데이터를 데이터와 동일 하게 배치합니다 !
.LC0:
.string "bitset::set"
.LC1:
.string "%s: __position (which is %zu) >= _Nb (which is %zu)"
apply_known_mask(std::bitset<64ul>&):
sub rsp, 40
xor esi, esi
mov ecx, 2
movabs rax, 21474836482
mov QWORD PTR [rsp], rax
mov r8d, 1
movabs rax, 94489280520
mov QWORD PTR [rsp+8], rax
movabs rax, 115964117017
mov QWORD PTR [rsp+16], rax
movabs rax, 124554051610
mov QWORD PTR [rsp+24], rax
mov rax, rsp
jmp .L2
.L3:
mov edx, DWORD PTR [rax]
mov rcx, rdx
cmp edx, 63
ja .L7
.L2:
mov rdx, r8
add rax, 4
sal rdx, cl
lea rcx, [rsp+32]
or rsi, rdx
cmp rax, rcx
jne .L3
and QWORD PTR [rdi], rsi
add rsp, 40
ret
.L7:
mov ecx, 64
mov esi, OFFSET FLAT:.LC0
mov edi, OFFSET FLAT:.LC1
xor eax, eax
call std::__throw_out_of_range_fmt(char const*, ...)
두 컴파일러 모두 올바른 작업을 수행 할 수 있도록이 코드를 어떻게 작성해야합니까? 실패하면 명확하고 빠르며 유지 관리가 가능하도록 어떻게 작성해야합니까?
최고의 버전은 C ++ 17입니다 .
template< unsigned char... indexes >
constexpr unsigned long long mask(){
return ((1ull<<indexes)|...|0ull);
}
그때
void apply_known_mask(std::bitset<64> &bits) {
constexpr auto m = mask<B,D,E,H,K,M,L,O>();
bits &= m;
}
다시 c ++ 14로 돌아가서이 이상한 속임수를 쓸 수 있습니다 :
template< unsigned char... indexes >
constexpr unsigned long long mask(){
auto r = 0ull;
using discard_t = int[]; // data never used
// value never used:
discard_t discard = {0,(void(
r |= (1ull << indexes) // side effect, used
),0)...};
(void)discard; // block unused var warnings
return r;
}
또는 c ++ 11 이 붙어 있으면 재귀 적으로 해결할 수 있습니다.
constexpr unsigned long long mask(){
return 0;
}
template<class...Tail>
constexpr unsigned long long mask(unsigned char b0, Tail...tail){
return (1ull<<b0) | mask(tail...);
}
template< unsigned char... indexes >
constexpr unsigned long long mask(){
return mask(indexes...);
}
Godbolt 모두 3 -CPP_VERSION 정의를 전환하고 동일한 어셈블리를 얻을 수 있습니다.
실제로 저는 가장 현대적인 것을 사용했습니다. 우리는 재귀가 없으므로 O (n ^ 2) 심볼 길이 (컴파일 시간 및 컴파일러 메모리 사용량을 폭발시킬 수 있음)가 없으므로 14 비트는 11입니다. 컴파일러가 해당 배열을 데드 코드 제거 할 필요가없고 배열 트릭이 추악하기 때문에 17이 14를 이겼습니다.
이 중 14 개가 가장 혼란 스럽다. 여기서 우리는 모든 0의 익명 배열을 만들고 부작용으로 결과를 구성한 다음 배열을 버립니다. 버려진 배열은 팩의 크기에 1을 더한 0과 빈 팩을 처리 할 수 있도록 1을 더합니다.
c ++ 14 버전 의 기능에 대한 자세한 설명 이것은 속임수이며, C ++ 14에서 효율적으로 매개 변수 팩을 확장하기 위해이 작업을 수행해야한다는 사실은 접는식이 c ++ 17에 추가 된 이유 중 하나입니다 .
내부에서 가장 잘 이해됩니다.
r |= (1ull << indexes) // side effect, used
이것은 고정 인덱스로 업데이트 r됩니다 1<<indexes. indexes매개 변수 팩이므로 확장해야합니다.
나머지 작업은 indexes내부 로 확장 할 매개 변수 팩을 제공하는 것 입니다.
한 걸음 :
(void(
r |= (1ull << indexes) // side effect, used
),0)
여기에 우리가 우리의 표현을 던져 void우리가 반환 값에 대한 상관 없어 나타내는, (우리는 단지 설정의 부작용을 원하는 r- C ++에서 표현이 좋아 a |= b도가 설정 한 값 반환 a에를).
그런 다음 우리는 쉼표 연산자를 사용 ,하고 0폐기하는 void"가치", 값을 반환합니다 0. 따라서 이것은 값이있는 표현식 0이며 계산의 부작용 0으로 비트를 설정합니다 r.
int discard[] = {0,(void(
r |= (1ull << indexes) // side effect, used
),0)...};
이 시점에서 파라미터 팩을 확장합니다 indexes. 그래서 우리는 얻는다 :
{
0,
(expression that sets a bit and returns 0),
(expression that sets a bit and returns 0),
[...]
(expression that sets a bit and returns 0),
}
에서 {}. 이러한 사용 ,이다 하지 콤마 연산자가 아니라 어레이 소자 분리막. 이것은 부작용으로 sizeof...(indexes)+1 0비트를 설정하는 s r입니다. 그런 다음 {}배열 구성 명령어를 배열에 할당합니다 discard.
다음으로 우리는 캐스팅 discard합니다 void-변수를 만들고 읽지 않으면 대부분의 컴파일러가 경고합니다. 당신이 그것을 캐스팅하면 모든 컴파일러가 불평하지 않을 것입니다. void"예, 알아요, 이것을 사용하지 않습니다"라고 말하는 방식이므로 경고가 표시되지 않습니다.
찾고있는 최적화는에서 -O3또는 수동으로 활성화 된 루프 필링 인 것 같습니다 -fpeel-loops. 왜 이것이 루프 언 롤링이 아닌 루프 필링의 범위에 해당하는지 잘 모르겠지만, 아마도 내부에서 비 로컬 제어 흐름이있는 루프를 풀지 않을 것입니다 (잠재적으로 범위 확인에서).
그러나 기본적으로 GCC는 모든 반복을 벗길 수 없기 때문에 중지해야합니다. 실험적으로 -O2 -fpeel-loops --param max-peeled-insns=200(기본값 100)을 전달 하면 원래 코드로 작업이 완료됩니다. https://godbolt.org/z/NNWrga
C ++ 11 만 사용해야 (&a)[N]하는 경우 배열을 캡처하는 방법입니다. 이를 통해 도우미 함수를 사용하지 않고도 단일 재귀 함수를 작성할 수 있습니다.
template <std::size_t N>
constexpr std::uint64_t generate_mask(Flags const (&a)[N], std::size_t i = 0u){
return i < N ? (1ull << a[i] | generate_mask(a, i + 1u)) : 0ull;
}
그것을 다음에 할당 constexpr auto:
void apply_known_mask(std::bitset<64>& bits) {
constexpr const Flags important_bits[] = { B, D, E, H, K, M, L, O };
constexpr auto m = generate_mask(important_bits); //< here
bits &= m;
}
테스트
int main() {
std::bitset<64> b;
b.flip();
apply_known_mask(b);
std::cout << b.to_string() << '\n';
}
산출
0000000000000000000000000000000000101110010000000000000100100100
// ^ ^^^ ^ ^ ^ ^
// O MLK H E D B
컴파일 타임에 계산 가능한 튜링을 계산할 수있는 C ++의 능력을 높이 평가해야합니다. 그것은 여전히 내 마음을 날려 버립니다 ( <> ).
이후 버전의 C ++ 14 및 C ++ 17 yakk의 대답은 이미 훌륭하게 다루고 있습니다.
적절한 EnumSet유형 을 작성하도록 권장합니다 .
Writing a basic EnumSet<E> in C++14 (onwards) based on std::uint64_t is trivial:
template <typename E>
class EnumSet {
public:
constexpr EnumSet() = default;
constexpr EnumSet(std::initializer_list<E> values) {
for (auto e : values) {
set(e);
}
}
constexpr bool has(E e) const { return mData & mask(e); }
constexpr EnumSet& set(E e) { mData |= mask(e); return *this; }
constexpr EnumSet& unset(E e) { mData &= ~mask(e); return *this; }
constexpr EnumSet& operator&=(const EnumSet& other) {
mData &= other.mData;
return *this;
}
constexpr EnumSet& operator|=(const EnumSet& other) {
mData |= other.mData;
return *this;
}
private:
static constexpr std::uint64_t mask(E e) {
return std::uint64_t(1) << e;
}
std::uint64_t mData = 0;
};
This allows you to write simple code:
void apply_known_mask(EnumSet<Flags>& flags) {
static constexpr EnumSet<Flags> IMPORTANT{ B, D, E, H, K, M, L, O };
flags &= IMPORTANT;
}
In C++11, it requires some convolutions, but remains possible nonetheless:
template <typename E>
class EnumSet {
public:
template <E... Values>
static constexpr EnumSet make() {
return EnumSet(make_impl(Values...));
}
constexpr EnumSet() = default;
constexpr bool has(E e) const { return mData & mask(e); }
void set(E e) { mData |= mask(e); }
void unset(E e) { mData &= ~mask(e); }
EnumSet& operator&=(const EnumSet& other) {
mData &= other.mData;
return *this;
}
EnumSet& operator|=(const EnumSet& other) {
mData |= other.mData;
return *this;
}
private:
static constexpr std::uint64_t mask(E e) {
return std::uint64_t(1) << e;
}
static constexpr std::uint64_t make_impl() { return 0; }
template <typename... Tail>
static constexpr std::uint64_t make_impl(E head, Tail... tail) {
return mask(head) | make_impl(tail...);
}
explicit constexpr EnumSet(std::uint64_t data): mData(data) {}
std::uint64_t mData = 0;
};
And is invoked with:
void apply_known_mask(EnumSet<Flags>& flags) {
static constexpr EnumSet<Flags> IMPORTANT =
EnumSet<Flags>::make<B, D, E, H, K, M, L, O>();
flags &= IMPORTANT;
}
Even GCC trivially generates an and instruction at -O1 godbolt:
apply_known_mask(EnumSet<Flags>&):
and QWORD PTR [rdi], 775946532
ret
Since C++11 you could also use classic TMP technique:
template<std::uint64_t Flag, std::uint64_t... Flags>
struct bitmask
{
static constexpr std::uint64_t mask =
bitmask<Flag>::value | bitmask<Flags...>::value;
};
template<std::uint64_t Flag>
struct bitmask<Flag>
{
static constexpr std::uint64_t value = (uint64_t)1 << Flag;
};
void apply_known_mask(std::bitset<64> &bits)
{
constexpr auto mask = bitmask<B, D, E, H, K, M, L, O>::value;
bits &= mask;
}
Link to Compiler Explorer: https://godbolt.org/z/Gk6KX1
The advantage of this approach over template constexpr function is that it's potentially slightly faster to compile due to rule of Chiel.
There are some far to 'clever' ideas here. You are probably not helping maintainability by following them.
is
{B, D, E, H, K, M, L, O};
so much easier to write than
(B| D| E| H| K| M| L| O);
?
Then none of the rest of the code is needed.
'development' 카테고리의 다른 글
| 캐럿 (^) 문자는 무엇을 의미합니까? (0) | 2020.07.26 |
|---|---|
| try / catch vs 예외 발생 (0) | 2020.07.26 |
| 분당 100k 적중을 얻기 위해 nginx worker_process 조정 (0) | 2020.07.26 |
| Thread.Sleep이 왜 그렇게 해로운가요? (0) | 2020.07.26 |
| 함수를 호출 할 때리스트를 * args로 변환 (0) | 2020.07.26 |