Apa pembagian pendukung bilangan bulat tercepat dengan nol tidak peduli apa hasilnya?

Ringkasan:

Saya mencari cara tercepat untuk menghitung

(int) x / (int) y

tanpa mendapatkan pengecualian untuk y==0. Sebaliknya saya hanya menginginkan hasil yang sewenang-wenang.

Latar Belakang:

Saat mengkodekan algoritma pemrosesan gambar, saya sering kali perlu membagi dengan nilai alfa (terakumulasi). Varian paling sederhana adalah kode C biasa dengan aritmatika integer. Masalah saya adalah bahwa saya biasanya mendapatkan kesalahan pembagian dengan nol untuk piksel hasil dengan alpha==0. Namun ini persis piksel di mana hasilnya tidak masalah sama sekali: Saya tidak peduli dengan nilai warna piksel alpha==0.

Rincian:

Saya mencari sesuatu seperti:

result = (y==0)? 0 : x/y;

atau

result = x / MAX( y, 1 );

x dan y adalah bilangan bulat positif. Kode tersebut dieksekusi berkali-kali dalam loop bersarang, jadi saya mencari cara untuk menyingkirkan percabangan bersyarat.

Ketika y tidak melebihi kisaran byte, saya senang dengan solusinya

unsigned char kill_zero_table[256] = { 1, 1, 2, 3, 4, 5, 6, 7, [...] 255 };
[...]
result = x / kill_zero_table[y];

Tapi ini jelas tidak berfungsi dengan baik untuk rentang yang lebih besar.

Saya kira pertanyaan terakhirnya adalah: Apa bit twiddling hack tercepat yang mengubah 0 menjadi nilai integer lainnya, sementara membiarkan semua nilai lain tidak berubah?

Klarifikasi

Saya tidak 100% yakin bahwa percabangan itu terlalu mahal. Namun, kompiler yang berbeda digunakan, jadi saya lebih suka melakukan benchmarking dengan sedikit pengoptimalan (yang memang dipertanyakan).

Yang pasti, kompiler sangat bagus dalam hal bit twiddling, tapi saya tidak bisa mengungkapkan hasil "tidak peduli" di C, jadi kompilator tidak akan pernah bisa menggunakan berbagai optimasi lengkap.

Kode harus sepenuhnya kompatibel dengan C, platform utamanya adalah Linux 64 Bit dengan gcc & clang dan MacOS.

Terinspirasi oleh beberapa komentar yang saya singkirkan dari cabang di Pentium dan gcckompiler saya menggunakan

int f (int x, int y)
{
        y += y == 0;
        return x/y;
}

Kompilator pada dasarnya mengenali bahwa ia dapat menggunakan tanda kondisi pengujian sebagai tambahan.

Sesuai permintaan perakitan:

.globl f
    .type   f, @function
f:
    pushl   %ebp
    xorl    %eax, %eax
    movl    %esp, %ebp
    movl    12(%ebp), %edx
    testl   %edx, %edx
    sete    %al
    addl    %edx, %eax
    movl    8(%ebp), %edx
    movl    %eax, %ecx
    popl    %ebp
    movl    %edx, %eax
    sarl    $31, %edx
    idivl   %ecx
    ret

Karena ini ternyata pertanyaan dan jawaban yang populer, saya akan menjelaskan sedikit lebih banyak. Contoh di atas didasarkan pada idiom pemrograman yang dikenali oleh compiler. Dalam kasus di atas ekspresi boolean digunakan dalam aritmatika integral dan penggunaan bendera kondisi ditemukan di perangkat keras untuk tujuan ini. Secara umum, flag hanya dapat diakses di C dengan menggunakan idiom. Itulah mengapa sangat sulit untuk membuat pustaka integer presisi multipel portabel di C tanpa menggunakan perakitan (inline). Dugaan saya adalah bahwa kompiler yang paling baik akan memahami idiom di atas.

Cara lain untuk menghindari cabang, seperti yang juga disebutkan dalam beberapa komentar di atas, adalah eksekusi berpredikat. Oleh karena itu, saya mengambil kode pertama philipp dan kode saya dan menjalankannya melalui kompiler dari ARM dan kompiler GCC untuk arsitektur ARM, yang menampilkan eksekusi berpredikat. Kedua kompiler menghindari cabang di kedua contoh kode:

Versi Philipp dengan kompiler ARM:

f PROC
        CMP      r1,#0
        BNE      __aeabi_idivmod
        MOVEQ    r0,#0
        BX       lr

Versi Philipp dengan GCC:

f:
        subs    r3, r1, #0
        str     lr, [sp, #-4]!
        moveq   r0, r3
        ldreq   pc, [sp], #4
        bl      __divsi3
        ldr     pc, [sp], #4

Kode saya dengan kompiler ARM:

f PROC
        RSBS     r2,r1,#1
        MOVCC    r2,#0
        ADD      r1,r1,r2
        B        __aeabi_idivmod

Kode saya dengan GCC:

f:
        str     lr, [sp, #-4]!
        cmp     r1, #0
        addeq   r1, r1, #1
        bl      __divsi3
        ldr     pc, [sp], #4

Semua versi masih memerlukan cabang ke rutinitas divisi, karena versi ARM ini tidak memiliki perangkat keras untuk sebuah divisi, tetapi pengujian untuk y == 0sepenuhnya diimplementasikan melalui eksekusi predikat.

Berikut adalah beberapa angka konkret, di Windows yang menggunakan GCC 4.7.2:

#include <stdio.h>
#include <stdlib.h>

int main()
{
  unsigned int result = 0;
  for (int n = -500000000; n != 500000000; n++)
  {
    int d = -1;
    for (int i = 0; i != ITERATIONS; i++)
      d &= rand();

#if CHECK == 0
    if (d == 0) result++;
#elif CHECK == 1
    result += n / d;
#elif CHECK == 2
    result += n / (d + !d);
#elif CHECK == 3
    result += d == 0 ? 0 : n / d;
#elif CHECK == 4
    result += d == 0 ? 1 : n / d;
#elif CHECK == 5
    if (d != 0) result += n / d;
#endif
  }
  printf("%u\n", result);
}

Perhatikan bahwa saya sengaja tidak menelepon srand(), sehingga rand()selalu mengembalikan hasil yang persis sama. Perhatikan juga bahwa -DCHECK=0hanya menghitung angka nol, sehingga jelas seberapa sering muncul.

Sekarang, kompilasi dan pengaturan waktunya dengan berbagai cara:

$ for it in 0 1 2 3 4 5; do for ch in 0 1 2 3 4 5; do gcc test.cc -o test -O -DITERATIONS=$it -DCHECK=$ch && { time=`time ./test`; echo "Iterations $it, check $ch: exit status $?, output $time"; }; done; done

menunjukkan keluaran yang dapat diringkas dalam sebuah tabel:

Iterations → | 0        | 1        | 2        | 3         | 4         | 5
-------------+-------------------------------------------------------------------
Zeroes       | 0        | 1        | 133173   | 1593376   | 135245875 | 373728555
Check 1      | 0m0.612s | -        | -        | -         | -         | -
Check 2      | 0m0.612s | 0m6.527s | 0m9.718s | 0m13.464s | 0m18.422s | 0m22.871s
Check 3      | 0m0.616s | 0m5.601s | 0m8.954s | 0m13.211s | 0m19.579s | 0m25.389s
Check 4      | 0m0.611s | 0m5.570s | 0m9.030s | 0m13.544s | 0m19.393s | 0m25.081s
Check 5      | 0m0.612s | 0m5.627s | 0m9.322s | 0m14.218s | 0m19.576s | 0m25.443s

Jika nol jarang terjadi, -DCHECK=2versi tersebut berkinerja buruk. Saat angka nol mulai muncul lebih banyak,-DCHECK=2 kasing mulai bekerja secara signifikan lebih baik. Dari opsi lain, sebenarnya tidak banyak perbedaan.

Karena -O3, bagaimanapun, ini adalah cerita yang berbeda:

Iterations → | 0        | 1        | 2        | 3         | 4         | 5
-------------+-------------------------------------------------------------------
Zeroes       | 0        | 1        | 133173   | 1593376   | 135245875 | 373728555
Check 1      | 0m0.646s | -        | -        | -         | -         | -
Check 2      | 0m0.654s | 0m5.670s | 0m9.905s | 0m14.238s | 0m17.520s | 0m22.101s
Check 3      | 0m0.647s | 0m5.611s | 0m9.085s | 0m13.626s | 0m18.679s | 0m25.513s
Check 4      | 0m0.649s | 0m5.381s | 0m9.117s | 0m13.692s | 0m18.878s | 0m25.354s
Check 5      | 0m0.649s | 0m6.178s | 0m9.032s | 0m13.783s | 0m18.593s | 0m25.377s

Di sana, centang 2 tidak memiliki kekurangan dibandingkan dengan pemeriksaan lainnya, dan ini menjaga manfaat karena angka nol menjadi lebih umum.

Anda harus benar-benar mengukur untuk melihat apa yang terjadi dengan compiler Anda dan data sampel perwakilan Anda.

Tanpa mengetahui platformnya, tidak ada cara untuk mengetahui metode paling efisien yang tepat, namun, pada sistem umum ini mungkin mendekati optimal (menggunakan sintaks assembler Intel):

(asumsikan pembagi masuk ecxdan pembagi masuk eax)

mov ebx, ecx
neg ebx
sbb ebx, ebx
add ecx, ebx
div eax, ecx

Empat instruksi siklus tunggal yang tidak bercabang ditambah pembagian. Hasil bagi akan masuk eaxdan sisanya akan masuk edxdi akhir. (Jenis ini menunjukkan mengapa Anda tidak ingin mengirim kompiler untuk melakukan pekerjaan pria).

Menurut tautan ini , Anda cukup memblokir sinyal SIGFPE dengan sigaction()(Saya belum mencobanya sendiri, tetapi saya yakin ini akan berfungsi).

Ini adalah pendekatan tercepat yang mungkin jika kesalahan bagi dengan nol sangat jarang terjadi: Anda hanya membayar untuk divisi dengan nol, bukan untuk divisi yang valid, jalur eksekusi normal tidak berubah sama sekali.

Namun, OS akan terlibat dalam setiap pengecualian yang diabaikan, yang mahal harganya. Saya pikir, Anda harus memiliki setidaknya seribu divisi bagus per divisi dengan nol yang Anda abaikan. Jika pengecualian lebih sering dari itu, Anda mungkin akan membayar lebih dengan mengabaikan pengecualian daripada dengan memeriksa setiap nilai sebelum pembagian.