[c언어]xor swap 알고리즘을 배열에 적용시 문제점
글쓴이: zeroxy / 작성시간: 화, 2011/01/11 - 10:57오전
배열에 대해 xor swap 알고리즘을 적용 했을 때
하나의 값이 0으로 바뀌는 문제가 발생했습니다.
#include <stdio.h>
int main(void)
{
int a[2]={1,2};
printf("%d %d\n",a[0],a[1]);
a[0]^=a[1]^=a[0]^=a[1];
printf("%d %d\n",a[0],a[1]);
return 0;
}[user1@centos cprog]$ gcc test.c
[user1@centos cprog]$ ./a.out
1 2
0 1
왜 이런 문제가 발생할까요?
변수 2개를 선언해서 사용 할 때는 잘 되는데 배열에 대해서 적용하니 안되는것이 궁금합니다.
Forums:
변수든 배열이든 ^=를 한 줄씩 쓰세요.
그리고 과거 스레드입니다. 참고하시길..
http://kldp.org/node/104634
----------------------------------------------------------------------------------------
Don't Feed the Trolls!
----------------------------------------------------------------------------------------
gcc 문제인듯이요.
gcc version 4.4.5 (Ubuntu/Linaro 4.4.4-14ubuntu5)의 경우 -O2 -O3 -Os에서는 문제 없으나 -O0에서 문제 발생하는군요. -O0에서 대충 이런 코드가 생성이 되는군요. gcc말고 제가 쓰는 다른 컴파일러는 문제가 없는듯.
tmp = a[1];
a[0] = a[0] ^ a[1];
a[1] = a[1] ^ a[0];
a[0] = tmp ^ a[1];
한줄로 안쓰고 그냥 풀어 쓰면 문제 없어요.
a[0]^=a[1];
a[1]^=a[0];
a[0]^=a[1];
토픽에는 벗어났습니다만,
토픽에는 벗어났습니다만,
단순히 임시변수를 이용하는 방법보다
xor 연산을 해서 swap 하는 것이 더 효율적일까요...?
적어도 세번의 연산과 세번의 할당을 해야하는데,
임시변수를 만들지 않는다는 점만이 유일한 장점아닐까요?
xor 연산은 일단 cost 가 minimum 에
xor 연산은 일단 cost 가 minimum 에 가까운 연산입니다. + 나 * 같은 연산과는 다르죠.
assign 도 register 에만 assign 한다면 상당히 cost 가 낮습니다.
간단한 32bit int 를 32bit cpu 계열에서 swap 한다고 할때, 임시변수를 만들면,
1. register 를 하나 더 쓰거나 memory access 를 더 해야합니다. memory access 는 일단 단순한 경우는 발생하지 않으므로 제외하겠습니다. memory access 가 발생하면 무조건 더 느리니까요.
2. 임시변수를 만들어도 assign 은 3회를 해야합니다. ( temp = a; a = b; b = a; )
따라서 3번의 assign 은 어차피 같은 비용이 듭니다.
위의 내용을 전부 배제하면, 결국 3번의 xor 이 cost 가 쎄냐 임시 변수를 만드는 비용이 쎄냐 만 남게 되는데 compiler 의 최적화 입장에서 보면 register 한개의 여부가 치명적일때도 있고 아닐때도 있습니다.
따라서 문맥이 길어지는 경우 즉, int swap 이 inline 함수라면, 이경우 xor 연산이 cost 가 더 낮을 가능성이 꽤 높아집니다.
추가로 swap 한 변수에 연산을 추가로 하게 된다면 더더욱 최적화 될 가능성이 높아집니다. ( 레지스터 1개가 비므로 )
거기에 cache 등등을 따진다면 더더욱 복잡해 집니다.
결국 상황에 따라 선택해서 잘 써야하는게 옳겠지만, xor 3회는 무시해도 될 정도로 정말 아주아주 낮은 cost 이기 때문에 상당히 gain 을 얻을 수 있는 가능성이 높다고 할 수 있겠지요.
Neogeo - Future is Now.
하지만 실제로 해보면 임시변수를 쓰는게 살짝 더 빠릅니다
결국 xor을 쓴다고 해도 데이터 의존성때문에 파이프라이닝이 잘 되지 못합니다. 실제 레지스터간의 값을 옮기는 것도 파이프라인수준에서는 xor연산보다 코스트가 더 든다고 말하기 힘들고요.
관련링크 및 설명
실질측정자료
http://dna.daum.net/technote/ccpp/CPPSwap
임시변수와 대입 세번을 할 경우 최적화방법
http://en.wikipedia.org/wiki/Register_renaming
활용가능한 register가 두개가 있을경우 다음과 같이 생각할 수 있습니다.
Memory에서 register로 불러들이는 연산을 고려하게 되면 XOR을 활용하는 것은
Memory load 2번, xor 3번, memory store 2번
만일 register renaming을 하게 되면 임시변수와 대입 세번은
Memory load 2번, memory store 2번
VLIW compiler와 함께 이를 설명하고 있는 것으로 다음 링크가 있습니다.
http://minjang.egloos.com/1241820
위에서는 GCC가 XOR 방법과 임시변수 활용법 모두 같은 code를 생성했다고 하네요.
마지막으로
http://en.wikipedia.org/wiki/Swap_(computer_science)
위에서 swap과 관련된 추가 설명을 볼 수 있습니다.
결국 이정도 level의 최적화는 C언어 level에서 설명할 수 없다고 보는 것이 맞을 겁니다.
공간과 시간 둘다 말입니다.
그냥 실측을 해서 대조해보는 수 밖에 없으며, 일반화는 하지 않는 것이 좋을 것 같습니다.
c언어 자체의 제약 아닌가요??
저도 표준을 찾아보지는 않았지만 한 statement안에서 같은 변수의 값을 두번 바꾸는 행위는 정의되지 않은 동작으로 알고 있습니다. 이것때문일듯 하네요.
댓글 달기