이진 탐색은 어디까지 빨라질 수 있을까?

수 많은 값들 속에서 특정 값의 위치를 찾는건 컴퓨터가 수행하는 작업들 중 가장 기본적인 작업이면서도 자주 쓰이는 작업입니다. 특정 이름으로 된 파일을 열거나, 주소를 이용해 특정 사이트에 접속하거나, 검색엔진에 검색어를 입력해 원하는 결과를 찾는 일 등 수많은 작업들이 결국에는 데이터의 위치를 찾는 작업으로 귀결되지요. 그래서 컴퓨터 과학에서는 이런 종류의 작업에 '검색 알고리즘(Search Algorithm)'이라는 이름을 붙여서 심도 있게 연구하고 있습니다.

이번 포스팅에서 다룰 내용은 값 집합이 고정되어 있는 상태에서 특정 값이 해당 집합 내에 존재하는지, 존재하면 어느 위치에 존재하는지를 찾는 것입니다. 따라서 값 집합에 새로운 값이 추가되거나 값 집합에서 특정 값이 제거되는 등 값 집합 자체가 바뀔 수 있는 상황에서의 탐색은 다루지 않습니다. (이 경우에는 값 집합이 변경될 때마다 처리하는 비용도 고려해야하기 때문에 사용할 수 있는 알고리즘이 달라집니다.) 또한 탐색의 대상되는 값은 정수형 혹은 실수형 숫자로 한정하겠습니다.

이진 탐색(Binary Search)

탐색 알고리즘 중 가장 유명한 알고리즘이죠. 전체 값 집합이 정렬되어 있는 경우에 사용가능하며, 매 시도마다 탐색 범위가 절반씩 줄어들어서 값 집합이 아주 커도 빠르게 답을 찾을 수 있습니다. 이진 탐색에 대해 간단한 예시를 들어보면 다음과 같습니다. 다음과 같이 총 7개로 된 값 배열이 있고, 오름차순으로 정렬이 되어있다고 가정합시다.

index	0	1	2	3	4	5	6
value	1	5	7	8	10	15	20

위 배열에서 9가 존재하는지, 존재한다면 어디에 존재하는지를 알아내봅시다.

1. 초기 탐색 범위는 index 0~6 사이.
   1. 탐색 범위의 한 가운데인 index 3의 값을 가져온다: 8
   2. $8<9$이므로, 우리가 찾고자하는 값은 index 4~6사이에 있을 것
2. 탐색 범위가 index 4~6로 좁혀짐.
   1. 탐색 범위의 한 가운데인 index 5의 값을 가져온다: 15
   2. $15>9$이므로, 우리가 찾고자하는 값은 index 4에 있을 것
3. 탐색 범위가 index 4로 좁혀짐.
   1. index 4의 값은 10이므로, 우리가 찾고자 하는 값인 9와 다르다.
   2. 즉 9는 위 배열 내에 존재하지 않는다.

매 단계마다 탐색 범위가 절반씩 줄어드는 것을 볼 수 있습니다. 따라서 입력 길이가 아무리 길어도 금세 탐색 범위가 줄어들어서 빠른 시간 안에 결과를 구할 수 있습니다(시간복잡도가 $O(\log n)$입니다). 이보다 더 빠른 탐색 방법에는 해시 탐색(시간 복잡도가 평균적으로 $O(1)$, 최악의 경우 $O(n)$) 밖에 없으며, 해시 탐색의 경우는 메모리를 매우 많이 사용하고 해시 충돌이 발생하는 경우 오히려 속도가 느려질 수도 있기 때문에 모든 상황에서 이진 탐색을 대체하기는 어렵습니다.

이론과 현실은 다르다

이진 탐색의 원리에 대해서 간단하게 살펴보았는데요, 현대의 컴퓨터 상에 실제로 구현해보면 이진탐색이 항상 빠르게 나오지는 않습니다. 윗 문단에서 살펴본 "길이 7짜리 배열에서 값 9를 찾는 예시"를 다시 생각해봅시다. 사람은 저 배열 전체를 한 눈에 보고 9가 있는지 없는지 바로 알아차릴 수 있지만, 이진 탐색을 사용하면 불편하게 비교 대상을 바꿔가면서 값을 찾아야하죠. 실제로 길이 7짜리 배열은 굳이 이진탐색을 쓰지 않고 앞에서부터 차례대로 값을 비교해나가는 방식(순차 탐색, Sequential Search or Linear Search)이 더 빠릅니다.

이론과 현실 사이에서 이렇게 괴리가 발생하는 이유는 최근 CPU의 구조를 살펴봐야 알 수 있습니다. CPU의 모든 연산은 레지스터(register)라는 CPU 속의 저장소에서만 일어납니다. 즉, 어떤 값들을 더하거나 비교하는 등의 연산을 수행하려면 이 값들을 먼저 읽어들여서 레지스터에 올려놓아야합니다. 그런데 레지스터의 개수는 극히 한정되어 있으므로 우리가 사용할 모든 값들을 레지스터에 올려놓는건 불가능합니다. 따라서 그때 그때 사용할 값들을 불러와서 레지스터에 올려야 합니다. 이렇게 값을 레지스터에 올리는 작업을 load라고 합니다. 문제는 우리가 사용할 값들이 실제로 위치하는 RAM은 CPU에 비해 너무나도 느리다는 것입니다. RAM에서 레지스터로 값을 load하는 작업은 너무나도 오래 걸려요.

따라서 이를 해결하기 위해 현대의 CPU들은 캐시 메모리(Cache Memory)라는 것을 도입합니다. 이는 레지스터보다는 느리지만 RAM보다는 빠른 메모리로, CPU가 쓸 값들을 잠깐 저장해두는 장소라고 생각하시면 됩니다. CPU가 RAM 상의 특정 값을 요구하는 경우 그 주변에 있는 값들을 뭉텅이로 한꺼번에 가져와서 캐시에 저장해두고, 다음번에 그 값을 찾으면 캐시에서 빠르게 가져와서 레지스터에 넣어주는 식입니다. 이 캐시 메모리의 존재로 CPU가 더 빠르게 일들을 처리할 수 있습니다.

캐시 메모리는 참조 지역성(Locality of Reference)이라는 개념을 바탕에 두고 작동합니다. 간단히 말하면, 방금 쓰인 값들 근처에 있는 값들이 조만간 또 쓰일 가능성이 높다는 것이죠. 이 때문에 특정 값을 읽어올때 그 주변의 값들을 한꺼번에 가져와 캐시에 저장해두면 다음 번에 쓰일 값들이 캐시에 있을 확률이 높습니다. 이진 탐색이 항상 선형 탐색보다 빠르지 못한 이유도 여기에 있죠.

그렇다면 가상으로 캐시 메모리를 만들어두고 한번 시뮬레이션을 해봅시다. 캐시 메모리의 크기는 2이고, 캐시 메모리에서 값을 가져오는데(캐시 적중)는 1초, 일반 RAM에서 값을 가져오는데(캐시 부적중)는 100초가 걸린다고 가정하겠습니다.

순차 탐색의 경우

절차	작업 대상 메모리	캐시 메모리
초기 상태	index 0 1 2 3 4 5 6 value 1 5 7 8 10 15 20	index - - value - -
index 0의 값을 읽기 캐시 부적중: 100초 소요 작업후 index 0, 1이 캐시에 적재됨	index 0 1 2 3 4 5 6 value 1 5 7 8 10 15 20	index - - value - -
index 1의 값을 읽기 캐시 적중: 1초 소요	index 0 1 2 3 4 5 6 value 1 5 7 8 10 15 20	index 0 1 value 1 5
index 2의 값을 읽기 캐시 부적중: 100초 소요 작업후 index 2, 3이 캐시에 적재됨	index 0 1 2 3 4 5 6 value 1 5 7 8 10 15 20	index 0 1 value 1 5
index 3의 값을 읽기 캐시 적중: 1초 소요	index 0 1 2 3 4 5 6 value 1 5 7 8 10 15 20	index 2 3 value 7 8
index 4의 값을 읽기 캐시 부적중: 100초 소요 작업후 index 4, 5가 캐시에 적재됨	index 0 1 2 3 4 5 6 value 1 5 7 8 10 15 20	index 2 3 value 7 8
배열 내에 9가 없네. 탐색 종료	index 0 1 2 3 4 5 6 value 1 5 7 8 10 15 20	index 4 5 value 10 15

 

이진 탐색의 경우

절차	작업 대상 메모리	캐시 메모리
초기 상태	index 0 1 2 3 4 5 6 value 1 5 7 8 10 15 20	index - - value - -
index 3의 값을 읽기 캐시 부적중: 100초 소요 작업후 index 3, 4가 캐시에 적재됨	index 0 1 2 3 4 5 6 value 1 5 7 8 10 15 20	index - - value - -
index 5의 값을 읽기 캐시 부적중: 100초 소요 작업후 index 5, 6이 캐시에 적재됨	index 0 1 2 3 4 5 6 value 1 5 7 8 10 15 20	index 3 4 value 8 10
index 4의 값을 읽기 캐시 부적중: 100초 소요 작업후 index 4, 5가 캐시에 적재됨	index 0 1 2 3 4 5 6 value 1 5 7 8 10 15 20	index 5 6 value 15 20
배열 내에 9가 없네. 탐색 종료	index 0 1 2 3 4 5 6 value 1 5 7 8 10 15 20	index 4 5 value 10 15

순차 탐색의 경우 차례대로 접근하기 때문에 2번 중 1번은 캐시가 적중하는 반면, 이진 탐색의 경우는 매번 접근하는 위치가 앞뒤로 왔다갔다하므로 계속 적중에 실패하는걸 볼 수 있습니다. 그래서 순차 탐색은 총 5회 비교를 수행했음에도 메모리 접근에 소요된 시간이 302초, 이진 탐색은 총 3회 비교를 수행했음에도 메모리 접근에 소요된 시간이 300초가 나오지요. 만약 간략화된 상황에서 시뮬레이션을 돌리긴 했지만, 실제 CPU에서 일어나는 상황도 이와 제법 비슷합니다. 최신 Intel CPU를 기준으로 할때, 보통 비교 연산 자체는 1사이클만이 소요되는 반면, L1 Cache에서 값을 읽어오는 데에는 3사이클 정도, RAM에서 값을 읽어오는 데에는 200사이클 정도 걸리거든요. (참고 링크)

따라서 탐색 알고리즘을 직접 구현할때는 캐시 적중율도 반드시 고려해야합니다. 그렇지 않으면 이론상 최강인 알고리즘이 현실에서는 최약인 상황이 발생할지도 모르니깐요. 순수 이진 탐색의 경우 값을 읽어오는 index가 매번 바뀔 수 있으므로, 전략을 약간 수정해 시간 복잡도가 조금 크더라도 가능하면 인접한 index를 탐색하도록 하는게 좋아보입니다. 많이들 사용하는게 탐색 구간이 클때는 이진 탐색을 그대로 사용하다가 탐색 구간이 특정 크기 내로 줄어든 경우 순차 탐색으로 전환하는 방식입니다.

SIMD를 활용한 순차 탐색

SIMD(Single Instruction Multiple Data)는 한 명령어로 데이터 여러 개에 대해 연산을 수행하는 것을 말합니다. 요즘 CPU에는 대부분 포함되어 있는데요, Intel 계열에는 SSE과 AVX, ARM 계열에는 NEON이 대표적인 SIMD 명령어셋입니다. 이를 이용하면 연속된 값 4개(혹은 8개 등^[각주:1])를 한꺼번에 읽어들여 사칙연산이나 비교 등을 동시에 수행할 수 있습니다. 

순차 탐색의 경우 원래는 차례대로 비교해야할 $N$개의 수를 SIMD를 이용해 동시에 읽어들여 비교함으로써 빠르게 탐색이 가능합니다. 마찬가지로 이진 탐색의 경우도 탐색 범위가 좁아진 경우 SIMD 순차 탐색을 사용해서 속도를 높이는 게 가능하겠죠?

이진 탐색 트리(Binary Search Tree)

이진 탐색 대신에 이진 탐색 트리(Binary Search Tree)를 사용하는 것도 고려해봄직합니다. 이진 탐색 트리는 한 노드가 최대 2개의 자식만 가지는 트리로, 항상 왼쪽에는 자기보다 작은 자식을, 오른쪽에는 자기보다 큰 자식을 가지도록 배치하는게 특징입니다. 

포화 이진 탐색 트리

깊이가 깊어짐에 따라 총 자식의 개수는 2배씩 늘어나며, 전체 깊이가 $d$라고 할 때 모든 노드의 개수는 $2^d-1$개가 됩니다. 이진 탐색 트리에서는 왼쪽의 자식은 항상 자기보다 작고, 오른쪽의 자식은 항상 자기보다 크므로 이 특징을 활용해 특정 값이 어디에 있는지 쉽게 찾을 수 있습니다. 예를 들어 위 트리에서 9를 찾아봅시다.

이진 탐색 트리에서 9 찾기

1. 시작 노드인 7에서 시작
2. $9>7$이므로 오른쪽 자식으로 이동
3. $9<11$이므로 왼쪽 자식으로 이동
4. 9 발견! 끝!

이진 탐색과 마찬가지로 한 단계씩 깊이 들어갈때마다 탐색 범위가 절반으로 줄어듭니다(시간 복잡도가 $O(\log n)$). (아직까지는 이게 이진 탐색에 비해 특별히 나은점이 보이지 않을 겁니다. 그렇지만 참을성을 가지고 좀만 더 따라와주세요~) 일반적인 트리는 연속된 메모리 공간에 배치하기가 꽤나 까다롭습니다만, 이진 트리의 경우 간단한 규칙에 따라 배열에 모든 노드의 값을 배치할 수 있다는 장점이 있습니다. 위에서 아래로, 왼쪽에서 오른쪽 순으로 차례대로 index 번호를 매겨보겠습니다.

이진 탐색 트리. 흰 색은 노드의 value, 검은색은 노드의 index

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
value	7	3	11	1	5	9	13	0	2	4	6	8	10	12	14

이진 탐색 트리를 배열 형태로 바꿔서 한 줄로 늘어놓으니 규칙이 잘 안 보이긴 합니다만, 사실 간단한 규칙이 있습니다. 시작 노드의 위치는 항상 index 0이 되구요, 부모 노드의 index가 $i$일때, 왼쪽 자식 노드의 index는 $2i + 1$, 오른쪽 자식 노드의 index는 $2i + 2$가 된다는 것이죠. 따라서 우리는 이 이진 탐색 트리 배열을 탐색할때 항상 index가 작은 쪽에서 큰 쪽으로만 탐색하게 됩니다. 또한 자식 노드인 $2i + 1$과 $2i + 2$가 항상 인접해 있으므로 부모 노드에서 자식 노드로 이동할때 해당 영역의 메모리를 캐시에 미리 로드(prefetch)해두면 다음 연산을 더 빨리 수행할수 있습니다. 이진 탐색 트리를 이용한 탐색 알고리즘은 다음과 같이 정리할 수 있겠네요. 

1. $i \leftarrow 0$에서 시작
2. index $i$의 값을 읽어와서 $v$와 비교
   1. 두 값이 같은 경우 $i$를 반환하고 종료
   2. $v$가 더 큰 경우, $i \leftarrow 2i + 1$
   3. $v$가 더 작은 경우, $i \leftarrow 2i + 2$
3. $i < size$이면 2번으로 돌아가 반복. 아니면 "값이 없음"을 반환하고 종료

굉장히 간단한 코드라서 별다른 설명이 필요없을듯 합니다.

이진 탐색 트리는 이진 탐색과 동일한 시간 복잡도를 지니지만, 캐시 적중률 측면에서는 여러모로 유리한 점이 많습니다. 한 가지 아쉬운 점은 정렬된 배열에 대해서 바로 적용하는건 불가능하고, 해당 배열을 이진 탐색 트리 형태로 재배치해야한다는 것입니다. 다만 값 집합이 고정되어 있고 탐색을 반복적으로 수행하는 경우라면 이는 문제가 되지 않습니다.

참고로 전체 배열의 크기가 $2^d-1$의 꼴이 아니더라도 문제가 없습니다. 전체 노드가 $2^4-1 = 15$에서 3개 부족하여 $12$개인 경우 다음과 같이 가장 아래쪽 줄의 오른쪽에서 노드 3개를 뺀 모양으로 이진 트리를 구축하면 됩니다 (이런 형태를 완전 이진 트리라고 합니다).

배열의 포인터 keys와 그 배열의 크기 size를 받습니다. 먼저 keys를 오름차순으로 정렬한 뒤, 트리의 최종 깊이를 계산합니다(height). 포화 상태일때의 크기 complete_size에 비해 몇개나 모자란지 세고(off), off_start 이후의 값들은 discount를 적용하고, 그 이전의 값은 discount없이 규칙대로 재배치하면 끝입니다.

 

완전 이진 탐색 트리 - 제일 아래쪽 줄의 오른쪽에서만 노드가 몇 개 빠진 경우

완전 이진 탐색 트리. 숫자를 재배치해 0~11 범위로 맞추었음

이 경우에도 포화 이진 트리(빈 부분이 없이 꽉 찬 이진 트리)와 동일한 규칙이 적용되므로 동일한 알고리즘을 사용하면 됩니다.

k진 탐색 트리(k-ary Search Tree)

이진 탐색 트리를 확장시켜서 임의의 자연수 $k$에 대해 $k$진 탐색 트리를 만들어볼 수도 있습니다. 이진 탐색 트리에서는 각 노드에 값이 1개가 있었고, 왼쪽 자식은 이 값보다 작고 오른쪽 자식은 이 값보다 컸죠. $k$진 탐색 트리에서는 각 노드가 $k-1$개의 값을 가지고 있고, 자식 노드는 총 $k$개가 됩니다. 첫번째 자식 노드(제일 왼쪽 자식 노드)는 $k-1$개의 값 전부보다 작고, 두번째 자식 노드는 $k-1$개의 값 중 첫번째 값보다는 크지만 나머지보다는 작고, $\cdots$ $k$번째 자식 노드는 $k-1$개의 값 전부보다 큰 식이죠. 트리의 전체 깊이가 $d$라고 할 때 총 노드의 수는 $(k^d-1) / (k-1)$이 되며, 각 노드가 $k-1$개의 값을 가지고 있으니, 트리 전체에 들어갈 수 있는 값의 개수는 $k^d-1$개가 됩니다.

$k=3$인 경우의 그래프가 아래에 있으니 이를 보면 이해하기가 쉬우실 거에요!

포화 3진 탐색 트리

완전 k진 탐색 트리 - 제일 아래쪽 줄의 오른쪽에서만 노드가 몇 개 빠진 경우

완전 k진 탐색 트리. 숫자를 재배치해 0~20 범위로 맞추었음

$k$진 탐색 트리에서 특정 값을 찾는 것 역시 이진 탐색 트리와 유사합니다. 다만 각 노드마다 자식이 총 $k$개가 있고, 이 $k$개 중 어디로 내려가야할지 찾기 위해서는 총 $k-1$번의 비교가 필요하겠죠. 노드마다 값이 딱 1개만 있어서 1번만 비교하면 어느 자식으로 내려가야할지 알 수 있는 이진 탐색 트리에 비해서는 비효율적인게 사실입니다. 게다가 솔직히 개발자로써 2의 거듭제곱이 아니라 다른 수의 거듭제곱을 다루는 건 굉장히 심기가 불편한 일이기도 하구요. 굳이 이진 탐색 트리 대신 $k$진 탐색 트리를 다뤄야할 이유가 있을까요?

네, 있으니깐 여기서 다루고 있겠죠! 앞서 간단하게 설명한 SIMD때문입니다. SIMD 연산의 경우 연산 타입에 따라 동시에 4개,8개 혹은 16개의 값을 비교할 수 있다고 위에서 설명했었습니다. 이 때문에 $k$진 탐색 트리에서 매 노드마다 $k-1$번의 비교 연산을 수행해야하는 걸 1번의 SIMD 연산으로 대체할 수 있습니다. 5진 탐색 트리를 쓰면 4번의 비교 연산을 1개의 SIMD 명령어로 수행할 수 있으니 비교 연산이 이론상 4배 빨라지고, 9진 탐색 트리를 쓰면 8번의 비교 연산을 1개의 SIMD 명령어로 수행할 수 있으니 이론상 8배 빨라지는 셈입니다. 물론 현실에서는 앞에서 서술한 바와 같이 메모리의 문제로 그만큼까지는 빠르게 나오지 않겠지만요.

다행히도 $k$진 탐색 트리 역시 이진 탐색 트리와 마찬가지 방법으로 한 줄로 나열하여 배열에 넣는게 가능합니다. 이 경우 이진 탐색 트리와 동일하게 항상 index가 작은 쪽에서 큰 쪽으로만 탐색하게 되고 자식 노드가 항상 서로 인접해 있기 때문에 마찬가지로 캐시 적중 측면에서 유리한 점이 많습니다.

실험을 해보자!

지금까지 길게 아이디어만 늘어놓아보았는데요, 백문이 불여일견이죠, 직접 실험을 돌려서 어떤 방법이 제일 빠른지 확인해봅시다. 이하 실험 결과들은 GitHub에서 제공하는 workflow를 이용해 Intel(R) Xeon(R) CPU E5-2673 장비에서 수행된 것입니다. 이 장비는 SIMD확장으로 AVX2까지 지원하므로 SSE2와 AVX2를 사용시의 성능 향상 여부를 비교하는데 사용가능합니다. (AVX2가 2013년에 도입되었으므로 현재 사용하는 대다수의 CPU에서도 동일한 실험을 진행할 수 있을거에요.) 실제 장비가 가상화를 통해 인스턴스 위에서 테스트가 실행되기 때문에 실제 장비에서의 속도와 다소 차이가 발생할 수 있는데요, 이에 의한 오차를 최소화하기 위해 총 10회 반복수행하여 평균낸 결과를 추렸습니다. 실험에 사용한 코드는 https://github.com/bab2min/efficient-search 에서 확인 가능합니다.

실험 대상이 되는 알고리즘은 다음과 같습니다.

• Reference: C++표준의 std::lower_bound 함수를 이용해 값을 찾는 방식
• Hash: C++ 표준의 std::unordered_map을 이용해 값을 찾는 방식(해시 탐색)
• Balanced: 이진탐색 사용
• (SSE/AVX) Balanced: 이진탐색으로 탐색하다 탐색 범위가 SIMD 연산 1회 안으로 들어오는 경우 SIMD연산으로 마무리 탐색
• Binary: 배열에 들어가 있는 이진 탐색 트리를 탐색
• k-ary: 배열에 들어가 있는 k진 탐색 트리를 탐색
• (SSE/AVX) k-ary: 배열에 들어가 있는 k진 탐색 트리를 SIMD 연산을 활용해 탐색

Balanced & (SSE/AVX) Balanced

 

코드가 길고 복잡해보이지만, 이진 탐색을 진행하다 탐색 범위가 128비트 내로 들어올 경우 SSE2 연산을 이용한 탐색을 진행하는게 전부입니다.

위와 동일하지만, AVX2 연산을 이용하는 코드입니다.

Binary

이진 탐색 트리에 기반한 탐색 코드입니다.

k-ary & (SSE/AVX) k-ary

k진 탐색 트리에 기반한 탐색 트리로, k값은 템플릿 매개변수 n이라는 이름 받고 있습니다.

k진 탐색 트리의 SSE2 최적화 버전

k진 탐색 트리의 AVX2 최적화 버전

총 두가지 타입에 대해서 실험했습니다.

• 16b: 부호 있는 16bit 정수
• 32b: 부호 있는 32bit 정수

현재 관심있는 최적화 작업이 정수 타입에 대한 것이라서 위 두 타입에 대해서만 진행했지만, 동일한 방법을 float이나 double에도 적용가능합니다. 실험은 길이가 25, 50, 100, ... 12800인 배열에 임의의 값을 생성하여 넣은 다음, 이 배열 안에서 특정 값을 찾는 작업을 백 만회 수행하여 걸린 시간(ms)을 측정하였습니다. 단 값이 배열 내에 존재하는 경우가 50%에 근접하도록 설정했습니다.

Windows2019 MSVC14.29 환경에서 이진 탐색과 베이스라인의 소요 시간

Windows2019 MSVC14.29 환경에서 k진 탐색 트리와 베이스라인의 소요 시간

먼저 Windows의 결과입니다. 가로축은 배열의 길이고, 세로축은 100만회 탐색에 소요된 시간(ms)입니다. 일단 Reference의 경우 굉장히 느린 것을 볼 수 있습니다. 대부분의 방법보다 2배 이상 느리네요. 또한 특이한 점으로 Reference는 16비트보다 32비트 정수를 탐색하는게 더 빠릅니다. 반면 Hash의 경우 가장 빠른 것으로 확인되었습니다(대량의 메모리로 빠른 속도를 산 셈이라서 불공정한 비교이긴 합니다). 앞서 탐구한 이진 탐색과 SIMD 이진 탐색, k진 탐색 트리의 경우 Reference와 Hash 사이에 위치하는 양상을 보여줍니다. 다만 구체적인 양상은 이진탐색과 k진 탐색 트리가 상이합니다. 이진탐색에 SIMD를 결합한 것은 그냥 이진 탐색에 비해 속도 개선 효과가 거의 없어서 이진 탐색과 거의 동일합니다. 반면 9진/17진 탐색 트리의 경우 SIMD 미사용시 오히려 이진 탐색 트리보다 느리지만, SIMD를 사용할 경우 이진 탐색 트리보다 2배 이상 빨라지는 것을 확인할 수 있습니다.

Ubuntu18.04 GCC9 환경에서 이진 탐색과 베이스라인의 소요 시간

Ubuntu18.04 GCC9 환경에서 k진 탐색 트리와 베이스라인의 소요 시간

동일한 하드웨어임에도 Linux의 결과는 Windows와 제법 달랐습니다. 특히 차이가 나는건 Reference와 Hash였는데요, 이는 C++ 표준 라이브러리를 구현하는 방식에 있어서 MSVC와 GCC간의 차이 때문으로 보입니다. MSVC에서는 느렸던 Reference가 GCC에서는 꽤 빨라서 직접 구현한 이진 탐색과 거의 비슷한 속도를 보여줍니다. 반대로 GCC의 Hash는 MSVC보다 훨씬 느린 양상을 보입니다. 아마 해시 함수나 load factor등에서 차이가 있는게 아닐까 싶네요. 이진 탐색과 k진 탐색 트리의 속도 차이는 Windows와 비슷한 모양으로 나타납니다. GCC에서의 AVX 최적화는 좀 더 극적이라서 17진 탐색 트리에서 AVX2로 100만회 탐색을 할 경우 배열 크기가 12800인 상황에서 30ms도 안 걸립니다.

Windows2019 MSVC14.29 환경에서 이진 탐색의 Reference대비 속도 향상폭 그래프	Windows2019 MSVC14.29 환경에서 k진 탐색 트리의 Reference대비 속도 향상폭 그래프
Ubuntu18.04 GCC9 환경에서 이진 탐색의 Reference대비 속도 향상폭 그래프	Ubuntu18.04 GCC9 환경에서 k진 탐색 트리의 Reference대비 속도 향상폭 그래프

베이스라인인 Reference의 속도를 1로 두었을때 나머지 방법들의 속도가 몇배가 되는지를 그래프로 정리해보았습니다. 17진 탐색 트리를 AVX2로 순회하는 경우 Reference보다 평균 3~4배 정도 빠른 속도를 보여줍니다. 실험을 통해 알게 된 사실을 간단하게 정리해보면 다음과 같겠네요.

1. C++ std 표준 함수가 항상 최적은 아니다. (또한 컴파일러/표준 라이브러리에 따라 속도가 크게 달라진다.)
2. SIMD를 이용해 이진 탐색을 최적화하면 속도를 2배 이상 끌어올릴 수 있다. 특히 탐색 배열의 길이가 짧을 때의 개선폭이 크다.
3. 배열을 k진 탐색 트리 형태로 재배치하면, 이진탐색보다 훨씬 빠르게 탐색이 가능하다. SIMD 최적화를 이용할 경우 3~4배까지 빨라질 수 있다.
4. (당연하겠지만) 16bit정수를 탐색하는게 32bit정수보다 약간 더 빠르다.

마무리하며

최적화에 있어서 중요한 격언이 있습니다. "빠른 코드보다 더 빠른 것은 아무것도 하지 않는 코드이다." 사실 최적화 작업을 진행함에 있어서 먼저 해야할 것은 "병목을 일으키는 부분을 찾아 그 안에서 필요 없는 일을 하는 코드를 쳐내는 것"입니다. 이번 포스팅처럼 이미 $O(\log n)$으로 비교적 빠르게 작동하는 이진 탐색을 개선하는건 상대적으로 우선순위에서 밀리는 작업이죠. 그럼에도 이 최적화 실험을 진행한 이유는 개발중인 형태소 분석기 Kiwi때문이었습니다.

Kiwi의 분석 시간 대부분을 차지하는 작업이 형태소 Trie 탐색과 언어모델 Trie 탐색인데, 이 두 작업 모두 Key-Value 형태로 구성된 Dictionary를 탐색하는 작업을 제일 기본으로 수행합니다. 그리고 이 Dictionary는 모델 파일 내에 고정되어 있는 값이구요. 모든 Dictionary를 HashMap을 이용해 로딩할 경우 메모리 소비량이 너무 커지기 때문에 일차원 배열에 로딩한 뒤 이진 탐색을 사용하는 방식을 사용해왔습니다. 따라서 이진 탐색 자체의 한계를 돌파할 수 있다면 탐색 속도에서 꽤 이득을 볼 수 있던 상황이었던 것이죠. 다행히도 내부적으로 UTF-16을 사용하고 있기 때문에 16비트 정수 탐색을 사용할 수 있어서 32비트에 비해 좀더 빠른 속도를 낼 수 있게 됐네요. 처음 개발 시에는 이럴 줄 알고 UTF-16을 채택한건 아니었는데, 결과적으로는 적절한 선택이 되었네요.

현재 Kiwi 0.10.3버전에서는 SIMD 최적화가 반영된 이진 탐색이 적용되어 있는 상태이며, 0.11버전부터는 SIMD 최적화된 k진 탐색 트리를 적용하고자 현재 테스트를 진행 중에 있습니다. (큰 문제가 없다면 조만간 더 빠른 Kiwi를 만나보실 수 있을거에요~)

1. 정확히는 SSE, NEON은 128bit, AVX는 256bit를 동시에 처리할 수 있습니다. 연산에 사용하는 타입이 32bit 정수라면 SSE, NEON에서는 동시에 4개, AVX에서는 동시에 8개 처리할 수 있고, 16bit라면 SSE, NEON에서는 동시에 8개, AVX에서는 동시에 16개 처리할 수 있는 셈이죠. [본문으로]