작성자 고임
최초 작성일
2008년10월3일 최종 작성일 2008년 10월 6일 -> 박진홍 님이 원본 글을 알려주셔서 수정
오늘의 주제는 속도 최적화이다.
이 주제는 예전에 활동하던 개발자 모임에서 나왔던 주제인데, 정확히는 모르겠지만 5년 정도 지난 것 같다.
그때 어떤 개발자 분이 이 기법에 대해 소개를 해주셨는데, 불행히도 성함을 잊어버렸다.
이 기법은 외국의 어떤 사람이 창안한 것인데, 역시 그 외국 개발자도 이름을 잊어버렸다. -_-;
누가 먼저 창안을 하고, 누가 먼저 소개했는지 기억은 안나지만, 말도 많고, 탈도 많을 이 주제에 대해서 달려가 보도록 하자.
수정
http://en.wikipedia.org/wiki/Duff%27s_device
박진홍님께서 해당 기법의 정식 명칭과 해당 사이트를 알려주셨습니다. 감사합니다.
들어가기
이 글에서 소개하는 알고리즘은 속도 최적화에 관심이 있는 사람들은 대부분 알고 있는 유명한 알고리즘이며, 어셈으로 코딩한 것보다도 더 빠른 속도를 낸다는 평가를 받았던 때가 있었다. 그러나 최근의 CPU의 설계 기술과 컴파일러의 최적화 기술의 발전으로 인해 이 알고리즘의 쓰임새가 거의 없어지다시피 했다. 이 알고리즘으로 고생해서 속도 최적화를 해봤자, 컴파일러의 속도 최적화 옵션을 켜놓으면 가공할 능력으로 속도 최적화를 해주는 통에 이 알고리즘은 퇴물 취급을 받으며 많은 사람들의 기억속에 그저 특이한 코딩으로만 치부되면서 최적화 역사에 먼지 풀풀 뒤집어 쓰며 한켠을 차지하고 있다. 덕분에 요새 프로그래밍을 배우는 학생이나 최근에 프로그래밍 세계로 입문하는 분들은 이 알고리즘이 있다는 사실도 모른채 컴파일러의 최적화 기술에 기대고 있다.
물론 현재의 컴파일러 최적화 옵션으로도 충분한 속도 향상을 내주기 때문에 굳이 이 기법에 대해서 알 필요는 없다. 하지만 특수한 환경이나 특수한 상황에서는 여전히 막강한 기법인 이 속도 최적화 알고리즘을 아는 것만으로 다양한 상황에서의 당신의 코딩 대처법이 늘어날 수 있기에 여전히 의미가 있는 알고리즘이다. 알고 있기에 적용을 안하는 것과 모르고 있어서 적용을 못하는 건 엄청난 차이를 준다.
자 질문을 하나 던지고 시작하도록 한다.
void _NormalMemcpy(unsigned char * pDes, unsigned char* pSrc, unsigned long nCopySize){unsigned long m;
for(m = 0; m < nCopySize; m++) { pDes[m] = pSrc[m]; }}
위의 코드는 단순히 memcpy를 구현한 것에 지나지 않는다.
이 코드는 속도최적화 관점에서 보았을때 최적화 할 가능성이 보이는가?최적화 할 가능성이 보인다면 어떤 방식으로 속도 최적화를 구현할 수 있는가?
여기서 단서를 하나 달기로 한다. 컴파일러가 알아서 병렬 처리로 속도 최적화 하는 것은 제외한다. 힌트를 주자면, 알고리즘 만으로 명령어의 수를 줄여야 한다.
이 질문에 10분 이내에 속도 최적화가 가능하신 분에게는 이런 말을 전하고 싶다.
“당신은 혹시 천재?”
자, 이제 위의 질문에 대한 답을 알아보기로 한다. 의외로 간단하다.
문제를 단순화 시켜보자,
unsigned long m;
for(m = 0; m < 3; m++) { pDes[m] = pSrc[m]; }
위의 코드는 pSrc의 0번지부터 2번지까지 pDes에 차곡 차곡 넣는 코드이다. 위의 코드는 다음과 같은 의사 코드로 진행이 된다.
1 : m에 0을 넣음.2 : m이 3보다 작은가? 작으면 아래를 수행 크거나 같다면 종료. (현재 m 은 0이다.)3 : pDes에 pSrc의 현재 m의 번지값을 넣는다. 4 : m을 1증가한다. 5 : m이 3보다 작은가? 작으면 아래를 수행 크거나 같다면 종료. (현재 m 은 1이다.)6 : pDes에 pSrc의 현재 m의 번지값을 넣는다. 7 : m을 1증가한다. 8 : m이 3보다 작은가? 작으면 아래를 수행 크거나 같다면 종료. (현재 m 은 2이다.)9 : pDes에 pSrc의 현재 m의 번지값을 넣는다. 10 : m을 1증가한다. 11 : m이 3보다 작은가? 작으면 아래를 수행 크거나 같다면 종료. (현재 m 은 3이다.)12 : 종료한다.
대략 12개의 명령어 Set으로 위의 코드가 진행됨을 알 수 있다.
자. 명령어를 줄여서 최적화를 해보자.
최적화를 한 코드는 아래와 같다.
pDes[0] = pSrc[0];pDes[1] = pSrc[1];pDes[2] = pSrc[2];
어떤가 전율이 오지 않는가? 12개의 명령어가 단순히 3개로 줄어들어버렸다. 뭐 억지라고 할 수 있겠지만, 어쨌거나 속도 최적화는 속도 최적화이다.
여기서 주목해야할 것은 조건분기 명령어를 없앴다는 것에 있다.
예전부터 조건 분기문은 일반 명령어보다 작게는 1 머신 사이클 내지, 일반 명령어의 사이클 수보다 두배 정도의 속도를 자랑해왔다.
왜냐하면 비교도 해야하고, 그것에 따라 분기도 해야하므로, 명령어 사이클 수가 일반 명령어보다 클 수밖에 없었다.
따라서 여기서 결론을 하나 내리도록 하자.
속도 최적화는 조건분기 명령어를 줄이는 것이 가장 효율적이다.
그럼 앞에 문제를 살펴보도록 하자.
void _NormalMemcpy(unsigned char * pDes, unsigned char* pSrc, unsigned long nCopySize){unsigned long m;
for(m = 0; m < nCopySize; m++) { pDes[m] = pSrc[m]; }}
자, 이 문제를 풀기 위해선 저 for문에 들어가 있는 조건 분기문의 수를 줄여야 한다.
nCopySize가 아까의 경우는 3으로 고정되어있었고, 현재는 변수이기 때문에 아까의 경우처럼 일일히 대입하여 해결할 수 없게 된다.
그래서 외국의 어떤 사람은 이걸 해결하기 위해 나눗셈의 원리를 이용하게 된다. 나눗셈의 결과는 언제나 몫과 나머지가 발생이 된다.
예를 들어 83을 8로 나누게 되면 몫은 10이고, 나머지는 3이 된다.
이 이야기는 83이라는 숫자는 8의 집합이 10개이고, 나머지는 3이라는 의미가 된다.
자 여기까지 이야기했을때 무릎을 탁 치시는 분들도 계실줄로 안다.
그렇다면 이 문제는 어떤 공통되는 특정한 명령어 집합으로 저 위에서 발생이 되는 명령어들을 집합으로 나누어서 처리하면 된다는 결론에 이르게 된다. (아.. 이건 역시 말이 어렵다. )
자, 이해를 돕기 위해 이제 실제 속도 최적화 된 코드를 보면서 이야기 하도록 하자. 아래의 코드가 속도 최적화된 코드이다.
보기엔 뭔가 이상하긴 하지만, 그래도 C, C++의 표준 문법을 준수하는 코드이다.
여기서 최적화 기법을 몇 개 더 사용했다는 것을 미리 이야기 한다.
1. 후행연산자보다 선행연산자가 더 빠르다.2. 나머지 연산자 % 대신 2, 4, 8, 16과 같은 (2의 승수 - 1)값을 &연산으로 나머지 구하는 것이 빠르다.3. while문보다는 do-while이 대체적으로 더 빠르며 융통성을 지닐 수 있다.
01 : void _FastMemcpy(unsigned char * pDes, unsigned char* pSrc, unsigned long nCopySize)02 : {03 : --pDes; --pSrc;04 : 05 : switch(nCopySize & 7)06 : {07 : case 0:08 : do {09 : *(++pDes) = *(++pSrc); --nCopySize;10 : case 7: *(++pDes) = *(++pSrc); --nCopySize;11 : case 6: *(++pDes) = *(++pSrc); --nCopySize;12 : case 5: *(++pDes) = *(++pSrc); --nCopySize;13 : case 4: *(++pDes) = *(++pSrc); --nCopySize;14 : case 3: *(++pDes) = *(++pSrc); --nCopySize;15 : case 2: *(++pDes) = *(++pSrc); --nCopySize;16 : case 1: *(++pDes) = *(++pSrc); --nCopySize;17 : }while(nCopySize);18 : }19 : }
여러분들이 의아하게 생각되는 부분은 아마도 swich문 안에 do - while문이 들어가 있기 때문일텐데..
switch문에 해당되는 것은 나머지를 처리하기 위한 코드이고, do-while문에 해당되는 것은 몫을 처리하기 위한 코드이다.
위의 알고리즘을 설명하자면 다음과 같다.
위의 코드는 해당 명령어 집합을 8개로 설정한다.
즉, 8개의 if문을 없애고, 8개만큼 일일히 대입한다는 의미이다.
그러기 위해서 나머지를 가장 먼저 처리한다.
05 : switch(nCopySize & 7) // == switch(nCopySize % 8)
이 라인은 다음과 같은 8로 나누었을때의 나머지를 구하는 것과 같은 의미이다. 즉, 나머지를 우선 구하고 해당 나머지에 해당되는 위치부터 do while문을 시작하게 된다. 만일 nCopySize 가 10이라면, 8로 나누었을때 나머지가 2이기 때문에
15 : case 2: *(++pDes) = *(++pSrc); --nCopySize;
15번 라인으로 점프하여 순환을 시작한다. break 문이 없으므로, 계속해서 아래로 수행이 된다. 결국 17번 라인을 만나게 된다.
17 : }while(nCopySize);
17번 라인은 nCopySize가 0이 라면 순환을 멈추고, 빠져나가게 되고, 0이 아니라면 08번 라인으로 점프하여다시 8번의 대입문을 수행하게 된다.
08 : do {
숫자로 설명하자면, 만일 nCopySize가 54이라면,
53 = 6*8 + 5 와 같고
최초의 swich문에서 나머지인 5개만큼의 대입문을 수행하고 그 이후에는 do-while문을 6번 수행하게 되는 것이다.
여기서 당신은 집합의 단위 갯수를 8이 아닌 16을 선택할 수도 있고, 32를 선택할 수도 있다.집합의 단위 갯수가 늘어날수록 분기연산자는 그만큼 줄어들긴 하지만, 코드의 사이즈가 증가된다는 것을 명심하기 바란다.
아무래도 Switch 문과 do-wihle문의 결합으로 혼돈이 되시는 분들은 코드를 약간 바꾸어서 보는것도 이해에 도움이 되리라 생각이 들어 코드를 스파게티 코드의 주범인 goto문을 초빙하여 약간 변형해보았다.
사람들은 의도적으로 goto 문을 잘 사용하지 않는데, 그 이유는 가독성이 떨어진다는 것에 있다. 하지만, goto문을 잘만 활용하면 "오호 이런 놀랄만한 방법이 있나?" 라는 말이 나올만큼 독창적인 코드가 나오기도 한다.
자 아래의 코드를 감상해보도록 하자.
01 : void _FastMemcpy(unsigned char * pDes, unsigned char* pSrc, unsigned long nCopySize)02 : {03 : --pDes; --pSrc;04 : 05 : if(nCopySize % 8 == 0)06 : {07 : goto Jump_0;08 : }09 : else if(nCopySize % 8 == 1)10 : {11 : goto Jump_1;12 : }13 : else if(nCopySize % 8 == 2)14 : {15 : goto Jump_2;16 : }17 : else if(nCopySize % 8 == 3)18 : {19 : goto Jump_3;20 : }21 : else if(nCopySize % 8 == 4)22 : {23 : goto Jump_4;24 : }25 : else if(nCopySize % 8 == 5)26 : {27 : goto Jump_5;28 : }29 : else if(nCopySize % 8 == 6)30 : {31 : goto Jump_6;32 : }33 : else if(nCopySize % 8 == 7)34 : {35 : goto Jump_7;36 : }37 : 38 : Jump_0:39 : do {40 : *(++pDes) = *(++pSrc); --nCopySize;41 : Jump_7:42 : *(++pDes) = *(++pSrc); --nCopySize;43 : Jump_6:44 : *(++pDes) = *(++pSrc); --nCopySize;45 : Jump_5:46 : *(++pDes) = *(++pSrc); --nCopySize;47 : Jump_4:48 : *(++pDes) = *(++pSrc); --nCopySize;49 : Jump_3:50 : *(++pDes) = *(++pSrc); --nCopySize;51 : Jump_2:52 : *(++pDes) = *(++pSrc); --nCopySize;53 : Jump_1:54 : *(++pDes) = *(++pSrc); --nCopySize;55 : }while(nCopySize);56 : }
위의 코드를 보면 swich문을 goto 문 8개로 변경시켜놓은 코드이다. 상당히 코드가 복잡해졌지만, 정규적인 코드만 보던 사람들에게는 위의 swich문을 적용한 코드보다는 더 쉬울것이다.
if - if else 문에서 점프할 곳을 찾게 되는데 이것이 바로 나머지를 처리하는 부분이고, do - while문으로 진입하게 되면, 그때부터는 몫을 처리하는 부분이 된다.
여러분들이 C문법을 최초로 배웠을때 swich문은 단일 조건 다중 분기문으로 배웠을 것이다. 그때 책에서는 혹은 강사가 아무런 이야기도 하진 않았겠지만, swich 문은 형식화된 goto 문에 불과 하다. 실제적으로 컴파일러에 의해 처리가 될때도 goto 문으로 취급된다는 것을 명심하기 바란다.
여담이지만 여기서 if - if else와 swich문의 차이는 무엇일까? 그것은swich문은 단일 조건 다중 분기문이고if - if else문은 다중 조건 다중 분기문이다.
언제나 기초체력은 중요하다. 라는 것을 명심하기 바란다.
여기까지 설명을 듣고, 호기심 많은 분들은 이미 프로파일링을 돌려가며 속도를 비교하실 분들이 계실 것이다.
그런 분들을 위해 미리 이야기 하자면,
개발 환경이 VC 2003 이상의 컴파일러(VC6의 경우에는 CPU 팩이나 플랫폼 SDK의 최신 버전을 설치되어있는 경우)와 XP 이상의 운영체제, 병렬 처리 명령이 포함되어 있는 프로세서를 갖추셨다면, Release모드에서는 위의 FastMemcpy 보다 memcpy가 훨씬 더 빠르다.
훨씬 빠른 정도가 아니라 어처구니 없는 속도차를 보여준다.
그 이유는 VC6버전일때 이미 MS에서는 CPU에서 제공되는 병렬 처리 명령어에 관련된 CPU 팩을 제공하여 단순한 반복 코드일 경우, 병렬 처리 명령어를 사용하여 한꺼번에 처리하도록 하게 했다.( 원래는 멀티미디어 관련 코드를 좀더 빠르게 하기 위해서 만든 명령어이고, 그걸 위해 구성된 레지스터 였지만, VC 컴파일러에서는 그 명령어들을 이용하여 단순 코드에 대해 속도 최적화하는데 사용한다. )
따라서 최적화 한답시고, 이런 저런 코드 집어넣고, 어셈까지 동원해봤자,아무 생각없이 간단한 구조로 반복시키는 코드를 짜는 사람들이 더 빠른 속도의 코드를 만들어 내게 되는 것이다.
그렇다면 Fast Memory Copy 알고리즘 내에서 분기문을 무작정 없앤다며, 집합의 수를 128, 256, 이렇게 커다란 값을 사용하면 어떻게 될까?
그렇게 해봤자, 속도 향상이 조금 늘 순 있겠지만, 대체적으로 집합의 수는 해당 CPU의 파이프 라인의 갯수 정도로 정하는 것이 좋다.
이 이유는 CPU의 파이프라인과 밀접한 연관을 갖고 있다. CPU가 발전을 거듭하면서, 명령어를 빠르게 실행시키기 위해 파이프 라인이란걸 도입하게 된다.
이것은 지금 수행할 명령어 다음의 명령어를 미리 패치하여 실행시켜놓는 것을 의미하는데, 쉽게 설명하면파이프 라인이 8개라면 8개의 명령어가 순차적으로 동시에 실행되는 것 처럼 보이게 된다.
이때 파이프라인의 최대 취약점은 역시 분기 명령어이다.
조건 분기 명령어가 패치가 되면 다음 명령어가 무엇이 올지 모르기 때문에 이후 파이프 라인이 비어있게 된다. 요새는 어떤 기법을 사용하는지는 모르겠지만, 최초로 파이프라인이라는 개념이 CPU에 적용이 될때는 이러한 문제 때문에 조건 분기를 최대한 억제하는 것이 속도 향상의 지름길이었다.
따라서 집합의 수를 파이프라인 수 만큼 결정한다면, 한 집합이 파이프 라인으로 패치되어 그나마 병렬처리되는 효과를 볼 수가 있을 것이다. (병렬 처리 명령어와는 개념이 다르다.)
궁금하다면 실제로 테스트 해보기 바란다. 집합의 수가 8, 16, 32, 64, 128, 256, 512로 증가됨에 따라 속도는 점점 더 빨라지긴 하겠지만, 가장 효율이 좋은 부분을 지나면 아주 조금씩 빨라지는 것을 발견하게 될 것이다.
자, 그럼 이걸 어디에 써먹어야 할까?
답은 간단하다.
컴파일러 옵션만으로 최적화 하기 힘든 반복문에 사용하면 된다. 그것도 아주 반복횟수가 많은 모듈에 사용하면 금상첨화이다.
실제로 필자의 경우 저 알고리즘을 FFT, MPEG2 및 이미지관련 Processing 관련 코딩을 할때 이용하였으며, 꽤 좋은 성능을 냈던 것으로 기억이 된다.
또하나 마이크로 컨트롤러 레벨로 내려가면, 컴파일러가 효율이 좋지 않기 때문에 기본적인 속도 최적화 밖에 못하는 수준이므로, 여전히 펌웨어에서는 속도최적화의 좋은 대안이 된다.
다만 펌웨어의 크기가 1k안에 코드를 짜넣어야 하는 식의 코드 크기에 제한이 있다면, 남은 프로그램 메모리의 크기에 따라 선택을 하도록 한다.
어쨌든 재미난 코드를 선사해준 이름은 기억이 나지 않는 외국 프로그래머에게 박수를 치면서 마치도록 하겠다.
그럼 이만
고임
ps.
박진홍님이 알려주신 원본 글에 따라 Counting 변수를 줄여서 최적화를 한번 더 거쳤습니다. 사실 이렇게 하면 변수를 하나 더 사용하는 것이 되버려.. 펌웨어 쪽에서는 안좋을 수도 있으니, 상황에 맞게 판단해서 사용하시기 바랍니다.
01 : void _FastMemcpy(unsigned char * pDes, unsigned char* pSrc, unsigned long nCopySize)02 : {03 : unsigned long nLoopCount = nCopySize;04 : 05 : if(!(pDes && pSrc && nCopySize)) {return ; }06 : 07 : --pDes; --pSrc;08 : nLoopCount >>= 3;09 : 10 : switch(nCopySize & 7)11 : {12 : case 0:13 : do {14 : *(++pDes) = *(++pSrc);15 : case 7: *(++pDes) = *(++pSrc);16 : case 6: *(++pDes) = *(++pSrc);17 : case 5: *(++pDes) = *(++pSrc);18 : case 4: *(++pDes) = *(++pSrc);19 : case 3: *(++pDes) = *(++pSrc);20 : case 2: *(++pDes) = *(++pSrc);21 : case 1: *(++pDes) = *(++pSrc);22 : }while(--nLoopCount);23 : }24 : }
출처 : http://www.devpia.com/MAEUL/Contents/Detail.aspx?BoardID=51&MAEULNO=20&no=8174&page=2