'매크로'에 해당되는 글 1건

  1. 2011.02.19 Bitwise Switch (2)

Bitwise Switch

개발 2011.02.19 01:56

 코딩하다 비트셋을 쓰면 아래 같이 각 플래그들을 검사해서 해당되는 경우 관련 작업을 수행하는 식의 코드를 줄줄이 작성하는 경우가 가끔 있다.


if (bitset & FLAG_A) {
	/* A 플래그와 관련된 작업들 */
}

 ...

if (bitset & FLAG_Z) {
	/* Z 플래그와 관련된 작업들 */
}


 오늘 위와 같은 코드를 보다가 아래처럼 비트셋에 적용되는 switch 문이 있으면 좋겠다는 생각이 들어서 검색해보았는데 못 찾아서 (그 이유는 아래에서 밝혀진다 -_-) 직접 만들어 보기로 하였다.


bitwise_switch(bitset) {
	case FLAG_A: /* A 플래그와 관련된 작업들 */

	...

	case FLAG_Z: /* Z 플래그와 관련된 작업들 */
}


 사실 구현 자체는 그리 어려운게 아니지만 비트 연산을 이용한 몇 가지 트릭이 필요했다. 일단 코드는 아래와 같다.

 
// Calculate LSB index in O(1) using de bruijn sequences.
// For more information, read "Using de Bruijn sequences to index a 1 in a computer word"
inline const int GetLSBIndex(const uint32_t LSB)
{
	static const uint32_t DeBruijnConstant32 = 0x077CB531U;
	static const int32_t HashTable[32] =
	{
		 0,  1, 28,  2, 29, 14, 24,  3,
		30, 22, 20, 15, 25, 17,  4,  8,
		31, 27, 13, 23, 21, 19, 16,  7,
		26, 12, 18,  6, 11,  5, 10,  9
	};

	return HashTable[static_cast(LSB * DeBruijnConstant32) >> 27];
}

inline const uint32_t ExtractLSB(uint32_t& bitset)
{
	uint32_t LSB = bitset & (-bitset);
	bitset = bitset ^ LSB;
	return LSB;
}

#define bitwise_switch(bitset) \
	for (uint32_t __bitset__ = bitset; __bitset__ != 0;) \
		switch (GetLSBIndex(ExtractLSB(__bitset__))) \


 동작은 아주 간단하다. 주어진 비트셋에서 Least Significant Bit를 추출한 뒤 추출한 LSB의 위치를 계산, 이 값을 switch-case 문으로 넘기는 것을 반복하는 것이다.
 
 위 코드에서 함수 ExtractLSB는 주어진 비트셋에서 LSB를 뽑아내는 비트 연산 기법인 bitset & (-bitset)을 구현한 코드로 쉽게 이해할 수 있다. 함수 GetLSBIndex는 주어진 LSB 값을 받아 오프셋을 계산하는 함수인데, 이를 위해 De Bruijn 수열을 이용, Perfect hash function을 만들어 사용한다. 알고리즘의 원리가 궁금하신 분들은 이 논문을 참조하시면 되겠다. 비트 값을 굳이 이렇게 오프셋 값으로 바꿔서 사용하는 이유는 switch-case 분기문에 주어지는 인자가 연속된 정수 값인 경우 컴파일러가 이를 점프 테이블을 이용하는 간접 분기문으로 바꾸는 최적화를 해주기 때문이다.


 최적화가 목표였던 건 아니지만 그래도 각각의 비트에 대한 분기 처리가 O(1)에 처리되도록 신경을 썼으니 처리 속도가 궁금해진다. 그렇다면 이 기법을 이용하는 경우 속도가 얼마나 빨라질까? 불필요한 비트 검사가 생략되니 빨라질 수도 있겠지만, 비트 하나를 검사하는데 들어가는 비용이 확연히 커졌으니 느려질 수도 있다. 과연 결과는?


열기



 오늘의 교훈: 최적화 같은거로 고민하지 말자. 최적화로 얻는 시간보다 최적화에 들이는 시간이 더 많을거다. -_-;;

'개발' 카테고리의 다른 글

기본 타입 간 (무분별한) 변환은 자제합시다  (3) 2011.05.14
Visual Studio는 C/C++을 싫어해 (?)  (3) 2011.02.27
Bitwise Switch  (2) 2011.02.19
std::unique_ptr  (0) 2010.04.26
RVO와 NRVO  (0) 2010.04.26
volatile과 메모리 배리어  (2) 2009.11.11
Trackbacks 0 : Comments 2