Mengapa memproses array yang diurutkan lebih cepat daripada memproses array yang tidak disortir?

Ini adalah bagian dari kode C ++ yang menunjukkan beberapa perilaku yang sangat aneh. Untuk beberapa alasan aneh, mengurutkan data secara ajaib membuat kode hampir enam kali lebih cepat:

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

• Tanpa std::sort(data, data + arraySize);, kode berjalan dalam 11,54 detik.
• Dengan data yang diurutkan, kode ini berjalan dalam 1,93 detik.

Awalnya, saya pikir ini mungkin hanya sebuah anomali bahasa atau kompiler, jadi saya mencoba Java:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

Dengan hasil yang serupa tetapi tidak terlalu ekstrem.

Pikiran pertama saya adalah penyortiran membawa data ke dalam cache, tetapi kemudian saya berpikir betapa konyolnya karena array baru saja dihasilkan.

• Apa yang sedang terjadi?
• Mengapa memproses array yang diurutkan lebih cepat daripada memproses array yang tidak disortir?

Kode ini merangkum beberapa istilah independen, jadi urutannya tidak masalah.

Anda adalah korban gagal prediksi cabang .

Apa itu Prediksi Cabang?

Pertimbangkan persimpangan jalan kereta:

_{Gambar oleh Mecanismo, via Wikimedia Commons. Digunakan di bawah lisensi CC-By-SA 3.0 .}

Sekarang demi argumen, anggaplah ini kembali pada 1800-an - sebelum komunikasi jarak jauh atau radio.

Anda adalah operator persimpangan dan Anda mendengar kereta datang. Anda tidak tahu ke mana harus pergi. Anda menghentikan kereta untuk bertanya kepada pengemudi ke arah mana mereka inginkan. Dan kemudian Anda mengatur sakelar dengan tepat.

Kereta berat dan banyak inersia. Jadi mereka butuh selamanya untuk memulai dan memperlambat.

Apakah ada cara yang lebih baik? Anda menebak ke arah mana kereta akan pergi!

• Jika Anda menebak dengan benar, itu berlanjut.
• Jika Anda salah menebak, kapten akan berhenti, mundur, dan berteriak kepada Anda untuk membalik sakelar. Kemudian dapat memulai kembali di jalur lain.

Jika Anda menebak dengan benar setiap waktu , kereta tidak akan pernah berhenti.
Jika Anda salah menebak terlalu sering , kereta akan menghabiskan banyak waktu untuk berhenti, mencadangkan, dan memulai kembali.

Pertimbangkan pernyataan if: Pada level prosesor, ini adalah instruksi cabang:

Anda adalah prosesor dan Anda melihat cabang. Anda tidak tahu ke mana akan pergi. Apa yang kamu kerjakan? Anda menghentikan eksekusi dan menunggu hingga instruksi sebelumnya selesai. Kemudian Anda melanjutkan jalan yang benar.

Prosesor modern rumit dan memiliki jaringan pipa yang panjang. Jadi mereka butuh selamanya untuk "pemanasan" dan "melambat".

Apakah ada cara yang lebih baik? Anda menebak ke arah mana cabang akan pergi!

• Jika Anda menebak dengan benar, Anda terus mengeksekusi.
• Jika Anda salah menebak, Anda perlu menyiram pipa dan kembali ke cabang. Kemudian Anda dapat memulai kembali jalan lain.

Jika Anda menebak dengan benar setiap kali , eksekusi tidak akan pernah berhenti.
Jika Anda salah menebak terlalu sering , Anda menghabiskan banyak waktu untuk menunda, memutar kembali, dan memulai kembali.

Ini adalah prediksi cabang. Saya akui itu bukan analogi terbaik karena kereta hanya bisa memberi sinyal arah dengan bendera. Tetapi di komputer, prosesor tidak tahu ke arah mana cabang akan pergi sampai saat terakhir.

Jadi, bagaimana menurut Anda secara strategis untuk meminimalkan berapa kali kereta harus naik dan turun ke jalur lain? Anda melihat sejarah masa lalu! Jika kereta pergi ke kiri 99% dari waktu, maka Anda menebak ke kiri. Jika itu bergantian, maka Anda mengubah tebakan Anda. Jika berjalan satu arah setiap tiga kali, Anda menebak yang sama ...

Dengan kata lain, Anda mencoba mengidentifikasi suatu pola dan mengikutinya. Ini kurang lebih bagaimana alat prediksi cabang bekerja.

Sebagian besar aplikasi memiliki cabang yang berperilaku baik. Jadi prediktor cabang modern biasanya akan mencapai> 90% hit rate. Tetapi ketika dihadapkan dengan cabang yang tidak dapat diprediksi tanpa pola yang dapat dikenali, prediktor cabang hampir tidak berguna.

Bacaan lebih lanjut: artikel "Prediktor cabang" di Wikipedia .

Seperti yang diisyaratkan dari atas, pelakunya adalah pernyataan if ini:

if (data[c] >= 128)
    sum += data[c];

Perhatikan bahwa data terdistribusi secara merata antara 0 dan 255. Ketika data diurutkan, kira-kira setengah dari iterasi tidak akan memasukkan pernyataan if. Setelah itu, mereka semua akan memasukkan pernyataan if.

Ini sangat bersahabat dengan prediktor cabang karena cabang secara berurutan pergi ke arah yang sama berkali-kali. Bahkan penghitung jenuh sederhana akan dengan benar memprediksi cabang kecuali untuk beberapa iterasi setelah berganti arah.

Visualisasi cepat:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

Namun, ketika data benar-benar acak, prediktor cabang dianggap tidak berguna, karena tidak dapat memprediksi data acak. Dengan demikian kemungkinan akan ada sekitar 50% kesalahan prediksi (tidak lebih baik dari menebak secara acak).

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

Jadi apa yang bisa dilakukan?

Jika kompiler tidak dapat mengoptimalkan cabang menjadi gerakan bersyarat, Anda dapat mencoba beberapa peretasan jika Anda bersedia mengorbankan keterbacaan untuk kinerja.

Menggantikan:

if (data[c] >= 128)
    sum += data[c];

dengan:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

Ini menghilangkan cabang dan menggantinya dengan beberapa operasi bitwise.

_{(Perhatikan bahwa peretasan ini tidak sepenuhnya setara dengan pernyataan if asli. Namun dalam kasus ini, peretasan ini berlaku untuk semua nilai input data[].)}

Benchmark: Core i7 920 @ 3.5 GHz

C ++ - Visual Studio 2010 - Rilis x64

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - NetBeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

Pengamatan:

• Dengan Cabang: Ada perbedaan besar antara data yang diurutkan dan yang tidak disortir.
• Dengan Peretasan: Tidak ada perbedaan antara data yang diurutkan dan yang tidak disortir.
• Dalam kasus C ++, peretasan sebenarnya sedikit lebih lambat dibandingkan dengan cabang saat data diurutkan.

Aturan umum adalah untuk menghindari percabangan yang bergantung pada data dalam loop kritis (seperti dalam contoh ini).

Memperbarui:

• GCC 4.6.1 dengan -O3atau -ftree-vectorizepada x64 dapat menghasilkan gerakan bersyarat. Jadi tidak ada perbedaan antara data yang diurutkan dan yang tidak disortir - keduanya cepat.

  (Atau agak cepat: untuk kasus yang sudah disortir, cmovbisa lebih lambat terutama jika GCC menempatkannya di jalur kritis alih-alih adil add, terutama pada Intel sebelum Broadwell di mana cmovmemiliki 2 siklus latensi: flag optimasi gcc -O3 membuat kode lebih lambat dari -O2 )

• VC ++ 2010 tidak dapat menghasilkan gerakan bersyarat untuk cabang ini bahkan di bawah /Ox.

• Intel C ++ Compiler (ICC) 11 melakukan sesuatu yang ajaib. Ini menukar kedua loop , sehingga mengangkat cabang yang tidak dapat diprediksi ke loop luar. Jadi tidak hanya itu kebal terhadap ramalan, itu juga dua kali lebih cepat dari apa pun yang dapat dihasilkan oleh VC ++ dan GCC! Dengan kata lain, ICC memanfaatkan loop-tes untuk mengalahkan benchmark ...

• Jika Anda memberikan kompiler Intel kode branchless, itu hanya akan langsung membuat vektor ... dan sama cepat dengan cabang (dengan pertukaran loop).

Ini menunjukkan bahwa kompiler modern yang matang sekalipun dapat sangat bervariasi dalam kemampuannya untuk mengoptimalkan kode ...

Prediksi cabang.

Dengan array yang diurutkan, kondisi data[c] >= 128pertama false- tama adalah deretan nilai, kemudian menjadi trueuntuk semua nilai yang lebih baru. Itu mudah diprediksi. Dengan array yang tidak disortir, Anda membayar biaya percabangan.

Alasan mengapa kinerja meningkat secara drastis ketika data disortir adalah bahwa hukuman prediksi cabang dihapus, seperti yang dijelaskan dengan indah dalam jawaban Mysticial .

Sekarang, jika kita melihat kodenya

if (data[c] >= 128)
    sum += data[c];

kita dapat menemukan bahwa arti if... else...cabang khusus ini adalah menambahkan sesuatu ketika suatu kondisi terpenuhi. Jenis cabang ini dapat dengan mudah diubah menjadi pernyataan pemindahan bersyarat , yang akan dikompilasi menjadi instruksi pemindahan bersyarat:, cmovldalam suatu x86sistem. Cabang dan dengan demikian penalti prediksi cabang potensial dihapus.

Dalam C, dengan demikian C++, pernyataan, yang akan dikompilasi secara langsung (tanpa optimasi apa pun) ke dalam instruksi pemindahan bersyarat x86, adalah operator ternary ... ? ... : .... Jadi kami menulis ulang pernyataan di atas menjadi pernyataan yang setara:

sum += data[c] >=128 ? data[c] : 0;

Sambil mempertahankan keterbacaan, kita dapat memeriksa faktor percepatan.

Pada Intel Core i7 -2600K @ 3.4 GHz dan Mode Rilis Visual Studio 2010, patokannya adalah (format disalin dari Mysticial):

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

Hasilnya kuat dalam beberapa tes. Kami mendapatkan speedup yang hebat ketika hasil cabang tidak dapat diprediksi, tetapi kami sedikit menderita saat diprediksi. Bahkan, ketika menggunakan gerakan kondisional, kinerjanya sama terlepas dari pola data.

Sekarang mari kita melihat lebih dekat dengan menyelidiki x86perakitan yang mereka hasilkan. Untuk kesederhanaan, kami menggunakan dua fungsi max1dan max2.

max1menggunakan cabang kondisional if... else ...:

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2menggunakan operator ternary ... ? ... : ...:

int max2(int a, int b) {
    return a > b ? a : b;
}

Pada mesin x86-64, GCC -Shasilkan perakitan di bawah ini.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2menggunakan kode jauh lebih sedikit karena penggunaan instruksi cmovge. Tetapi keuntungan nyata adalah bahwa max2tidak melibatkan lompatan cabang jmp,, yang akan memiliki penalti kinerja yang signifikan jika hasil yang diprediksi tidak benar.

Jadi mengapa langkah kondisional berkinerja lebih baik?

Dalam x86prosesor yang khas , pelaksanaan instruksi dibagi menjadi beberapa tahap. Secara kasar, kami memiliki perangkat keras yang berbeda untuk menangani tahapan yang berbeda. Jadi kita tidak perlu menunggu satu instruksi untuk menyelesaikan untuk memulai yang baru. Ini disebut pipelining .

Dalam kasus cabang, instruksi berikut ditentukan oleh yang sebelumnya, jadi kami tidak bisa melakukan pipelining. Kita harus menunggu atau memprediksi.

Dalam kasus pemindahan bersyarat, instruksi pemindahan bersyarat eksekusi dibagi menjadi beberapa tahap, tetapi tahap sebelumnya suka Fetchdan Decodetidak bergantung pada hasil dari instruksi sebelumnya; hanya tahap terakhir yang membutuhkan hasilnya. Jadi, kami menunggu sebagian kecil dari waktu eksekusi satu instruksi. Inilah sebabnya mengapa versi pemindahan bersyarat lebih lambat daripada cabang saat prediksi mudah.

Buku Computer Systems: A Programmer's Perspective, edisi kedua menjelaskan ini secara terperinci. Anda dapat memeriksa Bagian 3.6.6 untuk Petunjuk Pergerakan Bersyarat , seluruh Bab 4 untuk Arsitektur Prosesor , dan Bagian 5.11.2 untuk perawatan khusus untuk Prediksi Cabang dan Denda Kesalahan prediksi .

Kadang-kadang, beberapa kompiler modern dapat mengoptimalkan kode kami ke perakitan dengan kinerja yang lebih baik, kadang-kadang beberapa kompiler tidak dapat (kode tersebut menggunakan kompiler asli Visual Studio). Mengetahui perbedaan kinerja antara gerakan cabang dan bersyarat saat tidak dapat diprediksi dapat membantu kami menulis kode dengan kinerja yang lebih baik ketika skenario menjadi sangat kompleks sehingga kompiler tidak dapat mengoptimalkannya secara otomatis.

Jika Anda ingin tahu tentang lebih banyak optimasi yang dapat dilakukan untuk kode ini, pertimbangkan ini:

Dimulai dengan loop asli:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Dengan interchange loop, kita dapat dengan aman mengubah loop ini ke:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Kemudian, Anda dapat melihat bahwa ifkondisi bersyarat konstan selama eksekusi iloop, sehingga Anda dapat menarik ifkeluar:

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

Kemudian, Anda melihat bahwa loop dalam dapat diciutkan menjadi satu ekspresi tunggal, dengan asumsi model floating point memungkinkan ( /fp:fastdilemparkan, misalnya)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

Yang itu 100.000 kali lebih cepat dari sebelumnya.

Tidak diragukan lagi beberapa dari kita akan tertarik pada cara mengidentifikasi kode yang bermasalah untuk prediktor cabang CPU. Alat Valgrindcachegrind memiliki simulator prediktor cabang, diaktifkan dengan menggunakan --branch-sim=yesbendera. Menjalankannya di atas contoh dalam pertanyaan ini, dengan jumlah loop luar dikurangi menjadi 10.000 dan dikompilasi dengan g++, memberikan hasil ini:

Diurutkan:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

Tidak disortir:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

Mengebor ke dalam output line-by-line yang diproduksi oleh cg_annotatekita lihat untuk loop yang dimaksud:

Diurutkan:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

Tidak disortir:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

Ini memungkinkan Anda dengan mudah mengidentifikasi garis yang bermasalah - dalam versi yang tidak disortir, if (data[c] >= 128)garis tersebut menyebabkan 164.050.007 cabang kondisional yang salah prediksi (Bcm ) di bawah model prediktor cabang cachegrind, sedangkan itu hanya menyebabkan 10.006 dalam versi yang diurutkan.

Atau, di Linux Anda dapat menggunakan subsistem penghitung kinerja untuk menyelesaikan tugas yang sama, tetapi dengan kinerja asli menggunakan penghitung CPU.

perf stat ./sumtest_sorted

Diurutkan:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

Tidak disortir:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

Itu juga dapat melakukan anotasi kode sumber dengan pembongkaran.

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted

 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

Lihat tutorial kinerja untuk lebih jelasnya.

Saya baru saja membaca pertanyaan ini dan jawabannya, dan saya merasa ada jawaban yang hilang.

Cara umum untuk menghilangkan prediksi cabang yang saya temukan bekerja sangat baik dalam bahasa yang dikelola adalah pencarian tabel alih-alih menggunakan cabang (meskipun saya belum mengujinya dalam kasus ini).

Pendekatan ini bekerja secara umum jika:

1. itu meja kecil dan cenderung di-cache di prosesor, dan
2. Anda menjalankan hal-hal dalam loop yang cukup ketat dan / atau prosesor dapat melakukan preload data.

Latar belakang dan alasannya

Dari perspektif prosesor, memori Anda lambat. Untuk mengimbangi perbedaan dalam kecepatan, beberapa cache dibangun ke prosesor Anda (L1 / L2 cache). Jadi bayangkan Anda melakukan perhitungan yang bagus dan mencari tahu bahwa Anda perlu memori. Prosesor akan mendapatkan operasinya 'memuat' dan memuat potongan memori ke dalam cache - dan kemudian menggunakan cache untuk melakukan sisa perhitungan. Karena memori relatif lambat, 'memuat' ini akan memperlambat program Anda.

Seperti prediksi cabang, ini dioptimalkan dalam prosesor Pentium: prosesor memperkirakan bahwa ia perlu memuat sepotong data dan mencoba memuatnya ke dalam cache sebelum operasi benar-benar menyentuh cache. Seperti yang telah kita lihat, prediksi cabang terkadang salah besar - dalam skenario terburuk Anda harus kembali dan benar-benar menunggu beban memori, yang akan memakan waktu selamanya ( dengan kata lain: gagal prediksi cabang buruk, memori memuat setelah gagal prediksi cabang hanya mengerikan! ).

Untungnya bagi kita, jika pola akses memori dapat diprediksi, prosesor akan memuatnya dalam cache cepat dan semuanya baik-baik saja.

Hal pertama yang perlu kita ketahui adalah apa yang kecil ? Meskipun lebih kecil umumnya lebih baik, aturan praktis adalah tetap berpegang pada tabel pencarian yang berukuran <= 4096 byte. Sebagai batas atas: jika tabel pencarian Anda lebih besar dari 64K mungkin perlu dipertimbangkan kembali.

Membangun meja

Jadi kita sudah tahu bahwa kita bisa membuat tabel kecil. Hal berikutnya yang harus dilakukan adalah mendapatkan fungsi pencarian di tempat. Fungsi pencarian biasanya merupakan fungsi kecil yang menggunakan beberapa operasi integer dasar (dan, atau, xor, shift, tambah, hapus, dan mungkin gandakan). Anda ingin agar input Anda diterjemahkan oleh fungsi pencarian ke semacam 'kunci unik' di tabel Anda, yang kemudian hanya memberi Anda jawaban dari semua pekerjaan yang Anda inginkan.

Dalam hal ini:> = 128 berarti kita dapat menyimpan nilainya, <128 berarti kita membuangnya. Cara termudah untuk melakukannya adalah dengan menggunakan 'DAN': jika kita menyimpannya, kita DAN dengan 7FFFFFFF; jika kita ingin menyingkirkannya, kita DAN itu dengan 0. Perhatikan juga bahwa 128 adalah kekuatan 2 - jadi kita dapat melanjutkan dan membuat tabel 32768/128 bilangan bulat dan mengisinya dengan nol dan banyak 7FFFFFFFF's.

Bahasa yang dikelola

Anda mungkin bertanya-tanya mengapa ini bekerja dengan baik dalam bahasa yang dikelola. Setelah semua, bahasa yang dikelola memeriksa batas-batas array dengan cabang untuk memastikan Anda tidak mengacaukan ...

Ya, tidak persis ... :-)

Ada beberapa upaya untuk menghilangkan cabang ini untuk bahasa yang dikelola. Sebagai contoh:

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

Dalam kasus ini, jelas bagi kompiler bahwa kondisi batas tidak akan pernah mengenai. Setidaknya kompiler Microsoft JIT (tapi saya berharap Java melakukan hal serupa) akan melihat ini dan menghapus centangnya sama sekali. WOW, itu berarti tidak ada cabang. Demikian pula, ia akan menangani kasus-kasus nyata lainnya.

Jika Anda mengalami masalah dengan pencarian dalam bahasa yang dikelola - kuncinya adalah menambahkan & 0x[something]FFFfungsi pencarian Anda untuk membuat pemeriksaan batas dapat diprediksi - dan melihatnya berjalan lebih cepat.

Hasil dari kasus ini

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/

int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
{
    lookup[c] = (c >= 128) ? c : 0;
}

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        /* Here you basically want to use simple operations - so no
        random branches, but things like &, |, *, -, +, etc. are fine. */
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();

Karena data didistribusikan antara 0 dan 255 ketika array diurutkan, sekitar paruh pertama iterasi tidak akan masuk ke if- ifpernyataan ( pernyataan dibagikan di bawah).

if (data[c] >= 128)
    sum += data[c];

Pertanyaannya adalah: Apa yang membuat pernyataan di atas tidak dieksekusi dalam kasus tertentu seperti dalam kasus data yang diurutkan? Di sinilah "prediksi cabang". Prediktor cabang adalah sirkuit digital yang mencoba menebak ke arah mana suatu cabang (misalnya if-then-elsestruktur) akan berjalan sebelum ini diketahui dengan pasti. Tujuan dari prediktor cabang adalah untuk meningkatkan aliran dalam pipa instruksi. Prediktor cabang memainkan peran penting dalam mencapai kinerja efektif tinggi!

Mari kita lakukan beberapa penandaan bangku untuk memahaminya dengan lebih baik

Kinerja suatu ifpernyataan tergantung pada apakah kondisinya memiliki pola yang dapat diprediksi. Jika kondisi selalu benar atau selalu salah, logika prediksi cabang dalam prosesor akan mengambil pola. Di sisi lain, jika polanya tidak dapat diprediksi, ifpernyataan tersebut akan jauh lebih mahal.

Mari kita mengukur kinerja loop ini dengan kondisi berbeda:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Berikut adalah timing dari loop dengan pola true-false yang berbeda:

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF…           513

(i & 2) == 0             TTFFTTFF…           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275

(i & 8) == 0             8T 8F 8T 8F …       752

(i & 16) == 0            16T 16F 16T 16F …   490

Pola " benar-salah " buruk "dapat membuat ifpernyataan hingga enam kali lebih lambat daripada pola" baik "! Tentu saja, pola mana yang baik dan mana yang buruk tergantung pada instruksi persis yang dihasilkan oleh kompiler dan pada prosesor tertentu.

Jadi tidak ada keraguan tentang dampak prediksi cabang terhadap kinerja!

Salah satu cara untuk menghindari kesalahan prediksi cabang adalah membangun tabel pencarian, dan mengindeksnya menggunakan data. Stefan de Bruijn mendiskusikan hal itu dalam jawabannya.

Tetapi dalam kasus ini, kita tahu nilai berada dalam kisaran [0, 255] dan kita hanya peduli pada nilai> = 128. Itu berarti kita dapat dengan mudah mengekstraksi bit tunggal yang akan memberi tahu kita apakah kita menginginkan nilai atau tidak: dengan menggeser data ke 7 bit yang tepat, kita dibiarkan dengan 0 bit atau 1 bit, dan kita hanya ingin menambahkan nilai ketika kita memiliki 1 bit. Sebut saja bit ini "bit keputusan".

Dengan menggunakan nilai 0/1 dari bit keputusan sebagai indeks ke dalam array, kita dapat membuat kode yang akan sama cepatnya apakah data diurutkan atau tidak diurutkan. Kode kami akan selalu menambahkan nilai, tetapi ketika bit keputusan adalah 0, kami akan menambahkan nilai di tempat yang tidak kami pedulikan. Berikut kodenya:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Kode ini menghabiskan setengah dari tambahan tetapi tidak pernah memiliki kegagalan prediksi cabang. Ini jauh lebih cepat pada data acak daripada versi dengan pernyataan if aktual.

Tetapi dalam pengujian saya, tabel pencarian eksplisit sedikit lebih cepat dari ini, mungkin karena pengindeksan ke tabel pencarian sedikit lebih cepat daripada sedikit pergeseran. Ini menunjukkan bagaimana kode saya mengatur dan menggunakan tabel pencarian (secara imajinatif disebut lut"Tabel Pencarian" dalam kode). Berikut kode C ++:

// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

Dalam hal ini, tabel pencarian hanya 256 byte, sehingga sangat cocok dalam cache dan semuanya cepat. Teknik ini tidak akan bekerja dengan baik jika datanya bernilai 24-bit dan kami hanya ingin setengah dari mereka ... tabel pencarian akan terlalu besar untuk praktis. Di sisi lain, kita bisa menggabungkan dua teknik yang ditunjukkan di atas: pertama-tama pindahkan bit, lalu indeks tabel pencarian. Untuk nilai 24-bit yang hanya kami inginkan nilai setengahnya, kami berpotensi menggeser data dengan 12 bit, dan dibiarkan dengan nilai 12-bit untuk indeks tabel. Indeks tabel 12-bit menyiratkan tabel nilai 4096, yang mungkin praktis.

Teknik pengindeksan ke dalam array, alih-alih menggunakan ifpernyataan, dapat digunakan untuk memutuskan pointer mana yang akan digunakan. Saya melihat perpustakaan yang mengimplementasikan pohon biner, dan bukannya memiliki dua pointer bernama ( pLeftdan pRightatau apa pun) memiliki panjang array pointer-2 dan menggunakan teknik "bit keputusan" untuk memutuskan mana yang akan diikuti. Misalnya, alih-alih:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

perpustakaan ini akan melakukan sesuatu seperti:

i = (x < node->value);
node = node->link[i];

Berikut tautan ke kode ini: Red Black Trees , Eternally Confuzzled

Dalam kasus yang diurutkan, Anda dapat melakukan lebih baik daripada mengandalkan prediksi cabang yang berhasil atau trik perbandingan tanpa cabang: hapus cabang sepenuhnya.

Memang, array dipartisi dalam zona bersebelahan dengan data < 128dan dengan lainnya data >= 128. Jadi, Anda harus menemukan titik partisi dengan pencarian dikotomik (menggunakanLg(arraySize) = 15 perbandingan), kemudian lakukan akumulasi langsung dari titik itu.

Sesuatu seperti (tidak dicentang)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

atau, sedikit lebih dikaburkan

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

Pendekatan yang lebih cepat, yang memberikan solusi perkiraan untuk diurutkan atau tidak disortir adalah: sum= 3137536;(dengan asumsi distribusi yang benar-benar seragam, 16384 sampel dengan nilai yang diharapkan 191,5) :-)

Perilaku di atas terjadi karena prediksi Cabang.

Untuk memahami prediksi cabang, seseorang harus terlebih dahulu memahami Instruction Pipeline :

Setiap instruksi dipecah menjadi urutan langkah-langkah sehingga langkah-langkah berbeda dapat dieksekusi bersamaan secara paralel. Teknik ini dikenal sebagai pipa instruksi dan ini digunakan untuk meningkatkan throughput pada prosesor modern. Untuk memahami ini dengan lebih baik, silakan lihat contoh ini di Wikipedia .

Secara umum, prosesor modern memiliki jaringan pipa yang cukup panjang, tetapi untuk kemudahan mari kita pertimbangkan 4 langkah ini saja.

1. JIKA - Ambil instruksi dari memori
2. ID - Decode instruksi
3. EX - Jalankan instruksi
4. WB - Tulis kembali ke register CPU

Pipa 4-tahap secara umum untuk 2 instruksi.

Kembali ke pertanyaan di atas, mari pertimbangkan petunjuk berikut:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

Tanpa prediksi cabang, berikut ini akan terjadi:

Untuk menjalankan instruksi B atau instruksi C prosesor harus menunggu sampai instruksi A tidak mencapai sampai tahap EX dalam pipa, karena keputusan untuk pergi ke instruksi B atau instruksi C tergantung pada hasil instruksi A. Jadi pipa akan terlihat seperti ini.

ketika jika kondisi mengembalikan true:

Ketika jika kondisi kembali salah:

Sebagai hasil dari menunggu hasil instruksi A, total siklus CPU yang dihabiskan dalam kasus di atas (tanpa prediksi cabang; untuk benar dan salah) adalah 7.

Jadi, apa prediksi cabang?

Prediktor cabang akan mencoba menebak ke arah mana sebuah cabang (struktur if-then-else) akan berjalan sebelum ini diketahui dengan pasti. Ia tidak akan menunggu instruksi A untuk mencapai tahap EX dari pipeline, tetapi akan menebak keputusan dan pergi ke instruksi itu (B atau C dalam kasus contoh kita).

Dalam hal dugaan yang benar, pipeline terlihat seperti ini:

Jika kemudian terdeteksi bahwa tebakan itu salah maka instruksi yang dieksekusi sebagian dibuang dan pipa memulai kembali dengan cabang yang benar, menimbulkan penundaan. Waktu yang terbuang dalam kasus salah duga cabang sama dengan jumlah tahapan dalam pipa dari tahap pengambilan ke tahap pelaksanaan. Mikroprosesor modern cenderung memiliki jaringan pipa yang cukup panjang sehingga penundaan kesalahan prediksi adalah antara 10 dan 20 siklus clock. Semakin lama pipa semakin besar kebutuhan untuk prediktor cabang yang baik .

Dalam kode OP, pertama kali ketika bersyarat, prediktor cabang tidak memiliki informasi untuk mendasarkan prediksi, sehingga pertama kali secara acak akan memilih instruksi berikutnya. Kemudian dalam for loop, ini dapat mendasarkan prediksi pada histori. Untuk array yang diurutkan dalam urutan menaik, ada tiga kemungkinan:

1. Semua elemen kurang dari 128
2. Semua elemen lebih besar dari 128
3. Beberapa elemen baru mulai kurang dari 128 dan kemudian menjadi lebih besar dari 128

Mari kita asumsikan bahwa prediktor akan selalu menganggap cabang yang benar pada putaran pertama.

Jadi dalam kasus pertama, ia akan selalu mengambil cabang yang benar karena secara historis semua prediksi benar. Dalam kasus ke-2, awalnya ini akan memprediksi yang salah, tetapi setelah beberapa iterasi, ia akan memprediksi dengan benar. Dalam kasus ke-3, ia awalnya akan memprediksi dengan benar sampai elemen kurang dari 128. Setelah itu akan gagal untuk beberapa waktu dan memperbaiki sendiri ketika melihat kegagalan prediksi cabang dalam sejarah.

Dalam semua kasus ini, kegagalannya akan terlalu sedikit jumlahnya dan sebagai hasilnya, hanya beberapa kali ia harus membuang instruksi yang dieksekusi sebagian dan memulai kembali dengan cabang yang benar, menghasilkan siklus CPU yang lebih sedikit.

Tetapi dalam kasus array acak yang tidak disortir, prediksi perlu membuang instruksi yang dieksekusi sebagian dan memulai kembali dengan cabang yang benar sebagian besar waktu dan menghasilkan siklus CPU lebih banyak dibandingkan dengan array yang diurutkan.

Jawaban resmi akan dari

1. Intel - Menghindari Biaya Kesalahan Cabang
2. Intel - Reorganisasi Cabang dan Lingkaran untuk Mencegah Mispredicts
3. Makalah ilmiah - arsitektur komputer prediksi cabang
4. Buku: JL Hennessy, DA Patterson: Arsitektur komputer: pendekatan kuantitatif
5. Artikel dalam publikasi ilmiah: TY Yeh, YN Patt membuat banyak dari ini berdasarkan prediksi cabang.

Anda juga dapat melihat dari diagram yang indah ini mengapa prediktor cabang menjadi bingung.

Setiap elemen dalam kode asli adalah nilai acak

data[c] = std::rand() % 256;

jadi sang prediktor akan berubah sisi sebagai std::rand()pukulan.

Di sisi lain, setelah diurutkan, prediktor pertama-tama akan pindah ke kondisi tidak diambil dan ketika nilai berubah menjadi nilai tinggi, prediktor akan dalam tiga kali menjalankan perubahan mulai dari sangat tidak diambil menjadi sangat diambil.

Dalam baris yang sama (saya pikir ini tidak disorot oleh jawaban apa pun) ada baiknya menyebutkan bahwa kadang-kadang (khususnya dalam perangkat lunak di mana kinerja penting — seperti di kernel Linux) Anda dapat menemukan beberapa pernyataan if seperti berikut:

if (likely( everything_is_ok ))
{
    /* Do something */
}

atau serupa:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

Keduanya likely()dan unlikely()sebenarnya makro yang didefinisikan dengan menggunakan sesuatu seperti GCC __builtin_expectuntuk membantu kompiler memasukkan kode prediksi untuk mendukung kondisi dengan mempertimbangkan informasi yang diberikan oleh pengguna. GCC mendukung bawaan lain yang dapat mengubah perilaku program yang sedang berjalan atau memancarkan instruksi tingkat rendah seperti membersihkan cache, dll. Lihat dokumentasi ini yang melewati bawaan GCC yang tersedia.

Biasanya optimasi semacam ini terutama ditemukan dalam aplikasi waktu nyata yang sulit atau sistem embedded di mana waktu eksekusi sangat penting dan sangat penting. Misalnya, jika Anda memeriksa beberapa kondisi kesalahan yang hanya terjadi 1/10000000 kali, lalu mengapa tidak memberi tahu kompiler tentang ini? Dengan cara ini, secara default, prediksi cabang akan menganggap bahwa kondisinya salah.

Operasi Boolean yang sering digunakan dalam C ++ menghasilkan banyak cabang dalam program yang dikompilasi. Jika cabang-cabang ini berada di dalam loop dan sulit untuk diprediksi, mereka dapat memperlambat eksekusi secara signifikan. Variabel Boolean disimpan sebagai bilangan bulat 8-bit dengan nilai 0untuk falsedan 1untuktrue .

Variabel Boolean terlalu ditentukan dalam arti bahwa semua operator yang memiliki variabel Boolean sebagai input memeriksa apakah input memiliki nilai selain 0atau 1, tetapi operator yang memiliki Boolean sebagai output tidak dapat menghasilkan nilai selain 0atau 1. Ini membuat operasi dengan variabel Boolean sebagai input kurang efisien daripada yang diperlukan. Pertimbangkan contoh:

bool a, b, c, d;
c = a && b;
d = a || b;

Ini biasanya diterapkan oleh kompiler dengan cara berikut:

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

Kode ini jauh dari optimal. Cabang mungkin membutuhkan waktu lama jika salah duga. Operasi Boolean dapat dibuat jauh lebih efisien jika diketahui dengan pasti bahwa operan tidak memiliki nilai selain 0dan 1. Alasan mengapa kompiler tidak membuat asumsi seperti itu adalah bahwa variabel mungkin memiliki nilai lain jika mereka tidak diinisialisasi atau berasal dari sumber yang tidak diketahui. Kode di atas dapat dioptimalkan jika adan btelah diinisialisasi ke nilai yang valid atau jika berasal dari operator yang menghasilkan output Boolean. Kode yang dioptimalkan terlihat seperti ini:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

chardigunakan sebagai ganti boolagar memungkinkan untuk menggunakan operator bitwise ( &dan |) alih-alih operator Boolean ( &&dan ||). Operator bitwise adalah instruksi tunggal yang hanya membutuhkan satu siklus clock. Operator ATAU ( |) bekerja bahkan jika adan bmemiliki nilai selain 0atau 1. Operator AND ( &) dan operator EKSKLUSIF ATAU ( ^) dapat memberikan hasil yang tidak konsisten jika operan memiliki nilai selain 0dan 1.

~tidak bisa digunakan untuk TIDAK. Sebagai gantinya, Anda bisa membuat Boolean TIDAK pada variabel yang diketahui 0atau 1dengan XOR'ing dengan 1:

bool a, b;
b = !a;

dapat dioptimalkan untuk:

char a = 0, b;
b = a ^ 1;

a && btidak dapat diganti dengan a & bjika badalah ekspresi yang tidak boleh dievaluasi jika aadalah false( &&tidak akan mengevaluasi b, &akan). Demikian juga, a || btidak bisa diganti dengan a | bjika badalah ekspresi yang tidak dievaluasi jika aistrue .

Menggunakan operator bitwise lebih menguntungkan jika operan adalah variabel daripada jika operan adalah perbandingan:

bool a; double x, y, z;
a = x > y && z < 5.0;

optimal dalam banyak kasus (kecuali jika Anda mengharapkan &&ekspresi menghasilkan banyak salah duga cabang).

Itu sudah pasti!...

Prediksi cabang membuat logika berjalan lebih lambat, karena pergantian yang terjadi dalam kode Anda! Ini seperti Anda akan jalan lurus atau jalan dengan banyak belokan, pasti yang lurus akan dilakukan lebih cepat! ...

Jika array diurutkan, kondisi Anda salah pada langkah pertama:, data[c] >= 128kemudian menjadi nilai sebenarnya untuk seluruh jalan ke ujung jalan. Begitulah cara Anda sampai ke akhir logika lebih cepat. Di sisi lain, menggunakan array yang tidak disortir, Anda perlu banyak proses dan pembalikan yang membuat kode Anda berjalan lebih lambat pasti ...

Lihatlah gambar yang saya buat untuk Anda di bawah ini. Jalan mana yang akan selesai lebih cepat?

Jadi secara pemrograman, prediksi cabang menyebabkan proses menjadi lebih lambat ...

Juga pada akhirnya, ada baiknya mengetahui bahwa kami memiliki dua jenis prediksi cabang yang masing-masing akan memengaruhi kode Anda secara berbeda:

1. Statis

2. Dinamis

Prediksi cabang statis digunakan oleh mikroprosesor saat pertama kali cabang bersyarat ditemukan, dan prediksi cabang dinamis digunakan untuk keberhasilan eksekusi kode cabang bersyarat.

Agar dapat menulis kode Anda secara efektif untuk mengambil keuntungan dari aturan-aturan ini, saat menulis if-else atau beralih pernyataan, periksa kasus yang paling umum terlebih dahulu dan bekerja secara progresif ke yang paling umum. Loop tidak selalu memerlukan urutan kode khusus untuk prediksi cabang statis, karena hanya kondisi loop iterator yang biasanya digunakan.

Pertanyaan ini telah dijawab berulang kali dengan sangat baik. Saya masih ingin menarik perhatian kelompok untuk analisis menarik lainnya.

Baru-baru ini contoh ini (dimodifikasi sangat sedikit) juga digunakan sebagai cara untuk menunjukkan bagaimana sepotong kode dapat diprofilkan dalam program itu sendiri pada Windows. Sepanjang jalan, penulis juga menunjukkan cara menggunakan hasil untuk menentukan di mana kode menghabiskan sebagian besar waktunya baik dalam kasus diurutkan & tidak disortir. Akhirnya karya ini juga menunjukkan bagaimana menggunakan fitur HAL (Hardware Abstraction Layer) yang sedikit diketahui untuk menentukan seberapa banyak kesalahan prediksi cabang yang terjadi dalam kasus yang tidak disortir.

Tautannya ada di sini: http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

Seperti apa yang telah disebutkan oleh orang lain, apa yang ada di balik misteri itu adalah Prediktor Cabang .

Saya tidak mencoba menambahkan sesuatu tetapi menjelaskan konsepnya dengan cara lain. Ada pengantar singkat tentang wiki yang berisi teks dan diagram. Saya suka penjelasan di bawah ini yang menggunakan diagram untuk menguraikan Prediktor Cabang secara intuitif.

Dalam arsitektur komputer, prediktor cabang adalah sirkuit digital yang mencoba menebak ke arah mana cabang (misalnya struktur if-then-else) akan berjalan sebelum hal ini diketahui dengan pasti. Tujuan dari prediktor cabang adalah untuk meningkatkan aliran dalam pipa instruksi. Prediktor cabang memainkan peran penting dalam mencapai kinerja efektif tinggi di banyak arsitektur mikroprosesor pipelined modern seperti x86.

Percabangan dua arah biasanya diterapkan dengan instruksi lompat bersyarat. Lompatan bersyarat dapat "tidak diambil" dan melanjutkan eksekusi dengan cabang kode pertama yang mengikuti segera setelah lompatan bersyarat, atau dapat "diambil" dan melompat ke tempat yang berbeda dalam memori program di mana cabang kode kedua adalah disimpan. Tidak diketahui secara pasti apakah lompatan bersyarat akan diambil atau tidak diambil sampai kondisinya telah dihitung dan lompatan bersyarat telah melewati tahap eksekusi dalam pipa instruksi (lihat gbr. 1).

Berdasarkan skenario yang dijelaskan, saya telah menulis demo animasi untuk menunjukkan bagaimana instruksi dieksekusi dalam pipa dalam situasi yang berbeda.

1. Tanpa Prediktor Cabang.

Tanpa prediksi cabang, prosesor harus menunggu sampai instruksi melompat bersyarat telah melewati tahap eksekusi sebelum instruksi berikutnya dapat memasuki tahap pengambilan di dalam pipa.

Contoh berisi tiga instruksi dan yang pertama adalah instruksi melompat bersyarat. Dua instruksi terakhir dapat masuk ke dalam pipa sampai instruksi lompat bersyarat dijalankan.

Diperlukan 9 siklus clock agar 3 instruksi dapat diselesaikan.

2. Gunakan Branch Predictor dan jangan melakukan lompatan bersyarat. Mari kita asumsikan bahwa prediksi tidak mengambil lompatan bersyarat.

Diperlukan 7 siklus clock agar 3 instruksi dapat diselesaikan.

3. Gunakan Branch Predictor dan lakukan lompatan bersyarat. Mari kita asumsikan bahwa prediksi tidak mengambil lompatan bersyarat.

Diperlukan 9 siklus clock agar 3 instruksi dapat diselesaikan.

Waktu yang terbuang dalam kasus salah duga cabang sama dengan jumlah tahapan dalam pipa dari tahap pengambilan ke tahap pelaksanaan. Mikroprosesor modern cenderung memiliki jaringan pipa yang cukup panjang sehingga penundaan kesalahan prediksi adalah antara 10 dan 20 siklus clock. Akibatnya, membuat saluran pipa lebih lama meningkatkan kebutuhan untuk prediktor cabang yang lebih maju.

Seperti yang Anda lihat, sepertinya kami tidak punya alasan untuk tidak menggunakan Branch Predictor.

Ini adalah demo yang cukup sederhana yang menjelaskan bagian paling mendasar dari Predictor Cabang. Jika gif-gif itu menjengkelkan, silakan hapus saja dari jawabannya dan pengunjung juga bisa mendapatkan kode sumber demo langsung dari BranchPredictorDemo

Keuntungan prediksi cabang!

Penting untuk dipahami bahwa misprediksi cabang tidak memperlambat program. Biaya prediksi yang terlewatkan adalah seolah-olah prediksi cabang tidak ada dan Anda menunggu evaluasi ekspresi untuk memutuskan kode apa yang akan dijalankan (penjelasan lebih lanjut pada paragraf berikutnya).

if (expression)
{
    // Run 1
} else {
    // Run 2
}

Setiap kali ada pernyataan if-else\ switch, ekspresi harus dievaluasi untuk menentukan blok mana yang harus dieksekusi. Dalam kode rakitan yang dihasilkan oleh kompiler, instruksi cabang bersyarat dimasukkan.

Instruksi cabang dapat menyebabkan komputer mulai mengeksekusi urutan instruksi yang berbeda dan dengan demikian menyimpang dari perilaku default dari mengeksekusi instruksi secara berurutan (yaitu jika ekspresi salah, program melewatkan kode ifblok) tergantung pada beberapa kondisi, yang merupakan evaluasi ekspresi dalam kasus kami.

Yang sedang berkata, kompiler mencoba untuk memprediksi hasil sebelum benar-benar dievaluasi. Ini akan mengambil instruksi dari ifblok, dan jika ekspresi ternyata benar, maka hebat! Kami memperoleh waktu yang dibutuhkan untuk mengevaluasinya dan membuat kemajuan dalam kode; jika tidak maka kita menjalankan kode yang salah, pipa disiram, dan blok yang benar dijalankan.

Visualisasi:

Katakanlah Anda harus memilih rute 1 atau rute 2. Menunggu pasangan Anda memeriksa peta, Anda telah berhenti di ## dan menunggu, atau Anda bisa memilih route1 dan jika Anda beruntung (rute 1 adalah rute yang benar), maka hebatnya Anda tidak perlu menunggu pasangan Anda memeriksa peta (Anda menghemat waktu yang diperlukan untuk memeriksa peta), jika tidak, Anda hanya akan kembali.

Sementara pipa pembilasan sangat cepat, saat ini pertaruhan ini sepadan. Memprediksi data yang diurutkan atau data yang berubah lambat selalu lebih mudah dan lebih baik daripada memprediksi perubahan cepat.

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------

Pada ARM, tidak diperlukan cabang, karena setiap instruksi memiliki bidang kondisi 4-bit, yang menguji (dengan biaya nol) salah satu dari 16 kondisi berbeda yang mungkin muncul dalam Daftar Status Prosesor, dan jika kondisi pada instruksi adalah salah, instruksi dilewati. Ini menghilangkan kebutuhan untuk cabang pendek, dan tidak akan ada prediksi cabang hit untuk algoritma ini. Oleh karena itu, versi yang diurutkan dari algoritma ini akan berjalan lebih lambat daripada versi yang tidak disortir pada ARM, karena overhead tambahan dari penyortiran.

Lingkaran dalam untuk algoritma ini akan terlihat seperti berikut ini dalam bahasa assembly ARM:

MOV R0, #0     // R0 = sum = 0
MOV R1, #0     // R1 = c = 0
ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop    // Inner loop branch label
    LDRB R3, [R2, R1]     // R3 = data[c]
    CMP R3, #128          // compare R3 to 128
    ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1        // c++
    CMP R1, #arraySize    // compare c to arraySize
    BLT inner_loop        // Branch to inner_loop if c < arraySize

Tapi ini sebenarnya bagian dari gambaran yang lebih besar:

CMPopcodes selalu memperbarui bit status dalam Prosesor Status Register (PSR), karena itulah tujuannya, tetapi sebagian besar instruksi lainnya tidak menyentuh PSR kecuali Anda menambahkan Sakhiran opsional pada instruksi, yang menetapkan bahwa PSR harus diperbarui berdasarkan pada hasil dari instruksi. Sama seperti sufiks kondisi 4-bit, kemampuan menjalankan instruksi tanpa mempengaruhi PSR adalah mekanisme yang mengurangi kebutuhan cabang pada ARM, dan juga memfasilitasi pengiriman yang tidak berurutan pada tingkat perangkat keras , karena setelah melakukan beberapa operasi X yang memperbarui bit status, selanjutnya (atau secara paralel) Anda dapat melakukan banyak pekerjaan lain yang secara eksplisit seharusnya tidak mempengaruhi bit status, maka Anda dapat menguji status bit status yang ditetapkan sebelumnya oleh X.

Bidang pengujian kondisi dan bidang "set bit status" opsional dapat digabungkan, misalnya:

• ADD R1, R2, R3melakukan R1 = R2 + R3tanpa memperbarui bit status apa pun.
• ADDGE R1, R2, R3 melakukan operasi yang sama hanya jika instruksi sebelumnya yang mempengaruhi bit status menghasilkan kondisi Lebih Besar dari atau Sama.
• ADDS R1, R2, R3Melakukan Selain dan kemudian update N, Z, Cdan Vbendera di Status Processor Register berdasarkan apakah hasilnya adalah negatif, nol, Dibawa (untuk penambahan unsigned), atau meluap (untuk penambahan ditandatangani).
• ADDSGE R1, R2, R3melakukan penambahan hanya jika GEtes benar, dan kemudian memperbarui bit status berdasarkan hasil penambahan.

Sebagian besar arsitektur prosesor tidak memiliki kemampuan ini untuk menentukan apakah bit status harus diperbarui untuk operasi yang diberikan, yang dapat mengharuskan penulisan kode tambahan untuk menyimpan dan kemudian mengembalikan bit status, atau mungkin memerlukan cabang tambahan, atau dapat membatasi prosesor keluar efisiensi eksekusi order: salah satu efek samping dari sebagian besar arsitektur set instruksi CPU memperbarui bit status setelah sebagian besar instruksi adalah bahwa jauh lebih sulit untuk memisahkan instruksi mana yang dapat dijalankan secara paralel tanpa mengganggu satu sama lain. Memperbarui bit status memiliki efek samping, oleh karena itu memiliki efek linierisasi pada kode.Kemampuan ARM untuk mencampur dan mencocokkan pengujian kondisi bebas cabang pada instruksi apa pun dengan opsi untuk memperbarui atau tidak memperbarui bit status setelah instruksi apa pun sangat kuat, baik untuk programmer dan kompiler bahasa assembly, dan menghasilkan kode yang sangat efisien.

Jika Anda pernah bertanya-tanya mengapa ARM sangat sukses secara fenomenal, efektivitas dan interaksi yang cemerlang dari kedua mekanisme ini adalah bagian besar dari cerita ini, karena mereka adalah salah satu sumber terbesar dari efisiensi arsitektur ARM. Kecemerlangan desainer asli ARM ISA pada tahun 1983, Steve Furber dan Roger (sekarang Sophie) Wilson, tidak dapat dilebih-lebihkan.

Ini tentang prediksi cabang. Apa itu?

• Prediktor cabang adalah salah satu teknik peningkatan kinerja kuno yang masih menemukan relevansi dengan arsitektur modern. Sementara teknik prediksi sederhana memberikan pencarian cepat dan efisiensi daya, mereka menderita tingkat kesalahan prediksi yang tinggi.

• Di sisi lain, prediksi cabang yang kompleks - baik berdasarkan neural atau varian prediksi cabang dua tingkat - memberikan akurasi prediksi yang lebih baik, tetapi mereka mengkonsumsi lebih banyak daya dan kompleksitas yang meningkat secara eksponensial.

• Selain itu, dalam teknik prediksi yang kompleks waktu yang dibutuhkan untuk memprediksi cabang itu sendiri sangat tinggi - mulai dari 2 hingga 5 siklus - yang sebanding dengan waktu pelaksanaan cabang yang sebenarnya.

• Prediksi cabang pada dasarnya adalah masalah optimisasi (minimalisasi) di mana penekanannya adalah pada untuk mencapai tingkat kesalahan serendah mungkin, konsumsi daya rendah, dan kompleksitas rendah dengan sumber daya minimum.

Ada tiga jenis cabang:

Meneruskan cabang bersyarat - berdasarkan kondisi run-time, PC (program counter) diubah untuk menunjuk ke sebuah alamat yang diteruskan dalam aliran instruksi.

Cabang conditional mundur - PC diubah untuk menunjuk mundur dalam aliran instruksi. Cabang didasarkan pada beberapa kondisi, seperti bercabang mundur ke awal loop program ketika tes di akhir loop menyatakan loop harus dieksekusi lagi.

Cabang tanpa syarat - ini termasuk lompatan, panggilan prosedur dan pengembalian yang tidak memiliki kondisi khusus. Misalnya, instruksi lompatan tanpa syarat dapat dikodekan dalam bahasa assembly hanya sebagai "jmp", dan aliran instruksi harus segera diarahkan ke lokasi target yang ditunjuk oleh instruksi lompat, sedangkan lompatan kondisional yang mungkin dikodekan sebagai "jmpne" akan mengarahkan aliran instruksi hanya jika hasil perbandingan dua nilai dalam instruksi "bandingkan" sebelumnya menunjukkan nilai-nilai tidak sama. (Skema pengalamatan tersegmentasi yang digunakan oleh arsitektur x86 menambah kompleksitas tambahan, karena lompatan dapat berupa "dekat" (dalam suatu segmen) atau "jauh" (di luar segmen). Setiap jenis memiliki efek yang berbeda pada algoritma prediksi cabang.)

Prediksi Cabang Statis / Dinamis : Prediksi cabang statis digunakan oleh mikroprosesor saat pertama kali cabang bersyarat ditemukan, dan prediksi cabang dinamis digunakan untuk eksekusi yang berhasil dari kode cabang bersyarat.

Referensi:

• Prediktor cabang

• Demonstrasi Penentuan Profil Diri

• Tinjauan Prediksi Cabang

• Prediksi Cabang

Selain fakta bahwa prediksi cabang dapat memperlambat Anda, array yang diurutkan memiliki keunggulan lain:

Anda dapat memiliki kondisi berhenti alih-alih hanya memeriksa nilainya, dengan cara ini Anda hanya mengulang data yang relevan, dan mengabaikan sisanya.
Prediksi cabang akan hilang hanya sekali.

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }

Array yang diurutkan diproses lebih cepat daripada array yang tidak disortir, karena fenomena yang disebut prediksi cabang.

Prediktor cabang adalah sirkuit digital (dalam arsitektur komputer) yang mencoba memprediksi ke arah mana cabang akan bergerak, meningkatkan aliran dalam pipa instruksi. Sirkuit / komputer memprediksi langkah selanjutnya dan menjalankannya.

Membuat prediksi yang salah mengarah ke kembali ke langkah sebelumnya, dan mengeksekusi dengan prediksi lain. Dengan asumsi prediksi itu benar, kode akan melanjutkan ke langkah berikutnya. Prediksi yang salah menghasilkan pengulangan langkah yang sama, sampai prediksi yang benar terjadi.

Jawaban atas pertanyaan Anda sangat sederhana.

Dalam array yang tidak disortir, komputer membuat beberapa prediksi, yang mengarah ke peningkatan kemungkinan kesalahan. Padahal, dalam array yang diurutkan, komputer membuat prediksi lebih sedikit, mengurangi kemungkinan kesalahan. Membuat prediksi lebih banyak membutuhkan lebih banyak waktu.

Disortir Array: TrafoTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Array yang Tidak Disortir: Jalan Melengkung

______   ________
|     |__|

Prediksi cabang: Menebak / memprediksi jalan mana yang lurus dan mengikutinya tanpa memeriksa

___________________________________________ Straight road
 |_________________________________________|Longer road

Meskipun kedua jalan mencapai tujuan yang sama, jalan lurus lebih pendek, dan yang lainnya lebih panjang. Jika kemudian Anda memilih yang lain karena kesalahan, tidak ada jalan untuk kembali, sehingga Anda akan membuang waktu ekstra jika Anda memilih jalan yang lebih panjang. Ini mirip dengan apa yang terjadi di komputer, dan saya harap ini membantu Anda memahami lebih baik.

Saya juga ingin mengutip @Simon_Weaver dari komentar:

Itu tidak membuat prediksi lebih sedikit - itu membuat lebih sedikit prediksi yang salah. Masih harus memprediksi untuk setiap kali melalui loop ...

Saya mencoba kode yang sama dengan MATLAB 2011b dengan MacBook Pro saya (Intel i7, 64 bit, 2,4 GHz) untuk kode MATLAB berikut:

% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);


%Sort the data
data1= sort(data); % data1= data  when no sorting done


%Start a stopwatch timer to measure the execution time
tic;

for i=1:100000

    for j=1:arraySize

        if data1(j)>=128
            sum=sum + data1(j);
        end
    end
end

toc;

ExeTimeWithSorting = toc - tic;

Hasil untuk kode MATLAB di atas adalah sebagai berikut:

  a: Elapsed time (without sorting) = 3479.880861 seconds.
  b: Elapsed time (with sorting ) = 2377.873098 seconds.

Hasil kode C seperti di @GManNickG saya dapatkan:

  a: Elapsed time (without sorting) = 19.8761 sec.
  b: Elapsed time (with sorting ) = 7.37778 sec.

Berdasarkan ini, terlihat MATLAB hampir 175 kali lebih lambat dari implementasi C tanpa penyortiran dan 350 kali lebih lambat dengan penyortiran. Dengan kata lain, efek (prediksi cabang) adalah 1,46x untuk implementasi MATLAB dan 2,7x untuk implementasi C.

Asumsi oleh jawaban lain bahwa seseorang perlu mengurutkan data tidak benar.

Kode berikut tidak mengurutkan seluruh array, tetapi hanya segmen 200 elemen, dan dengan demikian menjalankan tercepat.

Mengurutkan hanya bagian k-elemen melengkapi pra-pemrosesan dalam waktu linier O(n),, daripada O(n.log(n))waktu yang diperlukan untuk mengurutkan seluruh array.

#include <algorithm>
#include <ctime>
#include <iostream>

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

    for (unsigned c = 0; c < l; ++c)
        data[c] = std::rand() % 256;

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Ini juga "membuktikan" bahwa itu tidak ada hubungannya dengan masalah algoritmik seperti urutan, dan memang prediksi cabang.

Jawaban Bjarne Stroustrup untuk pertanyaan ini:

Itu terdengar seperti pertanyaan wawancara. Apakah itu benar Bagaimana kamu tahu? Merupakan ide yang buruk untuk menjawab pertanyaan tentang efisiensi tanpa terlebih dahulu melakukan beberapa pengukuran, jadi penting untuk mengetahui bagaimana mengukurnya.

Jadi, saya mencoba dengan vektor sejuta bilangan bulat dan mendapat:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

Saya berlari itu beberapa kali untuk memastikan. Ya, fenomena itu nyata. Kode kunci saya adalah:

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label 
         << duration_cast<microseconds>(t1 — t0).count() 
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

Setidaknya fenomena ini nyata dengan pengaturan kompiler, pustaka standar, dan pengoptimal ini. Implementasi yang berbeda dapat dan memang memberikan jawaban yang berbeda. Bahkan, seseorang melakukan penelitian yang lebih sistematis (pencarian web cepat akan menemukannya) dan sebagian besar implementasi menunjukkan efek itu.

Salah satu alasannya adalah prediksi cabang: operasi utama dalam algoritma pengurutan adalah “if(v[i] < pivot]) …” atau setara. Untuk urutan yang diurutkan tes itu selalu benar sedangkan, untuk urutan acak, cabang yang dipilih bervariasi secara acak.

Alasan lain adalah ketika vektor sudah diurutkan, kita tidak perlu memindahkan elemen ke posisi yang benar. Efek dari detail kecil ini adalah faktor lima atau enam yang kita lihat.

Quicksort (dan memilah secara umum) adalah studi kompleks yang telah menarik beberapa pemikir besar ilmu komputer. Fungsi sortir yang baik adalah hasil dari pemilihan algoritma yang baik dan memperhatikan kinerja perangkat keras dalam implementasinya.

Jika Anda ingin menulis kode yang efisien, Anda perlu tahu sedikit tentang arsitektur mesin.

Pertanyaan ini berakar pada Model Prediksi Cabang pada CPU. Saya akan merekomendasikan membaca makalah ini:

Meningkatkan Kecepatan Ambil Instruksi melalui Beberapa Prediksi Cabang dan Cache Alamat Cabang

Ketika Anda telah mengurutkan elemen, IR tidak dapat diganggu untuk mengambil semua instruksi CPU, lagi dan lagi, itu mengambilnya dari cache.

Salah satu cara untuk menghindari kesalahan prediksi cabang adalah membangun tabel pencarian, dan mengindeksnya menggunakan data. Stefan de Bruijn mendiskusikan hal itu dalam jawabannya.

Tetapi dalam kasus ini, kita tahu nilai berada dalam kisaran [0, 255] dan kita hanya peduli pada nilai> = 128. Itu berarti kita dapat dengan mudah mengekstraksi bit tunggal yang akan memberi tahu kita apakah kita menginginkan nilai atau tidak: dengan menggeser data ke 7 bit yang tepat, kita dibiarkan dengan 0 bit atau 1 bit, dan kita hanya ingin menambahkan nilai ketika kita memiliki 1 bit. Sebut saja bit ini "bit keputusan".

Dengan menggunakan nilai 0/1 dari bit keputusan sebagai indeks ke dalam array, kita dapat membuat kode yang akan sama cepatnya apakah data diurutkan atau tidak diurutkan. Kode kami akan selalu menambahkan nilai, tetapi ketika bit keputusan adalah 0, kami akan menambahkan nilai di tempat yang tidak kami pedulikan. Berikut kodenya:

// Uji

clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Kode ini menghabiskan setengah dari tambahan tetapi tidak pernah memiliki kegagalan prediksi cabang. Ini jauh lebih cepat pada data acak daripada versi dengan pernyataan if aktual.

Tetapi dalam pengujian saya, tabel pencarian eksplisit sedikit lebih cepat dari ini, mungkin karena pengindeksan ke tabel pencarian sedikit lebih cepat daripada sedikit pergeseran. Ini menunjukkan bagaimana kode saya mengatur dan menggunakan tabel pencarian (secara imajinatif disebut lut untuk "Tabel Pencarian" dalam kode). Berikut kode C ++:

// Nyatakan dan isi tabel pencarian

int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

Dalam hal ini, tabel pencarian hanya 256 byte, sehingga sangat cocok dalam cache dan semuanya cepat. Teknik ini tidak akan bekerja dengan baik jika datanya bernilai 24-bit dan kami hanya ingin setengah dari mereka ... tabel pencarian akan terlalu besar untuk praktis. Di sisi lain, kita bisa menggabungkan dua teknik yang ditunjukkan di atas: pertama-tama pindahkan bit, lalu indeks tabel pencarian. Untuk nilai 24-bit yang hanya kami inginkan nilai setengahnya, kami berpotensi menggeser data dengan 12 bit, dan dibiarkan dengan nilai 12-bit untuk indeks tabel. Indeks tabel 12-bit menyiratkan tabel nilai 4096, yang mungkin praktis.

Teknik pengindeksan ke dalam array, alih-alih menggunakan pernyataan if, dapat digunakan untuk memutuskan pointer mana yang akan digunakan. Saya melihat perpustakaan yang mengimplementasikan pohon biner, dan bukannya memiliki dua pointer bernama (pLeft dan pRight atau apa pun) memiliki panjang array array-2 dan menggunakan teknik "bit keputusan" untuk memutuskan mana yang akan diikuti. Misalnya, alih-alih:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;
this library would do something like:

i = (x < node->value);
node = node->link[i];

itu solusi yang bagus mungkin itu akan berhasil