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


Berikut ini adalah potongan kode C ++ yang tampaknya sangat aneh. Untuk beberapa alasan aneh, menyortir 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 berjalan dalam 1.93 detik.

Awalnya, saya pikir ini mungkin hanya bahasa atau kompilator anomali. Jadi saya mencobanya di Jawa.

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 agak mirip tetapi kurang ekstrim.


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

  • Apa yang sedang terjadi?
  • Mengapa lebih cepat memproses array yang diurutkan daripada array yang tidak disortir?
  • Kode ini menjumlahkan beberapa istilah independen, dan urutannya tidak menjadi masalah.

21647
2018-06-27 13:51


asal


Jawaban:


Anda adalah korban dari prediksi cabang gagal.


Apa itu Prediksi Cabang?

Pertimbangkan persimpangan jalan kereta api:

Licensed Image Gambar oleh Mecanismo, melalui Wikimedia Commons. Digunakan di bawah CC-By-SA 3.0 lisensi.

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

Anda adalah operator persimpangan dan Anda mendengar kereta datang. Anda tidak tahu jalan mana yang harus dituju. Anda menghentikan kereta untuk menanyakan kepada pengemudi arah mana yang mereka inginkan. Dan kemudian Anda mengatur sakelar secara tepat.

Kereta api berat dan memiliki banyak inersia. Jadi mereka mengambil waktu lama untuk memulai dan memperlambat.

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

  • Jika Anda menebak dengan benar, itu terus berlanjut.
  • Jika Anda salah menebak, kapten akan berhenti, mundur, dan berteriak kepada Anda untuk membalik tombol. Kemudian ia dapat memulai kembali jalur lainnya.

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


Pertimbangkan pernyataan if: Di tingkat prosesor, ini adalah instruksi cabang:

image2

Anda adalah seorang prosesor dan Anda melihat sebuah cabang. Anda tidak tahu jalan mana yang 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 saluran pipa yang panjang. Jadi mereka mengambil selamanya untuk "pemanasan" dan "memperlambat".

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 memutar kembali ke cabang. Kemudian Anda dapat memulai kembali jalur lainnya.

Jika Anda menebak dengan benar setiap saat, eksekusi tidak akan pernah berhenti.
Jika Anda salah menebak terlalu sering, Anda menghabiskan banyak waktu mengulur-ulur, memutar kembali, dan memulai kembali.


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

Jadi bagaimana Anda akan secara strategis menebak untuk meminimalkan berapa kali kereta harus mundur dan turun di jalur lain? Anda melihat sejarah masa lalu! Jika kereta berjalan 99% dari waktu, maka Anda tebak kiri. Jika bergantian, maka Anda mengubah tebakan Anda. Jika berjalan satu arah setiap 3 kali, Anda menebak hal yang sama ...

Dengan kata lain, Anda mencoba mengidentifikasi pola dan mengikutinya. Ini kurang lebih bagaimana cara kerja prediksi cabang.

Sebagian besar aplikasi memiliki cabang yang berperilaku baik. Jadi prediktor cabang modern biasanya akan mencapai> 90% rasio klik. Tetapi ketika berhadapan dengan cabang-cabang yang tidak dapat diprediksi tanpa pola yang dapat dikenali, prediksi cabang hampir tidak berguna.

Bacaan lebih lanjut: Artikel "Branch predictor" di Wikipedia.


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

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

Perhatikan bahwa data terdistribusi secara merata antara 0 dan 255. Ketika data disortir, kira-kira paruh pertama dari iterasi tidak akan masuk ke if-statement. Setelah itu, mereka semua akan memasukkan pernyataan if.

Ini sangat ramah kepada pencetus cabang karena cabangnya secara berurutan berjalan ke arah yang sama berkali-kali. Bahkan penghitung jenuh sederhana akan benar memprediksi cabang kecuali untuk beberapa iterasi setelah beralih 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, prediksi cabang tidak berguna karena tidak dapat memprediksi data acak. Dengan demikian mungkin akan ada sekitar 50% misprediction. (Tidak lebih baik daripada 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 compiler tidak dapat mengoptimalkan cabang menjadi langkah kondisional, 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 menggantikannya dengan beberapa operasi bitwise.

(Perhatikan bahwa hack ini tidak sepenuhnya setara dengan pernyataan if yang asli. Namun dalam kasus ini, 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

Observasi:

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

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


Memperbarui:

  • GCC 4.6.1 dengan -O3 atau -ftree-vectorize pada x64 dapat menghasilkan langkah kondisional. Jadi tidak ada perbedaan antara data yang disortir dan yang tidak disortir - keduanya cepat.

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

  • Intel Compiler 11 melakukan sesuatu yang ajaib. Saya t bertukar dua lilitan, dengan demikian mengangkat cabang yang tidak dapat diprediksi ke loop luar. Jadi tidak hanya itu kekebalan mispredictions, itu juga dua kali lebih cepat dari apa pun yang dapat menghasilkan VC ++ dan GCC! Dengan kata lain, ICC mengambil keuntungan dari tes-loop untuk mengalahkan patokan ...

  • Jika Anda memberi Intel Compiler kode tanpa cabang, itu hanya keluar-kanan vectorizes itu ... dan hanya secepat dengan cabang (dengan loop interchange).

Ini menunjukkan bahwa bahkan kompiler modern yang matang dapat berubah secara liar dalam kemampuan mereka untuk mengoptimasi kode ...


28564
2018-06-27 13:56



Prediksi cabang.

Dengan array yang diurutkan, kondisinya data[c] >= 128 adalah yang pertama false untuk serangkaian nilai, kemudian menjadi true untuk semua nilai selanjutnya. Itu mudah diprediksi. Dengan array yang tidak disortir, Anda membayar biaya pencabangan.


3635
2018-06-27 13:54



Alasan mengapa kinerja meningkat secara drastis ketika data diurutkan adalah bahwa penalti prediksi cabang dihapus, seperti yang dijelaskan dengan indah di Misteriusjawabannya.

Sekarang, jika kita melihat kode

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

kita dapat menemukan arti dari yang khusus ini if... else... cabang adalah menambahkan sesuatu ketika suatu kondisi dipenuhi. Jenis cabang ini dapat dengan mudah diubah menjadi langkah kondisional pernyataan, yang akan dikompilasi menjadi instruksi tindakan bersyarat: cmovl, dalam sebuah x86 sistem. Cabang dan dengan demikian potensi penalti prediksi cabang dihapus.

Di C, jadi C++, pernyataan, yang akan mengkompilasi secara langsung (tanpa pengoptimalan apa pun) ke dalam instruksi proses bersyarat di x86, adalah operator terner ... ? ... : .... Jadi kami menulis ulang pernyataan di atas menjadi yang setara:

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

Sambil mempertahankan keterbacaan, kita dapat memeriksa faktor kecepatan.

Pada Intel Core i7-2600K @ 3,4 GHz dan Visual Studio 2010 Release Mode, patokannya adalah (format yang 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 kecepatan tinggi ketika hasil cabang tidak dapat diprediksi, tetapi kami sedikit menderita ketika dapat diprediksi. Bahkan, ketika menggunakan langkah kondisional, kinerjanya sama terlepas dari pola datanya.

Sekarang mari kita lihat lebih dekat dengan menyelidiki x86 perakitan yang mereka hasilkan. Untuk kesederhanaan, kami menggunakan dua fungsi max1 dan max2.

max1 menggunakan cabang bersyarat if... else ...:

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

max2 menggunakan operator terner ... ? ... : ...:

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

Pada mesin x86-64, GCC -S menghasilkan 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

max2 menggunakan lebih sedikit kode karena penggunaan instruksi cmovge. Tetapi keuntungan sebenarnya adalah itu max2 tidak melibatkan lompatan cabang, jmp, yang akan memiliki penalti kinerja yang signifikan jika hasil yang diprediksi tidak tepat.

Jadi mengapa langkah kondisional berkinerja lebih baik?

Secara tipikal x86 prosesor, pelaksanaan instruksi dibagi menjadi beberapa tahap. Kira-kira, 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 dapat melakukan pipelining. Kita harus menunggu atau memprediksi.

Dalam kasus perpindahan bersyarat, eksekusi instruksi gerak kondisional dibagi menjadi beberapa tahap, tetapi tahap-tahap sebelumnya seperti Fetch dan Decode tidak bergantung pada hasil dari instruksi sebelumnya; hanya tahap terakhir yang membutuhkan hasilnya. Jadi, kami menunggu sebagian kecil dari waktu eksekusi satu instruksi. Inilah mengapa versi perpindahan bersyarat lebih lambat dari cabang ketika prediksi mudah.

Buku Sistem Komputer: Perspektif Programmer, edisi kedua menjelaskan ini secara detail. Anda dapat memeriksa Bagian 3.6.6 untuk Instruksi Pemindahan Bersyarat, seluruh Bab 4 untuk Arsitektur Prosesor, dan Bagian 5.11.2 untuk perawatan khusus untuk Prediksi Cabang dan Penalti Misprediasi.

Kadang-kadang, beberapa kompiler modern dapat mengoptimalkan kode kami untuk perakitan dengan kinerja yang lebih baik, kadang-kadang beberapa compiler tidak bisa (kode yang dimaksud adalah menggunakan compiler asli Visual Studio). Mengetahui perbedaan kinerja antara cabang dan langkah kondisional ketika tidak dapat diprediksi dapat membantu kita menulis kode dengan kinerja yang lebih baik ketika skenario menjadi begitu kompleks sehingga kompiler tidak dapat mengoptimalkannya secara otomatis.


2958
2018-06-28 02:14



Jika Anda ingin tahu tentang lebih banyak lagi optimisasi yang dapat dilakukan pada 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 loop interchange, kita dapat dengan aman mengubah loop ini menjadi:

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 if bersyarat adalah konstan selama eksekusi i lingkaran, sehingga Anda dapat mengerek if di luar:

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 lingkaran dalam dapat diciutkan menjadi satu ekspresi tunggal, dengan asumsi model titik mengambang memungkinkannya (/ fp: cepat dilempar, misalnya)

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

Yang itu 100.000x lebih cepat dari sebelumnya


2024
2017-07-03 02:25



Tidak diragukan lagi sebagian dari kita akan tertarik pada cara mengidentifikasi kode yang bermasalah untuk prediksi cabang CPU. Alat Valgrind cachegrind memiliki simulator cabang-prediktor, diaktifkan dengan menggunakan --branch-sim=yes bendera. Menjalankannya di atas contoh dalam pertanyaan ini, dengan jumlah loop luar dikurangi menjadi 10.000 dan dikompilasi 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%   )

Pengeboran ke dalam output line-by-line yang dihasilkan oleh cg_annotate kita melihat 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 mengidentifikasi dengan mudah baris bermasalah - dalam versi yang tidak disortir if (data[c] >= 128) garis menyebabkan 164.050.007 cabang bersyarat 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 bisa melakukan anotasi kode sumber dengan dissassembly.

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.


1687
2017-10-12 05:53



Saya baru saja membaca tentang 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 daripada menggunakan cabang (meskipun saya belum mengujinya dalam kasus ini).

Pendekatan ini bekerja secara umum jika:

  1. Ini adalah meja kecil dan kemungkinan akan di-cache dalam prosesor
  2. Anda menjalankan hal-hal dalam putaran yang cukup ketat dan / atau prosesor dapat melakukan pra-muat data

Latar belakang dan mengapa

Pfew, jadi apa maksudnya itu?

Dari perspektif prosesor, ingatan Anda lambat. Untuk mengimbangi perbedaan dalam kecepatan, mereka membangun beberapa cache dalam prosesor Anda (cache L1 / L2) yang mengkompensasi itu. Jadi bayangkan bahwa Anda melakukan perhitungan yang bagus dan cari tahu bahwa Anda membutuhkan ingatan. Prosesor akan mendapatkan operasi 'load' dan memuat bagian memori ke cache - dan kemudian menggunakan cache untuk melakukan sisa perhitungan. Karena memori relatif lambat, 'beban' ini akan memperlambat program Anda.

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

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

Hal pertama yang perlu kita ketahui adalah apa itu kecil? Sementara lebih kecil umumnya lebih baik, aturan praktis adalah untuk tetap ke tabel pencarian yang <= 4096 byte dalam ukuran. Sebagai batas atas: jika tabel pencarian Anda lebih besar dari 64K, itu mungkin layak dipertimbangkan kembali.

Membangun meja

Jadi kami tahu bahwa kami dapat membuat tabel kecil. Selanjutnya yang harus dilakukan adalah mendapatkan fungsi pencarian di tempat. Fungsi pencarian biasanya merupakan fungsi kecil yang menggunakan beberapa operasi bilangan bulat dasar (dan, atau, xor, shift, tambah, hapus dan mungkin bertambah banyak). Anda ingin masukan Anda diterjemahkan oleh fungsi pencarian ke beberapa jenis 'kunci unik' di tabel Anda, yang kemudian hanya memberi Anda jawaban dari semua pekerjaan yang Anda inginkan.

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

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

Yah, tidak juga ... :-)

Ada cukup banyak pekerjaan untuk menghilangkan cabang ini untuk bahasa yang dikelola. Sebagai contoh:

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

Dalam hal ini, jelas bagi kompilator bahwa kondisi batas tidak akan pernah terpukul. Setidaknya compiler Microsoft JIT (tapi saya berharap Java melakukan hal serupa) akan memperhatikan ini dan menghapus cek sama sekali. WOW - itu berarti tidak ada cabang. Demikian pula, akan menangani kasus-kasus lain yang jelas.

Jika Anda mengalami masalah dengan pencarian bahasa yang dikelola - kuncinya adalah menambahkan & 0x[something]FFFke fungsi 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 rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
    data[c] = rnd.Next(256);

//To keep the spirit of the code in-tact 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();

1158
2018-04-24 06:26



Ketika data didistribusikan antara 0 dan 255 ketika array diurutkan, sekitar paruh pertama iterasi tidak akan masuk if-statement (yang if pernyataan dibagi di bawah ini).

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

Pertanyaannya adalah: Apa yang membuat pernyataan di atas tidak mengeksekusi dalam kasus-kasus tertentu seperti dalam kasus data yang diurutkan? Di sinilah "prediktor cabang". Peramal cabang adalah rangkaian digital yang mencoba menerka cabang cabang mana (mis. An if-then-else struktur) akan pergi sebelum ini diketahui pasti. Tujuan dari peramal cabang adalah untuk meningkatkan aliran dalam pipa instruksi. Prediktor cabang memainkan peran penting dalam mencapai kinerja efektif yang tinggi!

Mari kita lakukan bench marking untuk memahaminya lebih baik

Kinerja sebuah if-statement 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, maka if-statement akan jauh lebih mahal.

Mari kita mengukur kinerja loop ini dengan berbagai kondisi:

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

Berikut adalah pengaturan waktu pengulangan 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

SEBUAH "buruk"Pola benar-salah dapat membuat if-tahap hingga enam kali lebih lambat daripada "baik" pola! Tentu saja, pola mana yang bagus dan mana yang buruk tergantung pada instruksi yang tepat yang dihasilkan oleh kompilator dan pada prosesor tertentu.

Jadi tidak ada keraguan tentang dampak prediksi cabang terhadap kinerja!


1033
2018-02-15 07:24