string.GetHashCode는 hash 값을 cache 할까?
잊혀져 가는 GetHashCode에 대한 자료들을 같이 소개도 할 겸,
순환참조와 XmlSerializer
; https://www.sysnet.pe.kr/2/0/751
Dictionary.Get(A) 대신 Dictionary.Get(A.GetHashCode())를 사용해서는 안되는 이유
; https://www.sysnet.pe.kr/2/0/889
이번에는 오늘 문득 코딩을 하다 궁금한 점이 있어서 그 결과를 써봅니다. (회사가 성능 관련 문제를 다루다 보니, 제가 만드는 코드 하나 하나에 직업병이 생기더군요. ^^)
보통 GetHashCode 사용에 부담스러울 때가 있는데요. 바로, "문자열"에 대해 GetHashCode를 호출하는 경우일 것입니다. 왜냐하면, 해시값을 내기 위해 모든 문자를 열람하게 되기 때문에 문자열이 커질수록 속도에 영향을 미칠 수 있기 때문입니다.
그렇다면, Immutable 속성의 string 타입에서 GetHashCode를 내부적으로 값을 cache하고 있지 않을까요? 어떻게 생각하세요?
답은? Cache 하고 있지 않습니다. ".NET Reflector"를 이용하여 System.String.GetHashCode의 코드를 살펴보면, 다음과 같이 매번 모든 문자열을 열람하는 것을 볼 수 있습니다.
public override unsafe int GetHashCode()
{
fixed (char* str = ((char*) this))
{
char* chPtr = str;
int num = 0x15051505;
int num2 = num;
int* numPtr = (int*) chPtr;
for (int i = this.Length; i > 0; i -= 4)
{
num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
if (i <= 2)
{
break;
}
num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
numPtr += 2;
}
return (num + (num2 * 0x5d588b65));
}
}
그런데, 위에서 보니 재미있는 코드가 눈에 띕니다. 바로, 내부적으로 관리하는 char* 버퍼를 int* 로 형변환 해서 사용한다는 점입니다. 이 때문에 문자열 길이가 4byte인 경우 루프를 2번 돌지 않고 1번 만에 처리해 버립니다. 오호~~~ 속도 향상을 위해 꽤나 고민한 흔적이 엿보입니다. ^^
그렇다면? C#의 문자열은 최소 4byte 간격으로 메모리를 패딩하고 있음을 짐작하게 됩니다. 정말 그런지 확인해 볼까요?
C#을 실행하고 메모리 윈도우를 통해서 조사해 보면 알 수 있을 것입니다.
어디... 문자열이 "t" 값만을 갖고 있는 경우를 볼까요?
== "t"인 경우 ===
74 00 00 00 00 00 00 80 28 ac 3a 00 01 00 00 00 71 00 00 00 00 00 00 00 00 00 t......€(￢:.....q.........
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
유니코드이기 때문에 내부적으로 "t" 값은 "74 00" 2바이트를 차지합니다. 그리고 C/C++에서의 "NULL" 표시를 위해 "0" 값을 사용하는데 이것 역시 2바이트를 차지하므로 사실상 "t" 한 글자를 표현하기 위해 "74 00 00 00"과 같이 4바이트를 필요로 합니다.
그럼 이번에는 "te"와 같이 두 글자로 늘여볼까요?
74 00 65 00 00 00 00 00 00 00 00 80 28 ac 3f 00 01 00 00 00 71 00 00 00 00 00 t.e........€(￢?.....q.....
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
"te"를 표현하기 위해 "74 00 65 00"이 소모되었지만, 널 문자가 빠졌기 때문에 "00 00"이 필요합니다. 하지만 4byte 정렬이기 때문에 사실상 "te" == "74 00 65 00 00 00 00 00"이 됩니다. 이렇게 판단할 수 있는 또 다른 근거로는, 그 이후에 "t"에서와 마찬가지로 "00 00 00 80" 값이 규칙적으로 나온다는 것을 관찰할 수 있기 때문입니다.
마지막으로 "test"로 해보면... 이제 결과를 예측할 수 있겠지요. ^^
74 00 65 00 73 00 74 00 00 00 00 00 00 00 00 80 28 ac 4d 00 08 00 00 00 71 00 t.e.s.t........€(￢M.....q.
77 00 65 00 72 00 74 00 65 00 73 00 74 00 00 00 00 00 00 00 00 00 00 00 00 00
GetHashCode가 값을 Cache 하고 있는지를 알아보려다가... 어느새 String의 내부 문자열 정렬을 알아보는 것 까지 와버렸군요. ^^
참고로, .NET 4.0의 string.GetHashCode를 외부로 빼서 구현해 보면 다음과 같습니다.
static unsafe void Main(string[] args)
{
string txt = "tes";
int hash1 = GetHashCode(txt);
int hash2 = txt.GetHashCode();
Console.WriteLine(hash1); // -175665545 (.NET 4.0인 경우.)
Console.WriteLine(hash2); // -175665545
Console.WriteLine(hash1 == hash2); // True
}
static unsafe int GetHashCode(string txt)
{
fixed (char* str = txt)
{
char* chPtr = str;
int num = 0x15051505;
int num2 = num;
int* numPtr = (int*)chPtr;
for (int i = txt.Length; i > 0; i -= 4)
{
num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
if (i <= 2)
{
break;
}
num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
numPtr += 2;
}
return (num + (num2 * 0x5d588b65));
}
}
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]