[Kiwi] 지능형 한국어 형태소 분석기 ver 0.3 - 알고리즘 최적화 & 메모리 풀

그새를 못 참고 업데이트했습니다. 이번 업데이트에서는 정확도 개선은 없었지만, 알고리즘 최적화와 메모리 관리 향상을 통한 성능 향상이 주요 내용입니다.

0.3 버전 업데이트 내역

• 속도가 0.2 버전 대비 약 86%향상되었습니다.

1.알고리즘 최적화

실행 속도를 높이기 위해서는 실행 시간의 대부분을 차지하는 함수를 튜닝하는게 좋습니다. 다행히도 마솔루야, 거룩하신 MS께서 내리신 Visual Studio에서 성능 분석에 아주아주 좋은 기능을 제공하더라구요.

이 기능을 활용하여 실행시간의 대부분을 소모하는 함수를 찾아 들어가보니 코드 순서를 바꾸고 불필요한 할당을 제거할 수 있는 부분이 있어서 라인 몇줄을 옮기고 지웠습니다. 별거 아닌 것 같은 작업이었지만 이를 통해 10%이상의 성능 향상을 얻을 수 있었죠.

2. 메모리 풀 관리

c++의 기본 메모리 할당자(allocator)가 범용적으로 제일 뛰어나다고 믿어왔었는데, 항상 default가 최선은 아니더라구요. 이번에 메모리 관리를 최적화하면서 많은 것을 배울 수 있었습니다. 여기서는 간단하게 c++의 메모리 관리 방법을 살펴보면서 최적화한 과정을 설명하도록 하겠습니다.

다음 표는 Kiwi 형태소 분석기 내에서 자주 사용되는 vector 컨테이너가 프로그램 실행(약 2만 문장을 분석)하는 동안 메모리 할당을 요청하는 횟수를 정리한 표입니다.

크기(byte)	할당횟수
32	22658253
64	11707092
96	8730568
128	7676374
160	2199410
192	5852745
288	3723174
416	2455901
608	1492526
896	736043
1344	213200
2016	41003
3008	3486
4512	10

32바이트의 경우는 2천만번이 넘게 할당 요청이 있었습니다. 그럼 이 할당된 메모리들은 얼마나 쓰였을까요? 곧바로 반환됐을까요? 아니면 오래오래 쓰이고 반환됐을까요? 아래 표를 보면서 생각해봅시다. 아래 표는 위와 같은 vector에서 동시에 할당된 블록크기의 최대숫자입니다.

크기(byte)	최대동시 할당횟수
32	22
64	17
96	15
128	14
160	2
192	14
288	14
416	13
608	14
896	10
1344	11
2016	8
3008	7
4512	1

위 표를 보시면 32바이트의 경우 동시에 할당되어 사용된 횟수는 최대 22회 밖에 없습니다. 즉 2천만번이 넘는 할당 요청 속에서도 동시에 할당된 수는 22번이 넘지 않았다는 것이고, 그 말은 할당 요청된 대부분의 메모리는 오래지 않아 반환되었다는 의미입니다. 아시다시피 c++에서 지역에 선언된 vector는 해당 스코프를 벗어나면서 자동으로 파괴자가 호출되면서 사용되는 메모리를 반환하기 때문이죠. 이는 메모리를 철저하게 관리하는데 도움이 되지만, 다뤄야하는 데이터 구조가 복잡하여 이중~삼중 컨테이너 사용하게 될 경우 메모리 할당과 해제를 자주 반복하게 합니다.

문제는 new 혹은 malloc으로 메모리를 할당하는 과정이 생각보다 오래 걸린다는 것이죠. 사용할 만큼 할당 받았다가 다시 반환하는게 뭐 그리 오래 걸리겠냐 생각할 수도 있지만, OS 호출을 거쳐야 하는 과정이라서 생각보다 비싼 작업입니다. 즉 자주 메모리를 할당했다가 반환하게 되면 다음과 같은 상황이 발생하게 되죠.

Kiwi: OS야, 나 메모리 좀 빌려주라

OS: 잠깐만, (빈 공간을 찾아서 할당해주고, 다른 프로그램에서 사용하지 못하게 색칠해둔다)

Kiwi: 어, 나 다 씀. 돌려줄게

OS: 잠깐만 (돌려받은 메모리를 확인하고 색칠해뒀던 부분을 지워서 다른 프로그램에서도 사용할 수 있게 한다)

Kiwi: 미안, 나 다시 필요해졌어.

OS: 잠깐만 (다시 빈 공간을 찾아서 할당해주고...)

Kiwi: 근데 나 또 다 씀. 돌려줄게

OS: 잠깐만...

Kiwi: 또 빌려줘.

OS: 부들부들...

어차피 잠깐 잠깐만 쓸 것이라면 매번 할당받았다 반환하는 것보다는, 아예 그 메모리 영역을 계속 들고 있다가 필요할때만 쓰는게 불필요한 OS 호출을 줄이고 빠르겠죠. 그래서 사용하는 것이 메모리 풀(Memory Pool)입니다. 먼저 충분한 양의 메모리를 할당받아놓고 필요한 부분씩만 떼어서 사용하는 방식이죠. 근데 생각보다 단순하지는 않습니다. 떼어줄때 어디가 사용하는 부분이고 어디가 사용하지 않는 부분인지 매번 체크할수도 없는 노릇이고, 그걸 일일히 루프 돌리면서 찾기에는 Pool 크기가 클때 비효율적이기 때문이죠. 따라서 메모리 풀은 다음과 같이 리스트 형태로 관리합니다.

크기가 8인 메모리 풀을 관리한다고 합시다. 그러면 다음과 같이 8칸의 메모리를 미리 할당받겠죠. (그림처럼 꼭 모든 블럭이 연속일 필요는 없습니다) 연두색은 사용가능한 메모리블럭, 진노랑색은 이미 사용중인 메모리블럭을 뜻합니다.

FreeList는 사용가능한 메모리 블럭을 가리킵니다. 그리고 각각의 메모리 블럭은 다음 사용가능한 메모리 블럭을 가리키게 되죠. 사용가능한 메모리 블럭이 없을 경우는 NULL을 가리킨다고 약속합시다.

메모리 할당 요청이 왔습니다. 이전 FreeList가 가리키던 메모리는 할당해줬습니다. 그러면 새로운 FreeList는 기존 FreeList의 메모리 블럭이 가리키던 다음 사용가능한 메모리블럭을 가리키게 바꿔줍니다.

또 메모리 할당 요청이 왔습니다. 이전 FreeList가 가리키던 메모리는 할당해줬습니다. 마찬가지로 새로운 FreeList는 기존 FreeList의 메모리 블럭이 가리키던 다음 사용가능한 메모리블럭을 가리키게 바꿔줍니다.

만약에 첫번째 메모리블럭을 반환받게 되면, FreeList를 첫번째 메모리블럭을 가리키게 하고, 첫번째 메모리 블럭은 이전 FreeList가 가리키던 메모리블럭을 가리키게 바꿔주면 됩니다.

여기서 재미난 아이디어는 각 메모리블럭이 포인터 크기 이상이 되면 굳이 다음 메모리블럭을 가리키는 포인터를 별도로 만들지 않아도 된다는 것입니다. 어차피 사용중인 메모리 블럭은 누구도 가리키고 있지 않으므로, 그 블럭 전체를 할당받은 쪽이 자유롭게 쓰도록 하면 되고, FreeList나 다른 메모리 블럭이 가리키는 메모리 블럭은 사용중이지 않으므로, 그 블럭을 다음 메모리를 가리키는 포인터로 자유롭게 쓸 수 있기 때문이죠.

다음과 같이 구현할 수 있겠죠. (이 코드는 다음 사이트의 내용을 참조하여 작성하였습니다. https://www.gamedev.net/resources/_/technical/general-programming/c-custom-memory-allocation-r3010)

template<size_t objectSize, size_t poolSize> class KPool { public: char* poolBuf; void** freeList; static KPool& getInstance() { static thread_local KPool inst; return inst; } void* allocate() { if (!freeList) throw bad_alloc(); void* p = freeList; freeList = (void**)(*freeList); return p; } void deallocate(void* p) { *((void**)p) = freeList; freeList = (void**)p; } private: KPool() { poolBuf = new char[poolSize * objectSize]; freeList = (void**)poolBuf; auto p = freeList; for (size_t i = 1; i < poolSize; i++) { *p = ((char*)p + objectSize); p = (void**)*p; } *p = nullptr; } KPool(const KPool&) {} ~KPool() { delete[] poolBuf; } };

thread_local한 싱글턴으로 작성했고, 또한 템플릿 클래스이기 때문에 objectSize와 poolSize에 따라 독립적인 클래스를 만들게 되죠. allocate를 통해 메모리를 할당받고, deallocate를 통해 메모리를 반환합니다. (malloc과 free를 생각하면 됩니다.) 이를 vector 컨테이너에 적용할 수 있도록 allocator로 만들어봅시다.

template <typename T> class pool_allocator : public allocator<T> { public: typedef size_t size_type; typedef T* pointer; typedef const T* const_pointer; template<typename _Tp1> struct rebind { typedef pool_allocator<_Tp1> other; }; pointer allocate(size_type n, const void *hint = 0) { return allocator<T>::allocate(n, hint); } void deallocate(pointer p, size_type n) { return allocator<T>::deallocate(p, n); } pool_allocator() throw() : allocator<T>() { } pool_allocator(const pool_allocator &a) throw() : allocator<T>(a) { } template <class U> pool_allocator(const pool_allocator<U> &a) throw() : allocator<T>(a) { } ~pool_allocator() throw() { } }; template <> class pool_allocator<someType> : public allocator<someType> { public: typedef size_t size_type; typedef value_type* pointer; typedef const value_type* const_pointer; template<typename _Tp1> struct rebind { typedef pool_allocator<_Tp1> other; }; pointer allocate(size_type n, const void *hint = 0) { // 128바이트 이하인 경우는 128바이트 크기의 메모리 풀 사용 if (n * sizeof(value_type) <= 128) return (pointer)KPool<128, 512>::getInstance().allocate(); // 1024바이트 이하인 경우는 1024바이트 크기의 메모리 풀 사용 if (n * sizeof(value_type) <= 1024) return (pointer)KPool<1024, 256>::getInstance().allocate(); // 나머지 경우는 일반 메모리 할당 사용 return allocator<value_type>::allocate(n, hint); } void deallocate(pointer p, size_type n) { if (n * sizeof(value_type) <= 128) return KPool<128, 512>::getInstance().deallocate(p); if (n * sizeof(value_type) <= 1024) return KPool<1024, 256>::getInstance().deallocate(p); return allocator<value_type>::deallocate(p, n); } pool_allocator() throw() : allocator<value_type>() { } pool_allocator(const pool_allocator &a) throw() : allocator<value_type>(a) { } template <class U> pool_allocator(const pool_allocator<U> &a) throw() : allocator<value_type>(a) { } ~pool_allocator() throw() { } };

pool_allocator가 모든 상황에서 적절하지는 않을수 있기 때문에 someType에 대해서만 KPool을 이용하도록 특수화시켜서 사용하도록 할거에요. 위의 pool_allocator를 통해 vector를 만들고자 하면 vector<someType, pool_allocator<someType>> someVector; 와 같은식으로 변수를 선언하면 됩니다. 즉 custom allocator를 구현하고, vector 템플릿 인자로 pool_allocator 하나만 추가해주면 간단하게 해당 컨테이너가 메모리 풀을 통해 메모리를 할당받게 됩니다. 간단하죠?

+보너스 코드

메모리 할당 로그 추적하는 logger_allocator

class KSingleLogger { public: map<size_t, size_t> totalAlloc; map<size_t, size_t> currentAlloc; map<size_t, size_t> maxAlloc; static KSingleLogger& getInstance() { static thread_local KSingleLogger inst; return inst; } private: KSingleLogger() { } KSingleLogger(const KSingleLogger&) {} }; template <typename T> class logger_allocator : public allocator<T> { public: typedef size_t size_type; typedef T* pointer; typedef const T* const_pointer; template<typename _Tp1> struct rebind { typedef logger_allocator<_Tp1> other; }; pointer allocate(size_type n, const void *hint = 0) { //fprintf(stderr, "Alloc %d bytes. (%zd)\n", n * sizeof(T), KSingleLogger::getInstance().counter++); size_t bytes = n * sizeof(T); auto& logger = KSingleLogger::getInstance(); logger.totalAlloc[bytes]++; logger.currentAlloc[bytes]++; logger.maxAlloc[bytes] = max(logger.maxAlloc[bytes], logger.currentAlloc[bytes]); return allocator<T>::allocate(n, hint); } void deallocate(pointer p, size_type n) { //fprintf(stderr, "Dealloc %d bytes (%p).\n", n * sizeof(T), p); KSingleLogger::getInstance().currentAlloc[n * sizeof(T)]--; return allocator<T>::deallocate(p, n); } logger_allocator() throw() : allocator<T>() { /*fprintf(stderr, "Hello allocator!\n");*/ } logger_allocator(const logger_allocator &a) throw() : allocator<T>(a) { } template <class U> logger_allocator(const logger_allocator<U> &a) throw() : allocator<T>(a) { } ~logger_allocator() throw() { } };

메모리 할당/해제를 추적하고 싶은 컨테이너에 logger_allocator를 사용한 뒤, 모든 작업이 끝나고 KSingleLogger::getInstance()를 통해서 totalAlloc, maxAlloc을 확인하면 위의 표처럼 전체 할당 횟수와 최대 동시 할당 횟수를 확인할 수 있습니다.

3. 속도가 얼마나 향상됐을까요?

	Kiwi 0.2 (ms)	알고리즘 최적화 (ms)	알고리즘 + 메모리풀 최적화 (ms)	최종 성능 향상(%)
텍스트A	11680	8651	5656	+107%
텍스트B	8864	6931	4865	+82%
텍스트C	7670	6174	4294	+79%
텍스트D	15808	13436	9073	+74%
텍스트E	21126	15412	11055	+91%
합계	65148	50604	34943	86%

거의 2배 정도 빨라졌다고 볼 수 있네요. 코드 몇 줄 옮기고 메모리 할당자 바꿔치웠다고 이렇게 성능이 올라가도 되는건가요... 속도 빨라지는거 보니깐 괜히 뿌듯해집니다. 적당히 만들다가 말려고 했는데, 좀더 할 의욕이 생기네요.

Kiwi 형태소 분석기의 모든 소스코드는 LGPL v3라이센스에 따라 https://github.com/bab2min/Kiwi에서 배포됩니다. 또한 웹 데모는 https://lab.bab2min.pe.kr/kiwi 사이트에서 테스트해볼 수 있습니다.