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;
}
첫 번째는 추가 레지스터를 사용하는 것처럼 보이지만 두 번째는 세 번의로드 및 저장을 수행하고 첫 번째는 각각 두 번만 수행합니다. 누군가가 더 빠른 이유와 이유를 말할 수 있습니까? 더 중요한 이유.
a와 b가 동일한 주소를 가리키면 XOR 메서드가 실패합니다. 첫 번째 XOR은 두 변수가 가리키는 메모리 주소의 모든 비트를 지우므로 함수가 초기 값에 관계없이 (* a == * b == 0)을 반환하면됩니다.
Wiki 페이지에 대한 추가 정보 : XOR 스왑 알고리즘
이 문제가 발생할 가능성은 낮지 만 예상치 못한 순간에 실패하는 영리한 방법이 아니라 항상 작동이 보장 된 방법을 사용하는 것을 선호합니다.
2 번은 종종 "영리한"방법으로 인용됩니다. 실제로 프로그래머의 명시 적 목표를 모호하게하기 때문에 속도가 느릴 가능성이 가장 높습니다. 이는 컴파일러가 실제 어셈블러 작업을 사용하여 스왑하도록 최적화 할 수 없음을 의미합니다. 또한 객체에 대해 비트 xor를 수행 할 수 있다고 가정합니다.
1 위를 고수하면 가장 일반적이고 가장 이해하기 쉬운 스왑이며 쉽게 템플릿 화 / 제네릭화할 수 있습니다.
이 위키 백과 섹션은 문제를 아주 잘 설명합니다 : http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice
최신 프로세서에서는 큰 배열을 정렬 할 때 다음을 사용할 수 있으며 속도 차이가 없습니다.
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주기), L3 (10주기), RAM (100주기), HD (!))에서 데이터를 가져와야합니다.
정말로 필요한 것은 스왑 메서드를 호출하는 알고리즘을 살펴 보는 것입니다. 이것은 사소한 연습이 아닙니다. Big-O 표기법이 유용하지만 O (n)는 작은 n의 경우 O (log n)보다 훨씬 빠를 수 있습니다. (저는 이것에 대한 CodingHorror 기사가 있다고 확신합니다.) 또한 많은 알고리즘은 코드가 필요한 것 이상을 수행하는 경우를 퇴화시킵니다 (거의 순서가 지정된 데이터에 qsort를 사용하는 것이 조기 종료 검사를 사용하는 거품 정렬보다 느릴 수 있음). 따라서 알고리즘과 사용중인 데이터를 분석해야합니다.
코드를 분석하는 방법으로 이어집니다. 프로파일 러는 유용하지만 결과를 해석하는 방법을 알아야합니다. 단일 실행을 사용하여 결과를 수집하지 말고 항상 여러 실행에 대한 평균 결과를 수집하십시오. 테스트 응용 프로그램이 중간에 OS에서 하드 디스크로 페이징 될 수 있기 때문입니다. 항상 프로파일 릴리스, 최적화 된 빌드, 프로파일 링 디버그 코드는 무의미합니다.
원래 질문에 관해서-어느 것이 더 빠릅니까? -윙 미러의 크기와 모양을보고 페라리가 람 부르기 니보다 빠른지 알아 내려는 것과 같습니다.
xor와 같은 비트 연산은 일반적으로 독자가 시각화하기가 매우 어렵 기 때문에 첫 번째 방법이 더 빠릅니다.
물론 가장 중요한 부분 인 이해가 더 빠릅니다.)
@Harry : 구석에 서서 당신이 제안한 것을 생각해보세요. 자신의 방식의 오류를 깨달았을 때 돌아 오십시오.
다음과 같은 이유로 함수를 매크로로 구현하지 마십시오.
유형 안전성. 없습니다. 다음은 컴파일 할 때만 경고를 생성하지만 런타임에는 실패합니다.
float a=1.5f,b=4.2f; swap (a,b);템플릿 함수는 항상 올바른 유형입니다 (그리고 경고를 오류로 처리하지 않는 이유는 무엇입니까?).
편집 : C에는 템플릿이 없기 때문에 각 유형에 대해 별도의 스왑을 작성하거나 일부 해키 메모리 액세스를 사용해야합니다.
텍스트 대체입니다. 다음은 런타임에 실패합니다 (이번에는 컴파일러 경고없이).
int a=1,temp=3; swap (a,temp);기능이 아닙니다. 따라서 qsort와 같은 것에 대한 인수로 사용할 수 없습니다.
- 컴파일러는 영리합니다. 정말 영리합니다. 정말 영리한 사람들이 만들었습니다. 그들은 함수의 인라인을 할 수 있습니다. 링크 타임에도 (더 똑똑합니다). 인라이닝은 코드 크기를 증가 시킨다는 것을 잊지 마십시오. 큰 코드는 명령어를 가져올 때 캐시 미스 가능성이 더 높음을 의미하며, 이는 코드 속도가 느리다는 것을 의미합니다.
부작용. 매크로에는 부작용이 있습니다! 중히 여기다:
int &f1 (); int &f2 (); void func () { swap (f1 (), f2 ()); }여기서 f1과 f2는 두 번 호출됩니다.
편집 : 불쾌한 부작용이있는 AC 버전 :
int a[10], b[10], i=0, j=0; swap (a[i++], b[j++]);
매크로 : 아니요라고 말하세요!
편집 : 이것이 내가주의해서 사용하라는 경고로 코드에서 눈에 띄도록 대문자로 매크로 이름을 정의하는 것을 선호하는 이유입니다.
EDIT2 : Leahn Novash의 의견에 답하려면 :
컴파일러에 의해 바이트 시퀀스로 변환되는 인라인되지 않은 함수 f가 있다고 가정하면 다음과 같이 바이트 수를 정의 할 수 있습니다.
bytes = C(p) + C(f)
여기서 C ()는 생성 된 바이트 수를, C (f)는 함수의 바이트이며 C (p)는 '하우스 키핑'코드, 컴파일러가 함수에 추가하는 프리앰블 및 포스트 앰블 (생성 함수의 스택 프레임을 파괴하는 등). 이제 함수 f를 호출하려면 C (c) 바이트가 필요합니다. 함수가 n 번 호출되면 총 코드 크기는 다음과 같습니다.
size = C(p) + C(f) + n.C(c)
이제 함수를 인라인 해 보겠습니다. 함수의 'housekeeping'인 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;")과 같이 코드가 더 커집니다.
이 질문을 우연히 발견하고 XOR 방법을 사용하기로 결정한 사람들을 위해. 함수 호출의 오버 헤드를 피하기 위해 함수를 인라인하거나 매크로를 사용하는 것을 고려해야합니다.
#define swap(a, b) \
do { \
int temp = a; \
a = b; \
b = temp; \
} while(0)
잘못된 것을 최적화하고 있습니다. 둘 다 너무 빨라야 만 측정 가능한 차이를 얻기 위해 수십억 번 실행해야합니다.
그리고 거의 모든 것이 성능에 훨씬 더 큰 영향을 미칠 것입니다. 예를 들어 스와핑하는 값이 메모리에서 마지막으로 터치 한 값에 가까워지면 프로세서 캐시에있을 수 있습니다. 그렇지 않으면 해당 값에 액세스해야합니다. 메모리-프로세서 내부에서 수행하는 작업보다 몇 배 더 느립니다.
어쨌든 병목 현상은 숫자를 바꾸는 방법보다 비효율적 인 알고리즘이나 부적절한 데이터 구조 (또는 통신 오버 헤드) 일 가능성이 훨씬 더 높습니다.
매크로에 대한 증오를 이해하지 못했습니다. 적절하게 사용하면 코드를 더 간결하고 읽기 쉽게 만들 수 있습니다. 저는 대부분의 프로그래머가 매크로를주의해서 사용해야한다는 것을 알고 있다고 생각합니다. 중요한 것은 특정 호출이 함수 호출 (모두 대문자)이 아니라 매크로라는 것을 분명히하는 것입니다. SWAP(a++, b++);일관된 문제의 원인 이라면 프로그래밍이 적합하지 않을 수 있습니다.
xor 트릭은 처음 볼 때 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);
}
실제로 알 수있는 유일한 방법은 테스트하는 것이며, 사용중인 컴파일러와 플랫폼에 따라 대답이 달라질 수도 있습니다. 현대 컴파일러는 요즘 코드를 최적화 하는 데 정말 능숙하며, 자신의 방식이 정말 빠르다는 것을 증명할 수 없다면 컴파일러를 능가하려고해서는 안됩니다.
그렇다고해서 1 번보다 2 번을 선택해야 할 타당한 이유가 있어야합니다. # 1의 코드는 훨씬 더 읽기 쉬우므로 항상 먼저 선택해야합니다. 변경 해야 한다는 것을 증명할 수있는 경우에만 # 2로 전환하고 , 그렇게한다면 무슨 일이 일어나고 있는지, 왜 그렇게했는지 설명하기 위해 주석을 달아주세요.
일화로서, 저는 조기에 최적화 하는 것을 좋아 하는 두 사람과 함께 일하며 정말 끔찍하고 유지 관리 할 수없는 코드를 만듭니다. 나는 또한 그들이 간단하지 않은 방식으로 코드를 작성함으로써 코드를 최적화하는 컴파일러의 능력을 방해했기 때문에 그들이 스스로를 쏘고 있다는 것을 더 자주 확신합니다.
나는 당신이 필요하지 않는 한 포인터로 그것을하지 않을 것입니다. 컴파일러는 포인터 앨리어싱 의 가능성 때문에 그것들을 아주 잘 최적화 할 수 없습니다 (포인터가 겹치지 않는 위치를 가리키고 있음을 보장 할 수 있다면 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 lookingAtAsmOutput.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_traditional ()에 대한 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 <<< "leave"및 "ret"을 포함하지 않는 명령어를 사용합니다.
.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
어셈블리 출력 요약 :
swap_traditional ()은 11 개의 명령어를 사용합니다.
swap_xor ()는 11 개의 명령어를 사용합니다.
Conclusion:
Both methods use the same amount of instructions to execute and therefore are approximately the same speed on this hardware platform.
Lesson learned:
When you have small code snippets, looking at the asm output is helpful to rapidly iterate your code and come up with the fastest ( i.e. least instructions ) code. And you can save time even because you don't have to run the program for each code change. You only need to run the code change at the end with a profiler to show that your code changes are faster.
I use this method a lot for heavy DSP code that needs speed.
For modern CPU architectures, method 1 will be faster, also with higher readability than method 2.
On modern CPU architectures, the XOR technique is considerably slower than using a temporary variable to do swapping. One reason is that modern CPUs strive to execute instructions in parallel via instruction pipelines. In the XOR technique, the inputs to each operation depend on the results of the previous operation, so they must be executed in strictly sequential order. If efficiency is of tremendous concern, it is advised to test the speeds of both the XOR technique and temporary variable swapping on the target architecture. Check out here for more info.
Edit: Method 2 is a way of in-place swapping (i.e. without using extra variables). To make this question complete, I will add another in-place swapping by using +/-.
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;
}
}
To answer your question as stated would require digging into the instruction timings of the particular CPU that this code will be running on which therefore require me to make a bunch of assumptions around the state of the caches in the system and the assembly code emitted by the compiler. It would be an interesting and useful exercise from the perspective of understanding how your processor of choice actually works but in the real world the difference will be negligible.
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;
In my opinion local optimizations like this should only be considered tightly related to the platform. It makes a huge difference if you are compiling this on a 16 bit uC compiler or on gcc with x64 as target.
If you have a specific target in mind then just try both of them and look at the generated asm code or profile your applciation with both methods and see which is actually faster on your platform.
If you can use some inline assembler and do the following (psuedo assembler):
PUSH A
A=B
POP B
You will save a lot of parameter passing and stack fix up code etc.
I just placed both swaps (as macros) in hand written quicksort I've been playing with. The XOR version was much faster (0.1sec) then the one with the temporary variable (0.6sec). The XOR did however corrupt the data in the array (probably the same address thing Ant mentioned).
As it was a fat pivot quicksort, the XOR version's speed is probably from making large portions of the array the same. I tried a third version of swap which was the easiest to understand and it had the same time as the single temporary version.
acopy=a;
bcopy=b;
a=bcopy;
b=acopy;
[I just put an if statements around each swap, so it won't try to swap with itself, and the XOR now takes the same time as the others (0.6 sec)]
If your compiler supports inline assembler and your target is 32-bit x86 then the XCHG instruction is probably the best way to do this... if you really do care that much about performance.
Here is a method which works with 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;
}
Below piece of code will do the same. This snippet is optimized way of programming as it doesn't use any 3rd variable.
x = x ^ y;
y = x ^ y;
x = x ^ y;
void swap(int* a, int* b)
{
*a = (*b - *a) + (*b = *a);
}
// My C is a little rusty, so I hope I got the * right :)
Another beautiful way.
#define Swap( a, b ) (a)^=(b)^=(a)^=(b)
Advantage
No need of function call and handy.
Drawback:
This fails when both inputs are same variable. It can be used only on integer variables.
ReferenceURL : https://stackoverflow.com/questions/36906/what-is-the-fastest-way-to-swap-values-in-c
'programing' 카테고리의 다른 글
| Groovy의 목록에서 Null 항목 제거 (0) | 2021.01.16 |
|---|---|
| 함수형 프로그래밍, 스칼라 맵 및 왼쪽 접기 (0) | 2021.01.16 |
| 일부 조각에서 MenuItem 숨기기 (0) | 2021.01.16 |
| Java에서 임의의 문자를 생성하는 기능이 있습니까? (0) | 2021.01.16 |
| 더 나은 점 : DataSet 또는 DataReader? (0) | 2021.01.16 |