yuchi's development

얼마전 Visual C++ MVP모임에 나갔다가 임시변수 없이 두 변수의 내용을 맞바꾸는 기법에 대한 애기가 나왔다.

바로 xor로 바꾸는 방법이 거론됐다.

이 내용을 전혀 모르는 분들이 계실지 모르니 잠깐 설명을 하자면..

A,B두 변수가 있다.

C = A^B이다. (xor연산자는 C에서 ^로 쓴다. 따라서 ^로 표기한다.)

이때 A^C = B이다. 또한 B^C = A이다.

그러니까 아래와 같다.

C = A^B

B = A^C

A = B^C

A^B를 xor mask라 하자. 이것을 B에 xor하면 A가 나오고 A에 xor 하면 B가 나온다.

이것은 다음과 같이 줄일 수 있다.

A ^= B     // (A = A^B <- A와 B의 xor mask

B ^= A    // B = B^(xor mask) 따라서 B는 A가 된다.

A ^= B    // A = (xor mask)^B , B는 A가 되었으므로 A = xor mask ^ A , 따라서 A는 B가 된다.

못믿겠으면 간단하게 실험해보자.

A = 10(이진수)

B = 01(이진수)

xor mask =

A^B =

10 ^ 01 = 11 <- xor mask

A ^ xor mask = 10 ^ 11  = 01 <- B

B ^ xor mask = 01 ^ 11 = 10 <- A

A와 B가 깔끔하게 바뀌었다.

하여간 대화 끝물에 xor로 교환하는 것이 임시변수를 만들어서 교한하는것보다 느리다는 얘기가 나왔다.

그럴리가..라고 생각했다. 펜티엄 133에서 펜티엄200 시절에 스프라이트 클리핑 할때 정말 많이 써먹었다. 클럭 측정해가면서 테스트했었는데 그땐 확실히 더 빨랐다.

그래서 간단하게 코드를 작성하고 성능 테스트를 해봤다.

배열 A와 배열 B에 100만개의 숫자를 넣는다.

100만개의 원소를 순회하며 A > B일 경우 두 변수의 값을 교환해서 A <= B가 되도록 만든다.

4가지 함수를 작성했다.

1. C로 작성. A>B인 경우 temp = A;  B = A;  A = temp; 로 교환
2. C로 작성 A>B인 경우 xor로 교환
3. x86 inline Assembly로 작성. xor로 교환하되 cmp명령 수행후 CF(캐리 플래그)의 상태를 이용, xor마스크를 살려두거나 0으로 만드는 방법으로 점프 없이 교환or교환하지않음 으로 처리.
4. x86 inline Assembly로 작성. xor로 교환하되 cmp명령 수행후 A<B인 경우 jle로 점프.

테스트 결과는 다음과 같다.

1. CmpAndSwap – 3824 micro seconds.
2. CmpAndSwapXOR_C – 3763 micro seconds.
3. CmpAndSwapXOR_ASM_NO_JMP – 1866 micro seconds.
4. CmpAndSwapXOR_ASM_JMP – 5353 micro seconds.

결과적으로 xor교환은 빠르지 않았다. C로 작성했고 임시변수를 이용해서 값을 교환한 1번이 xor을 사용한 4번보다 빠르고 2번보다 약간 느린데 거의 비슷하다.

3번은 유독 빠르게 나오는데 이것은 xor때문이라기보다  branch prediction이 실패하지 않기 때문으로 보인다. 점프를 전혀 하지 않기 때문에 branch prediction 실패할 이유가 없다.

재밌는 것은 A배열의 숫자가 무조건 B배열의 숫자보다 크게 해서 교환이 항상 일어나게 하거나, A배열의 숫자가 무조건 B배열의 숫자보 작게해서 교환이 항상 안일어나게 하면 분기 및 점프를 하는 함수들이 더 빠르다.

이 경우 항상 같은 어드레스로만 분기를 하기 때문에 분기예측 유닛이 거의 100% 다 맞추기 때문인걸로 보인다. 무분기 코드의 경우는 분기예측이 실패할 일은 없지만 모든 경우에 항상 일정 이상의 코드를 실행해야한다.

하여간 그러니까 결론은 이렇다.

1. xor치환은 안빠르다. -_-;
2. 무분기 코드는 성능상에서 효과가 있다.
3. 무분기 처리는 다음과 같이 한다.

테스트 해보고 싶은 분은 bitbucket주소를 링크하니 받아서 돌려보시라.