질문자 :xis
과학 응용 프로그램에서 수치 최적화를 하고 있습니다. 내가 알아차린 한 가지는 GCC가 pow(a,2) a*a 로 컴파일하여 최적화하지만 pow(a,6) 호출은 최적화되지 않고 실제로 라이브러리 함수 pow 호출하여 속도가 크게 느려진다는 것입니다. 성능. (반대로 인텔 C++ 컴파일러 , 실행 가능한 icc pow(a,6) 대한 라이브러리 호출을 제거합니다.)
내가 궁금한 점은 GCC 4.5.1 및 옵션 " -O3 -lm -funroll-loops -msse4 pow(a,6) 를 a*a*a*a*a*a 로 교체했을 때 다음을 사용한다는 것입니다. 5 mulsd 지침:
movapd %xmm14, %xmm13 mulsd %xmm14, %xmm13 mulsd %xmm14, %xmm13 mulsd %xmm14, %xmm13 mulsd %xmm14, %xmm13 mulsd %xmm14, %xmm13
(a*a*a)*(a*a*a) 라고 쓰면
movapd %xmm14, %xmm13 mulsd %xmm14, %xmm13 mulsd %xmm14, %xmm13 mulsd %xmm13, %xmm13
이는 곱하기 명령어의 수를 3으로 줄입니다. icc 도 비슷한 동작을 합니다.
컴파일러가 이 최적화 트릭을 인식하지 못하는 이유는 무엇입니까?
부동 소수점 수학은 연관되지 않기 때문 입니다. 부동 소수점 곱셈에서 피연산자를 그룹화하는 방식은 답의 수치적 정확도에 영향을 줍니다.
결과적으로 대부분의 컴파일러는 대답이 동일하게 유지될 것이라고 확신할 수 없거나 수치 정확도에 대해 신경 쓰지 않는다고 말하지 않는 한 부동 소수점 계산 재정렬에 대해 매우 보수적입니다. 예를 들어, gcc가 부동 소수점 연산을 다시 연결할 수 있도록 하는 gcc 의 -fassociative-math 옵션 또는 속도에 대한 정확도의 훨씬 더 적극적인 절충을 허용 -ffast-math
Lambdageek a*a*a*a*a*a 에서 (a*a*a)*(a*a*a) 로의 "최적화"가 변경될 수 있음을 올바르게 지적합니다. 가치. 이것이 C99에서 허용하지 않는 이유입니다(컴파일러 플래그 또는 pragma를 통해 사용자가 특별히 허용하지 않는 한). 일반적으로 프로그래머는 자신이 한 일을 이유를 위해 작성했으며 컴파일러는 이를 존중해야 한다고 가정합니다. (a*a*a)*(a*a*a) 를 원하면 그것을 작성하십시오.
하지만 쓰기가 어려울 수 있습니다. pow(a,6) 를 사용할 때 옳은 일을 [당신이 생각하는] 일을 할 수 없습니까? 그것은 잘못된 행동이 될 것이기 때문입니다. 좋은 수학 라이브러리가 있는 플랫폼에서 pow(a,6) a*a*a*a*a*a 또는 (a*a*a)*(a*a*a) 보다 훨씬 더 정확합니다. 일부 데이터를 제공하기 위해 Mac Pro에서 작은 실험을 실행하여 [1,2) 사이의 모든 단정밀도 부동 숫자에 대해 a^6을 평가할 때 최악의 오류를 측정했습니다.
worst relative error using powf(a, 6.f): 5.96e-08 worst relative error using (a*a*a)*(a*a*a): 2.94e-07 worst relative error using a*a*a*a*a*a: 2.58e-07
pow 를 사용하면 오류 경계가 4배만큼 줄어듭니다. -ffast-math 를 통해) 오류를 증가시키는 "최적화"를 해서는 안 됩니다.
GCC는 인라인 곱셈 트리를 생성해야 하는 pow( ) __builtin_powi(x,n) 를 제공합니다. 성능과 정확도를 절충하고 싶지만 빠른 계산을 활성화하고 싶지 않은 경우 사용하십시오.
또 다른 유사한 경우: 대부분의 컴파일러는 a + b + c + d 를 (a + b) + (c + d) 로 최적화하지 않고(두 번째 표현식이 더 잘 파이프라인될 수 있기 때문에 최적화) 주어진 대로 평가합니다(즉, (((a + b) + c) + d) ). 이것도 코너 케이스 때문입니다.
float a = 1e35, b = 1e-5, c = -1e35, d = 1e-5; printf("%e %e\n", a + b + c + d, (a + b) + (c + d));
1.000000e-05 0.000000e+00 출력합니다.
Fortran(과학 컴퓨팅용으로 설계됨)에는 거듭제곱 연산자가 내장되어 있으며 내가 아는 한 Fortran 컴파일러는 일반적으로 설명하는 것과 유사한 방식으로 정수 거듭제곱으로 올리는 것을 최적화합니다. C/C++에는 불행히도 거듭제곱 연산자가 없고 라이브러리 함수 pow() 있습니다. pow 특별히 처리하고 특별한 경우에 더 빠른 방법으로 계산하는 것을 막지는 않지만 덜 일반적으로 수행하는 것 같습니다 ...
몇 년 전 나는 최적의 방법으로 정수 거듭제곱을 계산하는 것을 더 편리하게 만들려고 노력했고 다음을 생각해 냈습니다. 그것은 C가 아니라 C++이며, 여전히 컴파일러가 최적화/인라인 방법에 대해 어느 정도 똑똑하다는 점에 의존합니다. 어쨌든 실제로 유용하게 사용되기를 바랍니다.
template<unsigned N> struct power_impl; template<unsigned N> struct power_impl { template<typename T> static T calc(const T &x) { if (N%2 == 0) return power_impl<N/2>::calc(x*x); else if (N%3 == 0) return power_impl<N/3>::calc(x*x*x); return power_impl<N-1>::calc(x)*x; } }; template<> struct power_impl<0> { template<typename T> static T calc(const T &) { return 1; } }; template<unsigned N, typename T> inline T power(const T &x) { return power_impl<N>::calc(x); }
호기심에 대한 설명: 이것은 거듭제곱을 계산하는 최적의 방법을 찾지 못하지만 최적의 솔루션을 찾는 것이 NP-완전한 문제 이고 이것은 어쨌든 작은 거듭제곱에 대해서만 가치가 있기 때문에 ( pow 세부 사항에 소란.
그런 다음 power<6>(a) .
이것은 쉽게 (6 철자를 필요 권한을 입력하지 할 수 괄호로들), 그리고 당신이없이 최적화의이 종류가 있습니다 a -ffast-math 부양 등 뭔가 정밀도가 경우에 보상 요약 (예를 들어 순서를 작업의 필수).
아마도 이것이 C++라는 사실을 잊고 C 프로그램에서 사용하십시오(C++ 컴파일러로 컴파일하는 경우).
이것이 유용할 수 있기를 바랍니다.
편집하다:
이것은 내 컴파일러에서 얻은 것입니다.
a*a*a*a*a*a ,
movapd %xmm1, %xmm0 mulsd %xmm1, %xmm0 mulsd %xmm1, %xmm0 mulsd %xmm1, %xmm0 mulsd %xmm1, %xmm0 mulsd %xmm1, %xmm0
(a*a*a)*(a*a*a) ,
movapd %xmm1, %xmm0 mulsd %xmm1, %xmm0 mulsd %xmm1, %xmm0 mulsd %xmm0, %xmm0
power<6>(a) ,
mulsd %xmm0, %xmm0 movapd %xmm0, %xmm1 mulsd %xmm0, %xmm1 mulsd %xmm0, %xmm1
GCC는 a가 정수일 때 a*a*a*a*a*a 를 (a*a*a)*(a*a*a) 이 명령으로 시도했습니다.
$ echo 'int f(int x) { return x*x*x*x*x*x; }' | gcc -o - -O2 -S -masm=intel -xc -
많은 gcc 플래그가 있지만 멋진 것은 없습니다. 의미: stdin에서 읽기; O2 최적화 수준을 사용하십시오. 바이너리 대신 출력 어셈블리 언어 목록; 목록은 Intel 어셈블리 언어 구문을 사용해야 합니다. 입력은 C 언어입니다(일반적으로 언어는 입력 파일 확장자에서 유추되지만 stdin에서 읽을 때는 파일 확장자가 없습니다). 그리고 stdout에 씁니다.
다음은 출력의 중요한 부분입니다. 어셈블리 언어에서 무슨 일이 일어나고 있는지 나타내는 몇 가지 주석으로 주석을 달았습니다.
; x is in edi to begin with. eax will be used as a temporary register. mov eax, edi ; temp = x imul eax, edi ; temp = x * temp imul eax, edi ; temp = x * temp imul eax, eax ; temp = temp * temp
Ubuntu 파생 제품인 Linux Mint 16 Petra에서 시스템 GCC를 사용하고 있습니다. 다음은 gcc 버전입니다.
$ gcc --version gcc (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1
다른 포스터에서 언급했듯이 부동 소수점 산술은 연관되지 않기 때문에 이 옵션은 부동 소수점에서 가능하지 않습니다.
32비트 부동 소수점 숫자(예: 1.024)는 1.024가 아니기 때문입니다. 컴퓨터에서 1.024는 (1.024-e)에서 (1.024+e)까지의 간격입니다. 여기서 "e"는 오류를 나타냅니다. 어떤 사람들은 이것을 깨닫지 못하고 또한 * in a*a는 임의의 정밀도 숫자에 오류가 첨부되지 않은 임의의 정밀도 숫자의 곱을 의미한다고 믿습니다. 일부 사람들이 이것을 깨닫지 못하는 이유는 아마도 초등학교에서 연습했던 수학 계산 때문일 것입니다. 오류가 붙지 않은 이상적인 숫자만 사용하고 곱셈을 수행할 때 "e"를 무시해도 된다고 생각합니다. 그들은 "float a=1.2", "a*a*a" 및 유사한 C 코드에 내재된 "e"를 보지 못합니다.
대부분의 프로그래머가 C 표현식 a*a*a*a*a*a가 실제로 이상적인 숫자로 작동하지 않는다는 아이디어를 인식하고 실행할 수 있다면 GCC 컴파일러는 "a*a *a*a*a*a"를 "t=(a*a); t*t*t"로 변환하면 더 적은 수의 곱셈이 필요합니다. 그러나 불행히도 GCC 컴파일러는 코드를 작성하는 프로그래머가 "a"가 오류가 있거나 없는 숫자라고 생각하는지 여부를 알지 못합니다. 따라서 GCC는 소스 코드가 보이는 대로만 수행합니다. 왜냐하면 이것이 GCC가 "육안"으로 보는 것이기 때문입니다.
당신이 어떤 프로그래머의 당신이 무엇인지 한 번 ..., 그 GCC 말할 수있는 "-ffast - 수학"스위치를 사용할 수있다 "이봐, GCC, 나는 내가 뭐하는 거지 알아!". 이렇게 하면 GCC가 a*a*a*a*a*a를 다른 텍스트 조각으로 변환할 수 있습니다. a*a*a*a*a*a와 다르게 보이지만 여전히 오류 간격 내에서 숫자를 계산합니다. 아*아*아*아*아*아. 이상적인 숫자가 아닌 간격으로 작업하고 있다는 것을 이미 알고 있기 때문에 괜찮습니다.
아직 부동 표현의 축약형에 대해 언급한 포스터는 없습니다(ISO C 표준, 6.5p8 및 7.12.2). FP_CONTRACT pragma가 ON a*a*a*a*a*a 와 같은 표현식을 단일 반올림으로 정확하게 평가되는 것처럼 단일 연산으로 간주할 수 있습니다. 예를 들어 컴파일러는 더 빠르고 정확한 내부 전력 함수로 이를 대체할 수 있습니다. 이는 동작이 부분적으로 소스 코드에서 직접 프로그래머에 의해 제어되는 반면 최종 사용자가 제공하는 컴파일러 옵션이 때때로 잘못 사용될 수 있다는 점에서 특히 흥미롭습니다.
FP_CONTRACT pragma의 기본 상태는 구현에 따라 정의되므로 컴파일러는 기본적으로 이러한 최적화를 수행할 수 있습니다. 따라서 IEEE 754 규칙을 엄격하게 준수해야 하는 이식 가능한 코드는 명시적으로 OFF 설정해야 합니다.
OFF 로 설정하기로 선택한 경우 이러한 최적화를 피함으로써 보수적이어야 합니다.
GCC는 이 pragma를 지원하지 않지만 기본 옵션을 사용하면 ON 가정합니다. 따라서 하드웨어 FMA가 있는 대상의 경우 a*b+c 가 fma(a,b,c)로 -ffp-contract=off 와 같은 옵션을 제공해야 합니다(pragma를 명시적으로 설정하려면 OFF ) 또는 -std=c99 (GCC가 일부 C 표준 버전(여기서는 C99)을 준수하도록 지시하므로 위의 단락을 따르십시오). 과거에는 후자의 옵션이 변환을 방지하지 않았으므로 GCC가 이 시점에서 준수하지 않았음을 의미합니다. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845
Lambdageek이 지적했듯이 float 곱셈은 연관되지 않고 정확도가 떨어질 수 있지만 정확도가 향상되면 결정론적 응용 프로그램을 원하기 때문에 최적화에 반대할 수 있습니다. 예를 들어 게임 시뮬레이션 클라이언트/서버에서 모든 클라이언트가 부동 소수점 계산이 결정적이기를 원하는 동일한 세계를 시뮬레이션해야 합니다.
"pow"와 같은 라이브러리 함수는 일반적으로 가능한 최소 오류(일반적인 경우)를 생성하도록 신중하게 제작됩니다. 이것은 일반적으로 스플라인으로 함수를 근사화하여 달성됩니다(Pascal의 의견에 따르면 가장 일반적인 구현은 Remez 알고리즘을 사용하는 것으로 보입니다)
기본적으로 다음 작업:
pow(x,y);
단일 곱셈 또는 나눗셈의 오류와 거의 같은 크기의 고유 오류가 있습니다.
다음 작업 동안:
float a=someValue; float b=a*a*a*a*a*a;
단일 곱셈 또는 나눗셈 오류의 5배 이상인 고유 오류가 있습니다(5개의 곱셈을 결합하기 때문에).
컴파일러는 수행 중인 최적화 유형에 대해 정말 주의해야 합니다.
-
pow(a,6) 를 a*a*a*a*a*a 최적화하면 성능이 향상될 수 있지만 부동 소수점 숫자의 정확도가 크게 떨어집니다. -
a*a*a*a*a*a 를 pow(a,6) 최적화하면 "a"가 오류 없이 곱셈을 허용하는 특수 값(2의 거듭제곱 또는 일부 작은 정수)이었기 때문에 실제로 정확도가 감소할 수 있습니다. -
pow(a,6) 를 (a*a*a)*(a*a*a) 또는 (a*a)*(a*a)*(a*a) 최적화하면 여전히 정확도가 떨어질 수 있습니다. pow 함수와 비교.
일반적으로 임의의 부동 소수점 값에 대해 "pow"는 결국 작성할 수 있는 어떤 함수보다 정확도가 더 우수하지만 일부 특수한 경우에는 다중 곱셈이 더 나은 정확도와 성능을 가질 수 있으므로 개발자가 더 적절한 것을 선택해야 합니다. 결국 다른 사람이 해당 코드를 "최적화"하지 못하도록 코드를 주석 처리합니다.
최적화에 의미가 있는 유일한 것(개인적인 의견, 그리고 GCC에서 특정 최적화 또는 컴파일러 플래그가 없는 선택)은 "pow(a,2)"를 "a*a"로 바꾸는 것뿐입니다. 그것이 컴파일러 벤더가 해야 할 유일한 제정신이 될 것입니다.
이 경우가 최적화될 것이라고는 전혀 예상하지 못했습니다. 표현식에 전체 작업을 제거하기 위해 다시 그룹화할 수 있는 하위 표현식이 포함되는 경우는 많지 않습니다. 저는 컴파일러 작성자가 드물게 발생하는 경우를 다루기보다는 눈에 띄는 개선을 가져올 가능성이 있는 영역에 시간을 투자할 것으로 예상합니다.
이 표현식이 적절한 컴파일러 스위치로 실제로 최적화될 수 있다는 다른 답변을 보고 놀랐습니다. 최적화가 사소하거나 훨씬 더 일반적인 최적화의 경우이거나 컴파일러 작성자가 매우 철저했습니다.
여기에서 수행한 것처럼 컴파일러에 힌트를 제공하는 데 아무런 문제가 없습니다. 명령문과 표현식을 재배열하여 어떤 차이를 가져올지 확인하는 것은 미세 최적화 프로세스의 정상적이고 예상되는 부분입니다.
컴파일러는 (적절한 스위치 없이) 일관성 없는 결과를 제공하기 위해 두 표현식을 고려하는 것이 정당할 수 있지만, 그 제한에 구속될 필요는 없습니다. 그 차이는 매우 작을 것입니다. 차이가 중요하다면 처음부터 표준 부동 소수점 산술을 사용해서는 안 됩니다.
이 질문에 대한 몇 가지 좋은 답변이 이미 있지만 완전성을 위해 C 표준의 적용 가능한 섹션은 5.1.2.2.3/15(이는 섹션 1.9/9와 동일합니다. C++11 표준). 이 섹션에서는 연산자가 실제로 연관되거나 교환 가능한 경우에만 다시 그룹화할 수 있다고 설명합니다.
gcc는 실제로 부동 소수점 숫자에 대해서도 이 최적화를 수행할 수 있습니다. 예를 들어,
double foo(double a) { return a*a*a*a*a*a; }
된다
foo(double): mulsd %xmm0, %xmm0 movapd %xmm0, %xmm1 mulsd %xmm0, %xmm1 mulsd %xmm1, %xmm0 ret
-O -funsafe-math-optimizations . 그러나 이 재정렬은 IEEE-754를 위반하므로 플래그가 필요합니다.
Peter Cordes가 주석에서 지적한 것처럼 부호 있는 정수는 오버플로가 없을 때 정확히 유지되고 오버플로가 있으면 정의되지 않은 동작이 발생하기 때문에 -funsafe-math-optimizations 그래서 당신은
foo(long): movq %rdi, %rax imulq %rdi, %rax imulq %rdi, %rax imulq %rax, %rax ret
그냥 -O . 부호 없는 정수의 경우 모드 2의 거듭제곱으로 작동하므로 오버플로가 발생하더라도 자유롭게 재정렬할 수 있으므로 훨씬 더 쉽습니다.
출처 : http:www.stackoverflow.com/questions/6430448/why-doesnt-gcc-optimize-aaaaaa-to-aaaaaa