Pertanyaan Mengapa GCC tidak mengoptimalkan a * a * a * a * a ke (a * a * a) * (a * a * a)?


Saya melakukan sejumlah pengoptimalan numerik pada aplikasi ilmiah. Satu hal yang saya perhatikan adalah bahwa GCC akan mengoptimalkan panggilan pow(a,2) dengan menyusunnya menjadi a*a, tapi panggilannya pow(a,6) tidak dioptimalkan dan benar-benar akan memanggil fungsi pustaka pow, yang sangat memperlambat kinerja. (Sebaliknya, Intel C ++ Compiler, dapat dieksekusi icc, akan menghilangkan panggilan perpustakaan untuk pow(a,6).)

Yang saya ingin tahu adalah ketika saya diganti pow(a,6) dengan a*a*a*a*a*a menggunakan GCC 4.5.1 dan opsi "-O3 -lm -funroll-loops -msse4", ini menggunakan 5 mulsd instruksi:

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13

sementara jika saya menulis (a*a*a)*(a*a*a), itu akan menghasilkan

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm13, %xmm13

yang mengurangi jumlah instruksi multiply ke 3. icc memiliki perilaku serupa.

Mengapa penyusun tidak mengenali trik pengoptimalan ini?


1965
2018-06-21 18:49


asal


Jawaban:


Karena Floating Point Math tidak Asosiatif. Cara Anda mengelompokkan operand dalam penggandaan floating point memiliki efek pada ketepatan numerik jawaban.

Akibatnya, sebagian besar penyusun sangat konservatif tentang penataan ulang penghitungan titik apung kecuali mereka dapat yakin bahwa jawabannya akan tetap sama, atau kecuali Anda memberi tahu mereka bahwa Anda tidak peduli dengan keakuratan numerik. Sebagai contoh: itu -fassociative-math pilihan gcc yang memungkinkan gcc untuk menghubungkan kembali operasi floating point, atau bahkan -ffast-math opsi yang memungkinkan pengorbanan akurasi yang lebih agresif terhadap kecepatan.


2565
2018-06-22 15:32



Lambdageek benar menunjukkan bahwa karena associativity tidak berlaku untuk angka floating-point, yang "optimalisasi" a*a*a*a*a*a untuk (a*a*a)*(a*a*a) dapat mengubah nilainya. Inilah mengapa hal itu dianulir oleh C99 (kecuali secara khusus diizinkan oleh pengguna, melalui flag compiler atau pragma). Secara umum, asumsi adalah bahwa programmer menulis apa yang dia lakukan karena suatu alasan, dan compiler harus menghargai itu. jika kamu mau (a*a*a)*(a*a*a), tulis itu.

Itu bisa menjadi sakit untuk menulis, meskipun; mengapa kompilator tidak dapat melakukan apa yang Anda anggap benar ketika Anda menggunakannya pow(a,6)? Karena itu akan menjadi salah sesuatu yang harus dikerjakan. Di platform dengan perpustakaan matematika yang bagus, pow(a,6) secara signifikan lebih akurat daripada keduanya a*a*a*a*a*a atau (a*a*a)*(a*a*a). Hanya untuk menyediakan beberapa data, saya menjalankan eksperimen kecil di Mac Pro saya, mengukur kesalahan terburuk dalam mengevaluasi ^ 6 untuk semua nomor floating presisi tunggal antara [1,2):

worst relative error using    powf(a, 6.f): 5.96e-08
worst relative error using (a*a*a)*(a*a*a): 2.94e-07
worst relative error using     a*a*a*a*a*a: 2.58e-07

Menggunakan pow bukannya pohon perkalian mengurangi kesalahan yang dibatasi oleh faktor 4. Compiler seharusnya tidak (dan biasanya tidak) membuat "optimisasi" yang meningkatkan kesalahan kecuali lisensi untuk melakukannya oleh pengguna (misalnya melalui -ffast-math).

Perhatikan bahwa GCC menyediakan __builtin_powi(x,n) sebagai alternatif untuk pow( ), yang harus menghasilkan pohon perkalian inline. Gunakan itu jika Anda ingin menukar akurasi untuk kinerja, tetapi tidak ingin mengaktifkan cepat-matematika.


613
2018-06-22 22:39



Kasus lain yang serupa: kebanyakan kompiler tidak akan dioptimalkan a + b + c + d untuk (a + b) + (c + d) (ini adalah optimasi karena ekspresi kedua dapat pipelined lebih baik) dan mengevaluasinya sebagai diberikan (yaitu sebagai (((a + b) + c) + d)). Ini juga karena kasus-kasus pojok:

float a = 1e35, b = 1e-5, c = -1e35, d = 1e-5;
printf("%e %e\n", a + b + c + d, (a + b) + (c + d));

Output ini 1.000000e-05 0.000000e+00


152
2018-06-23 11:44



Fortran (dirancang untuk komputasi ilmiah) memiliki operator daya internal, dan sejauh yang saya tahu, kompiler Fortran biasanya akan mengoptimalkan peningkatan ke daya bilangan bulat dengan cara yang mirip dengan apa yang Anda gambarkan. C / C ++ sayangnya tidak memiliki operator daya, hanya fungsi pustaka pow(). Ini tidak mencegah kompilator pintar memperlakukan pow khusus dan menghitungnya dengan cara yang lebih cepat untuk kasus-kasus khusus, tetapi tampaknya mereka melakukannya lebih jarang ...

Beberapa tahun yang lalu saya mencoba membuatnya lebih mudah untuk menghitung daya bilangan bulat secara optimal, dan datang dengan yang berikut. Ini C ++, bukan C meskipun, dan masih tergantung pada compiler yang agak pintar tentang cara mengoptimalkan / hal inline. Bagaimanapun, harap Anda mungkin akan menemukannya berguna dalam praktik:

template<unsigned N> struct power_impl;

template<unsigned N> struct power_impl {
    template<typename T>
    static T calc(const T &x) {
        if (N%2 == 0)
            return power_impl<N/2>::calc(x*x);
        else if (N%3 == 0)
            return power_impl<N/3>::calc(x*x*x);
        return power_impl<N-1>::calc(x)*x;
    }
};

template<> struct power_impl<0> {
    template<typename T>
    static T calc(const T &) { return 1; }
};

template<unsigned N, typename T>
inline T power(const T &x) {
    return power_impl<N>::calc(x);
}

Klarifikasi untuk yang penasaran: ini tidak menemukan cara optimal untuk menghitung kekuatan, tetapi sejak saat itu menemukan solusi optimal adalah masalah NP-lengkap dan ini hanya layak dilakukan untuk kekuatan kecil pula (dibandingkan dengan menggunakan pow), tidak ada alasan untuk repot dengan detailnya.

Kemudian gunakan saja sebagai power<6>(a).

Ini membuatnya mudah untuk mengetik kekuatan (tidak perlu mengeja 6 as dengan parens), dan memungkinkan Anda memiliki optimasi semacam ini tanpa -ffast-math jika Anda memiliki sesuatu yang presisi tergantung seperti penjumlahan dikompensasi (contoh di mana urutan operasi sangat penting).

Anda mungkin juga dapat lupa bahwa ini adalah C ++ dan hanya menggunakannya dalam program C (jika dikompilasi dengan kompiler C ++).

Semoga ini bisa bermanfaat.

EDIT:

Ini yang saya dapatkan dari compiler saya:

Untuk a*a*a*a*a*a,

    movapd  %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0

Untuk (a*a*a)*(a*a*a),

    movapd  %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm0, %xmm0

Untuk power<6>(a),

    mulsd   %xmm0, %xmm0
    movapd  %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
    mulsd   %xmm0, %xmm1

74
2018-06-23 10:07



Karena angka floating-point 32-bit - seperti 1.024 - bukan 1.024. Di komputer, 1,024 adalah interval: dari (1,024-e) hingga (1,024 + e), di mana "e" mewakili kesalahan. Beberapa orang gagal menyadari hal ini dan juga percaya bahwa * dalam * suatu kependekan dari penggandaan angka-angka presisi acak tanpa ada kesalahan yang melekat pada angka-angka itu. Alasan mengapa beberapa orang gagal menyadari hal ini adalah mungkin perhitungan matematika yang mereka lakukan di sekolah dasar: bekerja hanya dengan angka ideal tanpa kesalahan, dan percaya bahwa tidak masalah mengabaikan "e" saat melakukan perkalian. Mereka tidak melihat "e" tersirat dalam kode "float a = 1.2", "a * a * a" dan C serupa.

Haruskah mayoritas programmer mengenali (dan dapat mengeksekusi) ide bahwa ekspresi C a * a * a * a * a * a tidak benar-benar bekerja dengan angka ideal, kompiler GCC akan menjadi GRATIS untuk mengoptimalkan "a * a * a * a * a * a "menjadi mengatakan" t = (a * a); t * t * t "yang membutuhkan jumlah perkalian yang lebih kecil. Namun sayangnya, compiler GCC tidak tahu apakah programmer yang menulis kode menganggap bahwa "a" adalah angka dengan atau tanpa kesalahan. Jadi GCC hanya akan melakukan seperti apa kode sumbernya - karena itulah yang dilihat GCC dengan "mata telanjang".

... begitu Anda tahu programmer macam apa kamu Anda dapat menggunakan sakelar "-beri-matematika" untuk memberi tahu GCC bahwa "Hai, GCC, saya tahu apa yang saya lakukan!". Ini akan memungkinkan GCC untuk mengonversi a * a * a * a * a ke dalam bagian teks yang berbeda - ini terlihat berbeda dari * a * a * a * a * a - tetapi masih menghitung angka dalam interval kesalahan dari a * a * a * a * a * a. Ini tidak masalah, karena Anda sudah tahu bahwa Anda bekerja dengan interval, bukan angka ideal.


49
2018-03-29 06:51



GCC benar-benar mengoptimalkan * a * a * a * a * a ke (a * a * a) * (a * a * a) ketika a adalah bilangan bulat. Saya mencoba dengan perintah ini:

$ echo 'int f(int x) { return x*x*x*x*x*x; }' | gcc -o - -O2 -S -masm=intel -x c -

Ada banyak bendera gcc tetapi tidak ada yang mewah. Mereka berarti: Baca dari stdin; menggunakan tingkat pengoptimalan O2; daftar bahasa assembly output daripada biner; daftar harus menggunakan sintaks bahasa assembly Intel; input dalam bahasa C (biasanya bahasa disimpulkan dari ekstensi file input, tetapi tidak ada ekstensi file saat membaca dari stdin); dan menulis ke stdout.

Inilah bagian penting dari output. Saya telah memberi anotasi dengan beberapa komentar yang menunjukkan apa yang terjadi dalam bahasa assembly:

    ; x is in edi to begin with.  eax will be used as a temporary register.
    mov    eax, edi     ; temp1 = x
    imul    eax, edi    ; temp2 = x * temp1
    imul    eax, edi    ; temp3 = x * temp2
    imul    eax, eax    ; temp4 = temp3 * temp3

Saya menggunakan sistem GCC di Linux Mint 16 Petra, sebuah turunan Ubuntu. Inilah versi gcc:

$ gcc --version
gcc (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1

Seperti yang dicatat oleh poster lain, opsi ini tidak mungkin dalam floating point, karena floating point arithmetic sebenarnya bukan asosiatif.


49
2018-06-27 21:03



Belum ada poster yang menyebutkan kontraksi ekspresi mengambang (standar ISO C, 6.5p8 dan 7.12.2). Jika itu FP_CONTRACT pragma diatur ke ON, compiler diperbolehkan untuk menganggap ekspresi seperti a*a*a*a*a*a sebagai operasi tunggal, seakan dievaluasi persis dengan pembulatan tunggal. Sebagai contoh, kompilator dapat menggantinya dengan fungsi daya internal yang lebih cepat dan lebih akurat. Hal ini sangat menarik karena perilaku sebagian dikendalikan oleh pemrogram langsung dalam kode sumber, sementara opsi kompilator yang disediakan oleh pengguna akhir terkadang dapat digunakan secara tidak benar.

Keadaan default dari FP_CONTRACT pragma adalah implementasi yang ditentukan, sehingga kompilator diizinkan untuk melakukan pengoptimalan tersebut secara default. Jadi, kode portabel yang harus benar-benar mengikuti aturan IEEE 754 harus secara eksplisit mengaturnya OFF.

Jika compiler tidak mendukung pragma ini, maka harus konservatif dengan menghindari optimasi seperti itu, jika pengembang memilih untuk mengaturnya OFF.

GCC tidak mendukung pragma ini, tetapi dengan opsi default, ia menganggapnya seperti itu ON; jadi untuk target dengan perangkat keras FMA, jika seseorang ingin mencegah transformasi a*b+c untuk fma (a, b, c), seseorang perlu memberikan opsi seperti -ffp-contract=off (secara eksplisit mengatur pragma ke OFF) atau -std=c99 (untuk memberitahu GCC agar sesuai dengan beberapa versi standar C, di sini C99, jadi ikuti paragraf di atas). Di masa lalu, opsi terakhir tidak mencegah transformasi, yang berarti bahwa GCC tidak sesuai pada poin ini: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845


27
2018-06-23 12:44