다음과 같은 코드가 있습니다.
#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...);
}
3 가지 모두 Godbolt -CPP_VERSION 정의를 전환하고 동일한 어셈블리를 얻을 수 있습니다.
실제로 나는 내가 할 수있는 가장 현대적인 것을 사용합니다. 재귀가없고 따라서 O (n ^ 2) 심볼 길이 (컴파일 시간과 컴파일러 메모리 사용량이 폭발적으로 증가 할 수 있음)가 없기 때문에 14는 11을 이깁니다. 컴파일러가 해당 배열을 데드 코드 제거 할 필요가 없기 때문에 17은 14를 이깁니다. 그 배열 트릭은보기 흉합니다.
이 중 14 개가 가장 혼란 스럽습니다. 여기에서는 모두 0으로 구성된 익명 배열을 만들고, 부작용으로 결과를 생성 한 다음 배열을 버립니다. 버려진 배열에는 팩의 크기와 동일한 0과 1 (빈 팩을 처리 할 수 있도록 추가)이 있습니다.
무엇에 대한 자세한 설명 C ++ 14버전이하고 있습니다. 이것은 트릭 / 해킹이며, C ++ 14에서 효율적으로 매개 변수 팩을 확장하기 위해 이렇게해야한다는 사실이 fold 표현식이 추가 된 이유 중 하나입니다.C ++ 17.
내부에서 가장 잘 이해됩니다.
r |= (1ull << indexes) // side effect, used
이것은 고정 인덱스에 대해 업데이트 r
됩니다 1<<indexes
. indexes
매개 변수 팩이므로 확장해야합니다.
나머지 작업은 indexes
내부 를 확장 할 매개 변수 팩을 제공하는 것 입니다.
한 단계 더 :
(void(
r |= (1ull << indexes) // side effect, used
),0)
여기에서 표현식을로 캐스트 void
하여 반환 값에 대해 신경 쓰지 않는다는 것을 나타냅니다 ( r
C ++에서는 설정의 부작용 만 원합니다. 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
유형 을 작성하는 것이 좋습니다 .
EnumSet<E>
C ++ 14 (이후)에서 기초를 작성하는 std::uint64_t
것은 간단합니다.
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;
};
이를 통해 간단한 코드를 작성할 수 있습니다.
void apply_known_mask(EnumSet<Flags>& flags) {
static constexpr EnumSet<Flags> IMPORTANT{ B, D, E, H, K, M, L, O };
flags &= IMPORTANT;
}
C ++ 11에서는 일부 회선이 필요하지만 그럼에도 불구하고 여전히 가능합니다.
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;
};
그리고 다음과 함께 호출됩니다.
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;
}
GCC조차도 godboltand
에서 명령을 생성합니다 .-O1
apply_known_mask(EnumSet<Flags>&):
and QWORD PTR [rdi], 775946532
ret
답변
C ++ 11부터 고전적인 TMP 기술을 사용할 수도 있습니다.
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;
}
컴파일러 탐색기 링크 : https://godbolt.org/z/Gk6KX1
템플릿 constexpr 함수에 비해이 접근 방식의 장점 은 Chiel 규칙 으로 인해 컴파일하는 것이 잠재적으로 약간 더 빠르다는 것 입니다.
답변
여기에는 ‘영리한’아이디어가 있습니다. 당신은 아마도 그들을 따라가는 것으로 유지 관리를 돕지 않을 것입니다.
이다
{B, D, E, H, K, M, L, O};
작성하기가 훨씬 쉽습니다.
(B| D| E| H| K| M| L| O);
?
그러면 나머지 코드는 필요하지 않습니다.