intrinsic popcount, clz, ctz (gcc, msvc)

CPU마다 지원하는 instruction set(명령어 집합)이 있는데 특정한 instruction을 사용하기 위해서는 컴파일러 별 내장 함수(intrinsic function, builtin function)을 사용해야 합니다.

예를 들어 SSE4 instruction set에는 특정 수의 1bit 개수를 세는 POPCNT(population count) instruction이 있는데 이걸 사용하려면 gcc에서는 __builtin_popcnt를, msvc에서는 __popcnt를 사용해야 합니다. 참고로 msvc에서 intrinsic function을 사용하려면 <intrin.h> 헤더를 포함해야 합니다.

 

Fig 1. cpu-world에서 확인한 AMD Ryzen 3600의 Extensions / Techs

CPU마다 지원하는 instruction set이 다른데 이걸 확인해서 intrinsic function을 사용해야 합니다.

옛 CPU는 intruction set이 추가되지 않아 해당 instruction을 사용할 수 없을 수도 있습니다. 예를 들어 Intel Core 2 Duo E6550은 MMX, SSE, SSE2, SSE3, SSSE3 intruction set이 사용되는데, POPCNT instruction이 없습니다. 개발시 호환성 체크를 잘 해줘야 합니다.

 

intrinsic function중에서 아래 세 개만 알아보겠습니다.

• population count
  • 1비트의 수
  • gcc: __builtin_popcount(unsigned int)
  • msvc: __popcnt(unsigned int)
• count leading zeros
  • 앞에서부터(msb부터) 1이 나오기 전 0의 개수
  • gcc: __builtin_clz(unsigned int)
  • msvc: __lzcnt(unsigned int)
• count trailing zeros
  • 뒤에서부터(lsb부터) 1이 나오기 전 0의 개수
  • gcc: __builtin_ctz(unsigned int)
  • msvc: X

기본적으로 unsigned int 형을 기준으로 계산됩니다.

gcc의 경우 unsigned long 타입의 함수를 사용하려면 함수 끝에 l을 붙이고, unsigned long long 타입의 함수를 사용하려면 함수 끝에 ll을 붙입니다.

msvc는 <intrin.h> 헤더를 포함해야 합니다. msvc에 기본적으로 ctz가 없는데 _BitScanForward을 사용하거나 아키텍처별 intrinsics list를 확인해서 써야 합니다. 제 CPU는 AMD Ryzen 3600인데, BMI를 지원하니 _tzcnt_u32, _tzcnt_u64를 쓰면 되겠네요. (ex. x64(amd64) intrinsics list)

 

* msvc documentation: __lzcnt
If you run code that uses this intrinsic on hardware that does not support the lzcnt instruction, the results are unpredictable.

msvc에서 __lzcnt를 사용할 때는 주의할 점이 있는데, lzcnt instruction이 지원되지 않는 cpu에서는 bsr이 실행된다고 합니다. microsoft document에는 unpredictable이라고 써있습니다. (참고링크)

 

아래는 예시입니다

// gcc
unsigned int x = 16;	// 00000000 00000000 00000000 00010000
cout << __builtin_popcount(x) << '\n';	// 1
cout << __builtin_clz(x) << '\n';	// 27
cout << __builtin_ctz(x) << '\n';	// 4

// msvc
#include <intrin.h>

unsigned int x = 16;	// 00000000 00000000 00000000 00010000
cout << __popcnt(x) << '\n';	// 1
cout << __lzcnt(x) << '\n';	// 27
// count trailing zeros -> _tzcnt_u32, _tzcnt_u64

 

글이 좀 길어졌는데요, c++20에는 std::popcount, std::countl_zero, std::countr_zero 등이 추가될 예정이니 instruction set으로 머리가 아파질 일이 덜어질 것 같습니다.