Mengapa GCC tidak mengoptimalkan a * a * a * a * a * a to (a * a * a) * (a * a * a)?

2120

Saya melakukan beberapa optimasi numerik pada aplikasi ilmiah. Satu hal yang saya perhatikan adalah bahwa GCC akan mengoptimalkan panggilan pow(a,2)dengan mengkompilasinya a*a, tetapi panggilan pow(a,6)tersebut tidak dioptimalkan dan benar-benar akan memanggil fungsi perpustakaan pow, yang sangat memperlambat kinerja. (Sebaliknya, Intel C ++ Compiler , dapat dieksekusi icc, akan menghilangkan panggilan perpustakaan pow(a,6).)

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

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

sedangkan 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 kalikan ke 3. iccmemiliki perilaku serupa.

Mengapa kompiler tidak mengenali trik pengoptimalan ini?

xis
sumber
13
Apa yang dimaksud dengan "mengenali pow (a, 6)"?
Varun Madiath
659
Um ... Anda tahu bahwa suatu suatu suatu suatu dan (a a a) * (a a * a) tidak sama dengan angka floating point, bukan? Anda harus menggunakan -funsafe-math atau -Fast-matematika atau sesuatu untuk itu.
Damon
106
Saya sarankan Anda membaca "Apa Yang Harus Diketahui Setiap Ilmuwan Tentang Aritmatika Floating Point" oleh David Goldberg: download.oracle.com/docs/cd/E19957-01/806-3568/… setelah itu Anda akan memiliki pemahaman yang lebih lengkap tentang lubang tar yang baru saja Anda masuki!
Phil Armstrong
189
Pertanyaan yang masuk akal. 20 tahun yang lalu saya mengajukan pertanyaan umum yang sama, dan dengan menghancurkan hambatan tunggal itu, mengurangi waktu pelaksanaan simulasi Monte Carlo dari 21 jam menjadi 7 jam. Kode di loop dalam dieksekusi 13 triliun kali dalam proses, tapi itu simulasi ke jendela over-night. (lihat jawaban di bawah)
23
Mungkin (a*a)*(a*a)*(a*a)ikut campur juga. Jumlah perkalian yang sama, tetapi mungkin lebih akurat.
Rok Kralj

Jawaban:

2738

Karena Floating Point Math bukan asosiatif . Cara Anda mengelompokkan operan dalam perkalian floating point memiliki efek pada akurasi numerik jawabannya.

Akibatnya, sebagian besar kompiler sangat konservatif dalam menyusun ulang perhitungan titik apung kecuali mereka dapat yakin bahwa jawabannya akan tetap sama, atau kecuali jika Anda memberi tahu mereka Anda tidak peduli dengan akurasi numerik. Sebagai contoh: pada -fassociative-mathpilihan dari gcc yang memungkinkan gcc untuk operasi floating point reassociate, atau bahkan -ffast-mathpilihan yang memungkinkan bahkan pengorbanan lebih agresif akurasi terhadap kecepatan.

Lambdageek
sumber
10
Iya. Dengan -Fast-Matematika melakukan optimasi seperti itu. Ide bagus! Tetapi karena kode kami lebih mementingkan akurasi daripada kecepatan, mungkin lebih baik tidak melewatinya.
xis
19
IIRC C99 memungkinkan kompiler melakukan optimasi FP "tidak aman" seperti itu, tetapi GCC (pada apa pun selain x87) membuat upaya yang wajar untuk mengikuti IEEE 754 - ini bukan "batas kesalahan"; hanya ada satu jawaban yang benar .
tc.
14
Detail implementasi powtidak ada di sini atau di sana; jawaban ini bahkan tidak merujuk pow.
Stephen Canon
14
@nedR: ICC default untuk mengizinkan re-asosiasi. Jika Anda ingin mendapatkan perilaku sesuai standar, Anda perlu mengatur -fp-model precisedengan ICC. clangdan gccdefault untuk reassociation kepatuhan ketat.
Stephen Canon
49
@ xis, itu tidak benar-benar tidak -fassociative-mathakurat; hanya saja a*a*a*a*a*adan (a*a*a)*(a*a*a)berbeda. Ini bukan tentang akurasi; ini tentang kesesuaian standar dan hasil yang dapat diulang secara ketat, misalnya hasil yang sama pada setiap kompiler. Angka floating point sudah tidak tepat. Jarang cocok untuk dikompilasi -fassociative-math.
Paul Draper
652

Lambdageek dengan benar menunjukkan bahwa karena associativity tidak berlaku untuk angka floating-point, "optimasi"a*a*a*a*a*auntuk(a*a*a)*(a*a*a)dapat mengubah nilai. Inilah mengapa itu dilarang 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 kompiler harus menghargai itu. Jika Anda mau(a*a*a)*(a*a*a), tulis itu.

Itu bisa jadi menyusahkan untuk menulis; mengapa kompiler tidak bisa melakukan [apa yang Anda anggap sebagai] hal yang benar ketika Anda gunakan pow(a,6)? Karena itu akan menjadi hal yang salah untuk dilakukan. Pada platform dengan perpustakaan matematika yang baik, pow(a,6)jauh lebih akurat daripada salah satu a*a*a*a*a*aatau (a*a*a)*(a*a*a). Hanya untuk memberikan beberapa data, saya menjalankan percobaan kecil pada Mac Pro saya, mengukur kesalahan terburuk dalam mengevaluasi ^ 6 untuk semua angka mengambang 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 powbukannya pohon multiplikasi mengurangi kesalahan terikat oleh faktor 4 . Kompiler tidak boleh (dan umumnya tidak) membuat "optimisasi" yang meningkatkan kesalahan kecuali diizinkan oleh pengguna (misalnya melalui -ffast-math).

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

Stephen Canon
sumber
29
Perhatikan juga bahwa Visual C ++ menyediakan versi pow () yang 'ditingkatkan'. Dengan menelepon _set_SSE2_enable(<flag>)dengan flag=1, ia akan menggunakan SSE2 jika memungkinkan. Ini mengurangi akurasi sedikit, tetapi meningkatkan kecepatan (dalam beberapa kasus). MSDN: _set_SSE2_enable () dan pow ()
TkTech
18
@TkTech: Akurasi yang berkurang adalah karena implementasi Microsoft, bukan ukuran register yang digunakan. Dimungkinkan untuk memberikan pembulatan yang benar pow menggunakan hanya register 32-bit, jika penulis perpustakaan sangat termotivasi. Ada powimplementasi berbasis SSE yang lebih akurat daripada kebanyakan implementasi berbasis x87, dan ada juga implementasi yang menukar beberapa akurasi untuk kecepatan.
Stephen Canon
9
@TkTech: Tentu saja, saya hanya ingin menjelaskan bahwa pengurangan keakuratan adalah karena pilihan yang dibuat oleh penulis perpustakaan, bukan intrinsik dengan penggunaan SSE.
Stephen Canon
7
Saya tertarik untuk mengetahui apa yang Anda gunakan sebagai "standar emas" di sini untuk menghitung kesalahan relatif - saya biasanya mengharapkannya a*a*a*a*a*a, tetapi tampaknya bukan itu masalahnya! :)
j_random_hacker
8
@j_random_hacker: karena saya membandingkan hasil presisi tunggal, cukuplah double-presisi untuk standar emas - kesalahan dari sebuah sebuah sebuah sebuah sebuah dihitung ganda * jauh lebih kecil dari kesalahan salah satu perhitungan presisi tunggal.
Stephen Canon
168

Kasus serupa lain: sebagian besar kompiler tidak akan mengoptimalkan a + b + c + duntuk (a + b) + (c + d)(ini adalah optimasi sejak ekspresi kedua dapat pipelined lebih baik) dan mengevaluasinya seperti yang diberikan (yaitu sebagai (((a + b) + c) + d)). Ini juga karena kasus sudut:

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

Ini output 1.000000e-05 0.000000e+00

sanjoyd
sumber
10
Ini tidak persis sama. Mengubah urutan penggandaan / pembagian (tidak termasuk pembagian dengan 0) lebih aman daripada urutan penjumlahan / pengurangan. Menurut pendapat saya yang sederhana, kompiler harus mencoba mengaitkan mults./divs. karena melakukan itu mengurangi jumlah total operasi dan di samping keuntungan kinerja juga keuntungan presisi.
CoffeDeveloper
4
@DarioOO: Tidak aman. Multiply dan bagi adalah sama dengan penambahan dan pengurangan eksponen, dan mengubah urutan dapat dengan mudah menyebabkan temporaries melebihi kisaran yang mungkin dari eksponen. (Tidak persis sama, karena eksponen tidak mengalami kehilangan presisi ... tetapi representasi masih sangat terbatas, dan penataan ulang dapat menyebabkan nilai-nilai tidak terwakili)
Ben Voigt
8
Saya pikir Anda kehilangan beberapa latar belakang kalkulus. Multplying dan membagi 2 angka memperkenalkan jumlah kesalahan yang sama. Sementara mengurangi / menambah 2 angka dapat menyebabkan kesalahan yang lebih besar terutama ketika 2 angka adalah urutan besarnya berbeda, maka itu lebih aman diatur ulang / dibagi daripada sub / tambahkan karena itu memperkenalkan perubahan kecil dalam kesalahan akhir.
CoffeDeveloper
8
@DarioOO: risikonya berbeda dengan mul / div: Pengubahan urutan baik membuat perubahan kecil pada hasil akhir, atau eksponen meluap di beberapa titik (di mana tidak ada sebelumnya) dan hasilnya sangat berbeda (berpotensi + inf atau 0).
Peter Cordes
@GameDeveloper Memberlakukan perolehan presisi dengan cara yang tidak dapat diprediksi sangat bermasalah.
curiousguy
80

Fortran (dirancang untuk komputasi ilmiah) memiliki operator daya bawaan, dan sejauh yang saya tahu kompiler Fortran biasanya akan mengoptimalkan peningkatan daya integer dengan cara yang mirip dengan yang Anda gambarkan. C / C ++ sayangnya tidak memiliki operator listrik, hanya fungsi perpustakaan pow(). Ini tidak mencegah kompiler pintar memperlakukan powkhusus dan menghitungnya dengan cara yang lebih cepat untuk kasus khusus, tetapi tampaknya mereka melakukannya lebih jarang ...

Beberapa tahun yang lalu saya mencoba membuatnya lebih nyaman untuk menghitung kekuatan bilangan bulat secara optimal, dan muncul sebagai berikut. Ini C ++, bukan C, dan masih tergantung pada kompiler yang agak pintar tentang cara mengoptimalkan / inline sesuatu. Ngomong-ngomong, semoga bermanfaat 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 karena menemukan solusi optimal adalah masalah NP-complete dan ini hanya layak dilakukan untuk kekuatan kecil (bukan menggunakan pow), tidak ada alasan untuk meributkan dengan detail.

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

Ini membuatnya mudah untuk mengetikkan kekuatan (tidak perlu menjelaskan 6 adetik dengan parens), dan memungkinkan Anda memiliki optimasi semacam ini tanpa -ffast-mathseandainya Anda memiliki sesuatu yang bergantung pada ketelitian seperti penjumlahan terkompensasi (contoh di mana urutan operasi sangat penting) .

Anda mungkin juga bisa 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 kompiler 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
Szabolcs
sumber
36
Menemukan pohon kekuatan yang optimal mungkin sulit, tetapi karena itu hanya menarik untuk kekuatan kecil, jawaban yang jelas adalah untuk melakukannya sekali (Knuth memberikan tabel hingga 100) dan menggunakan tabel hardcode tersebut (itulah yang dilakukan gcc secara internal untuk powi) .
Marc Glisse
7
Pada prosesor modern, kecepatan dibatasi oleh latensi. Misalnya, hasil perkalian mungkin tersedia setelah lima siklus. Dalam situasi itu, menemukan cara tercepat untuk menciptakan kekuatan mungkin lebih rumit.
gnasher729
3
Anda juga bisa mencoba menemukan pohon kekuasaan yang memberikan batas atas terendah untuk kesalahan pembulatan relatif, atau kesalahan pembulatan relatif rata-rata terendah.
gnasher729
1
Boost juga mendukung hal ini, misalnya boost :: math :: pow <6> (n); Saya pikir itu bahkan mencoba untuk mengurangi jumlah perkalian dengan mengekstraksi faktor umum.
gast128
Perhatikan bahwa yang terakhir setara dengan (a ** 2) ** 3
minmaxavg
62

GCC tidak benar-benar mengoptimalkan a*a*a*a*a*auntuk (a*a*a)*(a*a*a)saat 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. Maksudnya: Baca dari stdin; gunakan level optimisasi O2; daftar bahasa rakitan keluaran bukan biner; daftar harus menggunakan sintaksis 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 menjelaskannya 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  ; temp = x
imul eax, edi  ; temp = x * temp
imul eax, edi  ; temp = x * temp
imul eax, eax  ; temp = temp * temp

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

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

Seperti yang telah dicatat oleh poster lain, opsi ini tidak dimungkinkan dalam floating point, karena aritmatika floating point tidak asosiatif.

pikomancer
sumber
12
Ini sah untuk perkalian bilangan bulat karena luapan pelengkap dua adalah perilaku yang tidak ditentukan. Jika akan ada overflow, itu akan terjadi di suatu tempat, terlepas dari menata ulang operasi. Jadi, ekspresi tanpa overflow mengevaluasi hal yang sama, ekspresi bahwa overflow adalah perilaku yang tidak terdefinisi sehingga tidak masalah bagi kompiler untuk mengubah titik terjadinya overflow. gcc melakukan ini unsigned intjuga.
Peter Cordes
51

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

Jika sebagian besar programmer mengenali (dan dapat menjalankan) gagasan bahwa ekspresi C * a * a * a * a * a sebenarnya tidak bekerja dengan angka ideal, maka kompiler GCC kemudian akan GRATIS untuk mengoptimalkan "a * a * a * a * a * a "into say" t = (a * a); t * t * t "yang membutuhkan lebih banyak perkalian. Namun sayangnya, kompiler GCC tidak tahu apakah programmer yang menulis kode berpikir 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 seperti apa Anda , Anda dapat menggunakan tombol "-fast-math" untuk memberi tahu GCC bahwa "Hei, GCC, saya tahu apa yang saya lakukan!". Ini akan memungkinkan GCC untuk mengubah a * a * a * a * a * a menjadi bagian teks yang berbeda - itu terlihat berbeda dari * a * a * a * a * a - tetapi masih menghitung angka dalam interval kesalahan a * a * a * a * a * a. Ini OK, karena Anda sudah tahu Anda bekerja dengan interval, bukan angka ideal.


sumber
52
Angka titik mengambang tepat. Mereka belum tentu persis seperti yang Anda harapkan. Selain itu, teknik dengan epsilon sendiri merupakan perkiraan untuk bagaimana mengatasi hal-hal dalam kenyataan, karena kesalahan yang diharapkan sebenarnya relatif terhadap skala mantissa, yaitu, Anda biasanya sampai sekitar 1 LSB keluar, tetapi itu dapat meningkat dengan setiap operasi dilakukan jika Anda tidak hati-hati jadi berkonsultasilah dengan analis numerik sebelum melakukan sesuatu yang non-sepele dengan floating point. Gunakan perpustakaan yang tepat jika memungkinkan.
Donal Fellows
3
@DonalFellows: Standar IEEE mensyaratkan bahwa perhitungan titik-mengambang menghasilkan hasil yang paling akurat sesuai dengan apa hasilnya jika operan sumber adalah nilai yang tepat, tetapi itu tidak berarti mereka benar-benar mewakili nilai yang tepat. Dalam banyak kasus lebih bermanfaat untuk menganggap 0.1f sebagai (1.677.722 +/- 0.5) / 16.777.216, yang harus ditampilkan dengan jumlah angka desimal yang tersirat oleh ketidakpastian itu, daripada menganggapnya sebagai jumlah yang tepat (1.677.722 +/- 0.5) / 16.777.216 (yang harus ditampilkan hingga 24 angka desimal).
supercat
23
@supercat: IEEE-754 cukup jelas pada titik bahwa data floating-point melakukan mewakili nilai-nilai yang sebenarnya; klausa 3.2 - 3.4 adalah bagian yang relevan. Anda dapat, tentu saja, memilih untuk menafsirkannya sebaliknya, sama seperti Anda dapat memilih untuk menafsirkan int x = 3sebagai makna yaitu x3 +/- 0,5.
Stephen Canon
7
@supercat: Saya setuju sepenuhnya, tetapi itu tidak berarti bahwa Distancetidak persis sama dengan nilai numeriknya; itu berarti bahwa nilai numerik hanya perkiraan untuk beberapa kuantitas fisik yang dimodelkan.
Stephen Canon
10
Untuk analisis numerik, otak Anda akan berterima kasih jika Anda menginterpretasikan angka floating point bukan sebagai interval, tetapi sebagai nilai yang tepat (yang kebetulan bukan nilai yang Anda inginkan). Misalnya, jika x berada di suatu ronde 4.5 dengan kesalahan kurang dari 0,1, dan Anda menghitung (x + 1) - x, interpretasi "interval" membuat Anda dengan interval dari 0,8 ke 1,2, sedangkan interpretasi "nilai tepat" memberi tahu Anda hasilnya akan 1 dengan kesalahan paling banyak 2 ^ (- 50) dalam presisi ganda.
gnasher729
34

Belum ada poster yang menyebutkan kontraksi ekspresi mengambang (standar ISO C, 6.5p8 dan 7.12.2). Jika FP_CONTRACTpragma diatur ke ON, kompiler diperbolehkan untuk menganggap ekspresi seperti a*a*a*a*a*aoperasi tunggal, seolah dievaluasi secara tepat dengan pembulatan tunggal. Sebagai contoh, sebuah kompiler dapat menggantinya dengan fungsi daya internal yang lebih cepat dan lebih akurat. Ini sangat menarik karena perilaku sebagian dikendalikan oleh programmer secara langsung dalam kode sumber, sementara opsi kompiler yang disediakan oleh pengguna akhir kadang-kadang dapat digunakan secara tidak benar.

Keadaan standar FP_CONTRACTpragma ditentukan oleh implementasi, sehingga seorang kompiler diizinkan untuk melakukan optimasi tersebut secara default. Jadi kode portabel yang harus benar-benar mengikuti aturan IEEE 754 harus secara eksplisit mengaturnya OFF.

Jika kompiler tidak mendukung pragma ini, ia harus konservatif dengan menghindari optimasi seperti itu, seandainya pengembang telah memilih untuk mengaturnya OFF.

GCC tidak mendukung pragma ini, tetapi dengan opsi default, ia menganggapnya ON; jadi untuk target dengan FMA perangkat keras, jika seseorang ingin mencegah transformasi a*b+cke fma (a, b, c), kita perlu memberikan opsi seperti -ffp-contract=off(untuk 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 titik ini: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845

vinc17
sumber
3
Pertanyaan populer yang berumur panjang terkadang menunjukkan usia mereka. Pertanyaan ini ditanyakan dan dijawab pada tahun 2011, ketika GCC dapat dimaafkan karena tidak menghormati standar C99 yang baru-baru ini berlaku. Tentu saja sekarang ini tahun 2014, jadi GCC ... ahem.
Pascal Cuoq
Namun, bukankah seharusnya Anda menjawab pertanyaan titik mengambang yang relatif baru tanpa jawaban yang diterima? cough stackoverflow.com/questions/23703408 cough
Pascal Cuoq
Saya menemukannya ... mengganggu bahwa gcc tidak menerapkan pragma floating-point C99.
David Monniaux
1
@DavidMonniaux pragmas secara definisi opsional untuk diterapkan.
Tim Seguine
2
@TimSeguine Tetapi jika pragma tidak diimplementasikan, nilai standarnya harus paling membatasi untuk implementasi. Kurasa itulah yang dipikirkan David. Dengan GCC, ini sekarang diperbaiki untuk FP_CONTRACT jika seseorang menggunakan mode ISO C : itu masih tidak menerapkan pragma, tetapi dalam mode ISO C, sekarang diasumsikan bahwa pragma tidak aktif.
vinc17
28

Seperti yang ditunjukkan oleh Lambdageek, perkalian float bukan asosiatif dan Anda bisa mendapatkan akurasi yang lebih sedikit, tetapi juga ketika mendapatkan akurasi yang lebih baik, Anda dapat menentang optimasi, karena Anda menginginkan aplikasi deterministik. Misalnya dalam simulasi permainan klien / server, di mana setiap klien harus mensimulasikan dunia yang sama yang Anda inginkan perhitungan floating point menjadi deterministik.

Bjorn
sumber
3
@greggo Tidak, itu masih bersifat deterministik. Tidak ada keacakan ditambahkan dalam arti kata.
Alice
9
@ Alice Tampaknya cukup jelas Bjorn di sini menggunakan 'deterministik' dalam arti kode memberikan hasil yang sama pada platform yang berbeda dan versi kompiler yang berbeda dll (variabel eksternal yang mungkin di luar kendali programmer) - bukan kekurangan dari keacakan numerik aktual pada saat dijalankan. Jika Anda menunjukkan bahwa ini bukan penggunaan kata yang tepat, saya tidak akan berdebat dengan itu.
greggo
5
@greggo Kecuali bahkan dalam penafsiran Anda tentang apa yang dia katakan, itu masih salah; itulah inti dari IEEE 754, untuk memberikan karakteristik yang identik untuk sebagian besar (jika tidak semua) operasi lintas platform. Sekarang, ia tidak menyebutkan platform atau versi kompiler, yang akan menjadi perhatian yang valid jika Anda ingin setiap operasi pada setiap server / klien jarak jauh identik .... tetapi ini tidak jelas dari pernyataannya. Kata yang lebih baik mungkin "mirip" atau semacamnya.
Alice
8
@Alice Anda membuang-buang waktu semua orang, termasuk Anda sendiri, dengan berdebat semantik. Maknanya jelas.
Lanaru
11
@ Lanaru Seluruh titik standar adalah semantik; maknanya jelas tidak jelas.
Alice
28

Fungsi perpustakaan seperti "pow" biasanya dibuat dengan hati-hati untuk menghasilkan kesalahan seminimal mungkin (dalam kasus umum). Ini biasanya mencapai fungsi perkiraan dengan splines (menurut komentar Pascal implementasi yang paling umum tampaknya menggunakan algoritma Remez )

secara fundamental operasi berikut:

pow(x,y);

memiliki kesalahan inheren kira-kira sama besarnya dengan kesalahan dalam setiap perkalian atau pembagian tunggal .

Sedangkan operasi berikut:

float a=someValue;
float b=a*a*a*a*a*a;

memiliki kesalahan bawaan yang lebih besar dari 5 kali kesalahan satu perkalian atau pembagian (karena Anda menggabungkan 5 perkalian).

Compiler harus benar-benar berhati-hati dengan jenis optimasi yang dilakukannya:

  1. jika mengoptimalkan pow(a,6)untuk a*a*a*a*a*aitu mungkin meningkatkan kinerja, tapi secara drastis mengurangi akurasi untuk angka floating point.
  2. jika mengoptimalkan a*a*a*a*a*a untuk pow(a,6)itu benar-benar dapat mengurangi akurasi karena "a" adalah beberapa nilai khusus yang memungkinkan perkalian tanpa kesalahan (kekuatan 2 atau beberapa nomor bilangan bulat kecil)
  3. jika mengoptimalkan pow(a,6)ke (a*a*a)*(a*a*a)atau (a*a)*(a*a)*(a*a)ada masih bisa menjadi kehilangan akurasi dibandingkan dengan powfungsi.

Secara umum Anda tahu bahwa untuk nilai floating point arbitrer "pow" memiliki akurasi yang lebih baik daripada fungsi apa pun yang pada akhirnya dapat Anda tulis, tetapi dalam beberapa kasus khusus multiplikasi mungkin memiliki akurasi dan kinerja yang lebih baik, tergantung pada pengembang yang memilih apa yang lebih tepat, akhirnya mengomentari kode sehingga tidak ada orang lain yang akan "mengoptimalkan" kode itu.

Satu-satunya hal yang masuk akal (pendapat pribadi, dan tampaknya pilihan di GCC tanpa optimasi atau kompiler flag tertentu) untuk mengoptimalkan harus mengganti "pow (a, 2)" dengan "a * a". Itu akan menjadi satu-satunya hal waras yang harus dilakukan vendor kompiler.

CoffeDeveloper
sumber
7
downvoters harus menyadari bahwa jawaban ini baik-baik saja. Saya dapat mengutip lusinan sumber dan dokumentasi untuk mendukung jawaban saya dan saya mungkin lebih terlibat dengan ketelitian floating point dibandingkan dengan downvoter mana pun. Sangat masuk akal di StackOverflow menambahkan informasi yang hilang yang tidak dijawab oleh jawaban lain, jadi bersikaplah sopan dan jelaskan alasan Anda.
CoffeDeveloper
1
Sepertinya saya bahwa jawaban Stephen Canon mencakup apa yang Anda katakan. Anda tampaknya bersikeras bahwa libma diimplementasikan dengan splines: mereka lebih biasanya menggunakan reduksi argumen (tergantung dari fungsi yang diimplementasikan) ditambah polinomial tunggal koefisien yang telah diperoleh oleh varian algoritma Remez yang kurang lebih canggih. Kelancaran pada titik-titik persimpangan tidak dianggap sebagai nilai obyektif yang dikejar untuk fungsi libm (jika akhirnya cukup akurat, mereka secara otomatis cukup lancar bagaimanapun terlepas dari berapa banyak potongan domain yang dipecah menjadi).
Pascal Cuoq
Bagian kedua dari jawaban Anda benar-benar merindukan titik bahwa kompiler seharusnya menghasilkan kode yang mengimplementasikan apa yang dikatakan kode sumber, titik. Anda juga menggunakan kata "presisi" ketika Anda berarti "akurasi".
Pascal Cuoq
Terima kasih atas masukan Anda, saya sedikit mengoreksi jawabannya, sesuatu yang baru masih ada di 2 baris terakhir ^^
CoffeDeveloper
27

Saya tidak berharap kasus ini dioptimalkan sama sekali. Tidak dapat sering di mana ekspresi berisi subekspresi yang dapat dikelompokkan ulang untuk menghapus seluruh operasi. Saya berharap penulis kompiler menginvestasikan waktu mereka di bidang-bidang yang lebih mungkin menghasilkan peningkatan yang nyata, daripada menutupi kasus tepi yang jarang ditemui.

Saya terkejut mengetahui dari jawaban lain bahwa ungkapan ini memang dapat dioptimalkan dengan sakelar kompiler yang tepat. Entah optimasi itu sepele, atau itu adalah kasus tepi dari optimasi yang jauh lebih umum, atau penulis kompiler sangat teliti.

Tidak ada yang salah dengan memberikan petunjuk kepada kompiler seperti yang Anda lakukan di sini. Itu adalah bagian normal dan yang diharapkan dari proses optimasi mikro untuk mengatur ulang pernyataan dan ekspresi untuk melihat perbedaan apa yang akan mereka bawa.

Sementara kompiler dapat dibenarkan dalam mempertimbangkan dua ekspresi untuk memberikan hasil yang tidak konsisten (tanpa saklar yang tepat), Anda tidak perlu terikat oleh batasan itu. Perbedaannya akan sangat kecil - begitu banyak sehingga jika perbedaan itu penting bagi Anda, Anda seharusnya tidak menggunakan aritmatika floating point standar di tempat pertama.

Mark tebusan
sumber
17
Seperti dicatat oleh komentator lain, ini tidak benar sampai pada titik absurd; perbedaannya bisa mencapai setengah hingga 10% dari biaya, dan jika dijalankan dalam lingkaran yang ketat, itu akan diterjemahkan ke banyak instruksi yang terbuang untuk mendapatkan apa yang bisa menjadi jumlah presisi tambahan yang tidak signifikan. Mengatakan Anda tidak boleh menggunakan FP standar ketika Anda melakukan monte carlo adalah seperti mengatakan Anda harus selalu menggunakan pesawat terbang untuk melintasi negara; ia mengabaikan banyak eksternalitas. Akhirnya, ini BUKAN optimasi yang tidak biasa; analisis kode mati dan pengurangan / refisi kode sangat umum.
Alice
21

Sudah ada beberapa jawaban yang baik untuk pertanyaan ini, tetapi demi kelengkapan saya ingin menunjukkan bahwa bagian yang berlaku dari standar C adalah 5.1.2.2.3 / 15 (yang sama dengan bagian 1.9 / 9 dalam C ++ 11 standar). Bagian ini menyatakan bahwa operator hanya dapat dikelompokkan kembali jika mereka benar-benar asosiatif atau komutatif.

Rastaban
sumber
12

gcc sebenarnya dapat melakukan optimasi ini, bahkan untuk angka floating-point. Sebagai contoh,

double foo(double a) {
  return a*a*a*a*a*a;
}

menjadi

foo(double):
    mulsd   %xmm0, %xmm0
    movapd  %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
    mulsd   %xmm1, %xmm0
    ret

dengan -O -funsafe-math-optimizations. Penataan ulang ini melanggar IEEE-754, jadi, itu membutuhkan flag.

Bilangan bulat yang ditandatangani, seperti yang ditunjukkan oleh Peter Cordes dalam komentar, dapat melakukan pengoptimalan ini tanpa -funsafe-math-optimizationssejak itu berlaku tepat ketika tidak ada overflow dan jika ada overflow Anda mendapatkan perilaku yang tidak terdefinisi. Jadi kamu mengerti

foo(long):
    movq    %rdi, %rax
    imulq   %rdi, %rax
    imulq   %rdi, %rax
    imulq   %rax, %rax
    ret

dengan adil -O. Untuk bilangan bulat tak bertanda, itu bahkan lebih mudah karena mereka bekerja dengan kekuatan mod 2 dan sehingga dapat disusun ulang secara bebas bahkan dalam menghadapi overflow.

Charles
sumber
1
Link Godbolt dengan double, int dan unsigned. gcc dan dentang keduanya mengoptimalkan ketiganya dengan cara yang sama (dengan -ffast-math)
Peter Cordes
@PeterCordes Terima kasih!
Charles