Windows Heap Memory
From DevNote
Contents |
Overview
힙메모리(heap memory)는 유저모드 어플리케이션에서 동적 메모리 할당을 위해 가장 많이 사용되는 일종의 메모리 풀(memory pool)이다. 힙메모리는 빠른 할당과 해제(alloc and free)를 위해 윈도우즈의 경우 look-aside list와 free list를 가지고 있다. 최근에 발간된 "Advanced Windows Debugging"이란 책에 윈도우즈 힙에 관한 자세한 내용이 있다. Advanced Windows Debugging 샘플 챕터를 다운로드 받아 볼 수도 있다.
윈도우즈 힙메모리라 하면 HeapAlloc과 HeapFree를 사용하여 동적 메모리를 할당/해제하는 것을 말한다. 일반적으로 new/delete와 malloc/free를 Visual C에서 사용하면 윈도우 힙 API인 HeapAlloc/HeapFree가 최종으로 호출된다. 윈도우즈 힙메모리의 특징을 간략히 정리하면 아래와 같다.
Small Page size = 4KB VirtualAlloc granularity = 64KB Win32 heap alloc granularity = 8 bytes Win64 heap alloc granularity = 16 bytes Max heap block size = 0x7f000 (508KB) (If alloc size is greater than max heap size, it'll use VirtualAlloc) User virtual address space(Win32): - default = 0x00000000 ~ 0x7FFFFFFF (2GB) - 4GT[1]: large address aware = 0x00000000 ~ 0xBFFFFFFF (3GB) Heap synchronization: - One lock will be used to protect entire heap - HEAP_NO_SERIALIZE will make skip the lock mechanism Heap Look-Aside list: - Lock-free linked list - Using LIFO for cache locality optimization - 128 look-aside lists per heap - Can handle up to alloc size 1KB(Win32) or 2KB(Win64) Heap Free list - Can Handle upto max heap block size (508KB) Heap signatures: [2] - Heap handle signature = 0xEEFFEEFF - Tail fills = 0xABABABAB - Free heap fills = 0xFEEEFEEE - Alloc heap fills = 0xBAADF00D
Windows Low Fragmentation Heap vs. Hoard
윈도우즈의 Low Fragmentation Heap은 Windows 2000 부터 새로이 들어간 힙으로, 원래는 프로그램 상에서 설정해 주어야만 사용되었으나 Vista에서는 실행시간 중에 자동으로 LFH를 사용하는 오토 튜닝 기능이 추가되었다. 그런데, 여기서 흥미로운 점은 LFH가 거의 Lock-Free로 이루어져 있어, 멀티스레드를 사용한 프로그램에서 (특히 서버 프로그램이 이에 해당) 높은 성능을 보인다는 것이다.[3] 물론 멀티프로세서 혹은 멀티코어 시스템에서만 기본 힙에 비해 높은 성능향상을 보인다.
멀티스레드 메모리 테스트 프로그램을 사용하여, LFH를 멀티스레드 메모리 관리자로 유명한 Hoard와 비교해 보았다. 메모리 테스트 특성상 어떠한 방법을 사용하는 가에 따라 테스트 결과는 매우 다르게 나타난다. 여기서 사용한 방법은 Larson의 논문인 "Memory Allocation for Long-Running Server Applications"에서 아이디어를 얻어 이를 변형한 방법을 사용하였다. Larson의 방법과 다른 점은 일정 개수의 스레드와 메모리 컨택스트를 미리 만들어 놓고, 각 스레드는 큐로부터 하나의 메모리 컨택스트 빼온 후 메모리 할당과 해제인 alloc/free를 얼마간 반복한 후 다시 큐에 반환한다. 따라서, 여러 스레드간 메모리 공유가 일어나며 A 스레드에서 할당된 메모리는 B스레드에서 해제되는 경우가 발생한다. 이 테스트 방식은 여러 스레드가 동적 할당된 메모리 포인터를 공유하거나 서로 전달한다는 가정을 한 것이다. 예를 들면 producer/consumer 관계의 두 스레드가 대표적인 예에 해당할 수 있다.
아래 그래프는 LFH와 Hoard와의 비교 결과를 보여주는데, 간단히 말해 LFH가 월등히 뛰어난 결과를 나타내었다. 특히, 스레드가 증가할수록 Hoard는 성능 저하가 나타나고 있다. 이것은 Hoard가 내세우고 있는 멀티프로세서에서 높은 성능을 보인다는 것과는 매우 다른 결과이다. (이 테스트는 Intel Quad Core Q6600 Kentsfield 컴퓨터 + Windows Vista 에서 이루어졌다.)
각 스레드들이 어디서 가장 많은 시간을 보내고 있는지 알아보기 위해 아래 Hoard 메모리 테스트 프로그램에 디버거를 붙여서 콜스택을 출력해 보았다. 0번 스레드는 메인 스레드로 다른 테스트 스레드가 끝나기를 기다리고 있다. 나머지는 메모리 테스트 스레드인데 이상하게도 모든 스레드가 Kernel의 Sleep를 호출하고 있는 것이 보인다. Hoard의 소스를 자세히 살펴보지 못했으나, 이로서 Hoard는 내부에 어떤 event를 기다리고 있는 부분이 있다는 것을 알 수 있다. 하지만, 더 이상 왜 Hoard가 LFH에 비해 4배이상 느린지에 관해서는 자세히 알 수 없었다.
0 Id: bd0.fb4 Suspend: 1 Teb: 7ffdf000 Unfrozen ChildEBP RetAddr 0012fa6c 7795f7c0 ntdll!KiFastSystemCallRet 0012fa70 775b78e0 ntdll!NtDelayExecution+0xc 0012fad8 77571da0 kernel32!SleepEx+0x62 0012fae8 00401dc2 kernel32!Sleep+0xf 0012fb40 779b178f MemTest+0x1dc2 0012fbb0 7797dc7e ntdll!RtlDebugAllocateHeap+0x309 00290148 00000000 ntdll!RtlpAllocateHeap+0xc6 1 Id: bd0.a30 Suspend: 1 Teb: 7ffdd000 Unfrozen ChildEBP RetAddr 0088fed8 7795f7c0 ntdll!KiFastSystemCallRet 0088fedc 775b78e0 ntdll!NtDelayExecution+0xc 0088ff44 77571da0 kernel32!SleepEx+0x62 0088ff54 630023b4 kernel32!Sleep+0xf 0088ff68 6300191d winhoard+0x23b4 0088ff7c 00401c48 winhoard+0x191d 0088ffa0 775b3833 MemTest+0x1c48 0088ffac 7793a9bd kernel32!BaseThreadInitThunk+0xe 0088ffec 00000000 ntdll!_RtlUserThreadStart+0x23 2 Id: bd0.9e0 Suspend: 1 Teb: 7ffdc000 Unfrozen ChildEBP RetAddr 00a6fee0 7795f7c0 ntdll!KiFastSystemCallRet 00a6fee4 775b78e0 ntdll!NtDelayExecution+0xc 00a6ff4c 77571da0 kernel32!SleepEx+0x62 00a6ff5c 630023b4 kernel32!Sleep+0xf 00a6ff70 630015f4 winhoard+0x23b4 00a6ff7c 00401c60 winhoard+0x15f4 00a6ffa0 775b3833 MemTest+0x1c60 00a6ffac 7793a9bd kernel32!BaseThreadInitThunk+0xe 00a6ffec 00000000 ntdll!_RtlUserThreadStart+0x23 3 Id: bd0.c04 Suspend: 1 Teb: 7ffdb000 Unfrozen ChildEBP RetAddr 00b6fee0 7795f7c0 ntdll!KiFastSystemCallRet 00b6fee4 775b78e0 ntdll!NtDelayExecution+0xc 00b6ff4c 77571da0 kernel32!SleepEx+0x62 00b6ff5c 630023b4 kernel32!Sleep+0xf 00b6ff70 630015f4 winhoard+0x23b4 00b6ff7c 00401c60 winhoard+0x15f4 00b6ffa0 775b3833 MemTest+0x1c60 00b6ffac 7793a9bd kernel32!BaseThreadInitThunk+0xe 00b6ffec 00000000 ntdll!_RtlUserThreadStart+0x23
이에 비해 아래 콜스택은 LFH 테스트 프로그램을 실행 중에 나타난 것이다. (주의할 것은 디버거가 attach 되면 윈도우즈는 자동으로 Debug heap을 사용하므로 환경변수 _NO_DEBUG_HEAP를 set _NO_DEBUG_HEAP=1와 같이 셋팅해 주어야만 한다.) LFH의 경우 0번 메인 스레드를 제외하고는 모두 LFH API 내부 함수를 실행 중이며 별다른 Sleep나 Wait혹은 Critical Section함수를 부르고 있지는 않다.
0 Id: 6a4.f80 Suspend: 1 Teb: 00000000`7efdb000 Unfrozen ChildEBP RetAddr 0017fa68 776c1330 ntdll32!NtDelayExecution+0x15 0017fad0 776c0dac kernel32!SleepEx+0x62 0017fae0 00409ef2 kernel32!Sleep+0xf 0017fef8 00409ffa MemTest!RunThreads+0xc2 0017ff50 004013aa MemTest!main+0xca 0017ffa0 777319f1 MemTest!__tmainCRTStartup+0x15f 0017ffac 77e7d109 kernel32!BaseThreadInitThunk+0xe 0017ffec 00000000 ntdll32!_RtlUserThreadStart+0x23 1 Id: 6a4.124c Suspend: 1 Teb: 00000000`7efd8000 Unfrozen ChildEBP RetAddr 0078ff4c 77e2b2df ntdll32!RtlpLowFragHeapFree+0x34 0078ff60 77731d27 ntdll32!RtlFreeHeap+0x101 0078ff74 00409d73 kernel32!HeapFree+0x14 0078ffa0 777319f1 MemTest!ThreadProc+0x143 0078ffac 77e7d109 kernel32!BaseThreadInitThunk+0xe 0078ffec 00000000 ntdll32!_RtlUserThreadStart+0x23 2 Id: 6a4.106c Suspend: 1 Teb: 00000000`7efd5000 Unfrozen ChildEBP RetAddr 00dfff4c 77e2b2df ntdll32!RtlpLowFragHeapFree+0x324 00dfff60 77731d27 ntdll32!RtlFreeHeap+0x101 00dfff74 00409d73 kernel32!HeapFree+0x14 00dfffa0 777319f1 MemTest!ThreadProc+0x143 00dfffac 77e7d109 kernel32!BaseThreadInitThunk+0xe 00dfffec 00000000 ntdll32!_RtlUserThreadStart+0x23 3 Id: 6a4.1028 Suspend: 1 Teb: 00000000`7efad000 Unfrozen ChildEBP RetAddr 00efff4c 77e2b2df ntdll32!RtlpLowFragHeapFree+0xd4 00efff60 77731d27 ntdll32!RtlFreeHeap+0x101 00efff74 00409d73 kernel32!HeapFree+0x14 00efffa0 777319f1 MemTest!ThreadProc+0x143 00efffac 77e7d109 kernel32!BaseThreadInitThunk+0xe 00efffec 00000000 ntdll32!_RtlUserThreadStart+0x23
이러한 결과로 아직 LFH가 Hoard에 비해 월등하다고 (적어도 Windows 플랫폼에서) 확실히 단정 짓기는 이르다. 왜냐면, 멀티스레드 메모리 테스 테스트 결과는 그 방법에 따라 매우 다르게 나오기 때문이다. 또한 Hoard가 윈도우즈 버전에 (특히 비스타에서) 문제가 있을 수 있다. 하지만, 어쨋든 여기서 사용된 테스트 방법에서 LFH가 매우 빠른 성능을 보인것은 틀림이 없다.
메모리 테스트 프로그램 실행파일 및 소스코드
테스트 프로그램의 알고리즘에 관해 알고 싶은 사람들을 위해 아래 소스와 함께 아래 공개하니, 다운로드하여 직접 확인해 볼 수 있을 것이다.
멀티스레드 힙메모리 테스트 프로그램 실행파일 및 소스코드
