소프티어 - CPTI와 비트마스크

  평소에 코딩테스트랑은 담을 쌓고 살던 와중, 어쩌다보니 코딩테스트를 앞두고 소프티어에서 2~3레벨 문제를 풀어보고 있었다. Javascript로 풀어볼 수 있는 문제를 필터링했는데 C, C++, Java, Python, Rust만 사용할 수 있는 이 씁쓸함이란... 아무튼 첫번째로 잡아본 문제는 'CPTI'. 출처 - 소프티어, CPTI

Softeer - 현대자동차그룹 SW인재확보플랫폼

  문제는 링크만 남겨놓을까 했었는데, 근시일내에 소프티어 서비스가 종료된다는 공지사항이 떠있길래 부랴부랴 캡쳐해서 백업해뒀다. 아무튼 문제는 다음과 같다. 

소프티어 - CPTI

  이진수가 나온 시점에서 비트마스킹 생각이 먼저 떠올라서, scanf()를 사용해서 2진수 문자열을 입력받아 10진수로 변환한 뒤 배열에 저장하는 방식으로 코드를 작성했다. 이후 루프를 순회하며 두 값을 XOR한 뒤 1로 마스킹 된 비트의 갯수를 체크했다. 마스킹 된 비트의 갯수를 계산하는 로직이 잘 생각이 안나서 처음부터 순회할까 하다가, GPT에게 물어봐서 Brian Kernighan 알고리즘을 적용했다.

  Brian Kernighan 알고리즘은 주어진 비트마스크 값에서 1로 설정된 가장 마지막 값을 하나씩 제거하며 카운트하는 알고리즘으로, 1로 설정된 비트마스크의 갯수만큼 비트마스크를 순회한다. 전체 비트마스크의 길이만큼 반복하는 O(n)에 비해, 1로 설정된 비트의 갯수(k)만큼 반복하므로 일반적인 경우에는 O(n)보다 더 빠른 O(k)의 복잡도를 가진다. 최악의 경우는 모든 비트가 1로 설정되어있을 경우로, 이 때의 복잡도는 O(n)과 동일하다. 

int count = 0;

while(bitmask>0) {
  bitmask &= (bitmask-1);
  count++;
}

return count;

 

  아무튼 예제값을 입력해보니 잘 돌아가길래 제출했더니, 0.089초 정도 차이로 시간초과가 발생한다. 처음에는 문자열을 scanf()로 받은 뒤 전체 문자열을 순회하며 2진수로 바꾸는 과정때문에 문제인 줄 알았으나... GPT에게 최적화를 요청하자 Brian Kernighan 알고리즘 대신 빌트인으로 제공되는 __builtin_popcount()를 사용하란다. 엥, 설마 그 문제겠어...

  시험삼아 __builtin_popcount()를 적용해보니 0.73초가량 단축된 것을 확인할 수 있었다. 엥, 이러면 알고리즘 문제라고 할 수 있나...라는 생각이 들었지만, 그것보다 __builtin_popcount()가 어떻게 이렇게 시간을 단축할 수 있었는지 궁금해서 ChatGPT에게 물어봤다.

 

ChatGPT가 알려주는 __builtin_popcount()가 더 빠른 이유

  그러니까 __builtin_popcount()는 하드웨어적으로 1사이클만에 비트 카운트 계산이 끝나므로 더 빠를수밖에 없다는 내용. 그와 동시에 CPU에서 POPCNT를 지원하지 않을 경우 HAKMEM 스타일 알고리즘을 사용하면 루프 없이 6줄의 코드를 사용해 1로 체크된 값들을 카운트할 수 있다는 내용이 눈에 띄었다. 여기까지 왔으면 HAKMEM 스타일 알고리즘이 얼마나 빠른지, __builtin_popcount()를 사용했을 때와 비슷한 속도가 나오는지 테스트해보지 않을수가 없지 않겠는가.

HAKMEM 스타일 POPCOUNT 함수

  우선 ChatGPT에 표시된 구현 내용을 복사해서, countBitByHakmemStyle()이라는 함수를 작성했다.

__builtin_popcount()를 사용했을 때보다 0.3초정도 더 줄었다!

  __builtin_popcount()를 사용하던 구문을 주석처리한 뒤 countBitHakmemStyle() 함수를 실행하도록 대체하자, __builtin_popcount()를 사용했을 때보다 0.3초 더 단축됐다!

HAKMEM 스타일 popcount에 대한 단계적 설명

  일단 HAKMEM 스타일 popcount가 어떻게 동작하는건지 잘 이해가 안가서 ChatGPT에게 설명을 요청하자, 각 단계에서 일어나는 일을 상세히 설명해준다. 요약하면 비트 단위로 쪼개서 계산한 뒤, 합산한다는 것. 사실 잘 이해는 가지 않는다.

 

bitFlags에 작성했던, 1로 설정되어있는 비트의 갯수를 반환하는 함수 count().

  곰곰히 생각해보니 얼마전 몇 년간 방치했다가, Cursor를 써서 Typescript로 리팩토링했던 라이브러리 bitFlags가 생각났다. bitFlags에도 비슷한 기능을 구현했기 때문인데, 그때는 2진수 문자열로 변환한 뒤 정규표현식을 사용해서 0을 제거한 문자열 길이를 반환하는 방식으로 구현했다. Typescript 환경에서도 HAKMEM 스타일 popcount를 적용하면, 유의미한 성능차이가 있는지 궁금해졌다. 

HAKMEM 스타일 popcount를 적용 전/후 비교. 무려 0.4초 빨라졌다.

  전체 테스트 결과가 0.4초 감소했다. count()를 실행하는 테스트는 7개 정도인데, count()를 몇 번이나 사용하겠나싶긴 하지만 아무튼 꽤 시간이 단축됐다. 알고리즘 문제 풀이도 풀이지만, 모르던 알고리즘을 적용하여 성능을 비교하다보니 그냥 문제를 풀 때보다 훨씬 재밌던 것 같다. 일단 bitFlags는 HAKMEM 스타일 popcount를 적용해서 배포해둬야지... 헤힣...