strlen() 같은 기본 함수도 SIMD 명령으로 최적화할 수 있을까?

아래는 "VC++ 6.0을 사용하지 말아야 하는이유"에 대한 반박(?)의 글에 어떤분이 단, 댓글입니다.

---------------------------------------------------

원문 : 

11. SIMD  명령

=>대부분의 프로그램은 사용할 이유가 거의 없다.

게임, 그래픽, 오디오, 비디오등 고성능이 요구되는 프로그램에서 필요하다.

댓글 :

strlen() 같은 기본 함수도 SIMD 명령으로 최적화할 수 있습니다. 어설프게 알면 모르는 것만 못합니다.

---------------------------------------------------

문자열 처리에, SIMD명령을 사용할 수 있다는 생각은 못했네요. ㅎㅎ

SIMD명령어는 명령어 하나로, 여러개의 데이터를 한꺼번에 처리하기위한 용도로 개발된것으로 알고 있습니다.

가장 많이 사용하는곳이 영상, 오디오등 많은 데이터를 빠른시간내에 처리해야하는 곳으로 알고 있습니다.

보통 DSP프로세싱이라고 하는쪽이죠.

반면에 문자열 처리는 문자열의 길이가 1k도 안되는 경우가 대부분입니다.

문자 몇글자 바꾸는 용도가 주입니다.

예를들면, 이름, 전화번호, 주소, 등등

수년전에 strlen, strcpy등의 문자열처리함수를 최적화하려는 시도가 있었습니다.

당연히, 우리나라 KLDP 같은 인터넷 카폐에서요.

예) https://kldp.org/node/41076

여러사람이 당연히 최적화가 될 줄알고 시도를 했었지요.

관련 자료는 찾으려니 안나오네요.

시간나시면 찾아보세요.

결론만 말씀드리면, C언어의 문자열 처리 함수들은 매우 오래되었고, 초창기 CPU가 개발되면서부터 하드웨어적으로 구현이 되었다.

반대로 말하면, CPU는 C언어의 문자열 처리함수에 최적화 되었다.

라고 말할 수 있습니다.

이게 무슨 말이냐면,

프로그램 작성할때, 절반이상이 문자열처리라고 해도 과언은 아닙니다.

그래서 문자열 표준 라이브러리도 오래전부터 만들어 졌고, CPU는 어떻게하면, 문자열처리를 빨리 할 수 있을까?

고민을 많이 한듯 싶습니다.(추측)

말이 자꾸 길어지니, 더 짧게 말하면,

C언어의 문자열 처리 함수는 매우 작은 크기로, 매우 빠르게 동작한다는 겁니다.

CPU구조가 C언어 문자열 처리를 가장 잘 해낼 수 있는 구조라고 생각하면 될듯 싶습니다.

위에서도 말씀드렸다시피, 문자열 데이터는 대부분 수십~수백 바이트 입니다.

1k바이트를 넘는 문자열 처리는 그다지 많지 않습니다.

물론, 수십k바이트에서 수메가 바이트의 문자열을 처리해야하는 프로그램도 있습니다.

memcpy와 같은 메모리 관련 함수로도 C언어의 문자열 처리 함수를 구현할 수 있습니다만,

차이점이 있습니다.

메모리 처리함수는 대용량(약 4kbyte이상) 데이터를 처리하는데 최적화 되어 있습니다.

예를 들어, strcpy함수와 memcpy함수를 사용해서 10바이트 문자열을 복사한다고 하면,

누가 더 빠를까요?

궁금하신 분들은 한번 테스트해보시기 바랍니다.

테스트의 공정성을 위해, 최소 수십만번이상 많은 횟수를 시도하여,

걸린시간을 수행횟수로 나누면 됩니다. (초당 몇회 수행되는지 수치로 비교)

테스트를 공정하게 할 수 있도록 테스트 조건을 설정하는것도, 노하우라면, 노하우입니다.

초보분들이 실수하는것중에 하나가, 1msec도 안걸리는 수백회 연산을 가지고 비교를 합니다.

MS 윈도우 운영체제들은 약 10msec의 컨텍스트 스위칭 타임이 존재합니다.

테스트는 최소한 수백 msec이상 테스트해야 한다는 말입니다.

더 자세한 사항은 인터넷 찾아보세요.

아뭏튼, strcpy함수와 memcpy함수중에 누가 더 빠를까요?

당연히 strcpy함수입니다.

왜냐하면, memcpy함수는 아까도 말씀드렸다시피, 대용량 데이터 처리에 최적화 되어 있습니다.

제가 예전에 테스트해본 결과로는 약 4k바이트 이상일경우에만 memcpy함수가 조금 빨랐습니다.

memcpy함수를 디스어셈블리하여 분석해보시면, 데이터가 얼마나 되고, 바이트얼라인이 어디서부터 되고,

등등의 조건을 검사하고, 최적의 조건이 나올때까지, 한바이트씩 처리하다가, 최적의 조건이 나오면,

약 4바이트씩 처리하게 됩니다.

이와 달리, 문자열 처리함수는 1문자(1~2바이트)씩 하나씩 처리합니다만,

아까도 설명 드렸다시피, CPU자체가 문자열 처리에 최적화 되어있어,

매우 작은 코드로, 매우 빨리 수행이 됩니다.

생각나는데로, 아래와 같은 코드를 작성해보았습니다.

void My_strcpy(char*dst,char*src) 

{ 

while(*src) 

{ 

*dst++=*src++;

} 

*dst=0;

} 

내용물은 딸랑 3줄입니다. ㅎㅎ

CPU는 C언어코드를 거의 그대로 실행 할 수 있도록 발전이 되어 왔습니다.

군더더기가 전혀 없습니다.

디스어셈블리한 코드는 아래와 같습니다.

225:  void My_strcpy(char*dst,char*src)

226:  {

00401FA0   push        ebp

00401FA1   mov         ebp,esp

00401FA3   sub         esp,40h

00401FA6   push        ebx

00401FA7   push        esi

00401FA8   push        edi

00401FA9   lea         edi,[ebp-40h]

00401FAC   mov         ecx,10h

00401FB1   mov         eax,0CCCCCCCCh

00401FB6   rep stos    dword ptr [edi]

227:      while(*src)

00401FB8   mov         eax,dword ptr [ebp+0Ch]

00401FBB   movsx       ecx,byte ptr [eax]

00401FBE   test        ecx,ecx

00401FC0   je          My_strcpy+40h (00401fe0)

228:      {

229:          *dst++=*src++;

00401FC2   mov         edx,dword ptr [ebp+8]

00401FC5   mov         eax,dword ptr [ebp+0Ch]

00401FC8   mov         cl,byte ptr [eax]

00401FCA   mov         byte ptr [edx],cl

00401FCC   mov         edx,dword ptr [ebp+8]

00401FCF   add         edx,1

00401FD2   mov         dword ptr [ebp+8],edx

00401FD5   mov         eax,dword ptr [ebp+0Ch]

00401FD8   add         eax,1

00401FDB   mov         dword ptr [ebp+0Ch],eax

230:      }

00401FDE   jmp         My_strcpy+18h (00401fb8)

231:      *dst=0;

00401FE0   mov         ecx,dword ptr [ebp+8]

00401FE3   mov         byte ptr [ecx],0

232:  }

00401FE6   pop         edi

00401FE7   pop         esi

00401FE8   pop         ebx

00401FE9   mov         esp,ebp

00401FEB   pop         ebp

00401FEC   ret

생각보다는 명령어가 많습니다.

물론 우리가 사용하는 표준 함수들은 이것조차 어셈블러로 최적화 되어 있습니다.

아래는 strcpy함수를 역어셈블한 결과입니다.

엄청 길고 복잡합니다.

10217940   push        edi

10217941   mov         edi,dword ptr [esp+8]

10217945   jmp         102179B1

10217947   lea         esp,[esp]

1021794E   mov         edi,edi

10217950   mov         ecx,dword ptr [esp+4]

10217954   push        edi

10217955   test        ecx,3

1021795B   je          1021796C

1021795D   mov         al,byte ptr [ecx]

1021795F   inc         ecx

10217960   test        al,al

10217962   je          1021799F

10217964   test        ecx,3

1021796A   jne         1021795D

1021796C   mov         eax,dword ptr [ecx]

1021796E   mov         edx,7EFEFEFFh

10217973   add         edx,eax

10217975   xor         eax,0FFh

10217978   xor         eax,edx

1021797A   add         ecx,4

1021797D   test        eax,81010100h

10217982   je          1021796C

10217984   mov         eax,dword ptr [ecx-4]

10217987   test        al,al

10217989   je          102179AE

1021798B   test        ah,ah

1021798D   je          102179A9

1021798F   test        eax,0FF0000h

10217994   je          102179A4

10217996   test        eax,0FF000000h

1021799B   je          1021799F

1021799D   jmp         1021796C

1021799F   lea         edi,[ecx-1]

102179A2   jmp         102179B1

102179A4   lea         edi,[ecx-2]

102179A7   jmp         102179B1

102179A9   lea         edi,[ecx-3]

102179AC   jmp         102179B1

102179AE   lea         edi,[ecx-4]

102179B1   mov         ecx,dword ptr [esp+0Ch]

102179B5   test        ecx,3

102179BB   je          102179D6

102179BD   mov         dl,byte ptr [ecx]

102179BF   inc         ecx

102179C0   test        dl,dl

102179C2   je          10217A28

102179C4   mov         byte ptr [edi],dl

102179C6   inc         edi

102179C7   test        ecx,3

102179CD   jne         102179BD

102179CF   jmp         102179D6

102179D1   mov         dword ptr [edi],edx

102179D3   add         edi,4

102179D6   mov         edx,7EFEFEFFh

102179DB   mov         eax,dword ptr [ecx]

102179DD   add         edx,eax

102179DF   xor         eax,0FFh

102179E2   xor         eax,edx

102179E4   mov         edx,dword ptr [ecx]

102179E6   add         ecx,4

102179E9   test        eax,81010100h

102179EE   je          102179D1

102179F0   test        dl,dl

102179F2   je          10217A28

102179F4   test        dh,dh

102179F6   je          10217A1F

102179F8   test        edx,0FF0000h

102179FE   je          10217A12

10217A00   test        edx,0FF000000h

10217A06   je          10217A0A

10217A08   jmp         102179D1

10217A0A   mov         dword ptr [edi],edx

10217A0C   mov         eax,dword ptr [esp+8]

10217A10   pop         edi

10217A11   ret

누가 더 빠른지 비교해봅시다.

단, 데이터 문자열의 길이에 따라, 결과는 달라집니다.

아래는 백만회*50회 수행시 결과입니다.

void main()

{

char buf1[1024],buf2[1024],*p="1234567890ABCDEFGHIJKLMN...XYZ";

int n,cnt=1000000;

DWORD t[2];

n=cnt;

t[0]=::GetTickCount();

while(n--)//루프문의 영향을 최소화하기위해, 1번 돌때마다 50회씩 수행

{

My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p);

My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p);

My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p);

My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p);

My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p);

My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p);

My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p);

My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p);

My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p);

My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p); My_strcpy(buf1,p);

}

t[0]=::GetTickCount()-t[0];

n=cnt;

t[1]=::GetTickCount();

while(n--)//루프문의 영향을 최소화하기위해, 1번 돌때마다 50회씩 수행

{

strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p);

strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p);

strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p);

strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p);

strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p);

strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p);

strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p);

strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p);

strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p);

strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p); strcpy(buf1,p);

}

t[1]=::GetTickCount()-t[1];

TRACE("%d만회 루프(x50회), My_strcpy : %d msec, strcpy : %d msec, %0.1f배 빠름",cnt/10000, t[0], t[1],((float)t[0])/t[1]);

//결과1 : 100만회 루프(x50회), My_strcpy : 13541 msec, strcpy : 1482 msec, 9.1배 빠름

}

아까 strcpy함수가 9배나 더빠릅니다.

strcpy함수는 표준함수이며, 특정 CPU에 최적화되어 있습니다.

CPU가 x86이냐, ARM이냐, 8051이냐에 따라, 어셈블리 실제코드는 다르게 설계됩니다.

그러면, "strcpy와 같은 문자열함수를 SIMD명령으로 최적화 할 수 있을까?"에 대한 답을 찾아 보겠습니다.

제목 : Why is strcmp not SIMD optimized?

URL : http://stackoverflow.com/questions/26586060/why-is-strcmp-not-simd-optimized

일부 발췌

strcmp compare 2 null terminated C strings.

So if you want to use SIMD you need to find the length first to ensure you didn't get out of the range.

But to find the length you need to compare every char with NULL in both strings.

So while you will be comparing every char in your C strings with NULL,

strcmp will already return a result before you will load your SIMD instructions.

JustAnotherCurious Oct 27 '14 at 11:11

요약 : SIMD명령을 사용하기 위해서는 데이터의 길이 가 필요한데,

문자열에서는 길이를 알기위해서, 1바이트씩 비교해가면서, 길이를 확인해야하는데,

이 과정이 strcmp와 동일하다.(SIMD를 사용할 필요가 없다)

일부 발췌

It has to know the length first and this requires scanning the string for the terminating zero byte.

If you scan for the length of the string you have already accomplished most of the work of a strcmp function. Therefore there is no benefit to use SSE2.

However, Intel added instructions for string handling in the SSE4.2 instruction set.

These handle the terminating zero byte problem.

For a nice write-up on them read this blog-post: http://www.strchr.com/strcmp_and_strlen_using_sse_4.2

요약 : SEE2명령을 사용할 경우에도, 문자열의 끝이 어디인기(길이가 얼마인지) 알아야하지만, 문자열의 끝이 '\0'으로 끝나는

C언어의 문자열 형태에서는 문자열의 길이를 한번 확인할 필요가 있다.

하지만, 인텔은 SEE2에 문자열 처리 명령을 추가했다. 링크참조(SEE2 문자열처리 동작 과정) 해라.

일부발췌

...

If you scan for the length of the string you have already accomplished most of the work of a strcmp function.

Therefore there is no benefit to use SSE2.

요약 : 문자열 길이를 알아야 SEE2를 사용할 수 있는데, 문자열 길이를 확인하는 과정을 했다면, 이미 strcmp의 기능을 수행한 상태이므로,

SEE2를 사용할 이유가 없다.

나머지 내용들 요약 : SIMD명령을 사용하여 한번에 16바이트씩 처리한다고 해도, 바이트 정렬 시키기위한 코드와

마지막 16바이트 이하의 문자열을 처리하기위한 과정과 노력은 작지 않다.

이미 길이를 알고 있고, 길이가 긴 문자열인 경우에는 SIMD명령이 효과가 있으나, 길이를 모르는 C언어의 문자열형태에서는

그 효과가 미미하거나, 더 느릴 수 도 있다.

=> 이 내용은 위에서도 언급했다시피, strcpy, memcpy와 같이 문자열의 길이에 따라 결과가 반대가 될 수 있다.

전체 요약 : SIMD명령으로 문자열을 처리한다고해도, 문자열의 길이를 알지 못하는, 짧은 길이의 C언어 문자열 형태에서는 효과가 없다.

SIMD명령이 효과가 있다고 하는것은 맞지않으나,

SEE명령은 효과가 있다.

http://stackoverflow.com/questions/1774791/faster-strlen

faster strlen?

http://stackoverflow.com/questions/1774791/faster-strlen

...

...안되...

...어려워...

...안되...

...그게 가능하겠어?...

...

Get a Core i7 processor.

Core i7 comes with the SSE 4.2 instruction set. Intel added four additional vector instructions to speed up strlen and related search tasks.

Here are some interesting thoughts about the new instructions:

http://smallcode.weblogs.us/oldblog/2007/11/

이 사람은, 더 나은 최신의 비쥬얼 스튜디오로, 직접 SIMD명령을 사용해서, 최적화를 하겠다는건가?