Microsoft MVP성태의 닷넷 이야기
VC++: 87. 무시할 수 없는 Visual C++ 런타임 함수 성능 [링크 복사], [링크+제목 복사],
조회: 25601
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
 
(연관된 글이 1개 있습니다.)

무시할 수 없는 Visual C++ 런타임 함수 성능

아래의 글에 달린 덧글 덕분에,

보이어-무어(Boyer-Moore) 알고리즘이 정말 빠를까?
; https://www.sysnet.pe.kr/2/0/1705

C 런타임 함수를 새롭게 보게 되었습니다. ^^

위의 글에서 strstr 함수가 boyer_moore 함수에 비해 굉장히 빠른 속도를 내는 것을 보았는데요. 덧글의 의견처럼 "C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\crt\src\strstr.c"에 해당하는 소스코드는 Visual C++에서 실행되는 strstr 함수가 아니었습니다.

이를 확인하는 방법은 간단합니다.

Visual C++ 프로젝트에서 "Runtime Library" 옵션을 "Multi-threaded Debug"로 바꾸고,

crt_func_debug_0.png

Visual Studio에서 디버깅을 시작한 다음 strstr 함수로 F11(Step-into)키를 눌러 진입하면 다음과 같이 소스 코드를 찾는 창이 뜹니다.

crt_func_debug_1.png

"f:\dd\vctools\crt\crtw32\string\i386\strstr.asm" 경로는 마이크로소프트 측에서 빌드했을 때의 경로이고, 우리는 그냥 strstr.asm 파일을 찾아서 매핑시켜주면 됩니다. Visual Studio 2013을 설치한 경우 다음의 경로에 있으니,

C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\crt\src\intel\strstr.asm

이 파일을 맞춰주면 Visual Studio에서 assembly 코드에 대한 라인 단위 디버깅으로 진입합니다. 거기다, "Registers" 창을 띄워 놓으면 레지스터 값 확인까지 가능합니다. 이렇게!

crt_func_debug_2.png

참고로, strstr.asm의 소스 코드는 다음과 같습니다.

        page    ,132
        title   strstr - search for one string inside another
;***
;strstr.asm - search for one string inside another
;
;       Copyright (c) Microsoft Corporation. All rights reserved.
;
;Purpose:
;       defines strstr() - search for one string inside another
;
;*******************************************************************************

        .xlist
        include cruntime.inc
        .list

page
;***
;char *strstr(str1, str2) - search for str2 in str1
;
;Purpose:
;       finds the first occurrence of str2 in str1
;
;Entry:
;       char *str1 - string to search in
;       char *str2 - string to search for
;
;Exit:
;       returns a pointer to the first occurrence of string2 in
;       string1, or NULL if string2 does not occur in string1
;
;Uses:
;
;Exceptions:
;
;*******************************************************************************


__from_strstr_to_strchr proto

        CODESEG

        public  strstr

strstr  proc \
        str1:ptr byte, \
        str2:ptr byte

        OPTION PROLOGUE:NONE, EPILOGUE:NONE

        mov     ecx,[esp + 8]       ; str2 (the string to be searched for)
        mov     eax,[esp + 4]       ; str1 (the string to be searched)

        push    edi                 ; Preserve edi, ebx and esi
        push    ebx
        push    esi

;   .FPO (cdwLocals, cdwParams, cbProlog, cbRegs, fUseBP, cbFrame)
    .FPO      ( 0, 2, $-strstr, 3, 0, 0 )

; Include SSE2/SSE4.2 code paths for platforms that support them.
        include strstr_sse.inc

        mov     dl,[ecx]            ; dl contains first char from str2

        mov     edi,eax             ; str1 (the string to be searched)

        test    dl,dl               ; is str2 empty?
        jz      empty_str2

        mov     dh,[ecx + 1]        ; second char from str2
        test    dh,dh               ; is str2 a one-character string?
        jz      strchr_call         ; if so, go use strchr code

; length of str2 is now known to be > 1 (used later)
; dl contains first char from str2
; dh contains second char from str2
; edi holds str1

findnext:
        mov     esi,edi             ; esi = edi = pointers to somewhere in str1
        mov     ecx,[esp + 14h]     ; str2

;use edi instead of esi to eliminate AGI
        mov     al,[edi]            ; al is next char from str1

        add     esi,1               ; increment pointer into str1

        cmp     al,dl
        je      first_char_found

        test    al,al               ; end of str1?
        jz      not_found           ; yes, and no match has been found

loop_start:
        mov     al,[esi]            ; put next char from str1 into al
        add     esi,1               ; increment pointer in str1
in_loop:
        cmp     al,dl
        je      first_char_found

        test    al,al               ; end of str1?
        jnz     loop_start          ; no, go get another char from str1

not_found:
        pop     esi
        pop     ebx
        pop     edi
        xor     eax,eax
        ret

; recall that dh contains the second char from str2

first_char_found:
        mov     al,[esi]            ; put next char from str1 into al
        add     esi,1

        cmp     al,dh               ; compare second chars
        jnz     in_loop             ; no match, continue search

two_first_chars_equal:
        lea     edi,[esi - 1]       ; store position of last read char in str1

compare_loop:
        mov     ah,[ecx + 2]        ; put next char from str2 into ah
        test    ah,ah               ; end of str2?
        jz      match               ; if so, then a match has been found

        mov     al,[esi]            ; get next char from str1
        add     esi,2               ; bump pointer into str1 by 2

        cmp     al,ah               ; are chars from str1 and str2 equal?
        jne     findnext            ; no

; do one more iteration

        mov     al,[ecx + 3]        ; put the next char from str2 into al
        test    al,al               ; end of str2
        jz      match               ; if so, then a match has been found

        mov     ah,[esi - 1]        ; get next char from str1
        add     ecx,2               ; bump pointer in str1 by 2
        cmp     al,ah               ; are chars from str1 and str2 equal?
        je      compare_loop

; no match. test some more chars (to improve execution time for bad strings).

        jmp     findnext

; str2 string contains only one character so it's like the strchr functioin

strchr_call:
        xor     eax,eax
        pop     esi
        pop     ebx
        pop     edi
        mov     al,dl
        jmp     __from_strstr_to_strchr

;
;
; Match!  Return (ebx - 1)
;
match:
        lea     eax,[edi - 1]
        pop     esi
        pop     ebx
        pop     edi
        ret

empty_str2:           ; empty target string, return src (ANSI mandated)
        mov     eax,edi
        pop     esi
        pop     ebx
        pop     edi
        ret

strstr  endp
        end

어셈블리로 최적화된 strstr 함수 말고, C 언어로 된 strstr 함수로 테스트 하는 경우에는 Boyer-Moore 알고리즘이 대체로 빠릅니다.

52KB의 문자열을 준비하고 발견되지 않는 문자열로 10번씩 테스트 해보면,

// x86/Release 빌드
// (낮을 수록 빠릅니다.)
// boyer_moore 검색 시간
boyer_moore (861)
boyer_moore (881)
boyer_moore (979)
boyer_moore (849)
boyer_moore (847)
boyer_moore (865)
boyer_moore (870)
boyer_moore (912)
boyer_moore (853)
boyer_moore (850)

// strstr 검색 시간
strstr (1691)
strstr (1335)
strstr (1320)
strstr (1357)
strstr (1338)
strstr (1296)
strstr (1294)
strstr (1290)
strstr (1291)
strstr (1587)

boyer_moore가 빠릅니다. 1/3 지점 앞 부분에 나오는 약간 긴 텍스트로 검색해 보면,

// boyer_moore 검색 시간
boyer_moore (260)
boyer_moore (31)
boyer_moore (32)
boyer_moore (32)
boyer_moore (42)
boyer_moore (33)
boyer_moore (32)
boyer_moore (31)
boyer_moore (32)
boyer_moore (32)

// strstr 검색 시간
strstr (1345)
strstr (704)
strstr (1498)
strstr (1501)
strstr (403)
strstr (183)
strstr (184)
strstr (183)
strstr (182)
strstr (362)

역시 boyer_moore가 빠릅니다. 뒤에서 1/3 지점에 나오는 짧은 텍스트로 검색을 해보면,

boyer_moore (457)
boyer_moore (431)
boyer_moore (429)
boyer_moore (429)
boyer_moore (430)
boyer_moore (430)
boyer_moore (429)
boyer_moore (430)
boyer_moore (429)
boyer_moore (429)

strstr (213)
strstr (212)
strstr (212)
strstr (212)
strstr (211)
strstr (212)
strstr (340)
strstr (214)
strstr (213)
strstr (213)

이번만큼은 C 언어 함수인 strstr이 빠릅니다.

재미있군요. ^^ strstr C 함수가 사실 굉장히 간단한 편인데도 불구하고 assembly로 최적화했을 때의 속도 향상이 '월등'해지는 것이 꽤나 인상적입니다.




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

[연관 글]






[최초 등록일: ]
[최종 수정일: 2/6/2015]

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

비밀번호

댓글 작성자
 




... 61  62  63  64  65  66  67  68  69  70  71  72  73  74  [75]  ...
NoWriterDateCnt.TitleFile(s)
12153정성태2/23/202024419.NET Framework: 898. Trampoline을 이용한 후킹의 한계파일 다운로드1
12152정성태2/23/202021424.NET Framework: 897. 실행 시에 메서드 가로채기 - CLR Injection: Runtime Method Replacer 개선 - 세 번째 이야기(Trampoline 후킹)파일 다운로드1
12151정성태2/22/202024058.NET Framework: 896. C# - Win32 API를 Trampoline 기법을 이용해 C# 메서드로 가로채는 방법 - 두 번째 이야기 (원본 함수 호출)파일 다운로드1
12150정성태2/21/202024148.NET Framework: 895. C# - Win32 API를 Trampoline 기법을 이용해 C# 메서드로 가로채는 방법 [1]파일 다운로드1
12149정성태2/20/202021060.NET Framework: 894. eBEST C# XingAPI 래퍼 - 연속 조회 처리 방법 [1]
12148정성태2/19/202025737디버깅 기술: 163. x64 환경에서 구현하는 다양한 Trampoline 기법 [1]
12147정성태2/19/202021044디버깅 기술: 162. x86/x64의 기계어 코드 최대 길이
12146정성태2/18/202022240.NET Framework: 893. eBEST C# XingAPI 래퍼 - 로그인 처리파일 다운로드1
12145정성태2/18/202023852.NET Framework: 892. eBEST C# XingAPI 래퍼 - Sqlite 지원 추가파일 다운로드1
12144정성태2/13/202024026.NET Framework: 891. 실행 시에 메서드 가로채기 - CLR Injection: Runtime Method Replacer 개선 - 두 번째 이야기파일 다운로드1
12143정성태2/13/202018443.NET Framework: 890. 상황별 GetFunctionPointer 반환값 정리 - x64파일 다운로드1
12142정성태2/12/202022360.NET Framework: 889. C# 코드로 접근하는 MethodDesc, MethodTable파일 다운로드1
12141정성태2/10/202021371.NET Framework: 888. C# - ASP.NET Core 웹 응용 프로그램의 출력 가로채기 [2]파일 다운로드1
12140정성태2/10/202022716.NET Framework: 887. C# - ASP.NET 웹 응용 프로그램의 출력 가로채기파일 다운로드1
12139정성태2/9/202022410.NET Framework: 886. C# - Console 응용 프로그램에서 UI 스레드 구현 방법
12138정성태2/9/202028616.NET Framework: 885. C# - 닷넷 응용 프로그램에서 SQLite 사용 [6]파일 다운로드1
12137정성태2/9/202020261오류 유형: 592. [AhnLab] 경고 - 디버거 실행을 탐지했습니다.
12136정성태2/6/202021908Windows: 168. Windows + S(또는 Q)로 뜨는 작업 표시줄의 검색 바가 동작하지 않는 경우
12135정성태2/6/202027708개발 환경 구성: 468. Nuget 패키지의 로컬 보관 폴더를 옮기는 방법 [2]
12134정성태2/5/202024974.NET Framework: 884. eBEST XingAPI의 C# 래퍼 버전 - XingAPINet Nuget 패키지 [5]파일 다운로드1
12133정성태2/5/202022727디버깅 기술: 161. Windbg 환경에서 확인해 본 .NET 메서드 JIT 컴파일 전과 후 - 두 번째 이야기
12132정성태1/28/202025742.NET Framework: 883. C#으로 구현하는 Win32 API 후킹(예: Sleep 호출 가로채기) [1]파일 다운로드1
12131정성태1/27/202024473개발 환경 구성: 467. LocaleEmulator를 이용해 유니코드를 지원하지 않는(한글이 깨지는) 프로그램을 실행하는 방법 [1]
12130정성태1/26/202022034VS.NET IDE: 142. Visual Studio에서 windbg의 "Open Executable..."처럼 EXE를 직접 열어 디버깅을 시작하는 방법
12129정성태1/26/202029063.NET Framework: 882. C# - 키움 Open API+ 사용 시 Registry 등록 없이 KHOpenAPI.ocx 사용하는 방법 [3]
12128정성태1/26/202023174오류 유형: 591. The code execution cannot proceed because mfc100.dll was not found. Reinstalling the program may fix this problem.
... 61  62  63  64  65  66  67  68  69  70  71  72  73  74  [75]  ...