TL;DR

  • 프레임마다 수명이 짧은 메모리를 다루는 게임 등의 고성능 애플리케이션에서 스택 할당자(bump allocator)는 할당을 정수 덧셈으로, 전체 해제를 정수 대입으로 처리해 할당 오버헤드를 줄이는 방식임.
  • 더블 헤드 스택 할당자는 하나의 메모리 블록에서 두 개의 스택이 반대 방향으로 자라게 해, 서로 다른 수명 주기를 가진 데이터의 할당이 뒤섞여도 메모리 단편화를 방지함.
  • 각 스택의 위치를 초기화하면 해당 데이터 영역을 다시 사용할 수 있으며, 두 위치가 교차하면 메모리가 부족한 상태임.
  • 원자적 덧셈으로 여러 스레드가 같은 할당자를 사용할 수 있고, 재귀 처리에서는 스택 위치를 저장했다가 되돌려 부분 해제도 가능함.
  • 반대쪽 스택을 오프셋 테이블에 사용하면 고정 메모리 영역에 크기가 다른 객체를 저장하면서 인덱스 기반 임의 접근과 객체 제거·이동을 지원함.

스택 할당자

  • 2010년경 Surreal Software(Midway Seattle)에서 오픈 월드 게임 “This is Vegas”를 개발했으며, Midway의 폐업으로 게임은 취소됨.
  • 애니메이션 프로그래밍 업무에서는 뼈대 집합마다 상태 머신을 두고, 각 상태를 애니메이션 블렌드 트리로 표현함. 상태가 바뀌면 연속성을 유지하도록 이전 상태에서 새 상태로 블렌딩함.
  • CPU에서 애니메이션을 평가하고 블렌딩하는 과정에 동적 메모리 할당이 많이 발생했지만, 할당된 메모리는 프레임의 일부 시간 동안만 필요했음. 프레임마다 애니메이션 대상 캐릭터가 카메라 절두체 등에 따라 크게 달라질 수 있어 할당도 매 프레임 발생했고, 프로파일링에서 할당자가 병목으로 나타남.
  • 이 문제를 해결하기 위해 할당은 정수 덧셈으로, 해제는 그보다 더 저렴하게 처리하는 스택 할당자를 구현함.
  • 필요한 최대 크기만큼 메모리 블록을 확보함. 예를 들어 1MB를 스택으로 사용하고, 스택의 최상단 위치를 나타내는 정수 변수 tos를 유지함.
  • 메모리를 할당할 때는 현재 tos 위치의 주소를 반환하고, 요청한 바이트 수만큼 tos를 증가시켜 다음 할당이 이어지는 위치에서 시작하게 함.
  • 실제 구현에서는 tos가 메모리 끝에 도달하는 경우를 처리할 수 있도록 메모리 크기도 알아야 함. 이때 널을 반환하거나 단언문을 발생시키는 등의 방식을 사용할 수 있음.
  • 메모리 사용이 끝나면 tos를 0으로 설정해 전체 영역을 해제함. 애니메이션 블렌딩 사례에서는 블렌딩이 끝나고 결과를 스키닝용 버텍스 셰이더로 전달할 버퍼에 복사한 뒤 tos를 초기화함. 게임 프레임의 모든 임시 할당에 이 할당자를 사용한다면 프레임 시작 시 초기화할 수 있음.
  • 프로파일러에서 할당 시간이 측정되지 않을 정도로 빨라짐. 할당은 정수 덧셈이고 전체 메모리 해제는 정수 변수 한 번의 대입임.
  • 이 할당자는 소멸자를 호출하지 않음. 생성자는 플레이스먼트 뉴(placement new)로 호출하기 쉽지만, 소멸자 호출은 수동 처리해야 해 오류가 발생하기 쉬움. RAII 패턴을 적용할 수도 있지만, 스택 할당자는 단순한 타입에 가장 적합함.
  • tos 변수를 원자적 덧셈으로 갱신하면 여러 스레드가 같은 스택 할당자에서 메모리를 할당할 수 있음. CPU의 포크/조인 작업이나 GPU의 복잡한 알고리즘에 유용할 수 있음.
  • 부분 해제도 가능함. 재귀 처리의 각 단계가 동적 할당을 한다면, 단계 시작 시 tos를 기억해 두었다가 처리가 끝난 뒤 해당 값으로 되돌릴 수 있음.

더블 헤드 스택 할당자

  • 몇 년 뒤 Blizzard의 StarCraft 2 팀에서 일할 때 상사인 James Anhalt에게 과거 메모리 단편화 문제를 해결하는 방법으로 더블 헤드 스택 할당자를 소개받음.
  • 플레이어가 월드를 이동할 때 이전 구역의 지오메트리가 해제되고 새 구역의 지오메트리가 디스크에서 스트리밍되는 게임을 가정함. 동시에 플레이어 캐릭터가 형태를 바꿀 수 있고, 형태가 바뀔 때마다 이전 형태의 메모리를 해제하고 새 형태를 디스크에서 스트리밍한다고 가정함.
  • 두 시스템이 서로 다른 시간표에 따라 무작위 크기의 메모리를 할당하고 해제하면 메모리가 단편화될 수 있음.
  • 전체 100MB 중 레벨 데이터에 20MB, 캐릭터에 30MB를 차례로 할당하고, 다시 레벨 데이터에 20MB와 캐릭터에 30MB를 할당하는 상황을 가정함. 레벨 데이터가 해제된 뒤 새 레벨 데이터에 30MB가 필요해도, 남은 40MB가 20MB 블록 두 개로 나뉘어 있으면 연속된 30MB 공간을 확보할 수 없음.
  • 해결 방식은 하나의 메모리 블록 안에 두 개의 스택 할당자를 두는 것임. 레벨 데이터의 tos는 0에서 시작해 위쪽으로 증가하고, 캐릭터 데이터의 tos는 메모리 끝에서 시작해 아래쪽으로 감소함. 두 위치가 교차해 레벨의 tos가 캐릭터의 tos보다 커지면 메모리가 부족한 상태임.
  • 레벨 데이터가 바뀌면 레벨의 tos를 0으로 되돌려 필요한 메모리를 다시 할당할 수 있음. 캐릭터 데이터가 해제될 때는 캐릭터의 tos를 메모리 끝으로 되돌려 다시 할당할 수 있음. 이 방식은 메모리 단편화를 일으키지 않음.
  • 각 스레드가 어느 쪽 스택에서든 할당할 수 있는 다중 스레드 환경에서도 동작함. tos 인덱스에 원자적 덧셈을 적용하면 됨.
  • 스택 할당자 두 개 대신 더블 헤드 스택을 쓰는 주요 이점은 메모리가 제한된 상황에서 한쪽 스택에 필요한 크기만큼의 메모리로 두 시스템을 지원하면서, 양쪽에 배분되는 메모리 비율을 유연하게 조정할 수 있다는 점임. 게임 사례에서는 일부 레벨이 더 많은 메모리를 쓸 수 있지만, 그 경우 캐릭터의 메모리 사용량을 줄여야 함.

고정 영역에 크기가 다른 객체 저장

  • 고정된 메모리 크기 안에 가변 크기 객체 여러 개를 저장하면서 인덱스로 임의 접근해야 하는 경우에도 변형된 더블 헤드 스택 할당자를 사용할 수 있음. 예를 들어 효율성을 위해 특정 크기의 네트워크 패킷을 보내면서, 그 안에 크기가 다른 네트워크 명령을 여러 개 인코딩하고 메시지를 쉽게 순회하려는 경우임.
  • 한쪽 스택은 동적 할당에 사용하고, 다른 쪽 스택은 동적 할당 영역의 오프셋을 담는 정수 배열에 사용함.
  • 빈 더블 헤드 스택에서 시작해 24바이트 객체를 할당하면 스택 0의 tos가 0이므로 해당 위치에 객체를 쓰고 tos를 24로 증가시킴. 스택 1에서는 정수 하나를 할당해 첫 번째 객체의 위치인 0을 오프셋으로 기록함.
  • 다음 객체를 14바이트 할당한다고 설명한 뒤, 예시에서는 스택 0의 tos가 24인 위치에 12바이트 객체를 쓰고 tos를 38로 증가시킴. 스택 1에는 두 번째 객체의 위치인 24를 기록함.
  • 객체 수를 추적하는 방법도 필요함. 오프셋 테이블 항목 수를 별도 정수로 관리하거나, 오프셋 테이블의 끝을 나타내는 센티널 값을 둘 수 있음. 센티널 값으로 이진수에서 모두 1인 ~0을 사용할 수 있음.
  • 다른 스택 할당자와 마찬가지로 다중 스레드 환경에서 사용할 수 있음. 두 업데이트를 비교 후 교환(CAS) 루프 등으로 트랜잭션처럼 묶을 필요는 없음.
  • 항목을 제거하거나 메모리에서 이동할 수도 있음. 이때 오프셋 테이블을 실제 위치에 맞게 갱신하면 단편화를 줄이는 방법이 됨.

링크