사실 최적화시 알고리즘보다 중요한 메모리 할당

• OS의 메모리 매니저의 기본 관리 단위는 페이지(4KB / 1MB / 2MB / 4MB)

그런데 사용자가 1Byte메모리 할당에 4KB를 할당받아 쓰기엔 너무 낭비가 크다

따라서 임의의 덩어리 메모리를 쪼개서 다양한 사이즈의 메모리 블록으로 사용할 수 있도록 하자. -> Heap 사용

Window의 메모리 할당

• new/malloc -> HeapAlloc() -> VirtualAlloc()

Commit하기전 reserver도 수행하는데 C/C++에서 malloc/new 시 에 보통 동시에 이루어짐

Heap 메모리란

• 큰 덩어리의 메모리부터 다양한 사이즈의의 메모리 블록을 할당.
• 해제 시 인접한 블록과 병합할 수 있으면 병합하여 더 큰 메모리 블록을 유지.
• 대부분의 메모리 관리 시스템이 heap based.

Heap의 성능 문제

• 할당시엔 적합한 사이즈의 블록 찾기
• 해제 시 병합 비용 최대한 큰 덩어리로 가질 수 있게 병합함
• 단편화
• Commit 비용

메모리 사용 특성 고려

• 특정 사이즈(struct의 사이즈)의 메모리 블록을 왕창 할당할 일이 많다.
• 게임에서는 메모리 사용량 peak에 도달한 후 다시 peak에 도달할 가능성이 높다(굳이 즉시 해제할 필요가 없다).

따라서 게임에서는 고정 사이즈 메모리풀 추가적으로 사용

• 사이즈가 고정된다.
• 적합한 사이즈의 메모리를 탐색할 필요가 없다.
• 병합이 필요 없다.
• 단편화가 생기지 않는다.
• 다양한 사이즈의 메모리를 할당할 수는 없으므로 heap을 완전히 대체할 수는 없다.

조금 더 똑똑하게

• 최대 블록 개수만큼 모두 할당해둘 필요는 없다.
• 최대 개수는 넉넉하게. 기본 할당 개수는 적게

초기상황 Block #0에 16개 할당되어있음

기존에 비해서 앞에 헤더를 추가한다. 1byte면 충분(align감안해 조금 더 크게)

처음에 0번 할당되었다는걸 인지하기위함

Alloc 32번 호출시엔 1번에서 할당해서 반환

48번 할당시

windows 같은경우는 low fragmentation heap LFH라는 게 존재

특정사이즈 이하는 LFH로 들어가는데 얘로 작동하면 생각보다 느리지않음

성능테스트

1블록 사이즈 1024 바이트 65536 할당/해제할때 걸리는 시간 측정

1024byte는 LFH써서 일반 할당 해제도 생각보다느리지는않음 ticks = ms

가변사이즈 테스트 : 차이가 좀 더 벌어짐

LFH를 못쓰게 256kb정도로 잡아버리고 할당해제를 해버린 결과

메모리풀 성능도 많이 느려졌는데 Commit 비용

일반적인 할당/해제에는 해제에 시간이 더 많이 들어감

메모리 블록 재활용

• CRT heap 또는 API에서 제공하는 할당 방법을 사용하되 한번 할당한 메모리(리소스)는 재활용한다.
• 해제 타이밍에 즉시 해제하지 않고 사이즈별로 분류해서 재활용 리스트에 등록해 둔다.
• 할당 타이밍에 재활용 리스트를 먼저 조회해서 적합한 사이즈의 메모리가 있으면 재활용한다.
• D3D등 정해진 방법으로 리소스를 할당해야 할 경우 유용하다

여러 번 할당, 한번에 해제

• 특정 타이밍에 여러 개의 블록을 할당하고 지속적으로 사용되지는 않는 경우.
• 선형 메모리로부터 순차적으로 할당(포인터 offset만 증가)한다.
• 더 이상 어떤 메모리도 사용되지 않을 때 선형 메모리를 통째로 해제한다.
• Tree빌드 등에 유용하다

On demand 배열

• 거대한 배열이 필요할 때
  • 그러나 그 배열의 일부만 사용되고
  • 어느 영역이 사용될지 알 수 없다.
• NxNxN씩 잘라서 배열 그룹을 만든다.
• 각 배열그룹 내의 메모리는 할당하지 않는다
• Access(), Alloc()등의 함수로 요청이 들어오면 그때 할당하고 포인터를 돌려준다.
• Paging기법과 유사
• 월드 공간을 그리드로 구현할 때 유용함

거대한 2차원 공간에

8x8로 sector를 나눈다고 생각하자

우리는 이 섹터를 캐싱해서 들고있자.

0,0에 대해서 필요할때 해당 섹터에 대해서 메모리를 받아와서(할당) 사용

일반적인 tip

작업용 임시 메모리

• Stack(로컬변수)는 대체로 cache hit한다. 따라서 작업용 메모리는 stack을 사용하는 편이 성능상 유리하다. 8byte짜리 32개 배열 정도는 문제X
• 그러나 stack 메모리를 너무 크게 잡으면 cache miss할 가능성이 높고 stack메모리를 추가 commit하느라 오히려 느려진다.
• 너무 큰 stack 변수(배열포함)를 사용하면 VC++에서 경고를 해준다.
• 큰 사이즈의 working 메모리가 필요할 경우 heap에다 잡아두고 사용한다.

멀티스레드 상황

• 스레드가 사용할 working메모리는 한번에 할당해서 배정하는 것이 가장 좋다.
• 메모리풀을 만들어 사용할 경우 lock이 필요없도록 아예 별도의 메모리 풀을 만들어서 배정한다. 스레드별로 메모리풀을 따로 준다.
• 스레드마다 heap을 사용할 필요가 있을 경우 별도의 heap을 만들어서 배정한다

부지불식간에 사용중인 동적할당 제거

• STL등 자료구조에서 new/delete를 사용할 경우 빈번하게 호출되고 있지 않은지 확인할것.
• 메모리풀 만들때 다른 자료구조 갖다 쓰려고 한다면 각별히 주의할것. 그 자료구조에서 메모리 할당/해제로 CPU자원을 낭비할 수 있다.
• 함수 안에서 String 클래스등 사용 주의.
• 렌더링 프레임에 malloc/free/new/delete 호출이 없도록 한다.
• 로딩이 느리다면 I/O비용을 의심하기 전에 메모리 할당/해제 비용부터 확인할 것

자투리

메모리릭 잡을때 사용 CRT Heap Check

https://learn.microsoft.com/en-us/cpp/c-runtime-library/reference/crtsetdbgflag?view=msvc-170

이것만 써도 거의 윈도우즈는 다 잡음

자체적으로 만든 메모리풀은 자체적으로 누수 체크 만들어야함 만들 때 같이 만들기

windbg 들고 힙 덤프뜨면됨

CRT힙에서 할당할때 콜스택 저장

소스코드 라인까지 같이 저장

오버로딩된것

스냅샷이 제일 좋음

메모리 할당

• 게임 루프 안에서 할당 해제
  • 고정사이즈 메모리풀
• 초기화/종료 처리등등 게임루프 밖에서 단발성 할당
  • malloc new → HeapAlloc
• 가변길이 쓸 경우
  • gpu 메모리를 맵핑해야하는 경우
  • 병합기능이 들어갈 경우 OS Heap 보다 잘 만들 수 없음

힙 함수자체는 시스템콜이아님 유저모드임 시스템콜 할 수도있음

릭 잡는 매크로 원리

**AddressSanitizer**

https://learn.microsoft.com/ko-kr/cpp/sanitizers/asan?view=msvc-170

원리 메모리 영역 복사본을 하나 항상 더 잡는다

shadow copy 써 넣어보고 깨먹나 안깨먹나 검사

https://github.com/google/sanitizers/wiki/AddressSanitizerAlgorithm

CRT Heap체크는 런타임에 무리없음

_CrtCheckMemory() 등으로 체크가능

호출시에만 느림

프로세스가 생성될때 기본적으로 CRT Heap을 하나 만들어줌

new malloc 시 해당 힙에서 가져옴

뉴/ 메모리 사용시 앞단에 해당 코드 필요