<질문>
특히, 일련의 if ... else if 문이 있고 각 문이 참으로 평가 될 상대 확률을 미리 알고 있다면 확률 순서대로 정렬하는 데 실행 시간이 얼마나 차이가나요? 예를 들어 다음을 선호해야합니까?
if (highly_likely)
//do something
else if (somewhat_likely)
//do something
else if (unlikely)
//do something
이에?:
if (unlikely)
//do something
else if (somewhat_likely)
//do something
else if (highly_likely)
//do something
정렬 된 버전이 더 빠를 것이 분명해 보이지만 가독성이나 부작용의 존재를 위해 최적화되지 않은 순서로 정렬 할 수 있습니다. 또한 실제로 코드를 실행할 때까지 CPU가 분기 예측을 얼마나 잘 수행하는지 알기 어렵습니다.
그래서 이것을 실험하는 과정에서 특정 사례에 대한 내 질문에 답하게되었지만 다른 의견 / 통찰도 듣고 싶습니다.
중요 :이 질문은 if 문이 프로그램 동작에 다른 영향을주지 않고 임의로 재정렬 될 수 있다고 가정합니다. 내 대답에는 세 가지 조건부 테스트가 상호 배타적이며 부작용이 없습니다. 확실히 원하는 행동을 얻기 위해 진술을 특정 순서로 평가해야한다면 효율성 문제는 논쟁의 여지가 있습니다.
<답변1>
일반적으로 모든 인텔 CPU는 아니지만 대부분의 인텔 CPU는 순방향 분기를 처음 볼 때 사용되지 않는다고 가정합니다. Godbolt의 작업을 참조하십시오.
그 후 분기는 분기 예측 캐시로 이동하고 과거 동작은 미래 분기 예측을 알리는 데 사용됩니다.
따라서 타이트한 루프에서 오 순서의 영향은 상대적으로 작을 것입니다. 분기 예측기는 어떤 분기 세트가 가장 가능성이 높은지 학습 할 것이며 루프에 사소한 양의 작업이있는 경우 작은 차이가 많이 합산되지 않습니다.
일반적인 코드에서 대부분의 컴파일러는 기본적으로 (다른 이유가 없음) 생성 된 기계어 코드를 코드에서 대략적으로 주문한 방식으로 정렬합니다. 따라서 if 문은 실패 할 때 정방향 분기입니다.
따라서 "첫 만남"에서 최상의 분기 예측을 얻을 가능성이 낮은 순서로 분기를 정렬해야합니다.
일련의 조건에 대해 여러 번 밀접하게 반복되고 사소한 작업을 수행하는 마이크로 벤치 마크는 명령 수 등의 작은 효과에 의해 지배 될 것이며 상대적인 분기 예측 문제에는 거의 영향을 미치지 않을 것입니다. 따라서이 경우 경험적 규칙이 신뢰할 수 없으므로 프로파일 링을해야합니다.
그 외에도 벡터화 및 기타 여러 최적화가 작고 타이트한 루프에 적용됩니다.
따라서 일반적인 코드에서 가장 가능성이 높은 코드를 if 블록에 넣으면 캐시되지 않은 분기 예측 누락이 최소화됩니다. 빡빡한 루프에서 시작하려면 일반적인 규칙을 따르고 더 많은 것을 알고 싶다면 프로필을 선택하는 것 외에는 선택의 여지가 거의 없습니다.
당연히 일부 테스트가 다른 테스트보다 훨씬 저렴하면이 모든 것이 창 밖으로 나옵니다.
<답변2>
두 개의 다른 if ... else if 블록의 실행 시간을 측정하기 위해 다음 테스트를 구성했습니다. 하나는 확률 순서로 정렬되고 다른 하나는 역순으로 정렬되었습니다.
#include
#include
#include
#include
#include
#include
using namespace std;
int main()
{
long long sortedTime = 0;
long long reverseTime = 0;
for (int n = 0; n != 500; ++n)
{
//Generate a vector of 5000 random integers from 1 to 100
random_device rnd_device;
mt19937 rnd_engine(rnd_device());
uniform_int_distribution rnd_dist(1, 100);
auto gen = std::bind(rnd_dist, rnd_engine);
vector rand_vec(5000);
generate(begin(rand_vec), end(rand_vec), gen);
volatile int nLow, nMid, nHigh;
chrono::time_point start, end;
//Sort the conditional statements in order of increasing likelyhood
nLow = nMid = nHigh = 0;
start = chrono::high_resolution_clock::now();
for (int& i : rand_vec) {
if (i >= 95) ++nHigh; //Least likely branch
else if (i < 20) ++nLow;
else if (i >= 20 && i < 95) ++nMid; //Most likely branch
}
end = chrono::high_resolution_clock::now();
reverseTime += chrono::duration_cast(end-start).count();
//Sort the conditional statements in order of decreasing likelyhood
nLow = nMid = nHigh = 0;
start = chrono::high_resolution_clock::now();
for (int& i : rand_vec) {
if (i >= 20 && i < 95) ++nMid; //Most likely branch
else if (i < 20) ++nLow;
else if (i >= 95) ++nHigh; //Least likely branch
}
end = chrono::high_resolution_clock::now();
sortedTime += chrono::duration_cast(end-start).count();
}
cout << "Percentage difference: " << 100 * (double(reverseTime) - double(sortedTime)) / double(sortedTime) << endl << endl;
}
/ O2와 함께 MSVC2017을 사용하면 결과는 정렬 된 버전이 정렬되지 않은 버전보다 지속적으로 약 28 % 더 빠르다는 것을 보여줍니다. luk32의 의견에 따라 두 테스트의 순서도 변경하여 눈에 띄는 차이를 만들었습니다 (22 % 대 28 %). 이 코드는 Intel Xeon E5-2697 v2의 Windows 7에서 실행되었습니다. 물론 이것은 매우 문제에 따라 다르며 결정적인 답변으로 해석되어서는 안됩니다.
<답변3>
대상 시스템이 영향을 받는지 확실하지 않는 한 그렇지 않습니다. 기본적으로 가독성을 기준으로합니다.
나는 당신의 결과를 매우 의심합니다. 예제를 약간 수정 했으므로 실행을 되 돌리는 것이 더 쉽습니다. Ideone은 역순이 많지는 않지만 더 빠르다는 것을 일관되게 보여줍니다. 특정 실행에서 이것은 때때로 뒤집 혔습니다. 결과가 결정적이지 않다고 말하고 싶습니다. coliru는 실제적인 차이도보고하지 않습니다. 나중에 odroid xu4에서 Exynos5422 CPU를 확인할 수 있습니다.
문제는 최신 CPU에 분기 예측자가 있다는 것입니다. 데이터와 명령을 모두 미리 가져 오는 데 전념하는 많은 논리가 있으며 최신 x86 CPU는 이에 관해서는 다소 똑똑합니다. ARM 또는 GPU와 같은 일부 더 얇은 아키텍처는 이에 취약 할 수 있습니다. 그러나 그것은 컴파일러와 타겟 시스템 모두에 정말로 크게 의존합니다.
분기 순서 최적화는 매우 취약하고 일시적이라고 말할 수 있습니다. 정말 미세 조정 단계로만 수행하십시오.
암호:
#include
#include
#include
#include
#include
#include
using namespace std;
int main()
{
//Generate a vector of random integers from 1 to 100
random_device rnd_device;
mt19937 rnd_engine(rnd_device());
uniform_int_distribution rnd_dist(1, 100);
auto gen = std::bind(rnd_dist, rnd_engine);
vector rand_vec(5000);
generate(begin(rand_vec), end(rand_vec), gen);
volatile int nLow, nMid, nHigh;
//Count the number of values in each of three different ranges
//Run the test a few times
for (int n = 0; n != 10; ++n) {
//Run the test again, but now sort the conditional statements in reverse-order of likelyhood
{
nLow = nMid = nHigh = 0;
auto start = chrono::high_resolution_clock::now();
for (int& i : rand_vec) {
if (i >= 95) ++nHigh; //Least likely branch
else if (i < 20) ++nLow;
else if (i >= 20 && i < 95) ++nMid; //Most likely branch
}
auto end = chrono::high_resolution_clock::now();
cout << "Reverse-sorted: \t" << chrono::duration_cast(end-start).count() << "ns" << endl;
}
{
//Sort the conditional statements in order of likelyhood
nLow = nMid = nHigh = 0;
auto start = chrono::high_resolution_clock::now();
for (int& i : rand_vec) {
if (i >= 20 && i < 95) ++nMid; //Most likely branch
else if (i < 20) ++nLow;
else if (i >= 95) ++nHigh; //Least likely branch
}
auto end = chrono::high_resolution_clock::now();
cout << "Sorted:\t\t\t" << chrono::duration_cast(end-start).count() << "ns" << endl;
}
cout << endl;
}
}
<답변4>
내 5 센트. if 문이 다음에 의존해야하는 순서의 효과 인 것 같습니다.
이러한 요소를 탐색하기 위해 다음 기능을 벤치마킹했습니다.
for (i = 0; i < data_sz * 1024; i++) {
if (data[i] < check_point) // highly likely
s += 3;
else if (data[i] > check_point) // samewhat likely
s += 2;
else if (data[i] == check_point) // very unlikely
s += 1;
}
for (i = 0; i < data_sz * 1024; i++) {
if (data[i] == check_point) // very unlikely
s += 1;
else if (data[i] > check_point) // samewhat likely
s += 2;
else if (data[i] < check_point) // highly likely
s += 3;
}
for (i = 0; i < data_sz * 1024; i++) {
if (likely(data[i] < check_point)) // highly likely
s += 3;
else if (data[i] > check_point) // samewhat likely
s += 2;
else if (unlikely(data[i] == check_point)) // very unlikely
s += 1;
}
for (i = 0; i < data_sz * 1024; i++) {
if (unlikely(data[i] == check_point)) // very unlikely
s += 1;
else if (data[i] > check_point) // samewhat likely
s += 2;
else if (likely(data[i] < check_point)) // highly likely
s += 3;
}
데이터 배열에는 0에서 100 사이의 난수가 포함됩니다.
const int RANGE_MAX = 100;
uint8_t data[DATA_MAX * 1024];
static void data_init(int data_sz)
{
int i;
srand(0);
for (i = 0; i < data_sz * 1024; i++)
data[i] = rand() % RANGE_MAX;
}
다음 결과는 Intel i5 @ 3,2GHz 및 G ++ 6.3.0에 대한 것입니다. 첫 번째 인수는 check_point (즉, 가능성이 높은 if 문에 대한 확률 %%)이고, 두 번째 인수는 data_sz (즉, 반복 횟수)입니다.
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4 4660 ns 4658 ns 150948
ordered_ifs/50/8 25636 ns 25635 ns 27852
ordered_ifs/75/4 4326 ns 4325 ns 162613
ordered_ifs/75/8 18242 ns 18242 ns 37931
ordered_ifs/100/4 1673 ns 1673 ns 417073
ordered_ifs/100/8 3381 ns 3381 ns 207612
reversed_ifs/50/4 5342 ns 5341 ns 126800
reversed_ifs/50/8 26050 ns 26050 ns 26894
reversed_ifs/75/4 3616 ns 3616 ns 193130
reversed_ifs/75/8 15697 ns 15696 ns 44618
reversed_ifs/100/4 3738 ns 3738 ns 188087
reversed_ifs/100/8 7476 ns 7476 ns 93752
ordered_ifs_with_hints/50/4 5551 ns 5551 ns 125160
ordered_ifs_with_hints/50/8 23191 ns 23190 ns 30028
ordered_ifs_with_hints/75/4 3165 ns 3165 ns 218492
ordered_ifs_with_hints/75/8 13785 ns 13785 ns 50574
ordered_ifs_with_hints/100/4 1575 ns 1575 ns 437687
ordered_ifs_with_hints/100/8 3130 ns 3130 ns 221205
reversed_ifs_with_hints/50/4 6573 ns 6572 ns 105629
reversed_ifs_with_hints/50/8 27351 ns 27351 ns 25568
reversed_ifs_with_hints/75/4 3537 ns 3537 ns 197470
reversed_ifs_with_hints/75/8 16130 ns 16130 ns 43279
reversed_ifs_with_hints/100/4 3737 ns 3737 ns 187583
reversed_ifs_with_hints/100/8 7446 ns 7446 ns 93782
4K 반복 및 (거의) 매우 좋아하는 진술의 확률이 100 % 인 경우 차이는 223 %입니다.
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4 1673 ns 1673 ns 417073
reversed_ifs/100/4 3738 ns 3738 ns 188087
4K 반복 및 매우 좋아하는 진술의 50 % 확률의 경우 차이는 약 14 %입니다.
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4 4660 ns 4658 ns 150948
reversed_ifs/50/4 5342 ns 5341 ns 126800
매우 좋아하는 진술의 (거의) 100 % 확률에 대한 4K 및 8K 반복의 차이는 예상대로 약 2 배입니다.
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4 1673 ns 1673 ns 417073
ordered_ifs/100/8 3381 ns 3381 ns 207612
그러나 매우 좋아하는 진술의 50 % 확률에 대한 4K 및 8K 반복의 차이는 5,5 배입니다.
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4 4660 ns 4658 ns 150948
ordered_ifs/50/8 25636 ns 25635 ns 27852
왜 그렇습니까? 분기 예측자가 누락 되었기 때문입니다. 위에서 언급 한 각 경우에 대한 분기 누락은 다음과 같습니다.
ordered_ifs/100/4 0.01% of branch-misses
ordered_ifs/100/8 0.01% of branch-misses
ordered_ifs/50/4 3.18% of branch-misses
ordered_ifs/50/8 15.22% of branch-misses
따라서 내 i5에서 분기 예측기는 그다지 가능성이없는 분기와 대규모 데이터 세트에 대해 크게 실패합니다.
4K 반복의 경우 결과는 50 % 확률에서 다소 나 빠지고 100 %에 가까운 확률에서는 다소 더 좋습니다.
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4 4660 ns 4658 ns 150948
ordered_ifs/100/4 1673 ns 1673 ns 417073
ordered_ifs_with_hints/50/4 5551 ns 5551 ns 125160
ordered_ifs_with_hints/100/4 1575 ns 1575 ns 437687
그러나 8K 반복의 경우 결과가 항상 조금 더 좋습니다.
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/8 25636 ns 25635 ns 27852
ordered_ifs/100/8 3381 ns 3381 ns 207612
ordered_ifs_with_hints/50/8 23191 ns 23190 ns 30028
ordered_ifs_with_hints/100/8 3130 ns 3130 ns 221205
따라서 힌트도 도움이되지만 조금만 있습니다.
전반적인 결론은 다음과 같습니다. 결과가 놀라 울 수 있으므로 항상 코드를 벤치마킹하십시오.
도움이 되었기를 바랍니다.
<답변5>
여기에있는 다른 답변 중 일부를 기반으로 할 때 유일한 실제 대답은 다음과 같습니다. 최소한 다음 사항에 따라 달라집니다 (이 순서가 중요하지는 않지만).
- 각 분기의 상대 확률입니다. 이것은 원래의 질문입니다. 기존 답변에 따르면 확률 별 정렬이 도움이되는 몇 가지 조건이있는 것 같지만 항상 그런 것은 아닙니다. 상대 확률이 그다지 다르지 않으면 순서에 따라 차이가있을 가능성이 낮습니다. 그러나 첫 번째 조건이 99.999 %의 시간 동안 발생하고 다음 조건이 남은 것의 일부인 경우에는 가능성이 가장 높은 것을 먼저 배치하는 것이 타이밍 측면에서 유익하다고 가정합니다.
- 각 분기에 대한 참 / 거짓 조건을 계산하는 비용. 조건을 테스트하는 데 드는 시간 비용이 한 분기와 다른 분기에 대해 실제로 높은 경우 이는 타이밍과 효율성에 상당한 영향을 미칠 수 있습니다. 예를 들어, 계산하는 데 1 시간 단위가 걸리는 조건 (예 : 부울 변수의 상태 확인)과 계산하는 데 수만, 수백, 수천 또는 심지어 수백만 시간 단위가 걸리는 다른 조건 (예 : 디스크의 파일 또는 대규모 데이터베이스에 대해 복잡한 SQL 쿼리 수행). 코드가 매번 순서대로 조건을 확인한다고 가정하면 더 빠른 조건이 가장 먼저 발생해야합니다 (먼저 실패하는 다른 조건에 의존하지 않는 한).
- 컴파일러 / 인터프리터 일부 컴파일러 (또는 인터프리터)는 성능에 영향을 줄 수있는 다른 종류의 최적화를 포함 할 수 있습니다 (그리고 이들 중 일부는 컴파일 및 / 또는 실행 중에 특정 옵션을 선택한 경우에만 존재 함). 따라서 동일한 시스템에서 동일한 시스템에서 두 번의 컴파일 및 실행을 벤치마킹하지 않는 한, 문제가되는 분기의 순서 만 다른 동일한 컴파일러를 사용하는 경우 컴파일러 변형에 대해 약간의 여유를 주어야합니다.
- 운영 체제 / 하드웨어 luk32 및 Yakk에서 언급했듯이 다양한 CPU에는 자체 최적화 기능이 있습니다 (운영 체제와 마찬가지로). 따라서 벤치 마크는 여기서도 변동에 취약합니다.
- 코드 블록 실행 빈도 분기를 포함하는 블록에 거의 액세스하지 않는 경우 (예 : 시작 중 한 번만), 분기를 어떤 순서로 넣는지는 거의 중요하지 않습니다. 반면에 코드가 코드의 중요한 부분에서이 코드 블록을 망치면 순서가 중요 할 수 있습니다 (벤치 마크에 따라 다름).
확실하게 알 수있는 유일한 방법은 코드가 최종적으로 실행될 의도 된 시스템과 동일하거나 매우 유사한 시스템에서 특정 사례를 벤치마킹하는 것입니다. 하드웨어, 운영 체제 등이 다른 다양한 시스템에서 실행하려는 경우 여러 변형을 벤치마킹하여 어떤 것이 가장 좋은지 확인하는 것이 좋습니다. 한 유형의 시스템에서 하나의 순서로 코드를 컴파일하고 다른 유형의 시스템에서 다른 순서로 코드를 컴파일하는 것도 좋은 생각 일 수 있습니다.
내 개인적인 경험 법칙 (대부분의 경우 벤치 마크가없는 경우)은 다음을 기준으로 주문하는 것입니다.
<답변6>
일반적으로 고성능 코드에서이 문제를 해결하는 방법은 가장 읽기 쉬운 순서를 유지하면서 컴파일러에 힌트를 제공하는 것입니다. 다음은 Linux 커널의 한 예입니다.
if (likely(access_ok(VERIFY_READ, from, n))) {
kasan_check_write(to, n);
res = raw_copy_from_user(to, from, n);
}
if (unlikely(res))
memset(to + (n - res), 0, res);
여기에서는 액세스 확인이 통과되고 res에 오류가 반환되지 않는다는 가정이 있습니다. 이러한 if 절 중 하나를 재정렬하려고하면 코드가 혼란 스러울 뿐이지 만, possible () 및 expected () 매크로는 실제로 정상적인 경우와 예외가 무엇인지 지적함으로써 가독성을 돕습니다.
이러한 매크로의 Linux 구현은 GCC 특정 기능을 사용합니다. clang과 Intel C 컴파일러가 동일한 구문을 지원하는 것 같지만 MSVC에는 이러한 기능이 없습니다.
<답변7>
또한 컴파일러와 컴파일하는 플랫폼에 따라 다릅니다.
이론적으로 가장 가능성이 높은 조건은 컨트롤 점프를 가능한 한 줄여야합니다.
일반적으로 가장 가능성이 높은 조건은 다음과 같습니다.
if (most_likely) {
// most likely instructions
} else …
가장 인기있는 asm은 조건이 참일 때 점프하는 조건부 분기를 기반으로합니다. 해당 C 코드는 다음과 같은 의사 asm으로 변환 될 수 있습니다.
jump to ELSE if not(most_likely)
// most likely instructions
jump to end
ELSE:
…
이것은 프로그램 카운터가 변경 되었기 때문에 (정말 일반적인 파이프 라인을 지원하는 아키텍처의 경우) 점프로 인해 CPU가 실행 파이프 라인을 취소하고 중단되기 때문입니다. 그런 다음 컴파일러에 관한 것인데, 이는 통계적으로 가장 가능성이 높은 제어 조건이 점프를 적게 만드는 것에 대한 정교한 최적화를 적용하거나 적용하지 않을 수 있습니다.
<답변8>
Lik32 코드를 사용하여 내 컴퓨터에서 테스트를 다시 실행하기로 결정했습니다. 내 창이나 컴파일러가 고해상도 1ms라고 생각하여 변경해야했습니다.
mingw32-g ++. exe -O3 -Wall -std = c ++ 11 -f 예외 -g
vector rand_vec(10000000);
GCC는 두 원본 코드에서 동일한 변환을 수행했습니다.
세 번째 조건은 항상 참이어야하므로 두 개의 첫 번째 조건 만 테스트됩니다. GCC는 여기서 일종의 셜록입니다.
역전
.L233:
mov DWORD PTR [rsp+104], 0
mov DWORD PTR [rsp+100], 0
mov DWORD PTR [rsp+96], 0
call std::chrono::_V2::system_clock::now()
mov rbp, rax
mov rax, QWORD PTR [rsp+8]
jmp .L219
.L293:
mov edx, DWORD PTR [rsp+104]
add edx, 1
mov DWORD PTR [rsp+104], edx
.L217:
add rax, 4
cmp r14, rax
je .L292
.L219:
mov edx, DWORD PTR [rax]
cmp edx, 94
jg .L293 // >= 95
cmp edx, 19
jg .L218 // >= 20
mov edx, DWORD PTR [rsp+96]
add rax, 4
add edx, 1 // < 20 Sherlock
mov DWORD PTR [rsp+96], edx
cmp r14, rax
jne .L219
.L292:
call std::chrono::_V2::system_clock::now()
.L218: // further down
mov edx, DWORD PTR [rsp+100]
add edx, 1
mov DWORD PTR [rsp+100], edx
jmp .L217
And sorted
mov DWORD PTR [rsp+104], 0
mov DWORD PTR [rsp+100], 0
mov DWORD PTR [rsp+96], 0
call std::chrono::_V2::system_clock::now()
mov rbp, rax
mov rax, QWORD PTR [rsp+8]
jmp .L226
.L296:
mov edx, DWORD PTR [rsp+100]
add edx, 1
mov DWORD PTR [rsp+100], edx
.L224:
add rax, 4
cmp r14, rax
je .L295
.L226:
mov edx, DWORD PTR [rax]
lea ecx, [rdx-20]
cmp ecx, 74
jbe .L296
cmp edx, 19
jle .L297
mov edx, DWORD PTR [rsp+104]
add rax, 4
add edx, 1
mov DWORD PTR [rsp+104], edx
cmp r14, rax
jne .L226
.L295:
call std::chrono::_V2::system_clock::now()
.L297: // further down
mov edx, DWORD PTR [rsp+96]
add edx, 1
mov DWORD PTR [rsp+96], edx
jmp .L224
따라서 이것은 마지막 경우에 분기 예측이 필요하지 않다는 것을 제외하고는 많은 것을 알려주지 않습니다.
이제 6 개의 if 조합을 모두 시도했는데, 상위 2 개는 원래 역순으로 정렬되었습니다. high는> = 95, low는 <20, mid는 20-94이며 각각 10000000 반복입니다.
high, low, mid: 43000000ns
mid, low, high: 46000000ns
high, mid, low: 45000000ns
low, mid, high: 44000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns
high, low, mid: 44000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 45000000ns
high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns
high, low, mid: 42000000ns
mid, low, high: 46000000ns
high, mid, low: 46000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 43000000ns
high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 44000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns
high, low, mid: 43000000ns
mid, low, high: 48000000ns
high, mid, low: 44000000ns
low, mid, high: 44000000ns
mid, high, low: 45000000ns
low, high, mid: 45000000ns
high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns
high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns
high, low, mid: 43000000ns
mid, low, high: 46000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 45000000ns
low, high, mid: 44000000ns
high, low, mid: 42000000ns
mid, low, high: 46000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 45000000ns
low, high, mid: 44000000ns
1900020, 7498968, 601012
Process returned 0 (0x0) execution time : 2.899 s
Press any key to continue.
그래서 왜 주문이 높고, 낮고, 중간보다 빠르다 (약간)
가장 예측할 수없는 것이 마지막이므로 분기 예측자를 통해 실행되지 않기 때문입니다.
if (i >= 95) ++nHigh; // most predictable with 94% taken
else if (i < 20) ++nLow; // (94-19)/94% taken ~80% taken
else if (i >= 20 && i < 95) ++nMid; // never taken as this is the remainder of the outfalls.
따라서 가지는 예측되고, 취해지며 나머지는
6 % + (0.94 *) 20 %는 잘못 예측합니다.
"정렬"
if (i >= 20 && i < 95) ++nMid; // 75% not taken
else if (i < 20) ++nLow; // 19/25 76% not taken
else if (i >= 95) ++nHigh; //Least likely branch
가지는 취하지 않고 취하지 않고 셜록으로 예측됩니다.
25 % + (0.75 *) 24 % 잘못된 예측
18 ~ 23 %의 차이 (~ 9 %의 측정 된 차이)를 제공하지만 %를 잘못 예측하는 대신주기를 계산해야합니다.
17주기가 내 Nehalem CPU의 페널티를 잘못 예측하고 각 검사가 발행하는 데 1주기 (4-5 명령)가 걸리고 루프도 1주기가 걸린다고 가정 해 봅시다. 데이터 종속성은 카운터와 루프 변수이지만, 잘못된 예측이 벗어나면 타이밍에 영향을주지 않아야합니다.
따라서 "역"의 경우 타이밍을 얻습니다 (컴퓨터 아키텍처 : A Quantitative Approach IIRC에서 사용되는 공식이어야 함).
mispredict*penalty+count+loop
0.06*17+1+1+ (=3.02)
(propability)*(first check+mispredict*penalty+count+loop)
(0.19)*(1+0.20*17+1+1)+ (= 0.19*6.4=1.22)
(propability)*(first check+second check+count+loop)
(0.75)*(1+1+1+1) (=3)
= 7.24 cycles per iteration
"sorted"도 마찬가지입니다.
0.25*17+1+1+ (=6.25)
(1-0.75)*(1+0.24*17+1+1)+ (=.25*7.08=1.77)
(1-0.75-0.19)*(1+1+1+1) (= 0.06*4=0.24)
= 8.26
(8.26-7.24) /8.26 = 13.8 % vs. ~ 9 % 측정 (측정에 가깝습니다!?!).
따라서 OP의 명백한 것은 분명하지 않습니다.
이러한 테스트를 사용하면 더 복잡한 코드 또는 더 많은 데이터 종속성이있는 다른 테스트는 확실히 다를 수 있으므로 사례를 측정하십시오.
테스트 순서를 변경하면 결과가 변경되었지만 루프 시작의 정렬이 다르기 때문일 수 있습니다. 루프 시작은 모든 최신 Intel CPU에서 16 바이트로 정렬되어야하지만이 경우에는 그렇지 않습니다.
<답변9>
원하는 논리적 순서로 배치하십시오. 물론 분기가 느릴 수 있지만 분기가 컴퓨터에서 수행하는 작업의 대부분이되어서는 안됩니다.
코드의 성능에 중요한 부분을 작업하는 경우 논리적 순서, 프로파일 기반 최적화 및 기타 기술을 사용하십시오. 그러나 일반 코드의 경우 스타일 선택에 더 가깝다고 생각합니다.
<답변10>
if-else 문의 상대 확률을 이미 알고있는 경우 성능을 위해 정렬 된 방식을 사용하는 것이 좋습니다. 이는 하나의 조건 (진짜 조건) 만 확인하기 때문입니다.
정렬되지 않은 방식으로 컴파일러는 모든 조건을 불필요하게 확인하고 시간이 걸립니다.
'개발 > C++' 카테고리의 다른 글
| STL 또는 Qt 컨테이너? (0) | 2020.09.30 |
|---|---|
| 역방향 반복기로 지우기를 호출하는 방법 (0) | 2020.09.30 |
| 보호 또는 개인 생성자 만있는 클래스에서 :: std :: make_shared를 어떻게 호출합니까? (0) | 2020.09.30 |
| 흥미로운 반복 템플릿 패턴 (CRTP)은 무엇입니까? (0) | 2020.09.30 |