Microsoft MVP성태의 닷넷 이야기
.NET Framework: 251. string.GetHashCode 는 hash 값을 cache 할까? [링크 복사], [링크+제목 복사]
조회: 9998
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
 

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 인 경우 루프를 4번 돌지 않고 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));
    }
}




[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[연관 글]





[최초 등록일: ]
[최종 수정일: 5/26/2012 ]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer@outlook.com

비밀번호

댓글 쓴 사람
 




1  2  3  4  5  6  7  8  9  10  [11]  12  13  14  15  ...
NoWriterDateCnt.TitleFile(s)
12127정성태1/28/2020710.NET Framework: 881. C# DLL에서 제공하는 Win32 export 함수의 내부 동작 방식(VT Fix up Table)파일 다운로드1
12126정성태1/25/2020661.NET Framework: 880. C# - PE 파일로부터 IMAGE_COR20_HEADER 및 VTableFixups 테이블 분석파일 다운로드1
12125정성태1/24/2020510VS.NET IDE: 141. IDE0019 - Use pattern matching
12124정성태1/24/20201151VS.NET IDE: 140. IDE1006 - Naming rule violation: These words must begin with upper case characters: ...
12123정성태1/23/2020912웹: 39. Google Analytics - gtag 함수를 이용해 페이지 URL 수정 및 별도의 이벤트 생성 방법
12122정성태1/22/2020819.NET Framework: 879. C/C++의 UNREFERENCED_PARAMETER 매크로를 C#에서 우회하는 방법(IDE0060 - Remove unused parameter '...')파일 다운로드1
12121정성태1/24/2020506VS.NET IDE: 139. Visual Studio - Error List: "Could not find schema information for the ..."파일 다운로드1
12120정성태1/20/2020776.NET Framework: 878. C# DLL에서 Win32 C/C++처럼 dllexport 함수를 제공하는 방법 - 네 번째 이야기(IL 코드로 직접 구현)파일 다운로드1
12119정성태1/17/2020878디버깅 기술: 160. Windbg 확장 DLL 만들기 (3) - C#으로 만드는 방법
12118정성태1/17/2020883개발 환경 구성: 466. C# DLL에서 Win32 C/C++처럼 dllexport 함수를 제공하는 방법 - 세 번째 이야기 [1]
12117정성태1/15/2020877디버깅 기술: 159. C# - 디버깅 중인 프로세스를 강제로 다른 디버거에서 연결하는 방법파일 다운로드1
12116정성태1/15/2020728디버깅 기술: 158. Visual Studio로 디버깅 시 sos.dll 확장 명령어를 (비롯한 windbg의 다양한 기능을) 수행하는 방법
12115정성태1/14/2020747디버깅 기술: 157. C# - PEB.ProcessHeap을 이용해 디버깅 중인지 확인하는 방법파일 다운로드1
12114정성태1/13/20201033디버깅 기술: 156. C# - PDB 파일로부터 심벌(Symbol) 및 타입(Type) 정보 열거 [1]파일 다운로드3
12113정성태1/12/20201460오류 유형: 590. Visual C++ 빌드 오류 - fatal error LNK1104: cannot open file 'atls.lib' [1]
12112정성태1/12/2020617오류 유형: 589. PowerShell - 원격 Invoke-Command 실행 시 "WinRM cannot complete the operation" 오류 발생
12111정성태3/23/20201659디버깅 기술: 155. C# - KernelMemoryIO 드라이버를 이용해 실행 프로그램을 숨기는 방법(DKOM: Direct Kernel Object Modification) [12]
12110정성태6/23/20201113디버깅 기술: 154. Patch Guard로 인해 블루 스크린(BSOD)가 발생하는 사례 [5]파일 다운로드1
12109정성태1/10/2020841오류 유형: 588. Driver 프로젝트 빌드 오류 - Inf2Cat error -2: "Inf2Cat, signability test failed."
12108정성태1/10/2020673오류 유형: 587. Kernel Driver 시작 시 127(The specified procedure could not be found.) 오류 메시지 발생
12107정성태1/10/2020765.NET Framework: 877. C# - 프로세스의 모든 핸들을 열람 - 두 번째 이야기
12106정성태1/8/2020865VC++: 136. C++ - OSR Driver Loader와 같은 Legacy 커널 드라이버 설치 프로그램 제작 [1]
12105정성태1/8/2020793디버깅 기술: 153. C# - PEB를 조작해 로드된 DLL을 숨기는 방법
12104정성태1/9/20201238DDK: 9. 커널 메모리를 읽고 쓰는 NT Legacy driver와 C# 클라이언트 프로그램 [4]
12103정성태4/23/20202101DDK: 8. Visual Studio 2019 + WDK Legacy Driver 제작- Hello World 예제 [1]파일 다운로드2
12102정성태1/6/20201343디버깅 기술: 152. User 권한(Ring 3)의 프로그램에서 _ETHREAD 주소(및 커널 메모리를 읽을 수 있다면 _EPROCESS 주소) 구하는 방법
1  2  3  4  5  6  7  8  9  10  [11]  12  13  14  15  ...