[오늘의 키워드]
ValueTuple이라는 자료형 정리Dictionary의 key와GetHashCode()메서드 트러블슈팅
[ValueTuple]
오늘 푼 알고리즘 문제에서 Queue에 (int idx, int priority)라는 자료형을 넣어봤는데, 잘 실행됐다.
나는 이게 익명 형식 (anonymous type)인줄 알았는데, 구글링으로 익명 형식의 example을 찾아보니, 사용법이 살짝 달랐다.
그래서 튜터님께 질문하러 갔는데, 튜플이라고 알려주셨다.
프로그래머스 - 프로세스
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public int solution(int[] priorities, int location)
{
int answer = 0;
List<int> pq = new List<int>();
Queue<(int idx, int priority)> q = new Queue<(int idx, int priority)>();
for (int i = 0; i < priorities.Length; i++)
{
pq.Add(priorities[i]);
q.Enqueue((i, priorities[i]));
}
pq = pq.OrderByDescending(x => x).ToList();
while (q.Count > 0)
{
(int idx, int priority) peek = q.Dequeue();
if (pq[0] == peek.priority)
{
pq.RemoveAt(0);
answer++;
if (peek.idx == location)
break;
}
else
q.Enqueue(peek);
}
return answer;
}
}[Anonymous Type] vs [Value Tuple] vs [Tuple]
익명 타입은 var example = new { ... };처럼 사용한다.
밸류 튜플은 var example = ( ... );처럼 사용한다.
또, 그냥 Tuple이라는 자료형도 있는데, 이 녀석은 var example = new ( ... );처럼 사용한다.
눈에 보이는 차이점부터 정리해보자면, 익명 타입은 중괄호를 사용하고, 두 튜플은 공통적으로 소괄호를 사용한다.
또, 밸류 튜플은 new 키워드가 없고, 나머지 두 자료형엔 new 키워드가 있다는 것으로 밸류 튜플은 값 타입, 나머지 투 자료형은 참조 타입이라는 것을 짐작할 수 있다. 사실 밸류 튜플은 이름부터 값(value)이긴 하다.
공식문서에서 친절하게 표로 비교해준 자료가 있다.
| 이름 | 액세스 한정자 | 형식 | 사용자 지정 멤버 이름 | 분해 지원 | 식 트리 지원 |
|---|---|---|---|---|---|
| 익명 형식 | internal | class | ✔️ | ❌ | ✔️ |
| Tuple | public | class | ❌ | ❌ | ✔️ |
| ValueTuple | public | struct | ✔️ | ✔️ | ❌ |
특이한 점은, 익명 형식은 액세스 한정자가 internal이라서, 같은 어셈블리에선 정의된 하나의 타입으로 인정되지만, 다른 어셈블리에선 모든 형식이 같은 두 익명 형식이라도 다른 타입으로 판단한다고 한다.
[Dictionary의 Key와 GetHashCode()]
현재 작업 중인 프로젝트에서 ChunkCoord라는 구조체를 선언해서 딕셔너리의 key로 사용하고 있었는데, 프레임이 갑자기 엄청나게 떨어져서 확인해보니까 딕셔너리에 TryGetValue로 접근할 때, 엄청난 양의 GC가 발생하고 있었다.
문제의 코드
/// <summary> 시야범위 내의 청크 생성 </summary>
private void UpdateChunksInViewRange()
{
_prevActiveChunks = _currentActiveChunks;
_currentActiveChunks = new();
for (int x = -WorldData.ViewRange; x < WorldData.ViewRange; x++)
{
for (int z = -WorldData.ViewRange; z < WorldData.ViewRange; z++)
{
if (_chunkMap.TryGetValue(_currentPlayerCoord + new ChunkCoord(x, z), out var currentChunk))
{
_currentActiveChunks.Add(currentChunk);
currentChunk.SetActive(true);
_prevActiveChunks.Remove(currentChunk);
}
}
}
foreach (var chunk in _prevActiveChunks)
chunk.IsActive = false;
}처음엔 도저히 이해가 안됐다.
몇 십분 전까지만 해도 GC 없이 잘 동작했던 코드였고, 디버깅을 해보니 list를 생성, 삭제하는 곳에서 GC가 발생하는 것도 아니고 딕셔너리 접근하는 것에서 GC가 발생하고 있었기 때문이다.
문제 발생 원인
진짜 문제는 ChunkCoord 구조체의 GetHashCode() 메서드를 잘못 오버라이딩해서 발생한 것이었다.
=연산자 오버로딩과 Equals() 메서드 오버로딩이 필요해서 오버로딩을 하고 나니까, GetHashCode() 메서드도 재정의하라고 IDE에서 띄워주길래, 구조체는 값 형식이니까 그냥 0 리턴해주면 되겠지. 라는 안일한 생각 때문에 발생했다.
진짜 문제의 코드
public struct ChunkCoord
{
public int x;
public int z;
public ChunkCoord(int x, int z)
{
this.x = x;
this.z = z;
}
public override int GetHashCode()
{
return 0; // ★
}
...
}HashSet, Dictionary 등등 해시를 이용하는 제네릭 컬렉션에서는 객체를 비교할 때 GetHashCode()를 이용하여 비교한 후, 같은 해시를 가졌다면 Equals()까지 체크한다.
또, 값 타입인 구조체는 Dictionary 선언 시, IEqualityComparer<T>를 생성자에 전달해주지 않았다면 접근마다 최소 한 번의 박싱이 일어나는데, 이 박싱은 곧 GC를 발생시킨다.
위와 같이 해버리면, 모든 객체가 0이라는 HashCode를 갖게 되고, 딕셔너리는 매 프레임 수십 수백 번의 비교마다 딕셔너리 내부의 모든 key가 전부 같다고 판단하는 것 같다.
내 경우엔 매 프레임 400번 딕셔너리에 접근하고, 딕셔너리에도 약 400개의 원소가 들어있으니 대략 16만번 딕셔너리 접근이 발생하니깐 위의 엄청난 양의 GC call이 드디어 이해가 간다...
해결
ChunkCoord 구조체에 IEqualityComparer<ChunkCoord> 인터페이스를 구현해주고, 딕셔너리 생성자에 comparer로 자기자신을 넘겨줬다.
사실 comparer는 저렇게 넘겨주는게 맞긴한가 싶기도 하고, 넘겨주나 안넘겨주나 인터페이스를 구현해놔서 그런지 잘 동작하긴 한다.
World.cs
private Dictionary<ChunkCoord, Chunk> _chunkMap = new(comparer: new ChunkCoord());ChunkCoord.cs
public struct ChunkCoord : IEqualityComparer<ChunkCoord>
{
public int x;
public int z;
public ChunkCoord(int x, int z)
{
this.x = x;
this.z = z;
}
public override string ToString()
{
return $"({x}, {z})";
}
public override int GetHashCode()
{
return HashCode.Combine(x, z);
}
public int GetHashCode(ChunkCoord obj)
{
return obj.GetHashCode();
}
...
}참고 자료
C# 의 타입 - 4. 객체의 식별 (Equals, GetHashCode)
GC에게 먹이를 주지 마시오
C# Equals()과 GetHashCode()를 함께 재정의 해야하는 이유
