Khususnya, jika saya memiliki serangkaian if... else ifpernyataan, dan entah bagaimana saya tahu sebelumnya probabilitas relatif yang akan dievaluasi oleh setiap pernyataan true, berapa banyak perbedaan dalam waktu eksekusi yang dibuat untuk menyortirnya dalam urutan probabilitas? Misalnya, saya harus memilih ini:

if (highly_likely)
  //do something
else if (somewhat_likely)
  //do something
else if (unlikely)
  //do something

untuk ini?:

if (unlikely)
  //do something
else if (somewhat_likely)
  //do something
else if (highly_likely)
  //do something

Tampaknya jelas bahwa versi yang diurutkan akan lebih cepat, namun untuk keterbacaan atau adanya efek samping, kami mungkin ingin memesannya secara tidak optimal. Juga sulit untuk mengatakan seberapa baik CPU akan melakukan dengan prediksi cabang sampai Anda benar-benar menjalankan kode.

Jadi, dalam percobaan dengan ini, saya akhirnya menjawab pertanyaan saya sendiri untuk kasus tertentu, namun saya ingin mendengar pendapat / wawasan lain juga.

Penting: pertanyaan ini mengasumsikan bahwa ifpernyataan dapat ditata ulang secara sewenang-wenang tanpa memiliki efek lain pada perilaku program. Dalam jawaban saya, ketiga tes bersyarat ini saling eksklusif dan tidak menghasilkan efek samping. Tentu saja, jika pernyataan harus dievaluasi dalam urutan tertentu untuk mencapai perilaku yang diinginkan, maka masalah efisiensi diperdebatkan.

Sebagai aturan umum, kebanyakan jika tidak semua CPU Intel menganggap cabang ke depan tidak diambil saat pertama kali melihatnya. Lihat karya Godbolt .

Setelah itu, cabang masuk ke cache prediksi cabang, dan perilaku masa lalu digunakan untuk menginformasikan prediksi cabang di masa depan.

Jadi dalam loop yang ketat, efek misordering akan relatif kecil. Prediktor cabang akan mempelajari set cabang mana yang paling mungkin, dan jika Anda memiliki jumlah pekerjaan non-sepele dalam loop, perbedaan kecil tidak akan bertambah banyak.

Dalam kode umum, kebanyakan kompiler secara default (tidak memiliki alasan lain) akan memesan kode mesin yang diproduksi kira-kira seperti Anda memesannya dalam kode Anda. Jadi, jika pernyataan adalah cabang maju ketika mereka gagal.

Jadi, Anda harus memesan cabang Anda dalam urutan penurunan kemungkinan untuk mendapatkan prediksi cabang terbaik dari "pertemuan pertama".

Sebuah microbenchmark yang berulang kali berulang kali ketat pada serangkaian kondisi dan melakukan pekerjaan sepele akan didominasi oleh efek kecil dari jumlah instruksi dan sejenisnya, dan sedikit dalam hal masalah prediksi cabang relatif. Jadi dalam hal ini Anda harus profil , karena aturan praktis tidak akan dapat diandalkan.

Selain itu, vektorisasi dan banyak optimasi lainnya berlaku untuk loop ketat kecil.

Jadi dalam kode umum, masukkan kode yang paling mungkin ke dalam if blok, dan itu akan menghasilkan prediksi cabang un-cache paling sedikit. Dalam putaran yang ketat, ikuti aturan umum untuk memulai, dan jika Anda perlu tahu lebih banyak, Anda tidak punya banyak pilihan selain profil.

Tentu ini semua keluar jendela jika beberapa tes jauh lebih murah daripada yang lain.

Saya membuat tes berikut untuk menghitung waktu eksekusi dua blok if... berbeda else if, satu diurutkan berdasarkan probabilitas, yang lain diurutkan dalam urutan terbalik:

#include <chrono>
#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <functional>

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<int> rnd_dist(1, 100);
        auto gen = std::bind(rnd_dist, rnd_engine);
        vector<int> rand_vec(5000);
        generate(begin(rand_vec), end(rand_vec), gen);

        volatile int nLow, nMid, nHigh;
        chrono::time_point<chrono::high_resolution_clock> 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<chrono::nanoseconds>(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<chrono::nanoseconds>(end-start).count();

    }

    cout << "Percentage difference: " << 100 * (double(reverseTime) - double(sortedTime)) / double(sortedTime) << endl << endl;
}

Menggunakan MSVC2017 dengan / O2, hasilnya menunjukkan bahwa versi yang diurutkan secara konsisten sekitar 28% lebih cepat daripada versi yang tidak disortir. Per komentar luk32, saya juga mengganti urutan dua tes, yang membuat perbedaan nyata (22% vs 28%). Kode dijalankan di bawah Windows 7 pada Intel Xeon E5-2697 v2. Ini, tentu saja, sangat spesifik masalah dan tidak boleh ditafsirkan sebagai jawaban konklusif.

Tidak, Anda tidak boleh, kecuali Anda benar-benar yakin bahwa sistem target terpengaruh.Secara default, pergi dengan keterbacaan.

Saya sangat meragukan hasil Anda. Saya telah sedikit memodifikasi contoh Anda, jadi membalikkan eksekusi lebih mudah. Ideone agak konsisten menunjukkan bahwa urutan terbalik lebih cepat, meskipun tidak banyak. Pada menjalankan tertentu bahkan ini kadang-kadang terbalik. Saya akan mengatakan hasilnya tidak meyakinkan. coliru melaporkan tidak ada perbedaan nyata juga. Saya dapat memeriksa CPU Exynos5422 pada x4 odroid saya nanti.

Masalahnya adalah bahwa CPU modern memiliki prediktor cabang. Ada banyak-banyak logika yang didedikasikan untuk mengambil data dan instruksi, dan CPU x86 modern agak pintar, ketika sampai pada hal ini. Beberapa arsitektur yang lebih ramping seperti ARM atau GPU mungkin rentan terhadap hal ini. Tetapi ini sangat tergantung pada kompiler dan sistem target.

Saya akan mengatakan bahwa optimasi pemesanan cabang cukup rapuh dan fana. Lakukan hanya sebagai langkah yang benar-benar selaras.

Kode:

#include <chrono>
#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <functional>

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<int> rnd_dist(1, 100);
    auto gen = std::bind(rnd_dist, rnd_engine);
    vector<int> 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<chrono::nanoseconds>(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<chrono::nanoseconds>(end-start).count() << "ns" << endl;
        }
        cout << endl;
    }
}

Hanya 5 sen saya. Tampaknya efek memesan jika pernyataan harus bergantung pada:

1. Probabilitas masing-masing pernyataan if.

2. Jumlah iterasi, sehingga prediktor cabang bisa masuk.

3. Petunjuk kompiler yang mungkin / tidak mungkin, yaitu tata letak kode.

Untuk menjelajahi faktor-faktor itu, saya membuat tolok ukur fungsi-fungsi berikut:

ordered_ifs ()

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;
}

reversed_ifs ()

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;
}

ordered_ifs_with_hints ()

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;
}

reversed_ifs_with_hints ()

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;
}

data

Array data berisi angka acak antara 0 dan 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;
}

Hasil

Hasil berikut untuk Intel i5 @ 3,2 GHz dan G ++ 6.3.0. Argumen pertama adalah check_point (yaitu probabilitas dalam %% untuk pernyataan if sangat mungkin), argumen kedua adalah data_sz (yaitu jumlah iterasi).

---------------------------------------------------------------------
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

Analisis

1. Pemesanan Tidak Penting

Untuk iterasi 4K dan (hampir) 100% kemungkinan pernyataan yang sangat disukai, perbedaannya sangat besar: 223%:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4                   1673 ns       1673 ns     417073
reversed_ifs/100/4                  3738 ns       3738 ns     188087

Untuk iterasi 4K dan probabilitas 50% dari pernyataan yang sangat disukai, perbedaannya adalah sekitar 14%:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
reversed_ifs/50/4                   5342 ns       5341 ns     126800

2. Jumlah Iterasi Tidak Peduli

Perbedaan antara iterasi 4K dan 8K untuk (hampir) 100% kemungkinan pernyataan yang sangat disukai sekitar dua kali (seperti yang diharapkan):

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs/100/8                   3381 ns       3381 ns     207612

Tetapi perbedaan antara iterasi 4K dan 8K untuk probabilitas 50% dari pernyataan yang sangat disukai adalah 5,5 kali:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/50/8                   25636 ns      25635 ns      27852

Kenapa begitu? Karena prediktor cabang meleset. Inilah cabang yang terlewatkan untuk setiap kasus yang disebutkan di atas:

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

Jadi pada i5 saya, prediktor cabang gagal secara spektakuler untuk cabang yang tidak begitu mungkin dan kumpulan data besar.

3. Petunjuk Bantuan Sedikit

Untuk iterasi 4K hasilnya agak lebih buruk untuk probabilitas 50% dan agak lebih baik untuk mendekati probabilitas 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

Tetapi untuk iterasi 8K hasilnya selalu sedikit lebih baik:

---------------------------------------------------------------------
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

Jadi, petunjuknya juga membantu, tetapi hanya sedikit.

Kesimpulan keseluruhan adalah: selalu membandingkan kode, karena hasilnya mungkin mengejutkan.

Semoga itu bisa membantu.

Berdasarkan beberapa jawaban lain di sini, sepertinya satu-satunya jawaban nyata adalah: itu tergantung . Itu tergantung pada paling tidak hal-hal berikut (meskipun tidak harus dalam urutan kepentingan ini):

• Probabilitas relatif dari masing-masing cabang. Ini adalah pertanyaan asli yang diajukan. Berdasarkan jawaban yang ada, tampaknya ada beberapa kondisi di mana pemesanan dengan probabilitas membantu, tetapi tampaknya tidak selalu demikian. Jika probabilitas relatif tidak jauh berbeda, maka tidak mungkin membuat perbedaan apa urutannya. Namun, jika kondisi pertama terjadi 99,999% dari waktu dan yang berikutnya adalah sebagian kecil dari apa yang tersisa, maka saya akan berasumsi bahwa menempatkan yang paling utama terlebih dahulu akan bermanfaat dalam hal waktu.
• Biaya perhitungan kondisi benar / salah untuk setiap cabang. Jika biaya waktu pengujian kondisi sangat tinggi untuk satu cabang dibandingkan yang lain, maka ini kemungkinan akan berdampak signifikan pada waktu dan efisiensi. Sebagai contoh, pertimbangkan suatu kondisi yang membutuhkan 1 unit waktu untuk menghitung (misalnya, memeriksa keadaan variabel Boolean) versus kondisi lain yang membutuhkan puluhan, ratusan, ribuan, atau bahkan jutaan unit waktu untuk dihitung (misalnya, memeriksa isi file pada disk atau melakukan query SQL yang kompleks terhadap database besar). Dengan asumsi kode memeriksa kondisi secara berurutan setiap kali, kondisi yang lebih cepat mungkin harus menjadi yang pertama (kecuali mereka bergantung pada kondisi lain yang gagal terlebih dahulu).
• Kompiler / Juru Bahasa Beberapa penyusun (atau juru bahasa) dapat menyertakan optimalisasi satu jenis yang lain yang dapat mempengaruhi kinerja (dan beberapa di antaranya hanya ada jika opsi tertentu dipilih selama kompilasi dan / atau eksekusi). Jadi, kecuali jika Anda membandingkan dua kompilasi dan eksekusi kode yang identik pada sistem yang sama menggunakan kompiler yang sama persis di mana satu-satunya perbedaan adalah urutan cabang yang bersangkutan, Anda harus memberikan kelonggaran untuk variasi kompiler.
• Sistem Operasi / Perangkat Keras Seperti disebutkan oleh luk32 dan Yakk, berbagai CPU memiliki optimasi sendiri (seperti halnya sistem operasi). Jadi tolok ukur sekali lagi rentan terhadap variasi di sini.
• Frekuensi pelaksanaan blok kode Jika blok yang menyertakan cabang jarang diakses (mis., Hanya sekali selama startup), maka mungkin sangat penting urutan apa yang Anda lakukan untuk menempatkan cabang. Di sisi lain, jika kode Anda memalu di blok kode ini selama bagian penting dari kode Anda, maka memesan mungkin sangat berarti (tergantung pada tolok ukur).

Satu-satunya cara untuk mengetahui secara pasti adalah dengan membandingkan kasus spesifik Anda, lebih disukai pada sistem yang identik dengan (atau sangat mirip dengan) sistem yang dimaksud di mana kode akhirnya akan berjalan. Jika ini dimaksudkan untuk berjalan pada satu set sistem yang berbeda-beda dengan perangkat keras yang berbeda, sistem operasi, dll., Maka itu ide yang baik untuk melakukan benchmarking di berbagai variasi untuk melihat mana yang terbaik. Bahkan mungkin ide yang baik untuk membuat kode dikompilasi dengan satu pemesanan pada satu jenis sistem dan satu lagi pemesanan pada jenis sistem lainnya.

Aturan praktis saya (untuk kebanyakan kasus, tanpa adanya patokan) adalah memesan berdasarkan:

1. Kondisi yang bergantung pada hasil dari kondisi sebelumnya,
2. Biaya komputasi kondisinya, lalu
3. Probabilitas relatif dari masing-masing cabang.

Cara saya biasanya melihat ini diselesaikan untuk kode kinerja tinggi adalah menjaga urutan yang paling mudah dibaca, tetapi memberikan petunjuk kepada kompiler. Ini adalah salah satu contoh dari kernel 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);

Di sini asumsinya adalah bahwa pemeriksaan akses akan berlalu, dan tidak ada kesalahan yang dikembalikan res. Mencoba untuk menyusun ulang salah satu dari ini jika klausa hanya akan membingungkan kode, tetapi likely()danunlikely() makro benar-benar membantu keterbacaan dengan menunjukkan apa kasus normal dan apa pengecualiannya.

Implementasi Linux dari makro tersebut menggunakan fitur spesifik GCC . Tampaknya dentang dan kompiler Intel C mendukung sintaks yang sama, tetapi MSVC tidak memiliki fitur tersebut .

Juga tergantung pada kompiler Anda dan platform yang Anda kompilasi.

Secara teori, kondisi yang paling mungkin harus membuat kontrol melompat seminimal mungkin.

Biasanya kondisi yang paling mungkin adalah yang pertama:

if (most_likely) {
     // most likely instructions
} else …

ASM paling populer didasarkan pada cabang kondisional yang melompat ketika kondisinya benar . Kode C itu kemungkinan akan diterjemahkan ke pseudo asm tersebut:

jump to ELSE if not(most_likely)
// most likely instructions
jump to end
ELSE:
…

Ini karena lompatan membuat cpu membatalkan pipa eksekusi dan berhenti karena penghitung program berubah (untuk arsitektur yang mendukung pipa yang benar-benar umum). Kemudian tentang kompiler, yang mungkin atau mungkin tidak menerapkan beberapa optimasi canggih tentang memiliki kondisi yang paling mungkin secara statistik untuk mendapatkan kontrol membuat lebih sedikit lompatan.

Saya memutuskan untuk menjalankan kembali tes pada mesin saya sendiri menggunakan kode Lik32. Saya harus mengubahnya karena windows atau kompiler saya berpikir resolusi tinggi adalah 1 ms, menggunakan

mingw32-g ++. exe -O3 -Wall -std = c ++ 11 -feksepsi -g

vector<int> rand_vec(10000000);

GCC telah melakukan transformasi yang sama pada kedua kode asli.

Perhatikan bahwa hanya dua kondisi pertama yang diuji karena yang ketiga harus selalu benar, GCC adalah sejenis Sherlock di sini.

Balik

.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

Jadi ini tidak memberi tahu kita banyak kecuali bahwa kasus terakhir tidak memerlukan prediksi cabang.

Sekarang saya mencoba semua 6 kombinasi if, 2 teratas adalah yang asli terbalik dan diurutkan. tinggi> = 95, rendah <20, sedang 20-94 dengan 10.000.000 iterasi masing-masing.

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.

Jadi mengapa urutannya tinggi, rendah, med maka lebih cepat (sedikit)

Karena yang paling tidak dapat diprediksi adalah yang terakhir dan karena itu tidak pernah dijalankan melalui prediktor cabang.

          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.

Jadi cabang akan diprediksi diambil, diambil, dan sisanya dengan

6% + (0,94 *) 20% mispredicts.

"Diurutkan"

          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

Cabang-cabang akan diprediksi dengan tidak diambil, tidak diambil dan Sherlock.

25% + (0,75 *) 24% salah duga

Memberikan perbedaan 18-23% (perbedaan terukur ~ 9%) tetapi kita perlu menghitung siklus alih-alih salah mengartikan%.

Mari kita asumsikan 17 siklus kesalahan hukuman pada CPU Nehalem saya dan bahwa setiap cek membutuhkan 1 siklus untuk mengeluarkan (4-5 instruksi) dan loop mengambil satu siklus juga. Ketergantungan data adalah variabel penghitung dan loop, tetapi begitu salah duga tidak keluar dari situ seharusnya tidak mempengaruhi waktu.

Jadi untuk "membalikkan", kita mendapatkan timing (ini harus menjadi rumus yang digunakan dalam Arsitektur Komputer: Pendekatan Kuantitatif 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

dan sama untuk "diurutkan"

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% diukur (dekat dengan yang diukur!?!).

Jadi yang jelas dari OP tidak jelas.

Dengan tes ini, tes lain dengan kode yang lebih rumit atau lebih banyak ketergantungan data tentu akan berbeda, jadi ukur kasus Anda.

Mengubah urutan pengujian mengubah hasil, tetapi itu bisa jadi karena keberpihakan yang berbeda pada awal loop yang idealnya harus 16 byte yang diluruskan pada semua CPU Intel yang lebih baru tetapi tidak dalam kasus ini.

Masukkan mereka dalam urutan logis apa pun yang Anda suka. Tentu, cabang mungkin lebih lambat, tetapi tidak seharusnya bercabang menjadi mayoritas pekerjaan yang dilakukan komputer Anda.

Jika Anda bekerja pada bagian kode kinerja kritis, maka tentu saja menggunakan urutan logis, optimasi dipandu profil dan teknik lainnya, tetapi untuk kode umum, saya pikir itu benar-benar lebih dari pilihan gaya.

Jika Anda sudah tahu probabilitas relatif pernyataan if-else, maka untuk tujuan kinerja lebih baik menggunakan cara yang diurutkan, karena hanya akan memeriksa satu kondisi (yang benar).

Dengan cara yang tidak disortir kompiler akan memeriksa semua kondisi yang tidak perlu dan akan memakan waktu.