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


24452

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.



16
@SachinVerma Dari atas kepala saya: 1) JVM mungkin akhirnya cukup pintar untuk menggunakan gerakan bersyarat. 2) Kode ini terikat memori. 200M terlalu besar untuk muat dalam cache CPU. Jadi kinerjanya akan terhambat oleh bandwidth memori dan bukannya percabangan.
Mysticial

12
@ Mysticial, sekitar 2). Saya pikir tabel prediksi melacak pola (terlepas dari variabel aktual yang diperiksa untuk pola itu) dan mengubah output prediksi berdasarkan sejarah. Bisakah Anda memberi saya alasan, mengapa array super besar tidak akan mendapat manfaat dari prediksi cabang?
Sachin Verma

15
@SachinVerma Ya, tapi ketika arraynya besar, faktor yang lebih besar kemungkinan ikut bermain - bandwidth memori. Memori tidak rata . Mengakses memori sangat lambat, dan ada sejumlah bandwidth yang terbatas. Untuk menyederhanakan banyak hal, hanya ada begitu banyak byte yang dapat ditransfer antara CPU dan memori dalam jumlah waktu yang tetap. Kode sederhana seperti yang ada di pertanyaan ini mungkin akan mencapai batas itu walaupun itu diperlambat oleh salah duga. Ini tidak terjadi dengan array 32768 (128KB) karena cocok dengan cache L2 CPU.
Mysticial

13
Ada kelemahan keamanan baru yang disebut BranchScope: cs.ucr.edu/~nael/pubs/asplos18.pdf
Veve

Jawaban:


31800

Anda adalah korban gagal prediksi cabang .


Apa itu Prediksi Cabang?

Pertimbangkan persimpangan jalan kereta:

Gambar menunjukkan persimpangan kereta api 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:

Cuplikan layar kode terkompilasi yang berisi pernyataan if

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


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:

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


256
Lihatlah pertanyaan tindak lanjut ini: stackoverflow.com/questions/11276291/... Intel Compiler cukup dekat untuk sepenuhnya menghilangkan loop luar.
Mysticial

24
@Mysticial Bagaimana kereta / kompiler tahu bahwa ia telah memasuki jalan yang salah?
onmyway133

26
@obe: Dengan struktur memori hierarkis, tidak mungkin untuk mengatakan berapa biaya cache yang hilang. Mungkin hilang di L1 dan diselesaikan di L2 lebih lambat, atau ketinggalan di L3 dan diselesaikan di memori sistem. Namun, kecuali karena alasan aneh cache miss ini menyebabkan memori di halaman non-residen dimuat dari disk, Anda memiliki poin yang bagus ... memori tidak memiliki waktu akses dalam kisaran milidetik dalam waktu sekitar 25-30 tahun ;)
Andon M. Coleman

21
Aturan praktis untuk menulis kode yang efisien pada prosesor modern: Segala sesuatu yang membuat eksekusi program Anda lebih teratur (kurang tidak merata) akan cenderung membuatnya lebih efisien. Jenis dalam contoh ini memiliki efek ini karena prediksi cabang. Akses lokalitas (bukan akses acak jauh dan luas) memiliki efek ini karena cache.
Lutz Prechelt

22
@ Tetaplah Ya. Prosesor masih memiliki prediksi cabang. Jika ada yang berubah, itu adalah kompiler. Saat ini, saya yakin mereka lebih cenderung melakukan apa yang dilakukan ICC dan GCC (di bawah -O3) di sini - yaitu, cabut cabang. Mengingat seberapa tinggi profil pertanyaan ini, sangat mungkin kompiler telah diperbarui untuk secara khusus menangani kasus dalam pertanyaan ini. Yang pasti memperhatikan SO. Dan itu terjadi pada pertanyaan ini di mana GCC diperbarui dalam 3 minggu. Saya tidak mengerti mengapa itu tidak terjadi di sini juga.
Mysticial

4087

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.


105
Apakah prediksi cabang bekerja lebih baik pada array yang diurutkan vs array dengan pola yang berbeda? Misalnya, untuk array -> {10, 5, 20, 10, 40, 20, ...} elemen berikutnya dalam array dari pola adalah 80. Apakah array semacam ini akan dipercepat oleh prediksi cabang di elemen berikutnya adalah 80 di sini jika polanya diikuti? Atau apakah biasanya hanya membantu dengan array yang diurutkan?
Adam Freeman

133
Jadi pada dasarnya semua yang saya pelajari secara konvensional tentang big-O ada di luar jendela? Lebih baik mengeluarkan biaya sortir daripada biaya percabangan?
Agrim Pathak

133
@AgrimPathak Itu tergantung. Untuk input yang tidak terlalu besar, algoritma dengan kompleksitas lebih tinggi lebih cepat daripada algoritma dengan kompleksitas lebih rendah ketika konstanta lebih kecil untuk algoritma dengan kompleksitas lebih tinggi. Di mana titik impas bisa sulit diprediksi. Juga, bandingkan ini , lokalitas itu penting. Big-O penting, tetapi itu bukan satu-satunya kriteria untuk kinerja.
Daniel Fischer

65
Kapan prediksi cabang terjadi? Kapan bahasa akan tahu bahwa array diurutkan? Saya sedang memikirkan situasi array yang terlihat seperti: [1,2,3,4,5, ... 998,999,1000, 3, 10001, 10002]? akankah ini mengaburkan 3 meningkatkan waktu berjalan? Apakah akan sepanjang array yang tidak disortir?
Filip Bartuzi

63
@FilipBartuzi Prediksi cabang terjadi di prosesor, di bawah tingkat bahasa (tetapi bahasa tersebut dapat menawarkan cara untuk memberi tahu kompiler apa yang mungkin terjadi, sehingga kompiler dapat memancarkan kode yang sesuai dengan itu). Dalam contoh Anda, 3 out-of-order akan menyebabkan salah duga cabang (untuk kondisi yang tepat, di mana 3 memberikan hasil yang berbeda dari 1000), dan dengan demikian memproses array yang mungkin akan memakan waktu beberapa lusin atau ratusan nanodetik lebih lama daripada array yang diurutkan akan, hampir tidak pernah terlihat. Apa yang menghabiskan waktu adalah tingkat kesalahan prediksi yang tinggi, satu kesalahan prediksi per 1000 tidak banyak.
Daniel Fischer

3312

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.


7
@ BlueRaja-DannyPflughoeft Ini adalah versi yang tidak dioptimalkan. Kompilator TIDAK mengoptimalkan operator ternary, itu hanya mentranslasikannya. GCC dapat mengoptimalkan jika-maka jika diberikan tingkat optimisasi yang memadai, namun yang satu ini menunjukkan kekuatan perpindahan bersyarat, dan optimasi manual membuat perbedaan.
WiSaGaN

100
@WiSaGaN Kode tidak menunjukkan apa-apa, karena kedua kode Anda dikompilasi ke kode mesin yang sama. Sangat penting bahwa orang tidak mendapatkan gagasan bahwa entah bagaimana pernyataan if dalam contoh Anda berbeda dari terenary dalam contoh Anda. Memang benar bahwa Anda memiliki kesamaan dalam paragraf terakhir Anda, tetapi itu tidak menghapus fakta bahwa sisa dari contoh ini berbahaya.
Justin L.

55
@WiSaGaN Downvote saya pasti akan berubah menjadi upvote jika Anda memodifikasi jawaban Anda untuk menghapus -O0contoh yang menyesatkan dan untuk menunjukkan perbedaan asm dioptimalkan pada dua testcases Anda.
Justin L.

56
@UpAndAdam Pada saat pengujian, VS2010 tidak dapat mengoptimalkan cabang asli menjadi gerakan bersyarat bahkan ketika menentukan tingkat optimisasi tinggi, sementara gcc bisa.
WiSaGaN

9
Trik operator ternary ini berfungsi dengan baik untuk Java. Setelah membaca jawaban Mystical, saya bertanya-tanya apa yang bisa dilakukan untuk Java untuk menghindari prediksi cabang palsu karena Java tidak memiliki sesuatu yang setara dengan -O3. operator ternary: 2.1943 dan asli: 6.0303s.
Kin Cheung

2272

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.


276
Jika Anda ingin menyontek, Anda bisa mengambil perkalian di luar loop dan lakukan penjumlahan * = 100000 setelah loop.
Jyaif

78
@Michael - Saya percaya bahwa contoh ini sebenarnya adalah contoh dari optimasi pengangkatan loop-invarian (LIH), dan BUKAN loop swap . Dalam hal ini, seluruh loop dalam tidak tergantung pada loop luar dan karenanya dapat diangkat dari loop luar, di mana hasilnya hanya dikalikan dengan jumlah lebih idari satu unit = 1e5. Tidak ada bedanya dengan hasil akhir, tetapi saya hanya ingin meluruskan karena ini adalah halaman yang sering dikunjungi.
Yair Altman

54
Meskipun tidak dalam semangat swapping loop yang sederhana, bagian dalam ifpada titik ini dapat dikonversi menjadi: sum += (data[j] >= 128) ? data[j] * 100000 : 0;yang dapat dikurangi cmovgeatau dikompilasi oleh kompiler .
Alex North-Keys

43
Loop luar adalah untuk membuat waktu yang diambil oleh loop dalam cukup besar untuk profil. Jadi mengapa Anda mengulangi swap. Pada akhirnya, loop itu akan dihapus.
saurabheights

34
@saurabheights: Pertanyaan yang salah: mengapa kompiler TIDAK melakukan loop swap. Microbenchmarks sulit;)
Matthieu M.

1885

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.


74
Ini menakutkan, dalam daftar yang tidak disortir, harus ada kemungkinan 50% untuk memukul add. Entah bagaimana prediksi cabang hanya memiliki tingkat kehilangan 25%, bagaimana bisa lebih baik dari 50% kehilangan?
TallBrian

128
@ tall.b.lo: 25% adalah dari semua cabang - ada dua cabang di loop, satu untuk data[c] >= 128(yang memiliki tingkat kehilangan 50% seperti yang Anda sarankan) dan satu untuk kondisi loop c < arraySizeyang memiliki ~ tingkat kehilangan 0% .
caf

1341

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();

57
Anda ingin memotong prediktor cabang, mengapa? Ini adalah optimasi.
Dustin Oprea

108
Karena tidak ada cabang yang lebih baik daripada cabang :-) Dalam banyak situasi ini hanya jauh lebih cepat ... jika Anda mengoptimalkan, itu pasti patut dicoba. Mereka juga menggunakannya sedikit di f.ex. graphics.stanford.edu/~seander/bithacks.html
atlaste

36
Secara umum tabel pencarian bisa cepat, tetapi apakah Anda menjalankan tes untuk kondisi khusus ini? Anda masih memiliki kondisi cabang dalam kode Anda, hanya sekarang ini dipindahkan ke bagian pembuatan tabel. Anda masih tidak akan mendapatkan peningkatan kinerja
Zain Rizvi

38
@ Zain jika Anda benar-benar ingin tahu ... Ya: 15 detik dengan cabang dan 10 dengan versi saya. Bagaimanapun juga, ini adalah teknik yang berguna untuk mengetahui cara mana pun.
atlaste

42
Mengapa tidak di sum += lookup[data[j]]mana lookuparray dengan 256 entri, yang pertama nol dan yang terakhir sama dengan indeks?
Kris Vandermotten

1200

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!


23
@ MoooDuck 'Karena itu tidak akan membuat perbedaan - nilai itu bisa apa saja, tetapi masih akan berada dalam batas ambang ini. Jadi mengapa menunjukkan nilai acak ketika Anda sudah tahu batasnya? Meskipun saya setuju bahwa Anda bisa menunjukkan satu demi kelengkapan, dan 'hanya untuk itu'.
cst1992

24
@ cst1992: Saat ini timingnya yang paling lambat adalah TTFFTTFFTTFF, yang tampaknya, bagi mata manusia saya, cukup dapat diprediksi. Acak secara inheren tidak dapat diprediksi, jadi sangat mungkin itu akan lebih lambat, dan dengan demikian di luar batas yang ditunjukkan di sini. OTOH, bisa jadi TTFFTTFF sempurna mengenai kasus patologis. Tidak tahu, karena dia tidak menunjukkan timing secara acak.
Mooing Duck

21
@MooingDuck Di mata manusia, "TTFFTTFFTTFF" adalah urutan yang dapat diprediksi, tetapi apa yang kita bicarakan di sini adalah perilaku prediktor cabang yang dibangun ke dalam CPU. Prediktor cabang bukanlah pengenalan pola level AI; ini sangat sederhana. Saat Anda baru saja berganti cabang, itu tidak dapat diprediksi dengan baik. Dalam sebagian besar kode, cabang berjalan dengan cara yang sama hampir sepanjang waktu; pertimbangkan loop yang dijalankan ribuan kali. Cabang pada akhir loop kembali ke awal loop 999 kali, dan kemudian kali keseribu melakukan sesuatu yang berbeda. Prediktor cabang yang sangat sederhana bekerja dengan baik, biasanya.
steveha

18
@steveha: Saya pikir Anda membuat asumsi tentang cara kerja peramal cabang CPU, dan saya tidak setuju dengan metodologi itu. Saya tidak tahu seberapa canggih prediktor cabang itu, tetapi saya pikir itu jauh lebih maju daripada Anda. Anda mungkin benar, tetapi pengukuran pasti akan baik.
Mooing Duck

5
@steveha: Prediktor adaptif dua tingkat dapat mengunci pola TTFFTTFF tanpa masalah apa pun. "Varian dari metode prediksi ini digunakan di sebagian besar mikroprosesor modern". Prediksi cabang lokal dan prediksi cabang Global didasarkan pada dua tingkat prediktor adaptif, mereka juga bisa. "Prediksi cabang global digunakan dalam prosesor AMD, dan pada prosesor Intel Pentium M, Core, Core 2, dan Silvermont" Juga menambahkan prediktor Agree, Prediktor hibrid, Prediksi lompatan tidak langsung, ke daftar itu. Loop predictor tidak akan terkunci, tetapi mencapai 75%. Hanya menyisakan 2 yang tidak bisa mengunci
Mooing Duck

1126

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


29
Benar, Anda juga bisa menggunakan bit secara langsung dan berkembang biak ( data[c]>>7- yang juga dibahas di sini); Saya sengaja mengabaikan solusi ini, tetapi tentu saja Anda benar. Hanya sebuah catatan kecil: Aturan praktis untuk tabel pencarian adalah bahwa jika cocok di 4KB (karena caching), itu akan berhasil - sebaiknya buat tabel sekecil mungkin. Untuk bahasa yang dikelola saya akan mendorongnya ke 64KB, untuk bahasa tingkat rendah seperti C ++ dan C, saya mungkin akan mempertimbangkan kembali (itu hanya pengalaman saya). Karena typeof(int) = 4, saya akan mencoba untuk tetap menggunakan maksimal 10 bit.
atlaste

17
Saya pikir pengindeksan dengan nilai 0/1 mungkin akan lebih cepat daripada bilangan bulat integer, tapi saya kira jika kinerja sangat penting Anda harus profil itu. Saya setuju bahwa tabel pencarian kecil sangat penting untuk menghindari tekanan cache, tetapi jelas jika Anda memiliki cache yang lebih besar, Anda bisa lolos dengan tabel pencarian yang lebih besar, jadi 4KB lebih merupakan aturan praktis daripada aturan keras. Saya pikir Anda maksud sizeof(int) == 4? Itu akan berlaku untuk 32-bit. Ponsel saya yang berumur dua tahun memiliki cache L1 32KB, jadi bahkan tabel lookup 4K bisa berfungsi, terutama jika nilai pencariannya adalah byte, bukan int.
steveha

12
Mungkin saya kehilangan sesuatu tetapi dalam jmetode Anda sama dengan 0 atau 1, mengapa Anda tidak mengalikan nilainya dengan jsebelum menambahkannya daripada menggunakan pengindeksan array (mungkin harus dikalikan dengan 1-jalih-alih j)
Richard Tingle

6
@steveha Penggandaan seharusnya lebih cepat, saya mencoba mencarinya di buku Intel, tetapi tidak dapat menemukannya ... apa pun caranya, pembandingan juga memberi saya hasil di sini.
atlaste

10
@steveha PS: jawaban lain yang mungkin adalah int c = data[j]; sum += c & -(c >> 7);yang tidak memerlukan perkalian sama sekali.
atlaste

1022

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


23
sum= 3137536- pintar. Itu agak jelas bukan inti dari pertanyaan. Pertanyaannya jelas tentang menjelaskan karakteristik kinerja yang mengejutkan. Saya cenderung mengatakan bahwa penambahan melakukan std::partitionalih - alih std::sortitu berharga. Padahal pertanyaan sebenarnya meluas ke lebih dari sekedar tolok ukur sintetis yang diberikan.
lihat

12
@DeadMG: ini memang bukan pencarian dikotomik standar untuk kunci yang diberikan, tetapi pencarian untuk indeks partisi; membutuhkan satu perbandingan per iterasi. Tapi jangan mengandalkan kode ini, saya belum memeriksanya. Jika Anda tertarik dengan implementasi yang benar dan terjamin, beri tahu saya.
Yves Daoust

832

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. Pipa 4-tahap secara umum

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: masukkan deskripsi gambar di sini

Ketika jika kondisi kembali salah: masukkan deskripsi gambar di sini

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: masukkan deskripsi gambar di sini

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.


1
bagaimana dua instruksi dieksekusi bersama? apakah ini dilakukan dengan core cpu terpisah atau instruksi pipa terintegrasi dalam cpu core tunggal?
M.kazem Akhgary

1
@ M.kazemAkhgary Semuanya ada di dalam satu inti logis. Jika Anda tertarik, ini dijelaskan dengan baik misalnya dalam Manual Pengembang Perangkat Lunak Intel
Sergey.quixoticaxis.Ivanov

728

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.

Diagram keadaan 2-bit

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.



697

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.


679

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


342

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?

Prediksi Cabang

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

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.


304

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


3
Itu adalah artikel yang sangat menarik (pada kenyataannya, saya baru saja membaca semua itu), tetapi bagaimana cara menjawab pertanyaan?
Peter Mortensen

2
@PeterMortensen Saya agak bingung dengan pertanyaan Anda. Sebagai contoh di sini adalah satu baris yang relevan dari bagian itu: When the input is unsorted, all the rest of the loop takes substantial time. But with sorted input, the processor is somehow able to spend not just less time in the body of the loop, meaning the buckets at offsets 0x18 and 0x1C, but vanishingly little time on the mechanism of looping. Penulis sedang mencoba untuk membahas profiling dalam konteks kode yang diposting di sini dan dalam proses mencoba menjelaskan mengapa kasus yang diurutkan jauh lebih cepat.
ForeverLearning

261

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

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

tanpa prediktor cabang

Diperlukan 9 siklus clock agar 3 instruksi dapat diselesaikan.

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

masukkan deskripsi gambar di sini

Diperlukan 7 siklus clock agar 3 instruksi dapat diselesaikan.

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

masukkan deskripsi gambar di sini

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


1
Hampir sama bagusnya dengan animasi pemasaran Intel, dan mereka terobsesi bukan hanya dengan prediksi cabang tetapi juga eksekusi yang salah, kedua strategi ini "spekulatif". Membaca di depan dalam memori dan penyimpanan (pre-fetch to buffer) juga spekulatif. Semuanya bertambah.
mckenzm

@ mckenzm: eksekutif spekulatif out-of-order membuat prediksi cabang lebih berharga; serta menyembunyikan gelembung fetch / decode, prediksi cabang + exec spekulatif menghapus dependensi kontrol dari latensi jalur kritis. Kode di dalam atau setelah if()blok dapat dijalankan sebelum kondisi cabang diketahui. Atau untuk loop pencarian seperti strlenatau memchr, interaksi dapat tumpang tindih. Jika Anda harus menunggu agar hasil pertandingan-atau-tidak diketahui sebelum menjalankan iterasi berikutnya, Anda akan mengalami bottleneck pada cache load + latensi ALU alih-alih throughput.
Peter Cordes

210

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

Sementara pipa pembilasan super cepat Tidak juga. Ini cepat dibandingkan dengan cache yang ketinggalan semua jalan ke DRAM, tetapi pada x86 kinerja tinggi modern (seperti keluarga Intel Sandybridge) ini sekitar selusin siklus. Meskipun pemulihan cepat memungkinkan untuk menghindari menunggu semua instruksi independen yang lebih tua untuk mencapai pensiun sebelum memulai pemulihan, Anda masih kehilangan banyak siklus front-end pada salah duga. Apa yang sebenarnya terjadi ketika CPU skylake salah memperkirakan cabang? . (Dan setiap siklus dapat sekitar 4 instruksi kerja.) Buruk untuk kode throughput tinggi.
Peter Cordes

153

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.


1
Inovasi lain dalam ARM adalah penambahan sufiks instruksi S, juga opsional pada (hampir) semua instruksi, yang jika tidak ada, mencegah instruksi mengubah bit status (dengan pengecualian instruksi CMP, yang tugasnya mengatur bit status, jadi tidak perlu sufiks S). Ini memungkinkan Anda untuk menghindari instruksi CMP dalam banyak kasus, selama perbandingannya dengan nol atau serupa (mis. SUBS R0, R0, # 1 akan mengatur bit Z (Nol) ketika R0 mencapai nol). Kondisional dan sufiks S dikenakan nol di atas kepala. Ini ISA yang sangat indah.
Luke Hutchison

2
Dengan tidak menambahkan akhiran S, Anda dapat memiliki beberapa instruksi bersyarat secara berturut-turut tanpa khawatir salah satu dari mereka dapat mengubah bit status, yang mungkin memiliki efek samping karena melewatkan sisa instruksi bersyarat.
Luke Hutchison

Perhatikan bahwa OP tidak termasuk waktu untuk menyortir pengukurannya. Mungkin kehilangan keseluruhan untuk mengurutkan terlebih dahulu sebelum menjalankan loop cabang x86, juga, meskipun case yang tidak diurutkan membuat loop berjalan jauh lebih lambat. Tetapi mengurutkan array besar membutuhkan banyak pekerjaan.
Peter Cordes

BTW, Anda bisa menyimpan instruksi dalam loop dengan mengindeks relatif ke akhir array. Sebelum loop, atur R2 = data + arraySize, lalu mulai dengan R1 = -arraySize. Bagian bawah loop menjadi adds r1, r1, #1/ bnz inner_loop. Kompiler tidak menggunakan pengoptimalan ini karena beberapa alasan: / Tapi bagaimanapun, eksekusi tambahan yang ditentukan tidak berbeda secara mendasar dalam hal ini dari apa yang dapat Anda lakukan dengan kode branchless pada SPA lainnya, seperti x86 cmov. Meskipun tidak sebagus: flag optimasi gcc -O3 membuat kode lebih lambat dari -O2
Peter Cordes

1
(ARM memprediksikan eksekusi benar-benar NOP instruksi, sehingga Anda bahkan dapat menggunakannya pada banyak atau toko yang akan kesalahan, tidak seperti x86 cmovdengan operan sumber memori. Sebagian besar ISA, termasuk AArch64, hanya memiliki operasi pilih ALU. Jadi predikasi ARM dapat menjadi kuat, dan dapat digunakan lebih efisien daripada kode tanpa cabang pada sebagian besar ISA.)
Peter Cordes

147

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:


146

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

1
Benar, tetapi biaya setup untuk mengurutkan array adalah O (N log N), jadi melanggar lebih awal tidak membantu Anda jika satu-satunya alasan Anda menyortir array adalah untuk dapat memecah lebih awal. Namun, jika Anda memiliki alasan lain untuk melakukan pre-sortir array, maka ya, ini sangat berharga.
Luke Hutchison

Tergantung berapa kali Anda mengurutkan data dibandingkan dengan berapa kali Anda mengulanginya. Jenis dalam contoh ini hanyalah contoh, tidak harus tepat sebelum perulangan
Yochai Timmer

2
Ya, itulah poin yang saya buat dalam komentar pertama saya :-) Anda mengatakan "Prediksi cabang hanya akan hilang satu kali." Tapi Anda tidak menghitung prediksi cabang O (N log N) meleset di dalam algoritma pengurutan, yang sebenarnya lebih besar dari prediksi cabang O (N) meleset dalam kasus tidak disortir. Jadi, Anda perlu menggunakan keseluruhan data yang diurutkan O (log N) kali untuk mencapai titik impas (mungkin sebenarnya lebih dekat dengan O (10 log N), tergantung pada algoritma pengurutan, misalnya untuk quicksort, karena kekurangan cache - mergesort lebih cache-koheren, jadi Anda perlu lebih dekat dengan O (2 log N) untuk mencapai titik impas.)
Luke Hutchison

Satu pengoptimalan yang signifikan adalah dengan melakukan hanya "setengah quicksort", menyortir hanya item yang kurang dari nilai target pivot 127 (dengan asumsi semuanya kurang dari atau sama dengan pivot diurutkan setelah pivot). Setelah Anda mencapai pivot, jumlah elemen sebelum pivot. Ini akan berjalan dalam waktu startup O (N) daripada O (N log N), meskipun masih akan ada banyak prediksi cabang yang terlewatkan, mungkin urutan O (5 N) berdasarkan pada angka yang saya berikan sebelumnya, karena itu setengah quicksort.
Luke Hutchison

132

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


124

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.


7
Hanya demi kelengkapan, ini mungkin bukan cara Anda mengimplementasikannya di Matlab. Saya yakin itu akan jauh lebih cepat jika dilakukan setelah membuat vektor masalah.
ysap

1
Matlab melakukan paralelisasi / vektorisasi otomatis dalam banyak situasi tetapi masalah di sini adalah untuk memeriksa efek prediksi cabang. Matlab bagaimanapun juga tidak kebal!
Shan

1
Apakah matlab menggunakan angka asli atau implementasi khusus lab mat (jumlah digit tak terbatas atau lebih?)
Thorbj?rn Ravn Andersen

55

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.


4
Saya tidak benar-benar melihat bagaimana ini membuktikan sesuatu? Satu-satunya hal yang telah Anda tunjukkan adalah bahwa "tidak melakukan semua pekerjaan mengurutkan seluruh array membutuhkan waktu lebih sedikit daripada mengurutkan seluruh array". Klaim Anda bahwa "ini juga berjalan tercepat" sangat bergantung pada arsitektur. Lihat jawaban saya tentang cara kerjanya di ARM. PS Anda bisa membuat kode Anda lebih cepat pada arsitektur non-ARM dengan meletakkan penjumlahan di dalam loop blok 200-elemen, mengurutkan secara terbalik, dan kemudian menggunakan saran Yochai Timmer untuk memecahkan begitu Anda mendapatkan nilai di luar kisaran. Dengan begitu setiap penjumlahan blok 200 elemen dapat diakhiri lebih awal.
Luke Hutchison

Jika Anda hanya ingin mengimplementasikan algoritma secara efisien pada data yang tidak disortir, Anda akan melakukan operasi itu tanpa cabang (dan dengan SIMD, misalnya dengan x86 pcmpgtbuntuk menemukan elemen dengan set bit tinggi, lalu DAN ke nol elemen yang lebih kecil). Menghabiskan waktu benar-benar menyortir potongan akan lebih lambat. Versi branchless akan memiliki kinerja data-independen, juga membuktikan bahwa biaya berasal dari salah prediksi cabang. Atau cukup gunakan penghitung kinerja untuk mengamati hal itu secara langsung, seperti Skylake int_misc.clear_resteer_cyclesatau int_misc.recovery_cyclesuntuk menghitung siklus menganggur front-end dari mispredicts
Peter Cordes

Kedua komentar di atas nampaknya mengabaikan masalah algoritmik umum dan kompleksitas, mendukung advokasi perangkat keras khusus dengan instruksi mesin khusus. Saya menemukan yang pertama khususnya picik karena dengan blak-blakan menolak wawasan umum yang penting dalam jawaban ini demi bantuan instruksi mesin khusus.
user2297550

36

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.


28

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.


Instruksi tetap panas di cache instruksi L1 CPU terlepas dari mispredicts. Masalahnya adalah mengambil mereka ke dalam pipa dalam urutan yang benar, sebelum instruksi segera-sebelumnya telah diterjemahkan dan selesai dieksekusi.
Peter Cordes

15

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


Kompiler / perangkat keras C ++ apa yang Anda uji dengan ini, dan dengan opsi kompiler apa? Saya terkejut bahwa versi aslinya tidak melakukan auto-vektorisasi ke kode SIMD tanpa cabang yang bagus. Apakah Anda mengaktifkan optimasi penuh?
Peter Cordes

Tabel pencarian entri 4096 terdengar gila. Jika Anda menggeser keluar setiap bit, Anda perlu tidak bisa hanya menggunakan hasil Lut jika Anda ingin menambahkan nomor asli. Ini semua terdengar seperti trik konyol untuk mengatasi kompiler Anda tidak mudah menggunakan teknik branchless. Lebih mudah akan mask = tmp < 128 : 0 : -1UL;/total += tmp & mask;
Peter Cordes
Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.
Judi bola