[C] 메모리 Swap 어떤 알고리즘이 제일 빠를까?

C언어 뿐만아니라 어떠한 언어든지

변수에 있는 값을 교환하는 일은 적지 않다.

기본적으로 int 자료형 변수 두개의 값을 교환하는 함수는 다음과 같다.

    void swap(int* one, int* other){
       int temp = *one;
       *one = *other;
       *other = temp;
    }

아주 간단한거니 설명은 필요없다.

이것을 제네릭하게 구현을 한다면

    void swap(void* one, void* other, size_t size){
       void* temp = malloc(size);
       memcpy(temp, one, size);
       memcpy(one, other, size);
       memcpy(other, temp, size);
       free(temp);
    }

C는 C++ 과 달리 템플릿이 없으므로, 제네릭한 함수를 구현하려면 void* 나

재정의 자료형방법을 사용하여야 한다.

자료형의 크기를 알수 없으니 크기도 같이 받고 크기만큼 임시변수를 할당하고, memcpy 함수를 통해 값을 교환한다.

그러면 임시변수를 만들지 않고 값을 교환하는 방법을 알아보자

    void swap(int* one, int* other){
     *one ^= *other;
     *other ^= *one;
     *one ^= *other;
    }

위의 함수는 xor 비트 연산의 특징을 이용한 것이다.

변수 a에 b를 xor 하면 c 가 나온다고 하자. 이때 c에 b를 xor 하면 a가 다시 나온다.

간단한 암호화 복호화 정도로 이해하면 된다.

여기서 중요한건 이런 자잘한 설명이 아니라

어떤 방법이 더 효율적인가? 이다.

당연 제네릭한 방법은 제외한다.

일반적인 설명은 다음과같다.

xor을 이용한 스왑은 메모리가 부족할시 사용(ex.임베디드시스템)

속도는 상황마다, 메모리 크기마다 다르다.

int형 변수로 10000000번을 swap 하면

temp 방법과 xor 방법의 시간차가 거의 없다.

long long형 변수로 하니 xor가 확실히 느렸다.

xor 가 더 느린 이유를 알고 가야한다.

사실 xor는 정수형 변수에만 사용이 가능하다.

(자료형을 속여서 사실 어떠한 변수나 객체던 xor 스왑이 가능하다)

그 이유는 temp 방법은 대입연산만 3번 들어가게 된다.

그런데 xor 방법은 대입연산은 마찬가지로 3번인데 , 추가적으로

xor연산도 3번 들어가게 된다. 이 근소한 차이로 인해

반복시간측정을 하였을때 시간차이가 나는 것이다.

Q1. 아주 큰 구조체나 객체를 swap 해야하는데 메모리가 부족합니다. 어떻게 해야하나요

객체를 xor로 swap 해야한다.

    void swap_xor(void* one, void* other, size_t size) {
       char* cone = (char*)one;
       char* cother = (char*)other;
       char* end = cone + size;
       char temp;
       while (cone != end){
          temp = *cone;
          *cone = *cother;
          *cother = temp;
          cone++;
          cother++;
       }
    }

소스에 주석이 있으니 이해하는것은 쉬울것이다.

그보다 구조체 또는 객체의 패딩에 관해 이야기를 좀 하자면,

기본적으로 4바이트 단위로 패딩이 되고, 이를 수정하려고

보통 #pragma pack(1) 와 같이 전처리기 키워드를 적을텐데,

절대 이렇게 해서는 안된다. 왜냐하면 저 전처리문은 저 줄 밑으로부터 컴파일하는 모든 객체의 패딩을 바꾸기 때문이다.

즉 인클루드에 의존성이 생길 가능성이있다.

그러므로 반드시 push로 패딩을 지정후 구조체를 선언한다.

그후 pop으로 다시 본래의 패딩값으로 돌려놓는 방식을 사용해야한다.

--------------------------APPEND------------------------------------------

사실 swap을 구현함에 있어 제일 빠른 swap은 define SWAP 이라고 생각하였다.

나는 4가지방법의 swap 함수를 생각해내었고

그에 따라 성능 측정을 해보았다.

**성능측정을 할 때는, 반드시 같은 프로세스에서 N번이상을 수행한후, 평균을 내야한다.

**처음 수행되는 프로시저의경우 수행시간이 약간 늦게 측정될 수 있다.

    #define SWAP(A,B,TYPE) do{TYPE t=(A);(A)=(B);(B)=t;}while(0)
    void swap_memcpy(void* one, void* other, size_t size) {
     void* temp = malloc(size);
     memcpy(temp, one, size);
     memcpy(one, other, size);
     memcpy(other, temp, size);
     free(temp);
    }
    void swap_char(void* one, void* other, size_t size) {
     char* cone = (char*)one;
     char* cother = (char*)other;
     char* end = cone + size;
     char temp;
     while (cone != end){
      temp = *cone;
      *cone = *cother;
      *cother = temp;
      cone++;
      cother++;
     }
    }
    void swap_xor(void* one, void* other, size_t size) {
     char* cone = (char*)one;
     char* cother = (char*)other;
     while (size--){
      *cone ^= *cother;
      *cother ^= *cone;
      *cone ^= *cother;
      cone++;
      cother++;
     }
    }

위 4가지 함수들을 임의의 구조체 Z에 대해 swap 테스트를 하였다.

swap count 만큼 swap함수를 실행한다.

이를 50번한다음 평균 시간을 계산한 것이다.

DEBUG 모드에서는 define swap 과 char[] swap이 비슷한 속도를 보였다.

xor swap역시 빠르나 앞의 두 함수에 비해 이득이 없다.

void* temp 를 이용한 swap 은 거의...사용이 불가능할정도로 느리다.

사실 C로 제네릭한 구현에 있어 void*를 쓴다고 하는데..

이제 보니 void* 는 답이 아닌거같다.

linux kernel의 list도 그렇고, swap도 그렇고 void*를 단순히 주소를 받는데만 사용하지

이를 이용해 구현하는순간 속도는 보장하지 못하게 된다.

어쨋든 RELEASE모드에서 좀 색다른 결과가나오는데, define swap의 경우 최적화를 못하는건지, 매우 느려진다.

더 좋은 swap 이 있으면, 추가로 포스팅 하겠다.