[UE5] TMap의 key값으로 FName을 사용하면 빠른 편이다.

프로젝트의 TMap컨테이너를 사용해야하는데 Key값으로 FName을 사용하거나 주소값 (AActor*라던가 등)을 사용하곤 한다.

 

이 때 FName을 Key값으로 사용할 시, 성능이 괜찮은지 궁금해서 구글링하던 결과 괜찮은 글을 찾았다.

근데 이건 6년전 글이라 UnrealEngine4 버전 기준이다.

성능이 빠르다는것은 5버전이더라도 유효할것이고, 이유도 비슷할거라서 일단 포스팅했다.

5내에서의 원리는 추후... 언젠가 조금이라도 분석해보겠다.

 

 

https://www.reddit.com/r/unrealengine/comments/828neo/questionfname_performance_in_a_database_tmap/?rdt=45138

From the unrealengine community on Reddit

 

구글번역하면 코드도 번역이 되어서 보기편하게 코드만 빼고 번역해봤다.

 

 

======= ======= ======= ======= ======= ======= ======= ======= ======= ======= ======= ======= =

 

TLDR; TMap<FName, T2>는 기본적으로 TMap<int64, T2>만큼 성능이 좋습니다.

TMap 컨테이너는 해시세트를 사용하여 데이터를 저장하기 때문에 O(1) 성능이 매우 뛰어납니다.

키 값이 해시되는 속도와 해당 연산자==의 비용에 따라 해당 키 값이 다른 유형에 비해 얼마나 성능이 좋은지 결정됩니다.

TMap::FindChecked는 키를 조회하는 방법으로, 결국 TSet::FindId에 대한 호출로 귀결됩니다. 그 구현은 다음과 같습니다.

 

FSetElementId FindId(KeyInitType Key) const
{
	if (Elements.Num())
	{
		for(FSetElementId ElementId = GetTypedHash(KeyFuncs::GetKeyHash(Key));
			ElementId.IsValidId();
			ElementId = Elements[ElementId].HashNextId)
		{
			if(KeyFuncs::Matches(KeyFuncs::GetSetKey(Elements[ElementId].Value),Key))
			{
				// Return the first match, regardless of whether the set has multiple matches for the key or not.
				return ElementId;
			}
		}
	}
	return FSetElementId();
}

 

 

보시다시피 for 루프는 초기화 중에 키 값에 대해 GetTypedHash를 한 번 호출합니다.

FName의 해시 함수는 간단합니다. 단순히 int32의 FName::ComparisonIndex + FName::Number 두 개를 추가하기만 하면 됩니다.

그런 다음 루프 본문은 KeyFuncs::Matches를 사용하여 해시 조회를 비교합니다. 일치에서는 값 유형의 연산자==를 사용합니다. 따라서 해시 비교 성능은 FName::operator==에 따라 달라집니다.

FName::operator==는 다음과 같습니다.

FORCEINLINE bool operator==(const FName& Other) const
{
	#if WITH_CASE_PRESERVING_NAME
		return GetComparisonIndexFast() == Other.GetComparisonIndexFast() && GetNumber() == Other.GetNumber();
	#else
		static_assert(sizeof(CompositeComparisonValue) == sizeof(*this), "ComparisonValue does not cover the entire FName state");
		return CompositeComparisonValue == Other.CompositeComparisonValue;
	#endif
}

 

변경하지 않는 한, WITH_CASE_PRESERVING_NAME은 게임 런타임에서 false가 됩니다(그러나 편집기에서는 true). CompositeComparisonValue는 uint64로 정의됩니다. 따라서 런타임에 2개의 FName을 비교하는 것은 일치 항목을 찾거나 가능한 일치 항목을 모두 소진하는 데 필요한 각 해시 비교에 대해 하나의 해시(int32::operator+)와 하나의 int64::operator==와 같습니다.

요약:

TMap<FName, T2> 사용은 O(1)이고 상수 시간 비용은 몇 가지 함수 호출(아마도 최적화됨), 32비트 정수 추가 및 1개 이상의 int64 동일성 테스트입니다. 빠르다.

 

======== ======== ======== ======== ======== ======== ======== ======== ======== ======== =======

 

언리얼 5.0기준 FName의 해시함수 찾아봤는데 똑같다.