C에서 값을 교환하는 가장 빠른 방법은 무엇인가?

C에서 값을 교환하는 가장 빠른 방법은 무엇인가?

두 개의 정수를 교환하고 싶고, 다음 두 가지 구현 중 어떤 것이 더 빠를지 알고 싶다.온도 변수를 사용하는 확실한 방법:

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

또는 대부분의 사람들이 본 xor 버전:

void swap(int* a, int* b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

첫 번째는 여분의 레지스터를 사용하는 것처럼 보이지만, 두 번째 것은 세 개의 로드와 상점을 하는 반면 첫 번째는 각각 두 개만 하는 것이다.누가 나에게 어떤 것이 더 빠르고 왜 그런지 말해줄 수 있니?왜 더 중요한지.

2번은 종종 그것을 하는 "깨끗한" 방법으로 인용된다.사실 그것은 프로그래머의 명시적인 목표를 모호하게 하기 때문에 두 변수를 교환하기 때문에 더 느릴 가능성이 높다.이는 컴파일러가 실제 조립자 ops를 사용하여 스왑할 수 있도록 최적화할 수 없다는 것을 의미한다.또한 객체에 대해 약간 현명하게 xor를 수행할 수 있는 능력을 가정한다.

1번을 고수해, 가장 일반적이고 가장 이해할 수 있는 스왑이며 쉽게 템플화/제너럴화될 수 있다.

이 위키백과 섹션은 이 이슈들을 꽤 잘 설명한다: http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice

a와 b가 동일한 주소를 가리키면 XOR 방법이 실패한다.첫 번째 XOR는 두 변수 모두 가리키는 메모리 주소의 모든 비트를 지우므로, 일단 초기 값에 관계없이 함수가 (*a == *b == 0)을 반환하면 된다.

Wiki 페이지: XOR 스왑 알고리즘에 대한 추가 정보

비록 이 문제가 나올 것 같지는 않지만, 나는 항상 예상하지 못한 순간에 실패하는 영리한 방법이 아니라, 효과가 보장된 방법을 사용하는 것을 선호한다.

현대적인 CPU 아키텍처의 경우 방법 1은 방법 2보다 가독성이 높을 뿐만 아니라 더 빠를 것이다.

현대의 CPU 아키텍처에서 XOR 기법은 스와핑을 하기 위해 임시 변수를 사용하는 것보다 상당히 느리다.한 가지 이유는 현대 CPU가 명령 파이프라인을 통해 병렬로 명령을 실행하려고 하기 때문이다.XOR 기법에서는 각 연산에 대한 입력은 이전 연산의 결과에 따라 달라지기 때문에 엄격히 순차적으로 실행해야 한다.효율성이 매우 중요한 경우, XOR 기법과 대상 아키텍처에서 일시적인 변수 스와핑의 속도를 모두 시험하는 것이 좋다.자세한 내용은 여기를 참조하십시오.

---

편집: 방법 2는 추가 변수를 사용하지 않고 인플레이스 스와핑하는 방법이다.이 질문을 완료하려면 다음 작업을 수행하여 다른 인플레이스 스와핑을 추가하십시오.+/-.

void swap(int* a, int* b)
{
    if (a != b) // important to handle a/b share the same reference
    {
        *a = *a+*b;
        *b = *a-*b;
        *a = *a-*b;
    }
}

최신 프로세서에서 대형 어레이를 정렬할 때 다음을 사용할 수 있으며 속도 차이는 없다.

void swap (int *a, int *b)
{
  for (int i = 1 ; i ; i <<= 1)
  {
    if ((*a & i) != (*b & i))
    {
      *a ^= i;
      *b ^= i;
    }
  }
}

너의 질문에서 정말 중요한 부분은 '왜?' 부분이야.이제 20년 전 8086일로 거슬러 올라가면 위와 같은 것이 진정한 퍼포먼스 킬러였을 테지만, 최근 펜티엄에서는 당신이 올린 두 사람에게 있어서 매칭 스피드가 현명한 것이 될 것이다.

그 이유는 순전히 메모리에 달려 있으며 CPU와는 아무런 관련이 없다.

메모리 속도에 비해 CPU 속도는 천문학적으로 높아졌다.메모리 액세스는 애플리케이션 성능의 주요 병목 현상이 되었다.모든 스왑 알고리즘은 메모리에서 데이터가 가져오기를 기다리는 데 대부분의 시간을 할애할 것이다.최신 OS는 최대 5가지 수준의 메모리를 가질 수 있다.

• 캐시 레벨 1 - CPU와 동일한 속도로 실행되며 액세스 시간이 거의 없지만 작음
• 캐시 레벨 2-L1보다 약간 느리게 실행되지만 더 크고 액세스할 수 있는 오버헤드가 더 크다(일반적으로 먼저 데이터를 L1로 이동해야 함)
• 캐시 레벨 3 - (항상 존재하는 것은 아님) CPU 외부, L2보다 느리고 큰 경우가 많음
• RAM - 주 시스템 메모리는 일반적으로 읽기 요청이 지연되도록 파이프라인을 구현함(CPU는 데이터 요청, RAM은 메시지 전송, RAM은 데이터 가져오기, RAM은 CPU로 데이터 전송)
• 하드 디스크 - RAM이 충분하지 않을 때 데이터가 HD로 페이징되며, 이는 실제로 CPU 제어 하에 있는 것이 아니다.

정렬 알고리즘은 대개 매우 질서 없는 방식으로 메모리에 접근하기 때문에 메모리 액세스를 더 나쁘게 만들 것이며, 따라서 L2, RAM 또는 HD에서 데이터를 가져오는 비효율적인 오버헤드가 발생한다.

따라서 스왑 방법을 최적화하는 것은 정말 무의미하다. 몇 번만 호출하면 호출 수가 적어 비효율성이 숨겨지고, 많이 호출하면 캐시 누락 횟수(CPU가 L2(1's cycles of cycle), L3(10's cycles), RAM(100's of cycles), HD(!)로 인해 비효율성이 숨겨진다.

꼭 해야 할 일은 스왑 메소드를 호출하는 알고리즘을 살펴보는 것이다.이것은 사소한 운동이 아니다.Big-O 표기법은 유용하지만, O(n)는 작은 n의 경우 O(log n)보다 훨씬 더 빠를 수 있다. (이것에 대한 CodingHorror 기사가 분명히 있을 것이다.)또한 많은 알고리즘은 코드가 필요한 것보다 더 많은 기능을 하는 경우를 퇴보시킨다(거품 같은 조기 체크보다 거의 주문된 데이터에 qsort를 사용하는 것이 더 느릴 수 있다).따라서 알고리즘과 알고리즘이 사용하는 데이터를 분석해야 한다.

그래서 코드를 분석하는 방법이 나왔지프로파일러는 유용하지만 결과를 해석하는 방법을 알아야 한다.테스트 응용 프로그램이 OS에 의해 하드 Disk에 페이징될 수 있으므로 한 번의 실행으로 결과를 수집하지 마십시오. 여러 실행에서 항상 평균적인 결과를 얻으십시오.항상 프로파일 릴리스, 최적화된 빌드, 프로파일링 디버그 코드는 무의미하다.

원래의 질문인 - 어느 것이 더 빠를까? - 그것은 날개 거울의 크기와 모양을 보고 페라리가 람보르기니보다 더 빠른지 알아내려는 것과 같다.

매크로에 대한 증오를 이해하지 못했다.적절하게 사용하면 코드를 더 컴팩트하고 읽기 쉽게 만들 수 있다.나는 대부분의 프로그래머들이 매크로가 신중하게 사용되어야 한다는 것을 알고 있다고 믿는다. 중요한 것은 특정 통화는 기능 통화(all caps)가 아니라 매크로라는 것을 분명히 하는 것이다.만약SWAP(a++, b++);일관된 문제의 근원이며, 프로그래밍은 아마도 당신을 위한 것이 아닐 것이다.

물론, 처음 5000번 보는 것은 깔끔하지만, 실제로 하는 것은 신뢰성의 희생을 감수하면서 한 번 임시로 저장하는 것뿐이다.위에서 생성된 어셈블리를 보면 레지스터는 저장되지만 종속성은 생성된다.또한 xchg는 묵시적인 잠금 접두사를 가지고 있기 때문에 나는 추천하지 않을 것이다.

결국 우리 모두는 같은 장소에 오게 된다. 우리의 가장 영리한 코드에 의해 야기된 비생산적인 최적화 및 디버깅에 수 많은 시간이 허비된 후 - 단순성을 유지하라.

#define SWAP(type, a, b) \
    do { type t=(a);(a)=(b);(b)=t; } while (0)

void swap(size_t esize, void* a, void* b)
{
    char* x = (char*) a;
    char* y = (char*) b;
    char* z = x + esize;

    for ( ; x < z; x++, y++ )
        SWAP(char, *x, *y);
}

void swap(int* a, int* b)
{
    *a = (*b - *a) + (*b = *a);
}

// 내 C가 좀 녹슬었으니까 *맞았으면 좋겠다 :)

첫 번째는 xor와 같은 비트 연산들은 보통 독자들에게 시각화하기가 매우 어렵기 때문에 더 빠르다.

물론 가장 중요한 부분인 더 빨리 이해할 수 있다;)

@Harry 관련: 다음과 같은 이유로 매크로 기능을 구현하지 마십시오.

1. 유형 안전.없다.다음은 컴파일할 때만 경고를 생성하지만 런타임에 실패하는 경우:

   float a=1.5f,b=4.2f;
   swap (a,b);
   

   템플리트 함수는 항상 올바른 유형이다(그리고 경고를 오류로 처리하지 않는 이유는 무엇인가).

   편집: C에 템플릿이 없기 때문에 각 유형에 대해 별도의 스왑을 작성하거나 메모리 액세스 권한을 사용해야 한다.

2. 문자 대체다.런타임에 다음이 실패함(이번에 컴파일러 경고 없이):

   int a=1,temp=3;
   swap (a,temp);
   

3. 함수가 아니야.그래서, 그것은 qsort와 같은 것에 대한 주장으로 사용될 수 없다.

4. 컴파일러는 영리하다.내 말은 정말 영리하다는 뜻이야.정말 영리한 사람들이 만든 거야그들은 기능을 할 수 있다.링크 시간에도 (이것은 훨씬 더 영리하다.)인라이닝은 코드 크기를 증가시킨다는 것을 잊지 마십시오.빅 코드는 명령을 가져올 때 캐시 누락이 발생할 가능성이 더 높다는 것을 의미하며, 이는 코드가 더 느리다는 것을 의미한다.

5. 부작용.매크로에는 부작용이 있다!고려 사항:

   int &f1 ();
   int &f2 ();
   void func ()
   {
     swap (f1 (), f2 ());
   }
   

   여기서 f1과 f2는 두 번 호출된다.

   편집: 끔찍한 부작용이 있는 C 버전:

   int a[10], b[10], i=0, j=0;
   swap (a[i++], b[j++]);
   

매크로스: 싫다고만 해!

편집: 이것이 내가 UPERCASE에서 매크로 이름을 정의하여 코드에서 주의해서 사용할 경고로 돋보이게 하는 것을 선호하는 이유다.

편집2: Lean Novash의 코멘트에 답하기 위해:

컴파일러에 의해 바이트 시퀀스로 변환되는 비 인라인 함수 f가 있다고 가정하면 다음과 같이 바이트 수를 정의할 수 있다.

bytes = C(p) + C(f)

여기서 C()는 생성된 바이트 수를, C(f)는 함수의 바이트를, C(p)는 '하우스 키핑' 코드의 바이트를, 컴파일러가 함수에 추가하는 프리앰블과 포스트앰블(함수의 스택 프레임 등을 생성 및 파괴)이다.이제 함수 f를 호출하려면 C(c) 바이트가 필요하다.함수를 n배수로 부르면 총 코드 크기는 다음과 같다.

size = C(p) + C(f) + n.C(c)

이제 함수를 인라인으로 연결합시다.함수의 '하우스 키핑'인 C(p)는 함수가 호출자의 스택 프레임을 사용할 수 있기 때문에 0이 된다.C(c)도 호출 opcode가 없기 때문에 0이다.그러나, f는 통화가 있었던 곳이라면 어디든 복제된다.따라서 총 코드 크기는 다음과 같다.

size = n.C(f)

이제 C(f)가 C(c)보다 작으면 전체 실행 파일 크기가 줄어든다.그러나 C(f)가 C(c)보다 크면 코드 크기가 커진다.만약 C(f)와 C(c)가 비슷하다면 C(p)도 고려해야 한다.

따라서 C(f)와 C(c)는 얼마나 많은 바이트를 생산하는가.음, 가장 간단한 C++ 기능은 getter일 것이다.

void GetValue () { return m_value; }

4바이트 명령이 생성될 수 있는 경우:

mov eax,[ecx + offsetof (m_value)]

4바이트야통화 삽입은 5바이트다.그래서 전체적인 사이즈 절감이 있다.함수가 더 복잡한 경우, 인덱서("return m_value [index];") 또는 계산("return m_value_a + m_value_b;")이라고 말한다.

진짜 아는 유일한 방법은 그것을 시험하는 것이고, 그 답은 심지어 당신이 어떤 컴파일러와 플랫폼에 있는가에 따라 달라질 수도 있다.요즘 현대 컴파일러들은 코드를 최적화하는 데 정말 능숙하며, 자신의 방식이 정말 빠르다는 것을 증명할 수 없다면 컴파일러를 능가하려고 해서는 절대 안 된다.

그렇긴 하지만, 1번보다 2번을 선택할 수 있는 아주 좋은 이유가 있는 게 좋을 거야.#1의 코드는 훨씬 읽기 쉬우며, 그 때문에 항상 먼저 선택해야 한다.그 변화를 만들어야 한다는 것을 증명할 수 있는 경우에만 #2로 바꾸고, 그렇게 한다면 - 무슨 일이 일어나고 있는지 그리고 왜 그렇게 했는지를 명백하지 않은 방법으로 설명하기 위해 코멘트를 달아야 한다.

일화로써, 나는 조기 최적화를 좋아하는 몇몇 사람들과 함께 일한다. 그리고 그것은 정말 끔찍하고 유지 불가능한 코드를 만든다.나는 또한 그들이 종종 자기 발에 총을 겨누고 있다는 것에 기꺼이 걸겠다. 왜냐하면 그들은 컴파일러가 코드를 직진하지 않는 방식으로 적음으로써 최적화하는 능력을 방해했기 때문이다.

x=x+y-(y=x);

float x; cout << "X:"; cin >> x;
float y; cout << "Y:" ; cin >> y;

cout << "---------------------" << endl;
cout << "X=" << x << ", Y=" << y << endl;
x=x+y-(y=x);
cout << "X=" << x << ", Y=" << y << endl;

이 질문에 우연히 마주치는 사람들을 위해 XOR 방법을 사용하기로 결정한다.함수 호출의 오버헤드를 피하기 위해 함수를 정의하거나 매크로를 사용하는 것을 고려해야 한다.

#define swap(a, b)   \
do {                 \
    int temp = a;    \
    a = b;           \
    b = temp;        \
} while(0)

너는 잘못된 것을 최적화하고 있다. 둘 다 너무 빨라서 측정 가능한 차이를 얻기 위해 수십억 번 실행해야 할 것이다.

그리고 거의 모든 것이 성능에 훨씬 더 큰 영향을 미칠 것이다. 예를 들어, 스와핑하는 값이 마지막으로 터치한 값에 가까운 메모리에 있는 경우 프로세서 캐시에 있는 릴리(reily)가 된다. 그렇지 않으면 메모리에 액세스해야 할 것이다. 그렇지 않으면 메모리에 액세스해야 할 것이며, 프로세스 내에서 수행하는 작업보다 몇 배의 속도가 느릴 것이다.r

어쨌든, 병목현상은 숫자를 교환하는 방법보다 비효율적인 알고리즘이나 부적절한 데이터 구조(또는 통신 오버헤드)가 될 가능성이 훨씬 더 높다.

명시된 대로 질문에 답하려면 이 코드가 실행될 특정 CPU의 명령 시간을 조사해야 하며, 따라서 시스템 캐시의 상태와 컴파일러가 내보내는 어셈블리 코드에 대해 여러 가지 가정을 해야 한다.그것은 당신의 선택 프로세서가 실제로 어떻게 작동하는지 이해하는 관점에서 흥미롭고 유용한 연습이 될 것이다. 그러나 현실 세계에서는 그 차이는 무시할 수 있을 것이다.

또 다른 아름다운 방법.

#define Swap( a, b ) (a)^=(b)^=(a)^=(b)

장점

기능 호출이 필요 없고 편리함.

단점:

이것은 두 입력이 동일한 변수일 때 실패한다.정수 변수에만 사용할 수 있다.

아래 코드 조각도 같은 역할을 할 것이다.이 코드 조각은 세 번째 변수를 사용하지 않기 때문에 프로그래밍 방식이 최적화되어 있다.

  x = x ^ y;
  y = x ^ y;
  x = x ^ y;

네가 하지 않으면 나는 그것을 조언자로 하지 않을 것이다.컴파일러는 포인터 앨리어싱의 가능성 때문에 포인터 최적화를 잘 할 수 없다(포인터들이 오버랩되지 않는 위치를 가리킨다고 보장할 수 있다면, GCC는 적어도 이것을 최적화할 수 있는 확장자를 가지고 있다).

그리고 기능으로는 전혀 하지 않을 겁니다. 아주 간단한 작업이고 기능 호출 오버헤드가 중요하기 때문에.

가장 좋은 방법은 만일 당신이 필요로 하는 것이 원시 속도와 최적화 가능성이라면 매크로와 함께 하는 것이다.에서는 GCC를 할 수 .typeof()어떤 내장형에서도 사용할 수 있는 유연한 버전을 만들기 위해 빌트인.

이와 비슷한 것:

#define swap(a,b) \
  do { \
    typeof(a) temp; \
    temp = a; \
    a = b; \
    b = temp; \
  } while (0)

...    
{
  int a, b;
  swap(a, b);
  unsigned char x, y;
  swap(x, y);                 /* works with any type */
}

다른 컴파일러의 경우, 또는 표준 C89/99를 엄격히 준수해야 하는 경우 각 유형에 대해 별도의 매크로를 만들어야 한다.

좋은 컴파일러는 로컬/글로벌 변수를 인수로서 호출할 경우, 상황에 따라 가능한 한 공격적으로 이를 최적화할 것이다.

최고 등급의 모든 답변은 사실 확정적인 "사실"이 아니다...그들은 추측하는 사람들이다!

컴파일러에서 생성된 출력 어셈블리를 볼 수 있고 더 적은 어셈블리 지침에서 실행되는 코드를 볼 수 있기 때문에 어떤 코드가 더 적은 어셈블리 지침을 실행하는지를 확실히 알 수 있다!

여기 플래그 "gcc -std=c99 -S -O3 looking AtAsmOutput"으로 컴파일된 c 코드 입니다.c":

#include <stdio.h>
#include <stdlib.h>

void swap_traditional(int * restrict a, int * restrict b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void swap_xor(int * restrict a, int * restrict b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

int main() {
    int a = 5;
    int b = 6;
    swap_traditional(&a,&b);
    swap_xor(&a,&b);
}

swap_conventional()에 대한 ASM 출력은 >> 11<<< 지침서("leave", "ret", "size" 제외):

.globl swap_traditional
    .type   swap_traditional, @function
swap_traditional:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %ecx
    pushl   %ebx
    movl    (%edx), %ebx
    movl    (%ecx), %eax
    movl    %ebx, (%ecx)
    movl    %eax, (%edx)
    popl    %ebx
    popl    %ebp
    ret
    .size   swap_traditional, .-swap_traditional
    .p2align 4,,15

swap_xor()의 ASM 출력은 >> 11<<< "떠나"와 "뒤집기"를 포함하지 않는 지침:

.globl swap_xor
    .type   swap_xor, @function
swap_xor:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %ecx
    movl    12(%ebp), %edx
    movl    (%ecx), %eax
    xorl    (%edx), %eax
    movl    %eax, (%ecx)
    xorl    (%edx), %eax
    xorl    %eax, (%ecx)
    movl    %eax, (%edx)
    popl    %ebp
    ret
    .size   swap_xor, .-swap_xor
    .p2align 4,,15

어셈블리 출력 요약:
명령어를한다.
을 받는다.

결론:
두 방법 모두 실행하기 위해 동일한 양의 명령을 사용하므로 이 하드웨어 플랫폼에서 거의 동일한 속도다.

교훈:
작은 코드 스니펫이 있는 경우, asm 출력을 보면 코드를 빠르게 반복하고 가장 빠른 코드(즉, 최소 명령어)를 만드는 데 도움이 된다.그리고 각각의 코드 변경에 대해 프로그램을 실행할 필요가 없기 때문에 시간을 절약할 수 있다.당신은 당신의 코드 변경이 더 빠르다는 것을 보여주기 위해 프로파일러로 마지막에 코드 변경을 실행하기만 하면 된다.

나는 속도가 필요한 무거운 DSP 코드에 이 방법을 많이 사용한다.

내 생각에는 이와 같은 지역적 최적화는 플랫폼과 밀접한 관련이 있는 것으로 간주되어야 한다.만약 당신이 이것을 16비트 uC 컴파일러나 x64를 타겟으로 하여 gcc에서 컴파일한다면 그것은 큰 차이를 만든다.

특정 대상을 염두에 두고 있다면 두 가지 방법을 모두 사용해 보고 생성된 asm 코드를 보거나 두 가지 방법으로 응용 프로그램을 프로파일링하여 플랫폼에서 실제로 더 빠른 것이 무엇인지 확인하십시오.

일부 인라인 어셈블러를 사용하여 다음 작업을 수행할 수 있는 경우(psuedo 어셈블러):

PUSH A
A=B
POP B

당신은 많은 파라미터 전달과 스택 픽스업 코드 등을 저장할 것이다.

나는 방금 내가 가지고 놀던 퀵소트 두 가지를 손에 넣었다.XOR 버전은 임시 변수가 있는 버전(0.6초)보다 훨씬 빨랐다.그러나 XOR는 어레이의 데이터를 손상시켰다(아마도 Ant가 언급한 것과 동일한 주소일 것이다).

뚱뚱한 피벗 퀵소트였기 때문에 XOR 버전의 속도는 아마도 어레이의 많은 부분을 동일하게 만드는 것에서 비롯되었을 것이다.나는 가장 이해하기 쉬운 세 번째 버전의 스왑을 시도했고 단일 임시 버전과 같은 시간을 가졌다.

acopy=a;
bcopy=b;
a=bcopy;
b=acopy;

[If 문구를 각 스왑에 넣었을 뿐이므로 자체와 스왑을 시도하지 않을 것이며, XOR는 이제 다른 스왑과 동일한 시간을 갖는다(0.6초)]

컴파일러가 인라인 어셈블러를 지원하고 타겟이 32비트 x86이라면 XCHG 지침이 아마도 가장 좋은 방법일 것이다...만약 당신이 정말로 성과에 대해 그렇게 많이 신경 쓴다면.

MSVC++와 함께 작동하는 방법은 다음과 같다.

#include <stdio.h>

#define exchange(a,b)   __asm mov eax, a \
                        __asm xchg eax, b \
                        __asm mov a, eax               

int main(int arg, char** argv)
{
    int a = 1, b = 2;
    printf("%d %d --> ", a, b);
    exchange(a,b)
    printf("%d %d\r\n", a, b);
    return 0;
}

참조URL: https://stackoverflow.com/questions/36906/what-is-the-fastest-way-to-swap-values-in-c