UE5 TSparseArray

1. TSparseArray

TSparseArray는 언리얼 엔진의 독특하고 강력한 컨테이너로, TArray와 유사하게 순서가 있는 원소들의 목록을 관리하지만, 원소의 메모리 주소 안정성(Pointer Stability)과 효율적인 삭제 및 추가라는 차이점을 가집니다.

TArray에서는 중간에 있는 원소를 삭제하면 그 뒤의 모든 원소들이 메모리상에서 앞으로 이동(shift)하여 빈 공간을 채웁니다. 이로 인해 삭제된 원소보다 뒤에 있던 원소들의 주소와 인덱스가 모두 변경됩니다. TSparseArray는 이러한 문제를 해결하기 위해 설계되었습니다.

• 포인터/인덱스 안정성: 한번 추가된 원소는 다른 원소가 추가되거나 삭제되어도 그 메모리 주소나 배열 내 인덱스가 절대 변하지 않습니다. 이는 해당 원소에 대한 포인터나 인덱스를 외부에서 안전하게 저장하고 참조할 수 있게 해줍니다.
• 효율적인 삭제: 원소를 삭제할 때 데이터를 실제로 제거하고 메모리를 이동시키는 대신, 해당 슬롯(slot)을 '비어있음(empty)' 또는 '자유(free)' 상태로 표시만 합니다. 이 연산은 O(1)의 시간 복잡도를 가집니다.
• 메모리 재사용: 삭제되어 비어있는 슬롯은 나중에 새로운 원소가 추가될 때 재사용됩니다. 이를 통해 잦은 메모리 할당 및 해제 오버헤드를 줄입니다.
• Hole (구멍): 삭제된 슬롯으로 인해 배열 중간중간에 데이터가 없는 '구멍'이 생길 수 있습니다. 이 때문에 'Sparse(희소한)'라는 이름이 붙었습니다.
• 순회 시 주의: 구멍이 존재하므로, 일반적인 for 루프(e.g., for (int32 i = 0; i < Array.Num(); ++i))로 순회하면 유효하지 않은 데이터에 접근할 수 있습니다. 반드시 범위 기반 for 루프나 전용 반복자(TIterator)를 사용해야 합니다.

2. 내부 구조 및 구현 방식

TSparseArray의 핵심은 실제 데이터를 저장하는 TArray와 각 데이터 슬롯의 유효 여부를 추적하는 비트 배열(TBitArray)의 조합입니다.

TSparseArray의 주요 내부 멤버는 다음과 같습니다.

1. Data (TArray<ElementType, Allocator>): 원소들을 저장하는 기본 배열입니다. ElementType은 TSparseArray에 저장될 실제 데이터 타입이거나, FElementOrFreeListLink라는 특수한 공용체(union)일 수 있습니다.
2. AllocationFlags (TBitArray<Allocator>): Data 배열의 각 인덱스(슬롯)가 현재 유효한 데이터를 담고 있는지, 아니면 비어있는지를 나타내는 비트 배열입니다. true이면 해당 슬롯에 유효한 데이터가 있고, false이면 비어있다는 의미입니다.
3. FirstFreeIndex (int32): 비어있는 슬롯들로 구성된 단일 연결 리스트(singly linked list)의 헤드(head) 역할을 합니다. 다음에 새로운 원소가 추가될 때 재사용할 첫 번째 비어있는 슬롯의 인덱스를 가리킵니다. 만약 비어있는 슬롯이 없다면 -1 (INDEX_NONE) 값을 가집니다.
4. NumFreeIndices (int32): 현재 비어있는 슬롯의 총 개수를 저장합니다.

FElementOrFreeListLink 공용체(Union)

TSparseArray는 메모리를 효율적으로 사용하기 위해 재미있는 기법을 사용합니다. Data 배열의 슬롯이 유효한 원소를 담고 있을 때는 해당 원소의 데이터를 저장하지만, 슬롯이 비어있을 때는 그 공간을 '다음에 비어있는 슬롯'의 인덱스를 저장하는 용도로 재활용합니다. 이를 위해 FElementOrFreeListLink라는 공용체를 사용합니다.

union FElementOrFreeListLink
{
    ElementType ElementData; // 슬롯이 사용 중일 때
    int32 NextFreeIndex;     // 슬롯이 비어있을 때
};

• AllocationFlags의 특정 인덱스 비트가 true이면, Data 배열의 해당 인덱스는 ElementData로 해석됩니다.
• 비트가 false이면, 해당 인덱스는 NextFreeIndex로 해석되어 자유 리스트(free list)의 일부가 됩니다.

동작 과정

원소 추가 (Add)

1. 자유 슬롯 확인: FirstFreeIndex가 INDEX_NONE이 아닌지 확인하여 재사용할 수 있는 비어있는 슬롯이 있는지 검사합니다.
2. 슬롯 할당:
   • 재사용: 비어있는 슬롯이 있다면(FirstFreeIndex != INDEX_NONE), 해당 인덱스를 사용합니다. 그리고 FirstFreeIndex를 방금 사용한 슬롯의 NextFreeIndex 값으로 업데이트하여 자유 리스트의 다음 노드를 가리키게 합니다.
   • 신규 할당: 비어있는 슬롯이 없다면, Data 배열의 맨 뒤에 새로운 슬롯을 추가합니다 (Data.AddUninitialized(1)).
3. 데이터 저장: 할당된 슬롯에 새로운 원소의 데이터를 생성자 호출을 통해 저장합니다.
4. 플래그 설정: AllocationFlags에서 해당 슬롯의 비트를 true로 설정하여 이제 유효한 데이터가 있음을 표시합니다.

원소 삭제 (RemoveAt)

1. 유효성 검사: 삭제하려는 인덱스가 유효하고, AllocationFlags를 통해 해당 슬롯이 현재 사용 중인지 확인합니다.
2. 소멸자 호출: 해당 슬롯에 저장된 원소의 소멸자를 명시적으로 호출하여 리소스를 정리합니다.
3. 플래그 해제: AllocationFlags에서 해당 슬롯의 비트를 false로 설정하여 비어있음을 표시합니다.
4. 자유 리스트에 추가: 삭제된 슬롯을 자유 리스트의 맨 앞에 추가합니다. 즉, 해당 슬롯의 NextFreeIndex에 기존의 FirstFreeIndex 값을 저장하고, FirstFreeIndex를 방금 삭제된 슬롯의 인덱스로 업데이트합니다.

이러한 메커니즘 덕분에 원소를 삭제해도 다른 원소들의 위치는 전혀 영향을 받지 않습니다.

3. 계층 구조

TSparseArray의 동작 계층은 다음과 같습니다.

1. 사용자 영역 (User-Level Code):
   • 개발자가 TSparseArray<FMyStruct> MyArray;와 같이 선언하고 Add, RemoveAt, 범위 기반 for 루프 등을 사용합니다.
   • 원소의 포인터나 FScriptArray::FElementOrFreeListLink(내부 인덱스)를 다른 시스템에서 안정적으로 참조합니다.
2. 언리얼 API 계층 (Unreal API Layer):
   • TSparseArray 클래스에 정의된 public 메서드들입니다. Add는 내부적으로 자유 리스트를 확인하고, RemoveAt은 비트마스크와 자유 리스트를 조작하는 로직을 호출합니다.
   • begin(), end()와 같은 반복자 관련 함수들은 AllocationFlags를 확인하여 유효한 원소들만 순회하는 TIterator를 생성합니다.
3. 컨테이너 구현 계층 (Container Implementation Layer):
   • TSparseArray의 핵심 로직입니다.
   • TBitArray(AllocationFlags)를 사용하여 할당 상태를 관리합니다.
   • FirstFreeIndex와 FElementOrFreeListLink 공용체를 통해 자유 리스트를 관리하고 메모리를 재사용합니다.
   • 실제 데이터 저장을 위해 내부적으로 TArray를 사용합니다.
4. 메모리 할당 계층 (Memory Allocation Layer):
   • 내부 TArray와 TBitArray가 필요로 하는 메모리를 언리얼의 FMemory 시스템을 통해 할당받습니다. TSparseArray 자체가 직접 메모리를 할당하기보다는, 내부 컨테이너들이 이 계층과 상호작용합니다.

4. TSparseArray와 다른 컨테이너와의 비교

특징	TSparseArray	TArray	TSet
주요 목적	포인터 안정성을 보장하는 동적 배열	순서가 있는 일반적인 동적 배열	고유 원소의 빠른 검색 및 관리
포인터/인덱스 안정성	안정 (Stable)	불안정 (Unstable)	불안정 (Unstable)
원소 삭제 성능	O(1)	O(N) (중간 원소 삭제 시)	평균 O(1)
메모리 연속성	논리적으로 연속, 물리적으로는 '구멍' 존재	물리적으로 연속 (Cache-friendly)	불연속 (해시 테이블 구조)
순회 방식	반복자 또는 범위 기반 for 사용 필수	인덱스 기반 for 루프 가능	반복자 또는 범위 기반 for 사용
메모리 사용량	TArray + TBitArray 오버헤드	가장 적음	TArray + 해시 테이블 오버헤드
주요 사용 사례	- 원소의 주소를 외부에서 참조해야 할 때 - 잦은 추가/삭제가 발생하는 시스템 - UObject 관리 시스템의 내부 구현	- 순서가 중요하고 데이터가 연속적이어야 할 때 - 일반적인 대부분의 배열 요구사항	- 원소의 존재 여부를 빠르게 확인해야 할 때 - 중복을 허용하지 않는 목록 관리

TSparseArray의 장단점

장점:

• 포인터 및 인덱스 안정성: 컨테이너가 변경되어도 원소를 가리키는 포인터나 인덱스가 유효하게 유지된다는 점이 가장 큰 장점입니다.
• 빠른 원소 삭제: 원소 삭제 시 메모리 이동이 없으므로 O(1)로 매우 빠릅니다. 잦은 삭제가 발생하는 시나리오에 이상적입니다.
• 메모리 재사용: 삭제된 슬롯을 재사용하여 동적 메모리 할당/해제 횟수를 줄여줍니다.

단점:

• 메모리 비효율성: 삭제된 원소들이 '구멍'으로 남아 메모리 공간을 계속 차지하므로, 메모리 사용량이 TArray보다 클 수 있습니다. Shrink()를 호출하여 이 공간을 회수할 수 있지만, 이 경우 포인터 안정성이 깨집니다.
• 순회 비용: 유효한 원소만 건너뛰며 순회해야 하므로, 모든 원소가 꽉 차있는 TArray를 순회하는 것보다 약간의 오버헤드가 있습니다. (캐시 지역성 저하)
• 복잡성: 내부 구조가 TArray보다 복잡하고, 순회 시 주의가 필요합니다.

5. 언제 어디에 사용하는가?

TSparseArray는 안정적인 참조가 필요할 때 가장 빛을 발합니다.

• 엔진 내부 시스템: 언리얼 엔진의 UObject 관리 시스템은 TSparseArray와 유사한 구조를 사용하여 수많은 UObject들을 관리합니다. 각 UObject는 고유 ID(인덱스)를 가지며, 다른 객체가 생성되거나 소멸되어도 이 ID는 변하지 않아 안정적인 참조가 가능합니다.
• 게임플레이 시스템에서의 객체 풀(Object Pool): 총알, 이펙트 등 자주 생성되고 파괴되는 객체들을 미리 TSparseArray에 할당해두고, 필요할 때마다 활성화/비활성화 상태만 변경하여 사용할 수 있습니다. 객체의 포인터를 다른 곳에서 참조하고 있어도 안전합니다.
• ID 기반 시스템: 각 원소에 고유하고 불변하는 ID(배열의 인덱스)를 부여하고 싶을 때 유용합니다. 예를 들어, 게임 세션 동안 존재하는 모든 캐릭터에 고유 ID를 부여하고, 이 ID를 통해 캐릭터를 참조하는 시스템을 만들 수 있습니다.

    // 예시: 간단한 엔티티 관리 시스템
    TSparseArray<FCharacterInfo> AllCharacters;

    // 새로운 캐릭터 추가, 인덱스가 고유 ID가 됨
    int32 CharacterID = AllCharacters.Add(FCharacterInfo());

    // 나중에 ID를 사용해 캐릭터 정보에 직접 접근
    if (AllCharacters.IsAllocated(CharacterID))
    {
        FCharacterInfo& Info = AllCharacters[CharacterID];
        Info.Health -= 10;
    }

6. 요약

TSparseArray는 언리얼 엔진의 특별한 배열 컨테이너입니다. 일반적인 TArray와 가장 큰 차이점은, 한번 추가된 데이터의 메모리 주소나 인덱스가 절대 바뀌지 않는다는 것입니다. TArray는 중간에 있는 데이터를 지우면 뒤에 있는 데이터들이 앞으로 당겨지면서 주소와 인덱스가 다 바뀌지만, TSparseArray는 그렇지 않습니다.

 

TSparseArray는 데이터를 삭제할 때 실제로 메모리에서 지우는 게 아니라, 그 위치에 '여기는 비어있다'는 깃발(flag)만 꽂아둡니다. 내부적으로는 어떤 칸이 사용 중이고 어떤 칸이 비어있는지를 비트 배열로 전부 기록하고 있습니다. 그리고 나중에 새로운 데이터를 추가할 때, 이 비어있는 칸을 찾아서 재사용합니다. 이렇게 데이터를 이동시키지 않고 '비어있음' 표시만 하기 때문에, 다른 데이터들의 위치는 전혀 영향을 받지 않고 그대로 유지될 수 있습니다.

 

 가장 중요한 사용처는 배열에 들어있는 데이터의 주소를 다른 곳에서 오랫동안 저장하고 사용해야 할 때입니다. 예를 들어, 어떤 캐릭터 객체를 배열에 넣어두고, 다른 여러 시스템에서 그 캐릭터 객체의 포인터를 직접 참조하고 있다고 상상해보세요. 만약 TArray를 썼다면, 다른 캐릭터가 죽어서 배열에서 제거되는 순간 살아있는 캐릭터들의 메모리 주소가 바뀌면서 모든 포인터가 엉망이 될 수 있습니다. 하지만 TSparseArray를 사용하면 다른 캐릭터가 배열에서 제거되어도 기존 캐릭터의 주소는 그대로 유지되므로, 포인터들이 계속 안전하게 유효한 상태로 남게 됩니다.