MemoryAllocation

UserPreferences

1. 메모리 할당
2. 2개 이상의 힙을 사용한 메모리 단편화 해결 방안
3. Multi-Processor Heap
4. Windowx XP Low-fragmentation Heap
5. 링크

1 메모리 할당

메모리 할당에 있어서, 이슈는 2가지라고 볼 수 있다. 첫번째는 스레드 직렬화에 따른 성능 저하, 두번째는 대량의 할당/해제에 따른 단편화이다. 성능 저하를 피하면서 단편화를 최소화하는 것이 대부분의 범용 메모리 할당 알고리즘들이 추구하는 바이다.

2 2개 이상의 힙을 사용한 메모리 단편화 해결 방안

from Unmanaged Memory Fragmentation -- an old story

요약해보자면...

2개의 힙을 할당한 다음 N번째, 예를 들어 100000번째까지는 첫번째 힙에서 계속 할당을 하고, 100001번째부터는 두번째 힙에서 할당을 한다. 그러다 200000번째 할당이 필요하게 되면 다시 첫번째 힙에서부터 할당을 한다.



static size_t g_Allocs = 0;
static int    g_HeapIndex = 0;
static HANDLE g_Heap[2] = { NULL, NULL };
...
void* operator new (size_t size)
{
    if ((++g_Allocs % 100000) == 0) 
        g_HeapIndex ^= 0x10; 

    return ::HeapAlloc(g_Heap[HeapIndex], HEAP_ZERO_MEMORY, size);
}

대충 이런 식?

이와 같은 방법으로 메모리 할당을 하게 되면 한쪽에서는 할당만이 일어나고, 나머지 한쪽에서는 해제만이 일어나게 된다. 다른 쪽의 힙에서 할당을 하게 될 때쯤 되면, 그 힙은 거의 깨끗한 상태가 된다는 말이다.

물론 애플리케이션의 특성에 따라 달라지기는 하겠으나, 힙에 올라가는 데이터들이 금방 사라지는 데이터라는 점을 감안하면 괜찮을 것 같기도 하다. 장기간 힙에 존재하는 데이터의 경우(룩업테이블 같은...)에는 따로 힙을 마련해두면 그만. 문제는 저 100000이라는 숫자를 어떻게 정하느냐인데... 힙에 올라가는 데이터의 평균 수명과 초당 할당 호출 횟수를 알아내야하나?

3 Multi-Processor Heap

Visual C++ 6.0 샘플에 있던 소스로서, 멀티 프로세서 머신에서 돌아가는 멀티 스레드 프로그램의 성능 개선을 위한 메모리 할당 알고리즘이다. Visual C++ 6.0 샘플은 여기에서 다운로드받을 수 있다. 소스 원문에 있던 내용을 일부 옮겨보자면 다음과 같다.

Many multithreaded applications that use the standard memory allocation routines (malloc/free, LocalAlloc/LocalFree, HeapAlloc/HeapFree) suffer a significant performance penalty when running on a/ multi-processor machine. This is due to the serialization used by the default heap package. On a multiprocessor machine, more than one thread may simultaneously try to allocate memory. One thread will block on the critical section guarding the heap. The other thread must then signal the critical section when it is finished to unblock the waiting thread. The additional codepath of blocking and signalling adds significant overhead to the frequent memory allocation path.

By providing multiple heaps, this DLL allows simultaneous operations on each heap. A thread on processor 0 can allocate memory from one heap at the same time that a thread on processor 1 is allocating from a different heap. The additional overhead in this DLL is compensated by drastically reducing the number of times a thread must wait for heap access.

4 Windowx XP Low-fragmentation Heap

Low-fragmentation Heap

윈도우즈 XP 이상의 버전에서는 HeapSetInformation API를 이용해 단편화를 줄일 수 있다.


#include <windows.h>
#include <stdio.h>

void main()
{
    ULONG  HeapFragValue = 2;

    if(HeapSetInformation(GetProcessHeap(),
                       HeapCompatibilityInformation,
                       &HeapFragValue,
                       sizeof(HeapFragValue))
    )
    {
        printf("Success!\n");
    }
    else printf ("Failure (%d)\n", GetLastError());
}

API 한번 호출해주면 땡이니, 별다른 수고 없이 단편화를 줄일 수 있는 셈이다. 그러나 세상 만사 그리 쉬울 리 없다. 이 기능은 해당 힙에 HEAP_NO_SERIALIZE 같은 플래그들이 켜져 있는 경우에는 동작하지 않는다. 디버그 버전일 때도 안 돌아가는 모양이다. 사용할 일이 있기는 할지 의문이다.

5 링크

• the HOARD memory allocator
  
The Hoard memory allocator is a fast, scalable, and memory-efficient memory allocator. It runs on a variety of platforms, including Linux, Solaris, and Windows. Hoard is a drop-in replacement for malloc() that can dramatically improve application performance, especially for multithreaded programs running on multiprocessors. No change to your source is necessary. Just link it in or set just one environment variable.

• http://g.oswego.edu/dl/html/malloc.html
  
Doug Lea's malloc

• Real-Time Dynamic Memory Allocation
  
This is a web site dedicated to explicit dynamic storage allocation in the area of real-time systems. Although dynamic storage allocation is a deeply studied subject in computer science, it has not been widely used in real-time systems due to the commonly accepted idea that it is, due to the intrinsic nature of the problem, difficult or even impossible to design a efficient time-bounded algorithm.


• Gamasutra > Play by Play : Effective Memory Management
  
메모리 관리자를 직접 제작할 때 생각해야할 문제점들

• Inside memory management
  
The choices, tradeoffs, and implementations of dynamic allocation. (Linux)

• Policy-Based Memory Allocation
  

• see also MemoryManagement
  

• CategorySystemProgramming