고성능 애플리케이션, 특히 비디오 게임을 만들다 보면 제한된 자원을 최대한 활용하기 위한 저수준 기법을 자연스럽게 익히게 된다. 그중에서도 메모리 할당은 프레임마다 가변적인 양의 메모리를 다뤄야 하는 코드에서 늘 성능의 발목을 잡는 주제다. 일반적인 malloc/new 계열의 범용 할당자는 유연한 대신 비용이 크고, 프로파일링을 돌려 보면 특정 구간에서 핫스팟으로 떠오르는 경우가 흔하다. 이 글이 소개하는 스택 할당자(stack allocator), 흔히 범프 할당자(bump allocator)라고도 불리는 기법은 바로 그 지점을 겨냥한다. 참고로 여기서 말하는 스택 할당자는 프로그램 스택에서 직접 메모리를 떼어 쓰는 alloca와는 다른 개념이다.
정수 덧셈으로 끝나는 할당
기본 아이디어는 단순하다. 미리 필요한 최대치만큼, 예컨대 1MB의 메모리를 통째로 확보해 두고 이를 하나의 스택으로 삼는다. 그리고 스택의 꼭대기를 가리키는 정수 변수 하나(tos, top of stack)를 유지한다. 메모리를 요청하면 현재 tos가 가리키는 위치를 돌려주고, 요청한 바이트 수만큼 tos를 더해 다음 할당이 그 뒤에서 시작되도록 한다. 즉 할당은 정수 덧셈 한 번이다. 실제 구현에서는 전체 크기를 함께 들고 있다가 tos가 끝에 닿으면 널을 반환하거나 단언(assert)으로 처리하는 식의 경계 검사를 넣게 된다. 사용이 끝나면 tos를 0으로 되돌리는 것만으로 전체 메모리가 한꺼번에 해제된다.
글쓴이는 2010년경 Midway 시애틀의 Surreal Software에서 오픈월드 게임 'This is Vegas'(Midway 폐업과 함께 취소됨)의 애니메이션 프로그래밍을 맡으며 이 기법을 실제로 적용했다. 당시 애니메이션은 뼈대 집합별 상태 기계로 동작했고, 각 상태는 애니메이션 블렌드의 트리였으며 상태가 바뀔 때마다 이전 상태에서 새 상태로 블렌딩하며 연속성을 유지했다. 이 블렌딩 과정은 CPU에서 매 프레임 대량의 동적 할당을 일으켰는데, 카메라 절두체 등에 따라 어떤 캐릭터가 애니메이션되는지가 프레임마다 크게 달라졌기 때문에 이 할당들은 반드시 프레임 단위로, 그리고 프레임의 일부 구간만 존재하면 되는 일시적인 성격이었다. 스택 할당자를 적용하자 결과는 극적이었다. 블렌딩 결과를 스키닝용 정점 셰이더 버퍼로 복사한 뒤 tos를 0으로 되돌리기만 하면 됐고, 할당은 프로파일러에서 측정 가능한 시간을 더는 차지하지 않았다.
다만 분명한 한계가 있다. 이 할당자는 소멸자를 호출하지 않는다. 생성자는 placement new로 어렵지 않게 처리할 수 있지만 소멸자 호출은 수작업이어야 하고 그만큼 오류가 생기기 쉽다. RAII 패턴을 얹어 볼 수는 있으나, 스택 할당자는 소멸 처리가 단순한 타입을 다룰 때 가장 잘 맞는다는 점을 전제로 써야 한다. 한편 tos를 원자적(atomic) 덧셈으로 갱신하면 여러 스레드가 같은 할당자를 공유할 수 있어 포크/조인 방식이나 GPU의 복잡한 알고리즘에도 쓸 수 있고, 재귀 처리에서 각 단계 진입 시점의 tos를 기억했다가 되돌리는 '부분 해제'도 가능하다.
두 방향에서 자라는 스택
몇 년 뒤 글쓴이는 Blizzard의 StarCraft 2 팀에서 상사 James Anhalt로부터 더블 헤드 스택 할당자를 배웠다. 이는 메모리 단편화를 푸는 해법이다. 스트리밍 방식의 오픈월드를 상상해 보자. 플레이어가 이동하면 옛 레벨 지오메트리가 해제되고 새 지오메트리가 디스크에서 스트리밍되어 할당된다. 동시에 플레이어 캐릭터가 변신할 때마다 이전 형태가 해제되고 새 형태가 할당된다. 이렇게 서로 다른 두 시스템이 각자의 타임라인에서 제각각 크기의 메모리를 할당·해제하면 메모리는 조각난다. 예를 들어 총 100MB에서 레벨과 캐릭터가 번갈아 20/30/20/30MB를 할당한 뒤 옛 레벨 메모리를 비우면 40MB가 비긴 하지만 20MB짜리 두 덩어리로 흩어져 있어, 더 작은 30MB 단일 할당조차 받아들일 수 없게 된다.
해법은 하나의 메모리 블록을 쓰되 레벨 데이터의 tos는 0에서 위로 자라게 하고, 캐릭터 데이터의 tos는 메모리 끝에서 아래로 자라게 하는 것이다. 두 tos가 서로를 지나쳐 레벨 tos가 캐릭터 tos보다 커지는 순간이 메모리 소진 시점이다. 이렇게 하면 레벨이 바뀔 때 레벨 tos만 0으로 되돌려 재할당할 수 있고, 캐릭터도 자기 tos를 끝으로 되돌려 재할당할 수 있어 단편화가 전혀 생기지 않는다. '그냥 스택 할당자를 두 개 두면 안 되느냐'는 물음에 대한 답은 명확하다. 두 시스템에 쓸 전체 크기는 충분하다는 걸 알지만 어느 쪽에 얼마씩 돌아갈지는 유동적일 때, 하나의 블록을 공유하면 어떤 레벨은 메모리를 더 쓰고 대신 그 상황에서 캐릭터가 덜 쓰는 식의 탄력적 배분이 가능해진다.
오프셋 테이블로 임의 접근까지
이 구조의 변형은 가변 크기 객체 여러 개를 고정된 메모리에 담으면서도 인덱스로 임의 접근하고 싶을 때 쓸모가 있다. 효율을 위해 특정 크기의 네트워크 패킷 안에 가변 개수의 가변 크기 명령을 인코딩하되 메시지를 쉽게 순회하려는 경우가 대표적이다. 한쪽 스택은 동적 할당 자체에, 다른 쪽 스택은 각 할당의 메모리 내 오프셋을 담은 정수 배열에 쓰면 된다. 객체 개수는 별도 카운터로 세거나 오프셋 테이블에 센티넬 값(예: 모든 비트가 1인 ~0)을 두어 끝을 표시할 수 있다. 이 방식은 항목을 제거하거나 메모리 안에서 이동시킬 때 오프셋 테이블만 현실에 맞게 갱신하면 되므로, 그 자체로 단편화를 줄이는 또 다른 수단이 된다. 이 역시 다중 스레드에서 동작하며, 두 갱신을 CAS 루프 같은 트랜잭션으로 묶고 싶은 유혹이 들지만 실제로는 필요하지 않다.
실무에 옮길 때 새겨둘 만한 현장 의견도 있다. 원 글의 댓글에서 한 엔진 개발자는 성능 임계 경로 여러 곳에서 비슷한 접근을 쓰고 있다면서도, 원자적 카운터에 여러 스레드가 몰리면 캐시 일관성 트래싱 때문에 오히려 느려질 수 있다고 지적했다. 간단한 개선책은 스레드마다 할당자를 하나씩 두어 카운터가 항상 가장 가까운 캐시에 머물게 하는 것이다. 이후 데이터를 병합하거나, 각 스레드 스택을 훑는 커스텀 반복자를 쓰면 된다. 물론 할당 빈도와 양에 따라 득실은 달라진다. 결국 스택 할당자 계열의 매력은 비용 구조가 극단적으로 단순하다는 데 있지만, 소멸자 처리와 멀티스레드 경합이라는 두 제약을 이해하고 자신의 워크로드에 맞춰 설계해야 그 단순함이 성능으로 돌아온다.