두 변수 값 바꾸기에 대한 고찰 by object

두 값을 교환하는 방법: http://monac.egloos.com/1240200

두 변수 값을 바꾸는 swap 함수는 C/C++ 언어를 배우면서 빼놓을 수 없는 함수 예제이다. 가장 간단하게 임시 변수 temp를 써서 하는 방법이 있다. 그러나 누구나 한번쯤은 temp 없이 두 변수 값을 바꿀 수 있을까라는 고민을 해보았을 것이다. 그래서 XOR를 이용한 방법 등이 고안되기도 하였다. 컴퓨터 구조를 모른 채, 일반적인 컴퓨터 상식으로 생각하면 temp 변수를 거치면 직접 메모리까지 갔다 와야 하므로 시간도 더 걸릴 것으로 생각할 수 있다. 그래서 temp 변수가 없는 XOR 버전이 더 빠를 것으로 생각할 수 있다.

간단하게 아래 코드를 가지고 어느 경우가 더 빠른지 실험을 해보자. 단순히 코드를 수 백만 번 돌려 시간 측정하는 것 보다는 실제 컴파일러가 만들어내는 코드를 가지고 파악해보고자 한다.
#include <stdio.h>
#define SWAP1(a, b) {int temp = a; a = b; b = temp;}
#define SWAP2(a, b) {a ^= b; b ^= a; a ^= b;}

void foo(int a, int b)
{
    SWAP1(a, b);
    printf("%d, %d\n", a, b);
}

void goo(int a, int b)
{
    SWAP2(a, b);
    printf("%d, %d\n", a, b);
}

int main(int argc, char** argv)
{
    int a, b;

    a = atoi(argv[1]);
    b = atoi(argv[2]);

    foo(a, b);
    goo(a, b);

    return 0;
}


컴파일러는 먼저 gcc 컴파일러를 가지고 최적화 옵션 –O3을 주었고, 또 다른 컴파일러로 VLIW용 컴파일러인 VEX 컴파일러를 이용하였다. 역시 최적화 옵션을 주었다. 들어가기에 앞서 간단하게 VLIW 컴파일러 및 일반적인 컴파일러의 차이점에 대해서 이야기를 해보자.

gcc 컴파일러는 일반적인 general-purpose CPU를 위한 컴파일러이다. 예를 들어, x86 위에서 돌아가는 gcc 컴파일러를 생각해보자. 아무리 인텔과 AMD CPU가 레지스터를 수십개, 백여개 이상 가지고 있더라도 컴파일러가 볼 수 있는 레지스터는 여전히 eax, ebx와 같은 제한된 레지스터들 뿐이다.

그런데 최근의 대부분의 CPU는 높은 성능을 위해 명령어 수준의 병렬성(Instruction Level Parallelism, ILP)을 찾는데, 일반적인 CPU들은 모두 하드웨어에서 그것을 알아서 처리하고 있다. 이른바 superscalar, out-of-order execution CPU들이다. 컴파일러는 하드웨어의 깊숙한 정보는 알지 못한다. 그래서 순차적인 코드만 만들어줄 수 밖에 없다. 그러면 그것을 하드웨어가 받아서 직접 수행 도중 동적으로 ILP를 찾아 수행한다. 그러기 위해서는 복잡한 하드웨어 장치가 필수이다.

반면, VLIW (Very Long Instruction Word)는 인텔 Itanium에서 사용된 것으로 유명하다 (Itanium은 EPIC이라고 VLIW에서 한 단계 발전된 형태이지만 여전히 기본 철학은 VLIW 위에 있다). VLIW의 핵심은 ILP를 하드웨어가 아닌 컴파일러가 미리 찾아서 컴파일을 해준다는 것이다. 그래서 일반적인 어셈블리와 달리 VLIW는 동시에 수행 가능한 명령어들을 묶어서 (‘묶음’이라는 한글 용어는 순전히 제가 생각해놓은 것으로 각 VLIW 구현 방식마다 모두 용어가 다름, Itanium IA-64에서는 template이라고 부름) 바로 CPU에게 전달한다. 그러면 CPU는 단순히 이것을 믿고 그대로 수행한다. 일반적인 펜티엄 CPU에서 볼 수 있는 out-of-order execution 작업 등은 필요치 않다. 그래서 하드웨어가 단순해질 수 있다는 장점이 있어서 최근 임베디드 환경에서 VLIW가 많이 쓰이고 있다. 이것을 위해 하드웨어는 가능한 모든 정보를 컴파일러에게 알려 주어야 한다. 사용 가능한 functional unit의 개수 및 각 명령어의 latency 등을 다 알려줘야 컴파일러가 그것에 맞게 스케줄링을 할 수 있을 것이다.

왜 VLIW 컴파일러를 이용했냐면 CPU에서 수행하는 병렬성 찾는 작업을 직접 컴파일러에서 하기 때문에 실제 저 코드에 내포되어있는 병렬성을 손쉽게 확인할 수 있기 때문이다. 일반적인 CPU에서는 이 과정이 모두 숨겨져있기 때문에 시뮬레이터를 사용하지 않는 이상 알아내기가 힘들다.

간단하게 VEX 컴파일러가 만들어내는 명령어 묶음은 아래와 같이 생겼다.
1:     add $r6 = $r5, $r4
2: sub $r7 = $r5, $r4
3: ;;
4: stw 0[$r14] = $r7
5: xnop 2
6: ;;
;;는 명령어 묶음의 끝을 뜻한다. 그래서 1, 2번에 있는 add, sub 연산이 동시에 처리 가능하다는 것을 말한다. 5번에서 xnop는 multi cycle no operation을 뜻하고 store 명령이 한 사이클 이상의 시간이 걸린다는 사실을 알기 때문에 명시적으로 nop를 넣어주는 것이다.


서론 끝. 이제 본론으로 들어가 직접 swap 코드를 자세히 살펴보자.
1: int temp = a;
2: a = b;
3: b = temp;
4: printf(a, b);
언뜻 보기에는 4 명령어가 순차적으로 실행되어야 할 것 같지만 전혀 그렇지 않다. 먼저, 1번과 2번에는 변수 a가 Write-after-Read (WAR) 의존성이 있다. 순차적으로 실행될 때는 아무런 문제가 없는 녀석인데, 2번 명령이 1번 명령보다 앞서 실행된다면 문제가 생긴다는 것을 쉽게 알 수 있다. 그런데, 이런 WAR 의존성은 false dependence라고 해서 register 이름을 바꿈으로써 간단히 해결할 수 있다. 즉, 2번 명령의 a를 a’로 바꾸면 1번과 2번 명령은 동시에 실행이 될 수 있다.
1: int temp = a; a’ = b;
2: b = temp;
3: printf(a’, b);
그리고 이 이후에 a를 사용하는 녀석들도 모두 a’로 바꿔주는 작업을 해야 한다. 실제 최신 일반 CPU는 모두 이런 작업을 CPU 내에서 자동적으로 하고 있다. 이른바 Out-of-order execution이며 이 과정을 통틀어 scoreboarding 알고리즘 혹은 Tomasulo’s 알고리즘이라고도 부른다. 또 다시 2번과 3번 사이에도 변수 b를 두고 WAR 의존성이 있다:
1: int temp = a; a’ = b;
2: b’ = temp;
3: printf(a’, b’);
이제 이 코드를 놓고 생각하면 temp는 필요가 없는 변수가 되었다:
1: a’ = b;
2: b’ = a;
3: printf(a’, b’);
결국, 아주 똑똑한 컴파일러라면 그냥 바로:
1: printf(b, a);
를 만들어 낼 수가 있다. 즉, register renaming으로 원래 코드에 존재했던 WAR 의존성만 제거하니 이렇게 간단하게 축약이 됨을 알 수 있다.


반면에, XOR을 경우를 보면:
1: a = a ^ b;
2: b = b ^ a;
3: a = a ^ b;
4: printf(a, b);
위의 예와 같이 1번과 2번 사이에 역시 b를 두고 WAR 의존성이 있지만 이 보다는 a때문에 벌어지는 Read-after-Write가 더 심각하다. RAW는 register renaming으로 결코 풀 수 없으며 반드시 순차적으로 실행되어야 한다. 그래서 얘는 true dependence로 불린다. 물론 매우 빡시게 data speculation이라는 방법으로 미리 값을 예측하고 실행하는 방법도 있다. 마찬가지로 2와 3 사이에도 RAW가 있으므로 역시 동시에 실행시킬 수가 없다. 결국, XOR 버전은 최적화를 하지 못하고 주어진 대로 수행해야 한다. 물론 gcc 컴파일러에서 –O3을 주니까 최적의 코드로 바뀌기는 하지만 이 경우에는 보다 특수한 패턴을 찾아 최적화를 하는 것 같았다.


이제 VLIW 컴파일러인 VEX로 컴파일 해보자. 최적화 옵션은 –O3을 주었으며, 주어진 코드에는 loop가 없으므로 사실 상 –O1과 다른 바가 없다. 참고로 –O는 각 컴파일러마다 그 의미가 다르니까 gcc의 그것과 매칭 시켜서는 안 된다.
[minjang@mikkeli bin]$ ./cc -S -O4 temp.c
먼저, 일반적인 temp를 이용한 foo 함수를 살펴보자. 어셈블리 자체가 주석이 친절이 달아져 있어서 이해하기가 쉽다. (앞에 1: ~ 19: 문 번호는 내가 직접 입력한 것임)
1: .proc
2: .entry caller, sp=$r0.1, rl=$l0.0, asize=-32, arg($r0.3:s32,$r0.4:s32)
3: foo::
4: .trace 1
5:     c0    add $r0.1 = $r0.1, (-0x20)
6:     c0    mov $r0.5 = $r0.3
7: ;;                              ## 0

8: .call printf, caller, arg($r0.3:u32,$r0.4:s32,$r0.5:s32), ret($r0.3:s32)
9:     c0    call $l0.0 = printf
10:    c0    mov $r0.3 = (_?1STRINGPACKET.1 + 0)
11:    c0    stw 0x10[$r0.1] = $l0.0
12: ;;                              ## 1
13:    c0    ldw $l0.0 = 0x10[$r0.1]
14:          xnop 3
15: ;;                              ## 5
16: .return ret()
17:    c0    return $r0.1 = $r0.1, (0x20), $l0.0
18: ;;                              ## 6
19: .endp
먼저, 2번째 줄을 보면 함수의 인자는 $r0.3과 $r0.4를 통해 전달 되고 있다. 즉, $r0.3이 a, $r0.4가 b라는 것을 알 수 있다. s32는 signed 32-bit int임을 쉽게 짐작할 수 있다. 그리고 레지스터 이름에 $r0.과 같은 일종의 접두어가 붙는데 이것은 VLIW의 clustering이라는 개념에서 나온 것이다. 그리고 실제 명령어 앞에도 c0라는 cluster specifier가 있는데, 이번 경우에는 모두 같은 클러스터 내에서만 일어나므로 사실 상 의미는 없다. 그냥 무시해도 이해하는데 문제 없다.

첫 번째 명령어 묶음부터 살펴보자. 5번째 라인에서 $r0.1에 숫자를 더 하고 있다. 그리고 $r0.1은 2번 줄을 보면 이것은 sp, 즉 stack pointer임을 알 수 있다. 따라서 이 과정은 스택을 20바이트만큼 할당해주는 과정이다. 그리고 함수가 종료될 때 다시 이 스택을 정리하고 있음을 역시 확인할 수 있다 (17번째 줄).

6번째에서는 a가 저장되어있는 $r0.3를 임시 변수 temp에 해당하는 $r0.5로 복사하고 있다. 주어진 코드 그대로 번역된 셈이다. 이 두 명령이 동시에 실행 가능하고 한 사이클이면 종료가 된다. 7번 줄에서 ;;로 끝남을 확인.

8번 줄에는 이제 함수를 부를 때 인자와 리턴 값이 어떻게 저장되는지를 친절히 말해주고 있다. $r0.3에는 printf의 첫 인자인 스트링 문자열이 들어가고 있다. 그런데, printf의 두 번째 인자였던 a가 바로 b가 저장되어있는 $r0.4로 치환되어있음을 확인할 수 있다. 컴파일러가 최적화를 해준 것이다. 그리고 printf의 세 번째 인자가 되어야 할 b에는 이제 a값을 들고 있는 $r0.5가 들어감을 알 수 있다. 보다시피 전혀 store/load가 없어 당연히(?) 메모리까지 가는 일은 없고, 임시 레지스터 $r0.5 하나만 더 사양하고 있다.

나머지 10번 줄 이후는 큰 설명이 필요 없다. 그래도 설명을 하자면, 10번 줄에서 문자열을 로딩하고 있다. 사실 여기도 미묘하게 할 말이 있다. 9~11번 줄의 명령은 동시에 실행이 된다. 그러나 10번에서는 $r0.3이 값이 저장될 destination인 동시에, 이 $r0.3은 printf의 인자로 다시 읽혀지는 source 역할을 한다. 그래서 이 경우 $r0.3의 값을 기존의 값을 읽어야 하는지 아니면 parallel write 즉, 같은 명렁어 묶음에 있는 녀석으로 할 것인지를 결정해야 한다. 이 경우에는 후자의 경우를 채택한 것으로 생각할 수 있다.

그리고 11번 과정은 caller saved register를 저장하는 과정이다. 함수 호출 시, 함수 내에서 아마 $r10.0이라는 녀석은 마음대로 쓰는 것으로 약속되어있는 것 같다. 그래서 함수 부르기 전에 내가 직접 보관했다가 함수 호출이 끝난 뒤 다시 복구 하고 있다 (13번 째 줄). linker register를 함수 호출하기 전 스택에 저장하고 다시 복구 하는 과정이다 (13번째 줄). 그리고 load는 3 cycle이 걸리므로 xnop 3 (multicycle no-operation)을 부르고 있다.

결국 프로그램으로는 분명 temp라는 변수를 잡아두었지만 실제 최적화된 컴파일 코드에는 그것을 찾아 볼 수 없었다. 실제로 완벽하게 printf(b, a) 꼴까지는 만들어지지 않았지만:
1: temp = a;
2: printf(b, temp);
까지는 만들어내었다. 어쨌든 store/load가 없으므로 임시변수를 아무리 하이레벨 언어에서 써도 메모리에 갔다오는 삽질 없이 빠르게 실행됨을 알 수 있다.


이제는 XOR을 이용한 goo 함수를 보자.
1: .proc
2: .entry caller, sp=$r0.1, rl=$l0.0, asize=-32, arg($r0.3:s32,$r0.4:s32)
3: goo::
4: .trace 1
5:     c0    add $r0.1 = $r0.1, (-0x20)
6:     c0    xor $r0.3 = $r0.3, $r0.4
7: ;;                              ## 0
8:    c0    xor $r0.5 = $r0.4, $r0.3
9:    c0    stw 0x10[$r0.1] = $l0.0
10: ;;                              ## 1
11: .call printf, caller, arg($r0.3:u32,$r0.4:s32,$r0.5:s32), ret($r0.3:s32)
12:    c0    xor $r0.4 = $r0.3, $r0.5
13:    c0    call $l0.0 = printf
14:    c0    mov $r0.3 = (_?1STRINGPACKET.2 + 0)
15: ;;                              ## 2
16:    c0    ldw $l0.0 = 0x10[$r0.1]
17:           xnop 3
18: ;;                              ## 6
19: .return ret()
20:    c0    return $r0.1 = $r0.1, (0x20), $l0.0
21: ;;                              ## 7
22: .endp
다른 부분은 비슷하니 생략하고 핵심이 되는 교환 부분을 살펴보자:
6:    c0    xor $r0.3 = $r0.3, $r0.4   ## bblock 0, line 15,  t6,  t0,  t3
8:    c0    xor $r0.5 = $r0.4, $r0.3   ## bblock 0, line 15,  t13,  t3,  t6
12:   c0    xor $r0.4 = $r0.3, $r0.5   ## bblock 0, line 15,  t12,  t6,  t13
보듯이 고스란히 번역되었음을 볼 수 있다. 그리고 이 세 XOR 명령은 모두 RAW를 서로 가지고 있어서 각기 다른 사이클에서 실행되고 있다. 결국 temp를 사용한 버전보다 더 많은 시간이 소요됨을 알 수 있다.

마지막으로 각각의 버전에서 소요되는 cycle을 계산하면 temp 버전은 7 사이클인데 비해, XOR 버전은 8사이클이 걸린다. 물론 각 명령이 모두 1싸이클만에 완료된다는 가정이 있어야 한다. 그러나 이 예제에서 레지스터-레지스터 이동이나 단순한 정수 연산은 모두 1사이클에 완료할 수 있다. 여기서 한 사이클 그러니까 1Hz 까지고 너무 인생 쪼잔하게 살지 맙시다 라고 하시면 뭐 솔직히 할 말은 없어요. 그런데 한 사이클이라도 아끼는 것이 컴퓨터 공학이 추구하는 목적이니까 충분히 가치가 있는 이야기입니다.

그러나, gcc를 가지고 –O3으로 테스트 해보니 결과는 사뭇 달랐다. foo/goo 두 함수 모두 똑 같은 내용이 생성이 되었다. –O3이 아닌 –O2로 주었을 때는 약간 다른 점이 발견 되기는 하였다.

foo:
.LFB12:
    movl    %edi, %edx
    xorl    %eax, %eax
    movl    $.LC0, %edi
    jmp printf
.LFE12:
goo도 이와 완벽히 똑 같은 코드가 만들어졌다. 나의 능력으로는 해석하기 좀 불가능하다… 어쨌든 gcc는 이러한 경우를 대비해 많은 최적화 루틴을 두었음을 짐작할 수 있다.


요약을 하면 실험에서 사용한 VLIW 컴파일러에서는 temp 방식을 쓰는 것이 한 사이클을 더 아끼는 것으로 나왔다. 반면, gcc에서 최적화를 시켰을 경우 두 코드는 완전히 동일하게 나왔다. 이것은 CPU 한 사이클이라도 아껴야 하는 높은 성능이 요구되는 프로그램을 짤 때는 target platform에 대한 지식이 풍부해야 한다는 것을 말하고 있다. 결론은 공부합시다.

한번도 XOR 스왑 방식의 성능에 대해서 생각해보지 않았는데 살펴보니 의외의 결과를 얻어서 재밌네요. 혹시 이상한 점이나 궁금한 점은 언제든지 질문 환영입니다.

핑백

덧글

  • Gerald 2007/06/05 17:00 # 답글

    '결론은 공부합시다' 이거 맘에 듭니다 ^^ 잘 보고 갑니다.
  • abraxsus 2007/06/06 09:33 # 삭제 답글

    훌륭하다..ㅋㅋ
  • object 2007/06/06 13:36 # 답글

    저기 7사이클 8사이클 이건.. 어디까지 메모리 연산은 3사이클이 걸린다 뭐 이런 가정에 기반해서 얻어진 값입니다.
  • 2011/04/20 23:15 # 삭제 답글 비공개

    비공개 덧글입니다.
  • ㄷㄷ 2014/03/04 23:16 # 삭제 답글

    void swap( char* a, char* b);
    이런식의 함수라면 어떨까요?
    다른 결과가 나올 것 같은데요
  • 김민장 2014/03/05 02:34 #

    아마 포인터 참조(dereference)가 들어가면 더 어렵죠. char* a, char* b가 서로 겹칠 수가 있거든요. 만약 C99 같은 것의 restrict가 있어 포인터, a, b가 서로 겹치지 않는다면 제가 이야기한 결과와 같은 결과가 나와야 합니다. (컴파일러가 똑똑하다면)
  • 누아니 2016/03/13 00:49 # 삭제 답글

    [XOR swap 알고리즘] 위키백과에서 링크 타고 넘어온 공대생입니다. 내공이 모자라 모르는 단어들이 많았지만 재미있는 글이었습니다. 감사합니다.
댓글 입력 영역