Bit Hacks

[MIT OpenCourseWare] Bit Hacks

 

https://youtu.be/ZusiKXcz_ac?si=2uHDSpjQ7hHJohdj

 

 

Set the k-th Bit

Set k-th bit in a word x to 1.

 

Shift and OR.

 

Clear the k-th Bit

Clear the k-th bit in a word x.

 

Shift, completment, and AND.

 

Toggle the k-th Bit

Flip the k-th bit in a word x.

 

Shift and XOR.

 

Extract a Bit Field

Extract a bit field from a word x.

 

Mask and shift.

 

압축(Compressed)되어 있거나 인코딩(Encoded)된 데이터를 다룰 때 유용함.

 

Set a Bit Field

Set a bit field in a word x to a value y.

 

Invert mask to clear, and OR the shifted value.

For safety's sake : (y << shift) → ((y << shift) & mask)

- y가 높은 비트에 쓰레기 값을 갖고 있으면, 본래의 x 값이 오염될 수 있기 때문에 안전장치를 추가.

 

 

Ordinary Swap

Swap two integers x and y.

 

No-Temp Swap

Swap x and y without using a temporary.

 

두 번째 y = x ^ y; 가 완료되었을 때, y는 이미 이전의 x 값을 가지고 있음.

마지막으로  x =x ^ y;를 함으로써 Temp variable없이 Swap 성공.

 

Why it works

XOR is its own inverse : 

(x ^ y) ^ y => x

Performance

그다지 좋지 못함. 명령어 수준의 병렬성(Intsruction-Level Parallelism)을 활용하지 못하기 때문.

즉, CPU 레벨에서 슈퍼스칼라 등을 활용하지 못한다는 것인데, 3개의 연산이 전부 x, y를 사용하기 때문에 각각의 instruction이 전부 이전 x, y 결과 값에 의존적이기 때문인듯하다.

→ Temp를 쓴다면, 파이프라인 레벨에서 2개의 instruction을 병렬로 수행가능함.

 

Minimum of Two Integers

정수 x, y 둘 중 더 작은 값을 r에 저장해보자.

1) if - else statement

2) ternary operator

Performance

둘 다 if branch가 존재한다.

Caveat

현대 컴파일러는 일반적으로 예측불가능한 분기를 제거할만큼 충분히 똑똑하지만, 그렇지 않을 수도 있다.

 

No-Branch Minimum

분기없이 x, y 중 더 작은 값을 r에 저장하는 방법.

Why it works

우선, True / False가 각각 1과 0에 대응된다는 사실을 알고있다.
그리고 2가지 케이스를 생각해보자.

1) x < y인 경우

-(x < y)는 -1이 되는데, 2의 보수 표현법에서 -1은 모든 비트가 1이라는 것을 알고있다.

따라서 ((x ^ y) & -1)은 (x ^ y)와 동일하므로,

r = y ^ (x ^ y);

 

앞선 No-Branch Minimum에서, 2번의 xor을 하면 자기자신이라는 것 또한 알고 있으므로,

r = x

 

2) x >= y인 경우

-(x < y)는 0이 되므로, r = y ^ 0;

r = y

 

Merging Two Sorted Arrays

[1] Branch

아래 Merge Sort에 사용되는 서브루틴인 merge를 보자.

총 4개의 branch가 존재하는데, 각각 예측가능한지 예상해보자.

 

FYI) __restrict는 C, A, B가 서로 같은 포인터를 가리킬 경우, 파이프라인상으로 최적화하기 어렵기 때문에 서로 같은 주소가 아니라고 힌트를 주게 된다. 이 경우, 3개의 포인터들은 서로 같은 메모리 주소를 가리키지 않는다고 알려서 추가적인 최적화가 가능하다.

1) while (nb > 0)

- YES

nb가 0인 경우를 제외하고, true이므로 예측가능하다는 것이 밝혀져 있음.

 

2) while (na > 0)

- YES

1과 동일한 이유로, 예측가능

 

3) if (*A <= *B)

- NO

*A, *B의 값이 어떤 값인지 알지 못하기 때문에 예측 불가능 (50:50)

 

4) while (na > 0 && nb > 0)

- YES

na, nb 둘 중 하나가 0이 되기전 까지 true이므로, 예측 가능

[2] Branchless

[1]에서, 3) if (*A <= B*)는 예측이 불가능하므로 하드웨어가 예측되는 명령어를 Prefetch하기 힘들어진다. 따라서, 이전에 배웠던 No-Branch Minimum을 사용하여 추가적인 최적화가 가능해진다.

cmp 값이 (*A <= *B) 결과에 따라 1 또는 0이 되므로, 

A == cmp; na -= cmp;

B += !cmp; nb -= !cmp;

위 두 줄의 코드 중 한 줄만이 cmp 값에 따라 유효하게 된다.

 

Q) 효과가 있을까요?

A) 위 최적화는 일부 머신에서만 효과가 있다.

현대 머신의 clang -O3 옵션을 사용할 경우, branchless 버전이 branching 버전보다 오히려 느리다. 현대 컴파일러는 대부분의 경우에 사용자 프로그래머가 할 수 있는 최적화보다 더 최적화가능하다.

→ 이를 cmov, conditional move라고 하는데, 다음 주에 더 자세히 알아볼 예정

 

Q) Why Learn Bit Hacks?

Q) 실제로 효과도 없는 이런 야매들을 왜 배우고 있는거죠?

A)

1) 컴파일러가 이러한 비트 트릭을 사용하고 있기 때문인데, 비트 트릭을 이해하고 있다면 어셈블리 코드를 볼 때 컴파일러가 어떤 동작을 하는지 알 수 있다.

2) 컴파일러가 이러한 최적화를 자동으로 수행해주지 않는 경우가 있는데, 그럴 때는 사용자가 직접 최적화해야 함

3) Word에 대한 많은 bit hacks는 고성능 코드에서 널리 사용되는 벡터에 대한 bit/word hacks로 자연스럽게 확장될 수 있음.

4) 이러한 트릭들은 다른 도메인에서도 발생할 수 있기 때문에, 배우는 것 자체로 가치가 있다.

 

Modular Addition

효과가 있는 한 가지 예제

(0 <= x < n), (0 <= y < n)의 범위를 가정했을 때,

(x + y) mod n 연산을 한다고 해보자.

 

mod 연산을 할 때 컴파일러는 나눗셈을 수행하게 되는데, 나눗셈은 2의 거듭제곱이 아닌이상 비싼 연산에 해당된다.

컴파일러는 컴파일 타임에 (x + y)가 2의 거듭제곱인지 알 수 없으므로 단순히 나눗셈을 통해 mod 연산을 하게된다.

Case) 나눗셈 대신 Branch를 사용하면?

위 Branch 사용시, z < n의 결과를 예측할 수 없기 때문에 예상되는 결과 instruction을 prefetch하는 것이 불가능해진다.

 

Approach) 이전에 배웠던 No-Branch Minimum을 사용해보자.

(z >= n)의 값이 1 / 0에 따라 각각 z-n / z 의 결과를 가진다.

 

Q) z 값에 따라 여전히 분기가 존재하므로 위 최적화가 더 빠른 이유를 모르겠습니다

→ (z >= n)의 값에 따라 true/false로 나뉘는 것이 분기가 아니냐고 묻는듯

A) 서로 다른 2개의 코드 경로로 나뉠 때만 분기 예측이 발생하며, (z >= n)는 bool 값을 생성하므로 분기는 맞지만, 동일한 코드를 생성하므로 분기 예측 오류는 문제가되지 않음.

 

Round up to a Power of 2

--n;을 하는 이유 : 

→ n이 이미 2의 거듭제곱인 경우, 의도한 결과의 2배가 될 수 있기 때문.

 

n : 8이라고 가정해보자.

--n;을 하지 않을 경우, 0b1000 → 0b10000이 되므로 8이아닌 16이 된다.

따라서 미리 --n;을 통해 0b0111로 만들어 둔다면, 의도한 결과를 넘어가는 것을 막을 수 있다.

Least-Significant 1

Compute the mask of the least-significant 1 in word x.

 

2의 보수를 취한 -x를 알면, Least-Significant 1를 뽑아낼 수 있다.

Least-Significant 1을 제외하고는 반대 비트이기 때문에 bitwise and로 추출가능.

Why it works

The binary representation of -x is (~x)+1. (2's complement)

 

Q) Least-Significant 1 의 index를 어떻게 알 수 있을까? 다시 말해서, Log2 (r)

→ 위 예제에서 4를 의미

 

Log Base 2 of a Power of 2

Compute lg x, where x is a power of 2.

Why it works

먼저, DeBruijin Sequence(드 브루인 수열)이 무엇인지 알아야 한다.

-

N-Queens Problem