왜 C ++ 옵티마이 저가 이러한 임시 변수에 문제가 있거나 타이트 루프에서`v []`를 피해야합니까?
이 코드 스 니펫 에서는 기능적으로 동일한 두 루프의 성능을 비교합니다.
for (int i = 1; i < v.size()-1; ++i) {
int a = v[i-1];
int b = v[i];
int c = v[i+1];
if (a < b && b < c)
++n;
}
과
for (int i = 1; i < v.size()-1; ++i)
if (v[i-1] < v[i] && v[i] < v[i+1])
++n;
첫 번째는 최적화 플래그가 다음과 O2같이 설정된 여러 다른 C ++ 컴파일러에서 두 번째 것보다 훨씬 느리게 실행됩니다 .
- 두 번째 루프는 이제 Clang 3.7.0에서 약 330 % 느립니다.
- 두 번째 루프는 gcc 4.9.3에서 약 2 % 느립니다.
- 두 번째 루프는 Visual C ++ 2015에서 약 2 % 느립니다.
현대의 C ++ 최적화 프로그램이이 경우를 처리하는 데 문제가 있다는 점에 의아해합니다. 이유는 무엇입니까? 최상의 성능을 얻으려면 임시 변수를 사용하지 않고 추악한 코드를 작성해야합니까?
임시 변수를 사용하면 코드가 더 빨라지고 때로는 극적으로 빨라집니다. 무슨 일이야?
내가 사용중인 전체 코드는 다음과 같습니다.
#include <algorithm>
#include <chrono>
#include <random>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
using namespace std::chrono;
vector<int> v(1'000'000);
int f0()
{
int n = 0;
for (int i = 1; i < v.size()-1; ++i) {
int a = v[i-1];
int b = v[i];
int c = v[i+1];
if (a < b && b < c)
++n;
}
return n;
}
int f1()
{
int n = 0;
for (int i = 1; i < v.size()-1; ++i)
if (v[i-1] < v[i] && v[i] < v[i+1])
++n;
return n;
}
int main()
{
auto benchmark = [](int (*f)()) {
const int N = 100;
volatile long long result = 0;
vector<long long> timings(N);
for (int i = 0; i < N; ++i) {
auto t0 = high_resolution_clock::now();
result += f();
auto t1 = high_resolution_clock::now();
timings[i] = duration_cast<nanoseconds>(t1-t0).count();
}
sort(timings.begin(), timings.end());
cout << fixed << setprecision(6) << timings.front()/1'000'000.0 << "ms min\n";
cout << timings[timings.size()/2]/1'000'000.0 << "ms median\n" << "Result: " << result/N << "\n\n";
};
mt19937 generator (31415); // deterministic seed
uniform_int_distribution<> distribution(0, 1023);
for (auto& e: v)
e = distribution(generator);
benchmark(f0);
benchmark(f1);
cout << "\ndone\n";
return 0;
}
컴파일러가 std::vector<>::size()내부 벡터 버퍼 크기와 의 관계에 대한 지식이 부족한 것 같습니다 . 약간의 버그 std::vector가있는 사용자 정의 bugged_vector벡터 류 객체 인 것을 고려하십시오. ::size()내부 버퍼 크기보다 하나 더 많을 수 n있지만 그 후에는 v[n-2] >= v[n-1].
그런 다음 두 스 니펫은 다시 다른 의미를 갖습니다. 첫 번째 스 니펫은 element에 액세스 할 때 정의되지 않은 동작을가 v[v.size() - 1]집니다. 그러나 두 번째에는 없습니다.의 단락 특성으로 인해 마지막 반복에서 &&읽지 않습니다 v[v.size() - 1].
따라서 컴파일러가 우리 v가.가 아니라는 것을 증명할 수 없다면 bugged_vector단락을해야합니다. 이로 인해 기계어 코드에서 추가 점프가 발생합니다.
의 어셈블리 출력 clang을 보면 실제로 발생하는 것을 알 수 있습니다.
에서 Godbolt 컴파일러 탐색기 연타 3.7.0 -O2와 함께,에서 루프 f0입니다 :
### f0: just the loop
.LBB1_2: # =>This Inner Loop Header: Depth=1
mov edi, ecx
cmp edx, edi
setl r10b
mov ecx, dword ptr [r8 + 4*rsi + 4]
lea rsi, [rsi + 1]
cmp edi, ecx
setl dl
and dl, r10b
movzx edx, dl
add eax, edx
cmp rsi, r9
mov edx, edi
jb .LBB1_2
그리고 f1:
### f1: just the loop
.LBB2_2: # =>This Inner Loop Header: Depth=1
mov esi, r10d
mov r10d, dword ptr [r9 + 4*rdi]
lea rcx, [rdi + 1]
cmp esi, r10d
jge .LBB2_4 # <== This is Extra Jump
cmp r10d, dword ptr [r9 + 4*rdi + 4]
setl dl
movzx edx, dl
add eax, edx
.LBB2_4: # %._crit_edge.3
cmp rcx, r8
mov rdi, rcx
jb .LBB2_2
나는 추가 점프를 지적했다 f1. 그리고 우리가 (희망적으로) 알고 있듯이, 타이트한 루프에서 조건부 점프는 성능에 좋지 않습니다. (자세한 내용은 x86 태그 위키 의 성능 가이드 를 참조하십시오.)
GCC와 Visual Studio는 편집 . std::vector제대로 작동 한다는 것을 인식하고 두 조각에 대해 거의 동일한 어셈블리를 생성합니다. clang코드를 최적화하는 것이 더 나은 것으로 밝혀졌습니다 . 세 컴파일러 모두 v[i + 1]두 번째 예제에서 비교하기 전에 읽는 것이 안전하다는 것을 증명할 수는 없지만 (또는 그렇지 않은 경우) clang읽기 v[i + 1]가 유효하거나 UB 라는 추가 정보를 사용하여 첫 번째 예제 만 최적화하도록 관리합니다 .
2 %의 성능 차이는 무시할 수있는 수준이며 다른 순서 또는 일부 명령 선택으로 설명 할 수 있습니다.
문제를 올바르게 진단 한 @deniss의 답변을 확장 할 수있는 추가 통찰력이 있습니다.
덧붙여서, 이것은 "정렬되지 않은 배열보다 정렬 된 배열을 더 빨리 처리하는 이유는 무엇입니까?" 라는 가장 인기있는 C ++ Q & A 와 관련이 있습니다. .
주요 문제는 컴파일러가 논리 AND 연산자 (&&)를 준수해야하며 첫 번째 조건이 참이 아니면 v [i + 1]에서로드하지 않아야한다는 것입니다. 이것은 논리 AND 연산자의 의미 체계와 C ++ 11에 도입 된 강화 된 메모리 모델 의미 체계의 결과입니다. 표준 초안의 관련 절은 다음과 같습니다.
5.14 논리 AND 연산자 [expr.log.and]
달리 & , && 보장 좌우로 평가 : 제 오퍼랜드 인 경우 상기 제 피연산자 평가되지 거짓 .
ISO C ++ 14 표준 (초안 N3797)
투기 적 읽기
1.10 다중 스레드 실행 및 데이터 경쟁 [intro.multithread]
23 [ 참고 : 잠재적으로 공유 된 메모리 위치의 추론 적 읽기를 도입하는 변환은 잠재적으로 데이터 경쟁을 도입하기 때문에이 표준에 정의 된 C ++ 프로그램의 의미를 보존하지 못할 수 있습니다. 그러나 일반적으로 데이터 경합에 대해 잘 정의 된 의미 체계를 가진 특정 시스템을 대상으로하는 최적화 컴파일러의 컨텍스트에서 유효합니다. 경합을 용납하지 않거나 하드웨어 경합 감지를 제공하는 가상 머신에는 유효하지 않습니다. — end note ]
ISO C ++ 14 표준 (초안 N3797)
내 생각에 옵티마이 저는 안전하게 플레이하고 현재 예측로드가 해당 대상에 대해 감지 가능한 데이터 경쟁을 유발할 수 있는지 여부를 각 대상 프로세서에 대해 특수한 경우가 아니라 잠재적으로 공유 메모리에 대해 예측로드를 발행하지 않도록 선택합니다.
이를 구현하기 위해 컴파일러는 조건 분기를 생성합니다. 일반적으로 최신 프로세서는 매우 정교한 분기 예측 기능을 가지고 있고 오 예측 비율은 일반적으로 매우 낮기 때문에 눈에 띄지 않습니다. 그러나 여기의 데이터는 무작위입니다. 이것은 분기 예측을 죽입니다. 잘못된 예측의 비용은 CPU가 일반적으로주기 당 2 개의 명령어를 폐기한다는 점을 고려할 때 10 ~ 20 개의 CPU 사이클입니다. 이는 20 ~ 40 개의 명령어에 해당합니다. 예측 비율이 50 % (무작위)이면 모든 반복에 10-20 개의 명령어에 해당하는 잘못된 예측 페널티가 있습니다. HUGE .
참고 : 컴파일러 요소가 있음을 증명할 수 v[0]에 v[v.size()-2]관계없이 포함 된 값의 순으로, 참조 할 것. 이 경우 컴파일러는 벡터의 마지막 요소를 제외한 모든 요소를 무조건로드하는 코드를 생성 할 수 있습니다. v [v.size ()-1]에있는 벡터의 마지막 요소는 루프의 마지막 반복에서만 그리고 첫 번째 조건이 참인 경우에만로드 될 수 있습니다. 따라서 컴파일러는 마지막 반복까지 단락 회로 분기없이 루프에 대한 코드를 생성 한 다음 마지막 반복에 대해 단락 분기가있는 다른 코드를 사용할 수 있습니다. 그러면 컴파일러가 데이터가 무작위이고 분기 예측이 쓸모 없다는 것을 알고 있어야합니다. 따라서 컴파일러는 아직 그다지 정교하지 않습니다.
로컬 변수에 메모리 위치 우리가 비트 단위로 논리적 AND 연산자를 변경할 수있는 조건부 논리 AND 의해 생성 지점 (&&) 및 피 로딩을 피하기 위해서 코드 여기 니펫 데이터가 임의의 경우에 그 결과는 4 배 빠르게 거의이며
int f2()
{
int n = 0;
for (int i = 1; i < v.size()-1; ++i)
n += (v[i-1] < v[i]) & (v[i] < v[i+1]); // Bitwise AND
return n;
}
산출
3.642443ms min
3.779982ms median
Result: 166634
3.725968ms min
3.870808ms median
Result: 166634
1.052786ms min
1.081085ms median
Result: 166634
done
gcc 5.3의 결과는 8 배 더 빠릅니다 ( 여기 Coliru에서 라이브 ).
g++ --version
g++ -std=c++14 -O3 -Wall -Wextra -pedantic -pthread -pedantic-errors main.cpp -lm && ./a.out
g++ (GCC) 5.3.0
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
3.761290ms min
4.025739ms median
Result: 166634
3.823133ms min
4.050742ms median
Result: 166634
0.459393ms min
0.505011ms median
Result: 166634
done
컴파일러 가 조건 분기 v[i-1] < v[i] 를 생성 하지 않고 비교 를 평가할 수있는 방법이 궁금 할 것 입니다. 대답은 대상에 따라 다릅니다. x86의 경우 SETcc이는 EFLAGS 레지스터의 조건에 따라 1 바이트 결과 0 또는 1을 생성하는 명령어로 인해 가능 하며 조건 분기에서 사용할 수있는 동일한 조건이지만 분기없이. @deniss가 제공 한 생성 된 코드에서 생성 된 setl것을 볼 수 있습니다.이 코드 는 "보다 작음"조건이 충족되면 결과를 1로 설정하고 이전 비교 명령에 의해 평가됩니다.
cmp edx, edi ; a < b ?
setl r10b ; r10b = a < b ? 1 : 0
mov ecx, dword ptr [r8 + 4*rsi + 4] ; c = v[i+1]
lea rsi, [rsi + 1] ; ++i
cmp edi, ecx ; b < c ?
setl dl ; dl = b < c ? 1 : 0
and dl, r10b ; dl &= r10b
movzx edx, dl ; edx = zero extended dl
add eax, edx ; n += edx
f0과 f1은 의미가 다릅니다.
x() && y()우리가 아는 것처럼 x ()가 거짓 인 경우 단락이 발생합니다. 즉, x ()가 false이면 y () 를 평가 하지 않아야 합니다.
이는 y ()를 평가하기 위해 데이터를 미리 가져 오는 것을 방지하고 (적어도 clang에서) 조건부 점프를 삽입하여 분기 예측자가 누락되는 결과를 초래합니다.
또 다른 2 개의 테스트를 추가하면 요점이 증명됩니다.
#include <algorithm>
#include <chrono>
#include <random>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
using namespace std::chrono;
vector<int> v(1'000'000);
int f0()
{
int n = 0;
for (int i = 1; i < v.size()-1; ++i) {
int a = v[i-1];
int b = v[i];
int c = v[i+1];
if (a < b && b < c)
++n;
}
return n;
}
int f1()
{
int n = 0;
auto s = v.size() - 1;
for (size_t i = 1; i < s; ++i)
if (v[i-1] < v[i] && v[i] < v[i+1])
++n;
return n;
}
int f2()
{
int n = 0;
auto s = v.size() - 1;
for (size_t i = 1; i < s; ++i)
{
auto t1 = v[i-1] < v[i];
auto t2 = v[i] < v[i+1];
if (t1 && t2)
++n;
}
return n;
}
int f3()
{
int n = 0;
auto s = v.size() - 1;
for (size_t i = 1; i < s; ++i)
{
n += 1 * (v[i-1] < v[i]) * (v[i] < v[i+1]);
}
return n;
}
int main()
{
auto benchmark = [](int (*f)()) {
const int N = 100;
volatile long long result = 0;
vector<long long> timings(N);
for (int i = 0; i < N; ++i) {
auto t0 = high_resolution_clock::now();
result += f();
auto t1 = high_resolution_clock::now();
timings[i] = duration_cast<nanoseconds>(t1-t0).count();
}
sort(timings.begin(), timings.end());
cout << fixed << setprecision(6) << timings.front()/1'000'000.0 << "ms min\n";
cout << timings[timings.size()/2]/1'000'000.0 << "ms median\n" << "Result: " << result/N << "\n\n";
};
mt19937 generator (31415); // deterministic seed
uniform_int_distribution<> distribution(0, 1023);
for (auto& e: v)
e = distribution(generator);
benchmark(f0);
benchmark(f1);
benchmark(f2);
benchmark(f3);
cout << "\ndone\n";
return 0;
}
결과 (apple clang, -O2) :
1.233948ms min
1.320545ms median
Result: 166850
3.366751ms min
3.493069ms median
Result: 166850
1.261948ms min
1.361748ms median
Result: 166850
1.251434ms min
1.353653ms median
Result: 166850
지금까지 f()해당 gcc 또는 clang 의 버전을 완전히 최적화 할 수 있는 답변은 없습니다 . 그들은 모두 각 반복을 비교하는 asm을 생성합니다. Godbolt 컴파일러 탐색기에서 asm 출력이있는 코드를 참조하십시오 . (asm 출력에서 성능을 예측하기위한 중요한 배경 지식 : Agner Fog의 마이크로 아키텍처 가이드 및 x86 태그 위키 의 기타 링크 . 항상 그렇듯이 성능 카운터로 프로파일 링하여 중단을 찾는 것이 가장 좋습니다.)
v[i-1] < v[i]을 평가했을 때 이미 마지막 반복 작업을 수행했습니다 v[i] < v[i+1]. 이론적으로는 컴파일러가 더 잘 최적화 할 수 있도록 도와줍니다 (참조 f3()). 실제로는 어떤 경우에는 자동 벡터화를 무력화하고 gcc -mtune=core2는 큰 문제가있는 경우에도 부분 등록 중단으로 코드를 내 보냅니다 .
v.size() - 1루프의 상한 체크를 수동으로 올리는 것이 도움이되는 것 같습니다. 영업 이익의 f0와 f1할 사실은-계산을 다시하지 v.size()의 시작 / 끝 포인터에서을 v하지만 어떻게 든 여전히 계산할 때보다 덜 최적화 size_t upper = v.size() - 1외부 루프 ( f2()과 f4()).
별도의 문제는 상한이 있는 int루프 카운터 를 사용 size_t하면 루프가 잠재적으로 무한 하다는 것을 의미합니다. 이것이 다른 최적화에 얼마나 많은 영향을 미치는지 잘 모르겠습니다.
결론 : 컴파일러는 복잡한 짐승 입니다. 어떤 버전이 잘 최적화되는지 예측하는 것은 전혀 명확하거나 간단하지 않습니다.
Core2 E6600 (Merom / Conroe 마이크로 아키텍처)에서 64 비트 Ubuntu 15.10의 결과.
clang++-3.8 -O3 -march=core2 | g++ 5.2 -O3 -march=core2 | gcc 5.2 -O2 (default -mtune=generic)
f0 1.825ms min(1.858 med) | 5.008ms min(5.048 med) | 5.000 min(5.028 med)
f1 4.637ms min(4.673 med) | 4.899ms min(4.952 med) | 4.894 min(4.931 med)
f2 1.292ms min(1.323 med) | 1.058ms min(1.088 med) (autovec) | 4.888 min(4.912 med)
f3 1.082ms min(1.117 med) | 2.426ms min(2.458 med) | 2.420 min(2.465 med)
f4 1.291ms min(1.341 med) | 1.022ms min(1.052 med) (autovec) | 2.529 min(2.560 med)
결과는 Intel SnB 제품군 하드웨어, 특히 다를 수 있습니다. IvyBridge 이상에서는 부분적인 레지스터 속도 저하가 전혀 없습니다. Core2는 정렬되지 않은 느린로드와주기 당 하나의로드로 제한됩니다. 루프는 디코딩이 문제가되지 않을만큼 충분히 작을 수 있습니다.
f0및 f1:
gcc 5.2: The OP's f0 and f1 both make branchy loops, and won't auto-vectorize. f0 only uses one branch, though, and uses a weird setl sil / cmp sil, 1 / sbb eax, -1 to do the second half of the short-circuit compare. So it's still doing both comparisons on every iteration.
clang 3.8: f0: only one load per iteration, but does both compares and ands them together. f1: both compares each iteration, one with a branch to preserve the C semantics. Two loads per iteration.
int f2() {
int n = 0;
size_t upper = v.size()-1; // difference from f0: hoist upper bound and use size_t loop counter
for (size_t i = 1; i < upper; ++i) {
int a = v[i-1], b = v[i], c = v[i+1];
if (a < b && b < c)
++n;
}
return n;
}
gcc 5.2 -O3: auto-vectorizes, with three loads to get the three offset vectors needed to produce one vector of 4 compare results. Also, after combining the results from two pcmpgtd instructions, compares them against a vector of all-zero and then masks that. Zero is already the identity element for addition, so that's really silly.
clang 3.8 -O3: unrolls: every iteration does two loads, three cmp/setcc, two ands, and two adds.
int f4() {
int n = 0;
size_t upper = v.size()-1;
for (size_t i = 1; i < upper; ++i) {
int a = v[i-1], b = v[i], c = v[i+1];
bool ab_lt = a < b;
bool bc_lt = b < c;
n += (ab_lt & bc_lt); // some really minor code-gen differences from f2: auto-vectorizes to better code that runs slightly faster even for this large problem size
}
return n;
}
- gcc 5.2
-O3: autovectorizes likef2, but without the extrapcmpeqd. - gcc 5.2
-O2: didn't investigate why this is twice as fast asf2. - clang
-O3: about the same code asf2.
Attempt at compiler hand-holding
int f3() {
int n = 0;
int a = v[0], b = v[1]; // These happen before checking v.size, defeating the loop vectorizer or something
bool ab_lt = a < b;
size_t upper = v.size()-1;
for (size_t i = 1; i < upper; ++i) {
int c = v[i+1]; // only one load and compare inside the loop
bool bc_lt = b < c;
n += (ab_lt & bc_lt);
ab_lt = bc_lt;
a = b; // unused inside the loop, only the compare result is needed
b = c;
}
return n;
}
clang 3.8
-O3: Unrolls with 4 loads inside the loop (clang typically likes to unroll by 4 when there aren't complex loop-carried dependencies).
4 cmp/setcc, 4x and/movzx, 4x add. So clang did exactly what I was hoping, and made near-optimal scalar code. This was the fastest non-vectorized version, and (on core2 wheremovupsunaligned loads are slow) is as fast as gcc's vectorized versions.gcc 5.2
-O3: Fails to auto-vectorize. My theory on that is that accessing the array outside the loop confuses the auto-vectorizer. Maybe because we do it before checkingv.size(), or maybe just in general.하나의로드, 하나의 cmp / setcc, 그리고
and반복 당 하나씩 우리가 바라는 스칼라 코드로 컴파일합니다 . 그러나 gcc-mtune=core2는 큰 문제 가 있는 경우 에도 부분 레지스터 스톨을 생성합니다 (그의 일부만 작성한 후 와이드 레지스터를 읽을 때 병합 uop을 삽입하는 2 ~ 3 사이클 스톨). (setcc8 비트 피연산자 크기로만 사용할 수 있습니다. IMO는 AMD가 AMD64 ISA를 설계 할 때 변경 했어야합니다.) 이것이 gcc의 코드가 clang보다 2.5 배 느리게 실행되는 주된 이유입니다.
## the loop in f3(), from gcc 5.2 -O3 (same code with -O2)
.L31:
add rcx, 1 # i,
mov edi, DWORD PTR [r10+rcx*4] # a, MEM[base: _19, index: i_13, step: 4, offset: 0]
cmp edi, r8d # a, a # gcc's verbose-asm comments are a bit bogus here: one of these `a`s is from the last iteration, so this is really comparing c, b
mov r8d, edi # a, a
setg sil #, tmp124
and edx, esi # D.111089, tmp124 # PARTIAL-REG STALL: reading esi after writing sil
movzx edx, dl # using movzx to widen sil to esi would have solved the problem, instead of doing it after the and
add eax, edx # n, D.111085 # n += ...
cmp r9, rcx # upper, i
mov edx, esi # ab_lt, tmp124
jne .L31 #,
ret
'programing tip' 카테고리의 다른 글
| Golang은 가변 기능을 지원합니까? (0) | 2020.11.28 |
|---|---|
| redux에서 AJAX 요청을 만드는 방법 (0) | 2020.11.28 |
| .NET 단위 테스트 패키지? (0) | 2020.11.28 |
| git-svn이 특정 svn 브랜치를 원격 저장소로 사용하게하려면 어떻게해야합니까? (0) | 2020.11.28 |
| C ++에서 문자열로 가득 찬 std :: map을 반복하는 방법 (0) | 2020.11.28 |