요약
메모리 한 덩어리의 양 끝에서 스택 두 개를 마주 보게 키우면 빈 공간이 조각나는 문제를 막을 수 있습니다.
블로그 demofox의 저자가 게임 개발에서 쓰는 스택 할당자(미리 잡아 둔 메모리를 앞에서부터 차례로 떼어 주는 방식)의 변형을 소개했습니다. 블리자드에서 StarCraft 2를 만들 때 상사에게 배운 방법이라고 밝혔습니다.
왜 중요한가
- 수명이 서로 다른 두 시스템이 고정된 메모리를 함께 써도 빈 공간이 흩어져 큰 할당이 실패하는 일을 막습니다.
- 두 시스템의 몫을 미리 나누지 않으므로, 메모리가 빠듯할 때 한쪽이 덜 쓰는 만큼 다른 쪽이 더 쓸 수 있습니다.
핵심 내용
- 한 메모리 블록의 앞에서 위로, 뒤에서 아래로 스택을 키우고, 두 꼭대기가 엇갈리면 메모리가 바닥난 것으로 봅니다.
- 100MB를 레벨과 캐릭터가 20MB, 30MB씩 번갈아 쓰면, 레벨을 비운 뒤 40MB가 남아도 30MB를 한 번에 잡지 못합니다.
- 레벨은 한쪽, 캐릭터는 다른 쪽에 두면 각자 꼭대기만 되돌려 다시 쓸 수 있어 빈틈이 생기지 않습니다.
- 꼭대기 값을 원자적 연산(여러 스레드가 동시에 해도 깨지지 않는 연산)으로 더하기만 하면 멀티스레드에서도 쓸 수 있다고 했습니다.
- 한쪽에 크기가 제각각인 데이터를, 다른 쪽에 그 위치 목록을 쌓아 네트워크 패킷을 채우는 변형도 소개했습니다.
HN 반응
- 여러 이용자가 Quake 3의 메모리 관리, AmigaOS의 MEMF_REVERSE 옵션, 옛 유닉스의 힙과 스택 배치도 같은 발상이라고 보탰습니다.
- 원자적 덧셈만으로 충분하다는 주장에는 남은 공간이 적을 때 양쪽 할당이 겹칠 수 있어 두 값을 묶어 비교 후 교체해야 한다는 반론이 나왔습니다.
그런 경우라면 스택형 할당기는 최선의 전략이 아닙니다. 대신 순환형 할당기 같은 것을 쓸 수 있습니다. 제가 알기로 Quake는 서피스 캐시에 이 방식을 썼습니다.
흥미롭게도 Quake 3는 글에서 설명하는 것과 같은 양면 스택 할당기를 실제로 썼습니다. 엔진이 시작할 때 "hunk"라는 큰 덩어리를 한 번 할당합니다. "low hunk"에는 수명이 긴 데이터를, "high hunk"에는 임시 데이터를 할당합니다. 구현은 이 소스 파일에서 "hunk"를 검색해 보시면 됩니다 [1].
[1] https://github.com/id-Software/Quake-III-Arena/blob/master/code/qcommon/common.c
그래서 AmigaOS는 메모리 할당기를 호출할 때 MEMF_REVERSE 옵션을 줄 수 있었던 거죠. ( http://amigadev.elowar.com/read/ADCD_2.1/Includes_and_Autodocs_2._guide/node0332.html )
95년인가 96년쯤에 X 크기(1KB 정도였나) 넘는 할당은 전부 MEMF_REVERSE를 쓰게 만드는 아주 간단한 OS 패치를 만든 기억이 나는데, 메모리 단편화가 확 줄어서 효과가 대단했어요 :)
이런 패턴은 어떤 형태든 파이프라이닝을 다룰 때 꽤 흔합니다. 예전에 GPU로 가중치를 스트리밍할 때 구현한 다른 해법도 있는데, 영역을 두 번 미러 매핑해 두고 첫 번째 영역에서 순서대로 포인터를 내어주되, 가상 주소 덕분에 끝에 닿으면 앞으로 되돌아가게 하는 방식입니다. 제 경험으로는 이쪽이 조금 더 강력했습니다. 할당받을 "면"이 바닥나지 않으니 여러 단계 앞서서 할당할 수 있거든요. 양면 할당기는 안타깝게도 파이프라인의 여유 단계를 딱 하나만 허용합니다.
이른바 "매직 링 버퍼"죠: https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buffer/
옛날 방식의 싱글 스레드 유닉스 프로세스 모델이 거의 이렇습니다. 힙은 bss 끝에서 위로 자라고, 스택은 프로세스 맨 위에서 아래로 자라죠.
객체 종류마다 스택 할당기를 따로 두면 안 되나요? 여기서는 객체 종류가 두 개라서 양두 스택 할당기를 쓸 수 있지만, 종류가 세 개라면요?
글에 나온 시스템은 "범주"를 2개까지만 다룰 수 있습니다. 한 범주 안에는 서로 다른 타입이 여러 개 있어도 됩니다. 범주에서 중요한 점은 같은 범주의 모든 객체가 할당과 해제의 타임라인을 공유해야 한다는 것입니다. 이것이 범주마다 따로 성립하면 단편화는 생기지 않습니다.
범주가 2개인 경우, 양두 스택은 절반 크기의 스택 2개를 따로 운영하는 것보다 엄밀하게 낫습니다. 후자가 허용하는 할당·해제 순서는 전부 허용하면서, 후자가 허용하지 못하는 순서도 허용하니까요. 한쪽 범주가 일시적으로 메모리의 절반 넘게 필요하고 다른 범주는 그 순간 쓰지 않는 순서가 바로 그런 경우입니다.
저는 증분 GC가 사실 그렇게 나쁘지 않다고 봅니다. 객체의 수명은 처음 보기보다 훨씬 헷갈리게 마련입니다. 게임 디자인 결정 하나로 수명이 제멋대로 바뀌기도 쉽고요. 한 프레임만 살 거라는 걸 알아도, 그 최적화 기회를 놓친다고 왕국을 통째로 내주는 것은 아닙니다.
게임 개발에는 신경 쓸 문제가 그 말고도 많습니다. 수동 메모리 관리는 대체로 큰 스튜디오만 누릴 수 있는 사치입니다. 혼자 개발하는 사람이 원칙대로 이런 기술 싸움을 벌이면 정작 활주로까지 가지도 못할 겁니다. 이런 맞춤형 방식이 쓸 만하다고 증명하려면 대개 표본이 많이 필요합니다(돈 내는 고객이나 큰 QA 팀). 좋든 싫든, 낡고 심술궂은 GC가 위험이 가장 낮은 선택일 수 있습니다. 프레임이 몇 번 늦는 것은 게임이 죽는 것보다 게이머에게 훨씬 덜 거슬리니까요.
아마 맞는 말씀이고, 실제로는 별문제 없을 겁니다.
다만 기본적인 GC 방식을 들여다보면 할당된 살아 있는 객체를 전부 옮기거나, 마크 앤 스윕을 돌리게 되는데 그러면 할당 영역에 구멍이 생겨서 단편화 문제가 따라옵니다.
알맞은 종류의 GC를 고르고 제약 조건을 잘 알면 이런 문제를 피해 갈 수도 있겠지만, 글에서 설명한 단순한 양두 범프 할당기에는 그런 뚜렷한 해법이 없어 보입니다. 단, 수명 주기가 시간이 지나도 바뀌지 않는다는 전제에서요. 수명이 바뀌면 아레나 방식의 단순함이 깨지니까요.
요즘 GC에서는 끊김이 훨씬 덜 문제가 됩니다.
GC의 진짜 단점은 최대 메모리 사용량을 예측할 수 없다는 점입니다.
객체를 옮기는 할당을 감당할 수 없는 경우가 많습니다.
단일 스택 할당기는 다른 말로 하면 아레나 같은데, 양두 버전은 꽤 멋지네요.
마지막에 설명한 패턴이 멀티 스레드에서 정말 안전한가요? 예를 들어 스택에 딱 1바이트가 남았는데, T1이 동적 쪽 끝에서 1바이트를 할당하고(동적 객체가 우연히 1바이트라고 합시다), T2가 고정 크기 쪽 끝에서 1바이트를 할당하면 둘이 겹치지 않나요?
양쪽 끝을 서로 넘어서도록 증가·감소시켜도, 그걸 감지해서 적어도 한쪽 할당을 실패시키기만 하면 괜찮다고 생각합니다.
서로 다른 두 위치에서 동기화하는 셈이라 메모리 순서가 조금 까다롭습니다. 가장 단순한 방법은 모든 원자적 접근을 seqcst로 하는 것인데, 이 경우에는 겹침을 확인하기 전에 fence(seqcst) 한 번이면 충분하고 동기화 명령도 더 적게 쓸 것 같습니다.
오버플로 검사도 까다롭습니다. 할당이 실패했다면 이후 할당도(다른 스레드에서도) 실패하도록 해야 합니다. 오버플로 때문에 다시 증가해서 유효한 범위로 돌아오면 성공한 줄 알 수 있거든요. 그래서 스레드 안전한 범프 할당기에서는 대개 fetch_add를 쓸 수 없고, 쓰기 전에 오버플로를 감지하는 CAS 루프를 써야 합니다.
어차피 CAS 루프를 돌리고 항상 두 변수에 모두 접근하니, 특히 보통 양쪽에서 동시에 할당한다면 두 변수를 하나로 합치는 편이 더 빠를 수도 있습니다. 예를 들어 오프셋 두 개를 64비트 CAS 워드 하나에 채워 넣으면 여전히 4GB를 가리킬 수 있고, 할당을 정렬하면 더 늘릴 수 있습니다. seqcst를 걱정할 필요도 없고요.
글의 전체 인용문은 이렇습니다.
안타깝게도 그게 어떻게 가능한지는 설명하지 않습니다...
tos 변수 두 개를 하나의 원자 변수에 합쳐 담고 그 합친 값을 compare and swap 하면 가능할 겁니다.
할당기에 동기화가 필요하긴 하지만 보통 비용이 꽤 낮습니다(이런 할당은 대개 한 스레드에서 이뤄지고, 할당된 메모리를 여러 소비자에게 나눠 주어 병렬로 작업하게 하는 경우가 많거든요).
일반 할당기에서도 잘 통합니다. 예전 직장에서는 일반 메모리 관리자에 "높은 주소에 할당" 옵션을 두었는데, 가장 낮은 주소 대신 가능한 가장 높은 주소를 찾아 주는 방식이었습니다. 영구 데이터를 만드는 동안 임시 데이터를 할당해야 하는 상황에서, 불필요한 단편화를 피하는 데 꽤 좋았습니다.
이건 별로 설득력이 없습니다.
x <= X, y <= Y를 푸는 것이x + y <= Z를 푸는 것보다 훨씬 쉽습니다. 메모리에 올라가는 레벨 데이터(Cell 기반 시스템 등)와 에셋 파이프라인의 캐릭터 데이터 양쪽에 각각 한도를 두는 편이, 온갖 레벨 크기와 캐릭터 크기 조합이 서로 맞고 서로의 영역을 침범하지 않도록 보장하는 것보다 훨씬 낫습니다.요점은 x <= X, y <= Y이지만 x' + y' <= Z이고, 이때 x'와 y'는 (각각) x나 y보다 클 수 있다는 겁니다.
그렇죠. 하지만 x'와 y'가 어떤 값이든 x' + y' > Z가 되지 않는다는 건 어떻게 증명하나요? 실제로는
x < X, y < Y를 증명하는 쪽이 항상 더 쉽습니다.보통은 이것들 모두 (대체로) 증명하기 쉽다고 봅니다. 다만 다른 방식은 x'와 y'가 서로 독립적일 수 있게 해 줍니다.
잘게 나뉜 청크를 연결한 동적 스택은 어떤가요? 메모리를 더 적게 씁니다.
연속적이지 않잖아요.
당연히 청크 크기는 할당할 객체의 부류보다 크다고 가정한 거죠.
항상 가능한 건 아닙니다.
그런 경우라면 고정 스택도 불가능한 거죠.
그럴 리가요? 스택은 연속적인데요.
가변 크기 객체의 시퀀스를 저장하는 데는 바이파타이트 버퍼가 더 낫습니다. 원형 버퍼처럼 동작해서 범프 할당기처럼 메모리가 바닥나 막히는 일이 없습니다. 순차 순회가 필요하지만, 이런 용도에서 임의 접근이 필요한 경우는 드뭅니다.
하나 짚자면, 힙 위의 스택 구조나 여러 스택은 어떤 search-mark-sweep보다 훨씬 빠른 가비지 컬렉션입니다.
스택에서는 빠른 "해제" 때 메모리를 (보통) 0으로 지우거나 비우지 않는다는 점도 말해 둘 만합니다. 그만큼 내부 구조에 가까운 이야기죠...