게임 메모리 단편화를 없앤 양방향 스택 할당자
The Double Headed Stack Allocator
고성능 애플리케이션에서 메모리 할당은 성능 병목이 되기 쉽다. 저자는 Surreal Software와 Blizzard에서 게임을 개발하며 스택 할당자를 도입해 할당을 정수 덧셈으로, 해제를 단일 정수 대입으로 만들어 프로파일러에서 할당 비용을 사라지게 했다. 나아가 레벨과 캐릭터처럼 서로 다른 시스템이 각자 메모리를 할당·해제할 때 발생하는 단편화를 해결하기 위해, 한 메모리 블록의 양 끝에서 스택이 자라나는 '양방향 스택 할당자'를 소개한다. 이 기법은 멀티스레드 환경에서도 원자적 덧셈만으로 동작하며, 가변 크기 객체를 고정된 영역에 저장하는 변형도 다룬다.
할당이 더 이상 프로파일러에서 측정 가능한 시간을 차지하지 않았는데, 할당이 정수 덧셈이었고 모든 메모리 해제가 단일 정수 대입이었기 때문이다. 이보다 빠를 수는 없다.
HN 토론
33- tom_
이건 일반적인 할당자로도 잘 작동합니다. 예전에 일했던 곳에서는 일반 메모리 관리자에 allocate high 옵션이 있었는데, 이는 가장 낮은 주소 대신 가장 높은 주소를 찾아주는 것이었습니다. 일시적인 데이터를 할당하면서 영구적인 데이터를 생성해야 하는 상황에서 불필요한 단편화를 도입하지 않고 처리하기에 꽤 좋았습니다.
- Panzerschrek
> 플레이어가 세계를 돌아다니면서 오래된 레벨 지오메트리는 해제되고, 새로운 레벨 지오메트리는 할당되어 디스크에서 스트리밍되는 스트리밍 월드 게임을 상상해 보세요.
그런 경우에는 스택 같은 할당자가 최선의 전략이 아닙니다. 대신 일종의 순환 할당자를 사용할 수 있습니다. 제가 알기로 Quake는 서피스 캐시에 이 방식을 사용했습니다.
- kevin_thibedeau
양방향 버퍼는 가변 크기 객체의 시퀀스를 저장하는 데 더 적합합니다. 이는 순환 버퍼처럼 작동하며 범프 할당자 메모리 고갈에 빠지지 않습니다. 이를 위해서는 순차적 반복이 필요하지만 이런 것에는 랜덤 액세스가 거의 필요하지 않습니다.
- windenntw
그래서 AmigaOS는 메모리 할당자 호출에 MEMF_REVERSE 옵션을 허용했습니다 ( http://amigadev.elowar.com/read/ADCD_2.1/Includes_and_Autodo... )
95년이나 96년쯤에 X 크기(1KB 정도)를 초과하는 모든 할당을 MEMF_REVERSE를 사용하도록 강제하는 아주아주 간단한 OS 패치를 만든 기억이 있는데, 그게 메모리 단편화를 줄이는 데 놀라운 효과를 냈습니다 :)
- saagarjha
이런 종류의 패턴은 일종의 파이프라이닝을 다룰 때 꽤 흔합니다. GPU로 스트리밍 가중치를 다룰 때 제가 예전에 구현했던 또 다른 해결책은 해당 영역을 두 번 미러 매핑하고 첫 번째 영역에서 순서대로 포인터를 할당하되 가상 주소 지정을 사용해 앞쪽으로 랩어라운드할 수 있게 하는 것이었습니다. 할당할 "측면"이 부족해지지 않기 때문에 여러 단계를 미리 할당할 수 있어서 이 방식이 조금 더 강력하다고 느꼈습니다. 안타깝게도 양방향 할당자는 파이프라인에 실제로 한 단계만 추가로 허용합니다.