LFH (Low Fragmentation Heap), TBB alloc

[펌] http://egloos.zum.com/sweeper/v/2843922

1. LFH

msdn 소개 페이지 : http://msdn.microsoft.com/ko-kr/library/aa366750

Win2k SP4, WinXP, WinServer 2k3부터 적용되기 시작해서, WinVISTA부터는 시스템에서 자동으로 low-fragmentation heap(LFH)가 설정되기 시작했다.

Heap fragmentation은 잦은 할당과 해제 이후 가용 메모리가 작고 불연속적인 블록들로 나뉘어진 상태를 얘기한다.

힙이 조각나면, 전체 남아있는 메모리 양보다 작은 양에 대해 할당 요청해도, 해당 크기에 대해 연속적인 메모리 구간 확보가 되지 않아 메모리 할당 요청이 실패할 수 있다. 

LFH는 heap fragmentation을 줄여주고, 특히나 멀티쓰레드 환경에서 그 성능이 훨씬 더 비약적으로 좋아진다고 한다.

LFH는 128개의 서로 다른 블록 사이즈와 범위로 힙을 미리 구성하여, 메모리 단편화를 피한다.

이 128개의 범위의 사이즈를 bucket이라고 부르며, 힙을 통한 메모리 할당 요청이 들어오면, LFH는 요구된 사이즈를 포함할 수 있는 가장 작은 bucket을 선택한다.

참고로, 가장 작은 bucket의 사이즈는 8 bytes 이다.

<Bucket 의 구성>

Buckets	Granularity	Range
1-32	8	1-256
33-48	16	257-512
49-64	32	513-1024
65-80	64	1025-2048
81-96	128	2049-4096
97-112	256	4097-8192
113-128	512	8193-16384

1~32 버킷은 메모리 블록 크키가 8 bytes이며, 1~256 bytes 할당에 사용된다.

즉, 1~32 버킷의 graularity가 8 bytes 이므로... 아래와 같은 할당 사이즈를 부여받는다.

8, 16, 24, 32, 40, 48, 56, 64,  [1~8]

72, 80, 88, 96, 104, 112, 120, 128,  [9~16]

136, 144, 152, 160, 168, 176, 184, 192,  [17~24]

200, 208, 216, 224, 232, 240, 248, 256 [25~32]

예를 들어서, 17 bytes 요청이 들어오면 17은 16과 24의 사이이므로 버킷3 (24)의 크기가 사용된다.

2. 제약

LFH는 다음과 같은 제약 사항들을 가진다.

• LFH enabled heap이라도, 할당 크기가 16kb보다 작을 것. 16kb보다 더 크면 LFH 적용이 되지 않는다.

• HEAP_NO_SERIALIZE로 생성된 heap엔 적용되지 않는다. 자세한 내용은 MSDN 참고

• 고정 크기(Fixed size)로 생성된 heap엔 적용되지 않는다.

• 디버깅 툴에서는 LFH가 동작하지 않는다. 
  예를 들어 비쥬얼 스튜디오에서의 run 상태에선 활성화 되지 않는다.
  release 모드라도 F5로 실행시엔 되지 않으니, 그냥 실행파일을 직접 실행해 보라.
  

3. 사용법 (정리중...)

1) ProcessHeap 사용시

2) PrivateHeap 사용시

4. 성능 테스트

성능 비교 환경

• OS : Win2k8 R2
• CPU : i7 930 @ 2.80GHz, 쿼드코어, 하이퍼쓰레딩
• IDE : VisualStudio 2k10, x64 (64bit)

성능 비교는 현재 회사에서 사용중인 각기 다른 두 개의 직접 제작한 메모리매니져와 비교되었다.

(이 녀석들은 이미 상용화된 게임 서버에 실 사용되고 있는 녀석들이다)

직접 만든 두 개 메모리매니져의 차이는 멀티쓰레드간 동기화 처리 방식의 차이이며 그 차이는 다음과 같다.

• 하나는 InterlockedSinglyList를 사용하였음
• 하나는 손으로 만든 thread-safety가 보장된 스택

또 하나 비교된 녀석은 인텔의 TBB의 scalable_malloc을 사용한 것이다.

참고로, PrivateHeap을 생성하고 LFH를 명시적으로 켠 것과 그냥 malloc/free와의 성능차이는 아예 없었다.

이는, Windows Vista 이후부터 LFH가 자동으로 켜지는 사실과, Windows CRT malloc이 내부적으로 HeapAlloc을 사용하는 것을 입증해주는 것을 의미한다.

테스트 시나리오는 다음과 같다.

• 각 쓰레드는 20480번 루프를 돌며, 랜덤크기 할당을 한다.
• 환경을 동일하게 맞추기 위해 고정 난수 시드를 사용한다.
• 모두 할당이 끝나면 모조리 해제를 한다.
• 위 과정을 1280번 반복해서 테스트한다.
• 쓰레드 개수는 1 -> 4 -> 8 -> 16개로 점점 늘려서 테스트 해 본다.

LFH를 사용할 때 주의 사항이 16kb까지의 할당인데, 여기에 조심해야 할 것이 하나 있다.

16kb, 정확히는 userdata를 16344 바이트까지만 LFH 적용이 되었다. (16345부터 LFH 미적용되었음)

내부적으로 사용하는 metadata에 40 바이트 정도가 소요되는 듯 하다.

TBB scalable_malloc의 경우 인텔 홈페이지에선 다음과 같이 소개하고 있다.

(TBB : http://threadingbuildingblocks.org/)

TBB scalable memory allocator was designed to improve performance of multi-threaded applications. We have found that it performs especially well when threads allocate small memory blocks.

멀티쓰레드 환경에 강한 것을 목적으로 설계되었고, 특히 작은 메모리블럭을 할당할 때 성능이 훌륭하다 하였다.

이 모든 것들을 한꺼번에 테스트하기 위해 할당 최대 크기를 다음과 같이 세단계로 나누어 테스트 하였다.

• 16344
• RAND_MAX (0x7fff)
• 8192

(아래 그림들의 모자이크(?) 처리된 녀석들이 직접 만든 메모리매니져들이며, 세로축은 측정에 소요된 시간이므로, 막대가 낮을수록 좋은 성능을 보인 것이다)

(세로축의 숫자에 신경쓰지 말고, 대조군들간의 성능 차이만 보기 바란다)

<<< 최대 할당크기 16344 >>>

LFH가 감당할 수 있는 크기까지만 할당 테스트를 했을 때, 확실히 쓰레드 수가 증가할수록 LFH의 상대적인 성능은 증가했다.

늘 선형적인 성능 증가는 아니었지만, 멀티 쓰레드 환경에서 성능이 좋다는 것이 입증된 듯 하다.

TBB의 경우 16kb 한계를 뒀을 때 그 성능이 눈에 띄게 떨어지는 것을 확인할 수 있었다.

LFH 처럼 내부적으로 매니지하는 할당 크기의 한계가 있는 것이 아닌가 싶다.

TBB의 진면목은 8kb 테스트에서 확인할 수 있다.

<<< 최대 할당크기 RAND_MAX >>>

하지만, 할당 범위를 1~RAND_MAX(0x7fff)까지 잡고 테스트하면, LFH가 동작을 하다말다 해서 그 결과가 참혹했다.

쓰레드의 개수가 늘어날수록 처리 속도가 기하급수적으로 느려진다.

1개에서 4개로 늘리면 8배가 늘어났고, 4개에서 8개로 늘렸을 때도 8배가 늘어났다. 8개에서 16개로는 엄두가 안나 테스트하지 않았다.

위 그림을 보면 알겠지만, 워낙 LFH 소요시간이 상대적으로 느려 다른 녀석들은 그래프상에서의 의미가 거의 없어질 정도였다.

<<< 최대 할당크기 8192 >>>

할당 최대 크기를 8kb로 잡았을 땐, TBB scalable_malloc의 성능이 가장 뛰어났다.

이래저래 테스트 해 본 결과 TBB가 LFH 단독보다 성능 우위를 점하는 마지노선은 거의 8kb 였다.

9 kb가 넘어가면서부터 LFH가 조금씩 성능이 뛰어났었다.

그리고, TBB의 할당크기 범위가 1024~4096 정도일 때 LFH 대비 성능이 눈에 띄게 좋았다.

(대략적으로 1024일 땐 39~40%, 2048일땐 35%, 4096일땐 30% 정도 빨랐었다)

할당 최대 범위가 8192일 땐 평균 13~15% 정도 우위뿐이었다.

또 하나 TBB가 놀라웠던 점 중 하나가 논리코어 8개짜리 머신에서 16개의 쓰레드가 일을 할 때의 성능이었다.

위 그림에서도 나타나듯이, 쓰레드 경합이 있을 때 훨씬 더 빠른 결과를 보여주었다.

(최대 할당 범위를 2k로 잡고 쓰레드 16개로 테스트 해보면 TBB가 무려 2.2배 정도 빠르다)

하지만, 무조건 쓰레드 레이스가 심하게 발생한다고 성능 차이가 벌어지는 것은 아니었고,

논리 코어 수의 2배의 쓰레드가 일을 할 때 LFH와의 성능 차이가 가장 심했다.

1024 할당 범위로 테스트해 본 결과, i5-750에서도, i7-930에서도 쓰레드수를 계속 늘려봤지만, 코어수의 4배, 8배, 16배에서도  TBB가 빠르긴 했지만 성능의 차이가 갈수록 줄어들었다.

5. 결론

• LFH는 총 16384, 유저가 할당할 수 있는 크기 16344까지만 할당시 멀티쓰레드 환경에서 상당히 우수한 능력을 보여주었다.
• 특히, 직접 만든 메모리매니져에 비해 bucket grow 속도가 아주 빨랐다.
• 대형 MMORPG 서버에서는 초기 할당크기 이상으로 메모리풀이 늘어나기 마련이라, 인상적이었음.
• 단 싱글 쓰레드에서의 성능은 역시나 좋지 못했고, 해당 머신의 코어수에 근접한 쓰레드가 워킹할 때 가장 좋은 능력을 보여 주었다.
  
  
• TBB의 scalable_malloc는 8192 이내의 크기로 할당시 LFH보다 뛰어났으며, 4096 이내 할당시엔 LFH에 비해 꽤나 좋은 성능을 보여주었다.
• 다만, LFH처럼 built-in이 아니어서, 인텔 TBB의 tbb_malloc.dll 을 사용해야 하는 것이 조금 걸린다.
• 인텔에서 TBB 소스도 공개하고 있으니, dll 사용이 걸리면 필요한 내용을 직접 프로젝트에 포함시켜도 될 듯...

결국 가장 이상적인 형식은 할당되어야 하는 메모리 크기에 따라 메모리매니져를 혼용 운용하는 형태가 아닐까 한다.

굳이 TBB (8~4096) <-> LFH (4097 ~16344) <-> 기타 page 단위 alloc (16345 ~)의 형태까지 나누어야 되나 싶긴 하지만, 

적어도 LFH가 감당할 수 있는 크기와 그렇지 못한 크기로 나누어,

LFH alloc과 page 단위 alloc등의 형태로 나누어 관리한다면, 최적의 효과를 볼 수 있을것이라고 생각된다.